Back to results
US 8,027,983 B1Granted
Enhanced query performance using fixed length hashing of multidimensional data
AssigneeGoogle Inc.
InventorsSagnik Nandy, Jonathon A. Vance, Jan Matthias Ruhl
Life of this patent
Estimating the term…
Abstract
Methods, systems and apparatus, including computer program products, for enhancing query performance through fixed length hashing of multidimensional data. According to one method, a fixed length hash of a multidimensional data record is created where the hash has respective fixed length sections for each data dimension of the record being hashed. The composite fixed length hash is stored with a reference to the original data record to which it corresponds. Query parameters are hashed and compared to a corresponding section of the fixed length hash to determine a set of candidate records.
Claims19
A method, comprising:
- receiving, by a data processing apparatus, a data record from a collection of data records, the data record having multiple dimensions, each dimension corresponding to a respective field in the data record and specifying a value;
- receiving, by a data processing apparatus, a set of hashing options, the set of hashing options specifying hash lengths for hashes of the multiple dimensions of the data record, a hash length being specified for each dimension based on a number of different possible values of data in the dimension;
- and
- creating, by a data processing apparatus, a composite fixed length data hash of the data record, the composite fixed length data hash being a concatenation of respective hashes of values specified by respective dimensions of the data record, each of the respective hashes being in a respective section of the composite fixed length data hash, each respective section having a section length that corresponds to the hash length of a particular dimension to which the respective section corresponds, the composite fixed length data hash having a fixed length at least equal to a sum of the section lengths of respective sections in the composite fixed length data hash, wherein one section of the composite fixed length data hash includes multiple segments that store respective hash values corresponding to multiple values in a field of the data record, each of the segments having a segment length that is shorter than the section length of the section in which the segments are included.
1 more element
A method comprising:
- counting, by a data processing device, a number of list values that appear in a field of a data record;
- storing, by a data processing device, a wildcard hash value in a section of a composite fixed length data hash representing the data record in response to the number of list values exceeding a maximum value, the maximum value being determined based on a maximum number of values accurately represented by the section of the fixed length data hash, the composite fixed length data hash being a concatenation of hashes of values specified by fields of the data record, each section of the composite fixed length data hash containing a hash of a respective field of the data record;
- and
- in response to receiving a query hash corresponding to the section of the composite fixed length data hash in which the wildcard hash is stored, searching the field of the data record corresponding to the section for a value in the list that matches a query parameter from which the query hash was created, wherein one section of the composite fixed length data hash includes multiple segments that store respective hash values corresponding to multiple values in a field of the data record, each of the segments having a segment length that is shorter than a section length of the section in which the segments are included.
1 more element
A system comprising:
- a user interface device;
- and
- one or more computers configured to interact with the user interface device and to:
- receive a query value from the user interface device, the query value corresponding to a field of a set of data records;
- create a query hash of the query value;
- compare the query hash to a section of a set of composite fixed length data hashes that each represent respective data records in the set of data records, each composite fixed length data hash being a concatenation of hashes of values specified by fields of the respective data records, each section corresponding to a particular field of the respective data records, containing a hash of the particular field of a data record, and having a section length that is selected based on a number of different possible values of data in the particular field, each of the composite fixed length data hashes having a same fixed length corresponding to an aggregate section length for sections of the fixed length data hash, the section to which the query hash is compared being the section corresponding to the particular field to which the query value corresponds;
- and
- record references to data records that have a corresponding data hash section matching the query hash, wherein one section of the composite fixed length data hash includes multiple segments that store respective hash values corresponding to multiple values in a field of the data record, each of the segments having a segment length that is shorter than the section length of the section in which the segments are included.
5 more elements
Dependencies are inferred from the claim text.