Title: The Power of Tabulation Hashing
Speaker: Mikkel Thorup, AT&T Labs-Research
Date: Wednesday, March 6, 2013 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Randomized algorithms are often enjoyed for their simplicity, but the hash functions used to yield the desired theoretical guarantees are often neither simple nor practical. Here we show that the simplest possible tabulation hashing provides unexpectedly strong guarantees. The scheme itself dates back to Zobrist [1970]. Keys are viewed as consisting of c characters. We initialize c tablesT1,â¦,Tc mapping characters to random hash codes. A key x=(x1,â¦,xc) is hashed toT1[x1]???Tc[xc], where ? denotes xor. While this scheme is not even 4-independent, we show that it provides many of the guarantees that are normally obtained via higher independence, e.g., min-wise hashing for estimating set intersection, and cuckoo hashing. We shall also discuss a twist to simple tabulation that leads to reliable statistics with Chernoff-type concentration and extremely robust performance.