PERFECT HASHING OF VARIABLY-SIZED DATA

• US 20070245119A1
• Filed: 06/14/2007
• Published: 10/18/2007
• Est. Priority Date: 04/17/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hoppe, Hugues
• Granted Patent: US 7,965,297 B2
• Time in Patent Office: Days
• US Class Current: 711/216
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/5862 using texture
• CPC Class Codes: G09C 1/00 Apparatus or methods whereby a given sequence of signs, e.g. an intelligible text, is transformed into an unintelligible sequence of signs by transposing the signs or groups of signs or by replacing them by others according to a predetermined system cryptographic typewriters G09C3/00
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 67/1065 Discovery involving distributed pre-established resource-based relationships among peers, e.g. based on distributed hash tables [DHT] pre-configuration of logical or physical connections H04L67/1053
• CPC Class Codes: H04L 9/0643 Hash functions, e.g. MD5, SHA, HMAC or f9 MAC

Abstract

A “Variable-Rate Perfect Hasher” maps sparse variable-rate data of one or more dimensions into a hash table using a perfect hash function. In various embodiments, perfect hash tables are populated by first computing offset table address for each data point of a domain of sparse variable-rate data elements. Offset vectors are then computed for each offset table address based in part on the size of each data element by evaluating offset vectors in order of a sum of the data point addresses mapping to each offset vector. These offset vectors are then stored in the offset table. For each data point, the corresponding offset vector is then used to compute a hash table address. Data elements are then perfectly hashed into the hash table using the computed hash table addresses. The resulting hash tables support efficient random access of the variable-sized data elements stored therein.

Claims

1. A process for hashing variable-sized data, comprising:

receiving set of variable-sized data elements;

for each data element, computing a corresponding offset vector address from an address of the data element;

for each offset vector address, computing a corresponding offset vector for populating an offset table;

for each data element, computing a corresponding hash table address from a combination of the address of the data element and the corresponding offset vector; and

hashing each data element to a contiguous block of one or more storage locations in the hash table beginning with the corresponding hash table address.

2. The process of claim 1 wherein each computed offset vector ensures a perfect hash of the corresponding data element by ensuring that there are no collisions between any data elements being hashed to the hash table.

3. The process of claim 2 wherein computing the corresponding hash table address from a combination of the address of the data element and the corresponding offset vector further comprises:

adding a size of all data elements having the same corresponding offset vector address to create a composite sum for each offset vector address; and

evaluating each offset vector address in order of highest to lowest composite sum when computing the corresponding hash table address.

4. The process of claim 1 wherein computing the offset vector for each offset vector address comprises evaluating all possible offset vectors starting from a random offset vector until finding an offset vector for the corresponding data element that does not create any hash collisions based on a size of the corresponding data element.

5. The process of claim 1 wherein computing the offset vector for each offset vector address comprises placing hashes of spatially coherent data elements as close as possible to each other in the hash table by evaluating all possible offset vectors for each data element until identifying an invalid offset vector that results in a hash table collision, then identifying the closest offset vector to the invalid offset vector that does not result in a collision based on a size of the corresponding data element.

6. The process of claim 1 further comprising randomly accessing one or more the data elements by:

selecting an address of one or more of the data elements;

computing the corresponding offset vector addresses for the selected data elements;

retrieving the corresponding offset vector for each offset vector address from the offset table;

computing the corresponding hash table address for each data element from the retrieved offset vector and the data element address; and

retrieving the hashed data element from the hash table using the corresponding hash table address.

7. The process of claim 1 further comprising computing a binary mask over a domain representing a spatial extent of the data elements to indicate whether each data element contains any information.

8. The process of claim 7 further comprising using the mask to exclude all data elements not having any information from being used to compute offset vectors and to exclude those data elements from hashed to the hash table.

9. The process of claim 1 wherein the sparse, spatially coherent variable-rate data elements represents a grid-based representation of an image, and wherein each cell of the grid has variable-rate image data.

10. The process of claim 9 wherein the hash table is stored into a memory buffer of a graphics processing unit (GPU), and wherein the selected regions of the image are rendered by the GPU by providing GPU-based random access to hashed data elements within the hash table corresponding to the selected regions of the image.

11. A computer-readable medium having computer executable instructions stored thereon for perfectly hashing image data into a hash table, said computer executable instructions comprising:

