Optimal Fast Hashing

12 years 10 months ago
Optimal Fast Hashing
Abstract—This paper is about designing optimal highthroughput hashing schemes that minimize the total number of memory accesses needed to build and access an hash table. Recent schemes often promote the use of multiple-choice hashing. However, such a choice also implies a significant increase in the number of memory accesses to the hash table, which translates into higher power consumption and lower throughput. In this paper, we propose to only use choice when needed. Given some target hash table overflow rate, we provide a lower bound on the total number of needed memory accesses. Then, we design and analyze schemes that provably achieve this lower bound over a large range of target overflow values. Further, for the multilevel hash table scheme, we prove that the optimum occurs when its subtable sizes decrease in a geometric way, thus formally confirming a heuristic rule-of-thumb.
Josef Kanizo, David Hay, Isaac Keslassy
Added 24 May 2010
Updated 24 May 2010
Type Conference
Year 2009
Authors Josef Kanizo, David Hay, Isaac Keslassy
Comments (0)