Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Thursday, December 10, 2009, 12:15 pm

Duration: This information is not available in the database

Location: OAT S15/S16/S17

Speaker: Konstantinos Panagiotou (MPI Saarbrücken)

Sharp Load Thresholds for Cuckoo Hashing

he paradigm of many choices has influenced significantly the design of efficient data structures and, most notably, hash tables. Cuckoo hashing is a technique that extends this concept. There, we are given a table with~$n$ locations, and we assume that each location can hold one item. Each item to be inserted chooses randomly $k\ge 2$ locations and has to be placed in any one of them. How much load can cuckoo hashing handle before collisions prevent the successful assignment of the available items to the chosen locations? Practical evaluations of this method have shown that one can allocate a number of elements that is a large proportion of the size of the table, being very close to~1 even for small values of~$k$ such as 4 or 5.

In this talk we will show that there is a critical value for this proportion: with high probability, when the amount of available items is below this value, then these can be allocated successfully, but when it exceeds this value, the allocation becomes impossible. We give explicitly for each $k\geq 2$ this critical value. Our proofs are based on the translation of the question into a hypergraph setting, and the study of the related typical properties of random $k$-uniform hypergraphs.

Joint work with N. Fountoulakis.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2025  2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login