Name
Abstract | ||
|---|---|---|
The hash table, especially its external memory version, is one of the most important index structures in large databases. Assuming a truly random hash function, it is known that in a standard external hash table with block size b, searching for a particular key only takes expected average t_q=1+1/2Ω(b) disk accesses for any load factor α bounded away from $1$. However, such near-perfect performance is achieved only when b is known and the hash table is particularly tuned for working with such a blocking. In this paper we study if it is possible to build a cache-oblivious hash table that works well with any blocking. Such a hash table will automatically perform well across all levels of the memory hierarchy and does not need any hardware-specific tuning, an important feature in autonomous databases. We first show that linear probing, a classical collision resolution strategy for hash tables, can be easily made cache-oblivious but it only achieves t_q = 1 + O(αb). Then we demonstrate that it is possible to obtain t_q = 1 + 1/2Ω(b), thus matching the cache-aware bound, if the following two conditions hold: (a) b is a power of 2; and (b) every block starts at a memory address divisible by b. Both conditions hold on a real machine, although they are not stated in the cache-oblivious model. Interestingly, we also show that neither condition is dispensable: if either of them is removed, the best obtainable bound is t_q=1+O(αb), which is exactly what linear probing achieves. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1145/1807085.1807124 | Algorithmica |
Keywords | Field | DocType |
Cache-oblivious algorithms,Hashing | Primary clustering,Discrete mathematics,Double hashing,Computer science,Rolling hash,Theoretical computer science,Hash function,Quadratic probing,Dynamic perfect hashing,Linear hashing,Open addressing | Journal |
Volume | Issue | Citations |
69 | 4 | 2 |
PageRank | References | Authors |
0.36 | 24 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Rasmus Pagh | 1 | 1344 | 86.08 |
| Zhewei Wei | 2 | 215 | 20.07 |
| Ke Yi | 3 | 1659 | 77.79 |
| Qin Zhang | 4 | 693 | 42.56 |