receiving a sparse grid-based image comprised of a plurality of neighboring cells, wherein a subset of the cells contain variable-rate image data and wherein the remaining cells do not contain data;

computing a binary mask over the grid-based image to identify each cell of the subset of cells that contain variable-rate image data;

in accordance with the binary mask, for each cell that contains variable-rate image data, determining a cell address and computing a corresponding offset vector address, each said offset vector address corresponding to one or more of the cells;

for each offset vector address, computing a corresponding offset vector for populating a corresponding entry in an offset table;

in accordance with the binary mask, for each cell that contains variable-rate image data, computing a corresponding hash table address from a sum of the cell address and the corresponding offset vector; and

in accordance with the binary mask, for each cell that contains variable-rate image data, hashing the contents of each cell to a contiguous block of one or more storage locations within the hash table beginning with the corresponding hash table address.

12. The computer-readable medium of claim 11 wherein each computed offset vector ensures a perfect hash of the variable-rate image data for the one or more corresponding cells by ensuring that there are no collisions between any data of any of the cells being hashed to the hash table.

13. The computer-readable medium of claim 11 wherein computing the offset vector for each offset vector address comprises evaluating all possible offset vectors starting from a random offset vector until finding an offset vector for the one or more corresponding cells that does not create any hash collisions based on a size of the variable-rate image data in each corresponding cell.

14. The computer-readable medium of claim 11 wherein computing the offset vector for each offset vector address comprises placing hashes of variable-rate image data of spatially coherent cells as close as possible to each other in the hash table by evaluating all possible offset vectors for each cell until identifying an invalid offset vector that results in a hash table collision, then identifying the closest offset vector to the invalid offset vector that does not result in a collision based on a size of the variable-rate image data in the corresponding cell.

15. The computer-readable medium of claim 11 further comprising randomly accessing the variable-rate image data of one or more selected cells:

selecting an address of one or more of the cells;

computing the corresponding offset vector addresses for the selected cells and retrieving the corresponding offset vector for each computed offset vector address from the offset table;

computing the corresponding hash table address for each selected cell from the retrieved offset vector and the corresponding cell address; and

retrieving the hashed data variable-rate data for each selected cell from the hash table using the corresponding hash table address.

16. The computer-readable medium of claim 15 further comprising instructions for storing the hash table into a memory buffer of a graphics processing unit (GPU), and wherein selected regions of the image are rendered by the GPU by providing GPU-based random access to hashed variable-rate data of the selected cells.

17. A method for performing a perfect hash of data sparsely populating a domain, comprising using a computing device to:

receiving set of variable-rate data elements, each data element corresponding to a populated data point within a sparse data domain;

determining an address for each populated data point and computing a corresponding offset vector address, each offset vector address corresponding to one or more of the populated data points;

computing and storing a corresponding offset vector for each offset vector address, wherein each computed offset vector ensures a perfect hash of the corresponding variable-rate data element of each of the corresponding populated data points;

for each populated data point, computing a corresponding hash table address from a sum of the data point address and the corresponding offset; and

hashing the spatially coherent variable-rate data element of each populated data point to a contiguous block of one or more storage locations within in a hash table beginning with the corresponding hash table address.

18. The method of claim 17 wherein computing the offset vector for each offset vector address comprises evaluating all possible offset vectors starting from a random offset vector until finding an offset vector for each of the one or more corresponding data point that does not create any hash collisions.

19. The method of claim 17 wherein computing the offset vector for each offset vector address comprises placing hashes of spatially coherent variable-rate data elements of the corresponding populated data points as close as possible to each other in the hash table by evaluating all possible offset vectors for each data point until identifying an invalid offset vector that results in a hash table collision, then identifying the closest offset vector to the invalid offset vector that does not result in a collision.

20. The method of claim 17 further comprising randomly accessing the spatially coherent variable-rate data elements of one or more selected data points by:

determining the address of each selected data point;

computing the corresponding offset vector addresses for the selected data points and retrieving the stored corresponding offset vector for each computed offset vector address;

computing the corresponding hash table address for each selected data point from the retrieved offset vector and the corresponding data point address; and

retrieving the hashed spatially coherent variable-rate data elements for each selected data point from the hash table using the corresponding hash table address.