# US 11,442,643 B2 · System and method for efficiently converting low-locality data into high-locality data

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

- Number: US 11,442,643 B2
- Document ID: US11442643B2
- Status: Granted
- Kind: B2
- Application number: 16/795,510
- Filed: 2020-02-19
- Published: 2021-08-19
- Granted: 2022-09-13
- Earliest claimed: 2020-02-13
- Assignees: Samsung Electronics Co., Ltd.
- Applicants: Samsung Electronics Co., Ltd.
- Inventors: Oluwole Jaiyeoba; Nima Elyasi; Changho Choi
- Web page: https://patentgrep.com/patent/US11442643B2

## CPC

- G06F 3/0644: {Management of space entities, e.g. partitions, extents, pools}
- G06F 3/061: {Improving I/O performance}
- G06F 3/0619: {in relation to data integrity, e.g. data losses, bit errors}
- G06F 3/0631: {by allocating resources to storage systems}
- G06F 3/0647: {Migration mechanisms}
- G06F 3/0658: {Controller construction arrangements}
- G06F 3/0659: {Command handling arrangements, e.g. command buffers, queues, command scheduling}
- G06F 3/0661: {Format or protocol conversion arrangements}
- G06F 3/067: {Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]}
- G06F 3/0679: {Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]}
- G06F 3/0683: {Plurality of storage devices}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A system and method for processing unstructured source data is described. Input data having a range of V is loaded from off-chip storage to on-chip storage. The input data is partitioned into P temporary parent partitions via the on-chip storage, where a particular one of the P temporary parent partitions has a range of V/P. The P temporary parent partitions are stored from the on-chip storage to the off-chip storage. The P temporary parent partitions are partitioned for generating P temporary child partitions until the target number of T partitions is generated, where data from of the P temporary parent partitions is source data for recursively loading, partitioning, and storing the source data. An application is configured to access partitioned data from the T partitions for generating an output. The accesses of the partitioned data are sequential read accesses of the off-chip storage.

## Claims

### Claim 1

A method for processing unstructured source data, the method comprising:
determining a target number of T partitions;
identifying the unstructured source data as input data for a first level of recursion;
recursively generating partitions based on the input data until the target number of T partitions are generated, wherein the recursively generating includes:
loading the input data from an off-chip storage device to an on-chip storage device, the input data having a range V;
partitioning the input data into P temporary partitions via the on-chip storage device, wherein a particular one of the P temporary partitions has a range of V/P;
storing the P temporary partitions from the on-chip storage device to the off-chip storage device; and
identifying data in one of the P temporary partitions as the input data for a next level of recursion,
wherein an application is configured to perform accesses of partitioned data from the T partitions for generating an output, wherein the accesses of the partitioned data are sequential read accesses of the off-chip storage device and wherein T, V, and P are numerical values greater than 1.

### Claim 2 (depends on 1)

The method of claim 1, wherein T is based on a storage capacity of the on-chip storage device, wherein a range of the partitioned data in a particular one of the generated T partitions is within the storage capacity of the on-chip device.

### Claim 3 (depends on 2)

The method of claim 2, wherein the input data for the first level of recursion has a range of R, wherein the range of the partitioned data in a particular one of the generated T partitions is R/T.

### Claim 4 (depends on 1)

The method of claim 1, wherein the partitioned data has higher locality than locality of the input data.

### Claim 5 (depends on 1)

The method of claim 1, wherein the loading of the input data is in batches via a sequential read operation of the off-chip storage device, and the storing of the P temporary partitions is via a sequential write operation of the off-chip storage device.

### Claim 6 (depends on 1)

The method of claim 1, wherein fixed memory space is allocated in the off-chip storage device, wherein all partitions generated at a particular level of recursion are stored in the fixed memory space.

### Claim 7 (depends on 1)

