# US 2018/0321869 A1 · Distributing data by successive spatial partitionings

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2018/0321869 A1
- Document ID: US20180321869A1
- Status: Published application
- Kind: A1
- Application number: 15/589,339
- Filed: 2017-05-08
- Published: 2018-11-08
- Earliest claimed: 2017-05-08
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Aayush GUPTA; Sangeetha SESHADRI; Abdurrahman YASAR
- Web page: https://patentgrep.com/patent/US20180321869A1

## CPC

- G06F 3/0644: {Management of space entities, e.g. partitions, extents, pools}
- G06F 3/0604: {Improving or facilitating administration, e.g. storage management}
- G06F 3/0688: {Non-volatile semiconductor memory arrays}
- G06F 3/0689: {Disk arrays, e.g. RAID, JBOD}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A computer-implemented method for distributing data among memory devices may include performing successive spatial partitionings of a graph of data based upon vertices and associated edges to generate spatial partitions with each spatial partition having a respective number of edges below a threshold. The method may also include ordering the spatial partitions and distributing the spatial partitions among the memory devices based upon the ordering.

## Claims

### Claim 1

A computer-implemented method for distributing data among a plurality of memory devices comprising:
performing a plurality of successive spatial partitionings of a graph of data based upon vertices and associated edges to generate a plurality of spatial partitions with each spatial partition having a respective number of edges below a threshold;
ordering the plurality of spatial partitions; and
distributing the plurality of spatial partitions among the plurality of memory devices based upon the ordering.

### Claim 2 (depends on 1)

The computer-implemented method of claim 1 further comprising generating an index based upon the plurality of spatial partitions and associated vertices.

### Claim 3 (depends on 1)

The computer-implemented method of claim 1 wherein performing the plurality of successive partitionings comprises performing a plurality of successive quad tree partitionings.

### Claim 4 (depends on 1)

The computer-implemented method of claim 1 wherein the ordering is based upon a Hilbert curve.

### Claim 5 (depends on 1)

The computer-implemented method of claim 1 wherein the graph comprises a dynamic graph.

### Claim 6 (depends on 1)

The computer-implemented method of claim 1 wherein the plurality of memory devices comprises a plurality of magnetic media.

### Claim 7 (depends on 1)

The computer-implemented method of claim 1 wherein the plurality of memory devices comprises a plurality of solid-state memory devices.

### Claim 8

A computer system for distributing data comprising:
a plurality of memory devices; and
a processor coupled to the plurality of memory devices and configured to
perform a plurality of successive spatial partitionings of a graph of data based upon vertices and associated edges to generate a plurality of spatial partitions with each spatial partition having a respective number of edges below a threshold,
order the plurality of spatial partitions, and
distribute the plurality of spatial partitions among the plurality of memory devices based upon the ordering.

### Claim 9 (depends on 8)

The computer system of claim 8 wherein the processor is configured to generate an index based upon the plurality of spatial partitions and associated vertices.

### Claim 10 (depends on 8)

The computer system of claim 8 wherein the processor is configured to perform the plurality of successive partitionings by performing a plurality of successive quad tree partitionings.

### Claim 11 (depends on 8)

The computer system of claim 8 wherein the processor is configured to order based upon a Hilbert curve.

### Claim 12 (depends on 8)

The computer system of claim 8 wherein the graph comprises a dynamic graph.

### Claim 13 (depends on 8)

The computer system of claim 8 wherein the plurality of memory devices comprises a plurality of magnetic media.

### Claim 14 (depends on 8)

The computer system of claim 8 wherein the plurality of memory devices comprises a plurality of solid-state memory devices.

### Claim 15 (depends on 8)

The computer system of claim 8 wherein the plurality of memory devices are configured to be accessible in parallel.

### Claim 16

A computer-readable medium for distributing data among a plurality of memory devices, the computer-readable medium comprising computer executable instructions that when executed by a processor cause the processor to perform operations comprising:
performing a plurality of successive spatial partitionings of a graph of data based upon vertices and associated edges to generate a plurality of spatial partitions with each spatial partition having a respective number of edges below a threshold;
ordering the plurality of spatial partitions; and
distributing the plurality of spatial partitions among the plurality of memory devices based upon the ordering.

### Claim 17 (depends on 16)

The computer-readable medium of claim 16 wherein the computer-executable instructions cause the processor to generate an index based upon the plurality of spatial partitions and associated vertices.

### Claim 18 (depends on 16)

The computer-readable medium of claim 16 wherein performing the plurality of successive partitionings comprises performing a plurality of successive quad tree partitionings.

### Claim 19 (depends on 16)

The computer-readable medium of claim 16 wherein the ordering is based upon a Hilbert curve.

### Claim 20 (depends on 16)

The computer-readable medium of claim 16 wherein the graph comprises a dynamic graph.
