@techreport{TD:100272,
	att_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 Carter and Wegman (STOC'77).  Keys are
viewed as consisting of $c$ characters. We initialize $c$ tables $T_1,
dots, T_c$ mapping characters to random hash code. A key
$x=(x_1, dots, x_q)$ is hashed to $T_1[x_1] oplus cdots oplus
T_c[x_c]$, where $oplus$ 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., Chernoff-type concentration, min-wise hashing for
estimating set intersection, and cuckoo hashing.
}},
	att_authors={mp6431, mt2514},
	att_categories={},
	att_copyright={{ACM}},
	att_copyright_notice={{(c) ACM, 2011. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Proceedings of ACM STOC'11. {{, 2011-06-06}}.
}},
	att_donotupload={},
	att_private={false},
	att_projects={},
	att_tags={},
	att_techdoc={true},
	att_techdoc_key={TD:100272},
	att_url={http://web1.research.att.com:81/techdocs_downloads/TD:100272_DS1_2010-11-05T18:56:22.421Z.pdf},
	author={Mihai Patrascu and Mikkel Thorup},
	institution={{Proceedings of ACM STOC'11}},
	month={June},
	title={{The Power of Simple Tabulation Hashing}},
	year=2011,
}