演讲人： Mikkel Thorup 哥本哈根大学
时间： 2011-12-15 14:00-2011-12-15 15:00
地点：FIT 1-222
课件下载：点击下载
内容：

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 $\mathrm{<span\; style="font-size:\; 14px;"><span\; style="font-family:\; Times\; New\; Roman;">c</span></span>}$ characters. We initialize $\mathrm{<span\; style="font-size:\; 14px;"><span\; style="font-family:\; Times\; New\; Roman;">c</span></span>}$ tables ${\mathrm{<span\; style="font-size:\; 14px;"><span\; style="font-family:\; Times\; New\; Roman;">T</span></span>}}_{\mathrm{<span\; style="font-size:\; 14px;"><span\; style="font-family:\; Times\; New\; Roman;">1</span></span>}}<span\; style="font-size:\; 14px;"><span\; style="font-family:\; Times\; New\; Roman;">,</span></span><span\; style="font-size:\; 14px;"><span\; style="font-family:\; Times\; New\; Roman;">\dots </span></span><span\; style="font-size:\; 14px;"><span\; style="font-family:\; Times\; New\; Roman;">,</span></span>{\mathrm{<span\; style="font-size:\; 14px;"><span\; style="font-family:\; Times\; New\; Roman;">T</span></span>}}_{\mathrm{<span\; style="font-size:\; 14px;"><span\; style="font-family:\; Times\; New\; Roman;">c</span></span>}}$ mapping characters to random hash codes. A key $\mathrm{<span\; style="font-size:\; 14px;"><span\; style="font-family:\; Times\; New\; Roman;">x</span></span>}<span\; style="font-size:\; 14px;"><span\; style="font-family:\; Times\; New\; Roman;">=</span></span><span\; style="font-size:\; 14px;"><span\; style="font-family:\; Times\; New\; Roman;">(</span></span>{\mathrm{<span\; style="font-size:\; 14px;"><span\; style="font-family:\; Times\; New\; Roman;">x</span></span>}}_{\mathrm{<span\; style="font-size:\; 14px;"><span\; style="font-family:\; Times\; New\; Roman;">1</span></span>}}<span\; style="font-size:\; 14px;"><span\; style="font-family:\; Times\; New\; Roman;">,</span></span><span\; style="font-size:\; 14px;"><span\; style="font-family:\; Times\; New\; Roman;">\dots </span></span><span\; style="font-size:\; 14px;"><span\; style="font-family:\; Times\; New\; Roman;">,</span></span>{\mathrm{<span\; style="font-size:\; 14px;"><span\; style="font-family:\; Times\; New\; Roman;">x</span></span>}}_{\mathrm{<span\; style="font-size:\; 14px;"><span\; style="font-family:\; Times\; New\; Roman;">c</span></span>}}<span\; style="font-size:\; 14px;"><span\; style="font-family:\; Times\; New\; Roman;">)</span></span>$ is hashed to ${\mathrm{<span\; style="font-size:\; 14px;"><span\; style="font-family:\; Times\; New\; Roman;">T</span></span>}}_{\mathrm{<span\; style="font-size:\; 14px;"><span\; style="font-family:\; Times\; New\; Roman;">1</span></span>}}<span\; style="font-size:\; 14px;"><span\; style="font-family:\; Times\; New\; Roman;">[</span></span>{\mathrm{<span\; style="font-size:\; 14px;"><span\; style="font-family:\; Times\; New\; Roman;">x</span></span>}}_{\mathrm{<span\; style="font-size:\; 14px;"><span\; style="font-family:\; Times\; New\; Roman;">1</span></span>}}<span\; style="font-size:\; 14px;"><span\; style="font-family:\; Times\; New\; Roman;">]</span></span><span\; style="font-size:\; 14px;"><span\; style="font-family:\; Times\; New\; Roman;">\oplus </span></span><span\; style="font-size:\; 14px;"><span\; style="font-family:\; Times\; New\; Roman;">\cdots </span></span><span\; style="font-size:\; 14px;"><span\; style="font-family:\; Times\; New\; Roman;">\oplus </span></span>{\mathrm{<span\; style="font-size:\; 14px;"><span\; style="font-family:\; Times\; New\; Roman;">T</span></span>}}_{\mathrm{<span\; style="font-size:\; 14px;"><span\; style="font-family:\; Times\; New\; Roman;">c</span></span>}}<span\; style="font-size:\; 14px;"><span\; style="font-family:\; Times\; New\; Roman;">[</span></span>{\mathrm{<span\; style="font-size:\; 14px;"><span\; style="font-family:\; Times\; New\; Roman;">x</span></span>}}_{\mathrm{<span\; style="font-size:\; 14px;"><span\; style="font-family:\; Times\; New\; Roman;">c</span></span>}}<span\; style="font-size:\; 14px;"><span\; style="font-family:\; Times\; New\; Roman;">]</span></span>$, where $<span\; style="font-size:\; 14px;"><span\; style="font-family:\; Times\; New\; Roman;">\oplus </span></span>$ 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. We shall also discuss a twist to simple tabulation that leads to extremely robust performance for linear probing with small buffers.

个人简介: