Perfect multidimensional spatial hashing
US7619623B2 · kind B2 · utility
13Cited by
3References
18Claims
0Family size
Assignee
Inventors
Key dates
| Filing date | Apr 17, 2006 |
| Grant date | Nov 17, 2009 |
| Priority date | — |
| Expiry date | Apr 26, 2027 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/5862
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A multidimensional hash table is created based on a data source having sparse multidimensional data. The sparse source data is mapped into the hash table using a hash function. The hash function can be defined by accessing multidimensional values in an offset table. The offset values in the offset table can be precomputed from the static source data so as to avoid hash collisions, thus creating a perfect hash function. Additionally, the perfect hash function is designed to preserve spatial coherence of accesses, so as to improve locality of memory reference.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.