@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, }