Data Science & AI Lecture Series
Linear Probing Revisited: How to Get Rid of Clustering
William Kuszmaul
Linear Probing Revisited: How to Get Rid of Clustering
| When | Wednesday, November 1, 2023, 10:30 AM – 11:45 AM (MT) |
|---|---|
| Where | FASB 295 |
Abstract
The linear-probing hash table is one of the oldest and most widely used data structures in computer science. However, linear probing also famously comes with a major drawback: as soon as the hash table reaches a high memory utilization, elements within the hash table begin to cluster together, causing insertions to become slow. This clustering phenomenon, which was first discovered by Donald Knuth in 1962, increases the expected time per insertion to $\Theta(x^2)$ (rather than the more desirable $\Theta(x)$) in a hash table that is a $1 - 1/x$ fraction full. A natural question is whether one can somehow reduce clustering. In this talk, we establish an even stronger statement: the classical linear-probing hash table (even as it was first implemented in the 1950s) already has less clustering than the classical results would seem to suggest. As insertions and deletions are performed over time, the tombstones left behind by deletions cause the combinatorial structure of the hash table to stabilize in a way that eliminates clustering. This means that, for some versions of linear probing, the amortized expected time per operation is actually $\tilde{O}(x)$. We also present a new version of linear probing that avoids clustering entirely, achieving $O(x)$ expected time per operation.
Speaker
William Kuszmaul
MIT
William Kuszmaul’s research focuses on the design and analysis of randomized algorithms and data structures. He is currently the Rabin Postdoctoral Fellow in Theoretical Computer Science at Harvard University, and after that, he will begin as an Assistant Professor in the CS Department at CMU. His research has won numerous awards at both theory and systems conferences, including Distinguished Paper at ASPLOS’23, Best Student Paper at ESA’22, Best Paper Finalist at SPAA’22, Best Paper at FUN’20, and Best Paper Finalist at APOCS’20. Prior to his postdoc, William completed a PhD at MIT, where he was funded by the John and Fannie Hertz Fellowship.
Tags: algorithms & theory data management
Part of the Data Science & AI Lecture Series. Something wrong on this page? Edit _data/talks/2023-11-01-william-kuszmaul.toml.