US 8,935,257 B1Granted

Organizing, joining, and performing statistical calculations on massive sets of data

AssigneeLinkedIn Corporation

InventorsSrinivas S. Vemuri, Maneesh Varshney, Krishna P. Puttaswamy Naga, Rui Liu

Life of this patent

Estimating the term…

Loading patent…

Abstract

A system, method, and apparatus are provided for organizing and joining massive sets of data (e.g., tens or hundreds of millions of event records). A dataset is Blocked by first identifying a partition key, which comprises one or more columns of the data. Each Block will contain all dataset records that have partition key values assigned to that Block. A cost constraint (e.g., a maximum size, a maximum number of records) may also be applied to the Blocks. A Block index is generated to identify all Blocks, their corresponding (sequential) partition key values, and their locations. A second dataset that includes the partition key column(s) and that must be correlated with the first dataset may then be Blocked according to the same ranges of partition key values (but without the cost constraint). Corresponding Blocks of the datasets may then be Joined/Aggregated, and analyzed as necessary.

Claims28

Dependent claims

A method of correlating multiple multi-dimensional datasets, the method comprising:

selecting one or more dimensions of a first dataset as a partition key;
selecting a cost constraint;
dividing the first dataset into a first set of blocks with one or more computers, said dividing comprising, for each block in the first set of blocks:
associating with the block a distinct subset of partition key values such that a combination of all records of the first dataset having partition key values within the associated subset of partition key values satisfies the cost constraint;
collecting all records of the first dataset having partition key values within the associated subset of partition key values;
sorting the collected records using a sort key comprising one or more of the dataset dimensions other than the partition key;
and
writing the block to storage after said collecting and said sorting;
dividing a second multi-dimensional dataset that includes the partition key into a second set of blocks;
and
correlating the first dataset and the second dataset by:
for each pair of corresponding blocks in the first set of blocks and the second set of blocks, the corresponding blocks consisting of a first block in the first set of blocks and a second block in the second set of blocks:
storing the first block in memory;
for each of multiple sub-blocks of the second block, correlating the sub-block with the first block;
and
aggregating the correlations between the first block and each of the multiple sub-blocks of the second block.

13 more elements

A system, comprising:

a first multi-dimensional dataset;
one or more processors;
and
memory comprising instructions that, when executed by the one or more processors, cause the system to:
select one or more dimensions of the first dataset as a partition key;
select a cost constraint;
divide the first dataset into a first set of blocks, said dividing comprising, for each block in the first set of blocks:
associating with the block a distinct subset of partition key values such that a combination of all records of the first dataset having partition key values within the associated subset of partition key values satisfies the cost constraint;
collecting all records of the first dataset having partition key values within the associated subset of partition key values;
sorting the collected records using a sort key comprising one or more of the dataset dimensions other than the partition key;
and
writing the block to storage after said collecting and said sorting;
divide a second multi-dimensional dataset that includes the partition key into a second set of blocks;
and
correlate the first dataset and the second dataset by:
for each pair of corresponding blocks in the first set of blocks and the second set of blocks, the corresponding blocks consisting of a first block in the first set of blocks and a second block in the second set of blocks:
storing the first block in memory;
for each of multiple sub-blocks of the second block, correlating the sub-block with the first block;
and
aggregating the correlations between the first block and each of the multiple sub-blocks of the second block.

17 more elements

Dependencies are inferred from the claim text.