The method of claim 1, wherein during the first level of recursion of the recursive generating, the P temporary partitions are P temporary parent partitions, and during a second level of recursion of the recursive generating, the P temporary partitions are P temporary child partitions, wherein the storing of the P temporary child partitions during the second level of recursion includes invoking a data storage process including:
dynamically allocating a data block of a fixed size, wherein the data block stores a portion of a first one of the P temporary child partitions from a first parent partition of the P temporary parent partitions, and a portion of a second one of the P temporary child partitions from a second parent partition of the P temporary parent partitions, for maximizing use of storage space of the data block.

### Claim 8 (depends on 1)

The method of claim 1, wherein a portion of the partitioned data accessed from the off-chip storage device is stored on the on-chip storage device, the method further comprising:
accessing the partitioned data on the on-chip storage device via a random data access.

### Claim 9 (depends on 1)

The method of claim 1, wherein the on-chip storage device is a static random access memory, and the off-chip storage device is a dynamic random access memory or a solid state drive.

### Claim 10 (depends on 1)

The method of claim 1, wherein the unstructured source data is graph data, and the application is a graph processing application.

### Claim 11

A system for processing unstructured source data, the system comprising:
an off-chip storage device;
an on-chip storage device; and
a processor coupled to the on-chip and off-chip storage devices, the processor being configured to:
determine a target number of T partitions;
identify the unstructured source data as input data for a first level of recursion;
recursively generate partitions based on the input data until the target number of T partitions are generated, wherein the processor is configured to:
load the input data from the off-chip storage device to the on-chip storage device, the input data having a range V;
partition the input data into P temporary partitions via the on-chip storage device, wherein a particular one of the P temporary partitions has a range of V/P;
store the P temporary partitions from the on-chip storage device to the off-chip storage device; and
identify data in one of the P temporary partitions as the input data for a next level of recursion,
wherein an application is configured to perform accesses of partitioned data from the T partitions for generating an output, wherein the accesses of the partitioned data are sequential read accesses of the off-chip storage device and wherein T, V, and P are numerical values greater than 1.

### Claim 12 (depends on 11)

The system of claim 11, wherein T is based on a storage capacity of the on-chip storage device, wherein a range of the partitioned data in a particular one of the generated T partitions is within the storage capacity of the on-chip device.

### Claim 13 (depends on 11)

The system of claim 11, wherein the input data for the first level of recursion has a range of R, wherein the range of the partitioned data in a particular one of the generated T partitions is R/T.

### Claim 14 (depends on 11)

The system of claim 11, wherein the partitioned data has higher locality than locality of the input data.

### Claim 15 (depends on 11)

The system of claim 11, wherein the loading of the input data is in batches via a sequential read operation of the off-chip storage device, and the storing of the P temporary partitions is via a sequential write operation of the off-chip storage device.

### Claim 16 (depends on 11)

The system of claim 11, wherein fixed memory space is allocated in the off-chip storage device, wherein the processor is configured to store all partitions generated at a particular level of recursion using the fixed memory space.

### Claim 17 (depends on 11)

The system of claim 11, wherein during the first level of recursion of the recursive generating, the P temporary partitions are P temporary parent partitions, and during a second level of recursion of the recursive generating, the P temporary partitions are P temporary child partitions, wherein the processor is configured to store the P temporary child partitions during the second level of recursion via a data storage process including:
dynamically allocating a data block of a fixed size, wherein the data block stores a portion of a first one of the P temporary child partitions from a first parent partition of the P temporary parent partitions, and a portion of a second one of the P temporary child partitions from a second parent partition of the P temporary parent partitions, for maximizing use of storage space of the data block.

### Claim 18 (depends on 11)

The system of claim 11, wherein the processor is configured to store a portion of the partitioned data accessed from the off-chip storage device on the on-chip storage device, the processor being further configured to:
access the partitioned data on the on-chip storage device via a random data access.

### Claim 19 (depends on 11)

The system of claim 11, wherein the on-chip storage device is a static random access memory, and the off-chip storage device is a dynamic random access memory or a solid state drive.

### Claim 20 (depends on 11)

The system of claim 11, wherein the unstructured source data is graph data, and the application is a graph processing application.