BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:William Kuszmaul (MIT Mathematics) DTSTART:20211028T213000Z DTEND:20211028T230000Z DTSTAMP:20260423T021056Z UID:SPAMS/4 DESCRIPTION:Title: Li near Probing Revisited: Tombstones Mark the Demise of Primary Clustering\nby William Kuszmaul (MIT Mathematics) as part of MIT Simple Person's A pplied Mathematics Seminar\n\nLecture held in Room: 2 - 132 in the Simons Building.\n\nAbstract\nThe 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 ta ble reaches a high memory utilization\, elements within the hash table beg in to cluster together\, causing insertions to become slow. This phenomeno n\, now known as "primary clustering"\, was first captured by Donald Knuth in 1963\; at a load factor of $1 - 1/x$\, the expected time per insertion becomes $\\Theta(x^2)$\, rather than the more desirable $\\Theta(x)$.\n\n We show that there is more to the story than the classic analysis would se em to suggest. It turns out that small design decisions in how deletions a re implemented have dramatic effects on the asymptotic performance of inse rtions. If these design decisions are made correctly\, then even a hash ta ble that is continuously at a load factor $1 - \\Theta(1/x)$ can achieve a verage insertion time $\\tilde{O}(x)$. A key insight is that the tombstone s left behind by deletions cause a surprisingly strong "anti-clustering" e ffect\, and that when insertions and deletions are one-for-one\, the anti- clustering effects of deletions actually overpower the clustering effects of insertions.\n\nBased on joint work with Michael A. Bender and Bradley C . Kuszmaul.\nhttps://arxiv.org/abs/2107.01250\nTo appear in FOCS 2021.\n LOCATION:https://researchseminars.org/talk/SPAMS/4/ END:VEVENT END:VCALENDAR