Method for Efficient Aggregation of Numerous Data using Sparse Bit Sets

摘要

A data-processing technique for increasing data-size capacity and improving query speed on large datasets where fields within records are replaced by integers representing distinct values of those fields, the integers drawn from a densely-populated range, wherein a computer data storage structure is initialized and maintained to represent a large number of binary values (“bits”) within a smaller number of actual machine-memory bits of the computer. Representative structures and operations thereon, as well as applications of the data structure to support more-sophisticated data structures and operations, are described and claimed.

主权项

1. A method of performing space-efficient data query operations, comprising:
interning fields of a plurality of multi-field records to produce interned records representing the multi-field records; receiving a query to compute a result over the plurality of multi-field records; initializing a sparse bit set, said sparse bit set sized to accommodate a number of distinct values present in one of the fields of the plurality of multi-field records; dividing the interned records into two classes according to the query; and setting a bit in the sparse bit set for each interned record of one of the two classes, wherein an in-memory representation of the sparse bit set, exclusive of overhead, occupies fewer bits than the number of distinct values present in the one of the fields of the plurality of multi-field records.