License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2017.4
URN: urn:nbn:de:0030-drops-75074
URL: http://drops.dagstuhl.de/opus/volltexte/2017/7507/
Go to the corresponding LIPIcs Volume Portal


Thorup, Mikkel

Fast and Powerful Hashing Using Tabulation (Invited Talk)

pdf-format:
LIPIcs-ICALP-2017-4.pdf (0.3 MB)


Abstract

Randomized algorithms are often enjoyed for their simplicity, but the hash functions employed to yield the desired probabilistic guarantees are often too complicated to be practical. Here we survey recent results on how simple hashing schemes based on tabulation provide unexpectedly strong guarantees. Simple tabulation hashing dates back to Zobrist [1970]. Keys are viewed as consisting of c characters and we have precomputed character tables h_1,...,h_q mapping characters to random hash values. A key x=(x_1,...,x_c) is hashed to h_1[x_1] xor h_2[x_2]..... xor h_c[x_c]. This schemes is very fast with character tables in cache. While simple tabulation is not even 4-independent, it does provide many of the guarantees that are normally obtained via higher independence, e.g., linear probing and Cuckoo hashing. Next we consider twisted tabulation where one character is "twisted" with some simple operations. The resulting hash function has powerful distributional properties: Chernoff-Hoeffding type tail bounds and a very small bias for min-wise hashing. Finally, we consider double tabulation where we compose two simple tabulation functions, applying one to the output of the other, and show that this yields very high independence in the classic framework of Carter and Wegman [1977]. In fact, w.h.p., for a given set of size proportional to that of the space consumed, double tabulation gives fully-random hashing. While these tabulation schemes are all easy to implement and use, their analysis is not. This keynote talk surveys results from the papers in the reference list.

BibTeX - Entry

@InProceedings{thorup:LIPIcs:2017:7507,
  author =	{Mikkel Thorup},
  title =	{{Fast and Powerful Hashing Using Tabulation (Invited Talk)}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{4:1--4:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7507},
  URN =		{urn:nbn:de:0030-drops-75074},
  doi =		{10.4230/LIPIcs.ICALP.2017.4},
  annote =	{Keywords: Hashing, Randomized Algorithms}
}

Keywords: Hashing, Randomized Algorithms
Seminar: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Issue Date: 2017
Date of publication: 06.07.2017


DROPS-Home | Fulltext Search | Imprint Published by LZI