Abstract
We introduce a new tabulation-based hashing scheme called "twisted tabulation". It is essentially as simple and fast as simple tabulation, but has some powerful distributional properties illustrating its promise: (1) If we sample keys with arbitrary probabilities, then with high probability, the number of samples inside any subset is concentrated exponentially. With bounded independence we only get polynomial concentration, and with simple tabulation, we have no good bound even in the basic case of tossing an (unbiased) coin for each key. (2) With classic hash tables such as linear probing and collision-chaining, a window of B operations takes O(B) time with high probability, for B = Ω(lg n). Good amortized performance over any window of size B is equivalent to guaranteed throughput for an on-line system processing a stream via a buffer of size B (e.g., Internet routers).
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms |
| Editors | Sanjeev Khanna |
| Number of pages | 20 |
| Publisher | Association for Computing Machinery |
| Publication date | 2013 |
| Pages | 209-228 |
| ISBN (Print) | 978-1-611972-51-1 |
| ISBN (Electronic) | 978-1-61197-310-5 |
| DOIs | |
| Publication status | Published - 2013 |
| Event | Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms - Aster Crowne Plaza Hotel, New Orleans, United States Duration: 6 Jan 2013 → 8 Jan 2013 Conference number: 24 |
Conference
| Conference | Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms |
|---|---|
| Number | 24 |
| Location | Aster Crowne Plaza Hotel |
| Country/Territory | United States |
| City | New Orleans |
| Period | 06/01/2013 → 08/01/2013 |