[Sem-coll] Colloquium Today (1/28,Wednesday at 4:30pm)
kaul at math.iit.edu
Wed Jan 28 00:54:57 CST 2009
This is just a reminder that we have an Applied Math colloquium today
(Wednesday, 28th January) at 4:40pm. The location as usual is 106, E1
Bldg. Refreshments will be served at 4:20pm in Room 112.
Wednesday, January 28, 4:40pm
106, E1 Bldg. IIT
Pall Melsted, Carnegie Mellon University
"Random Walks for Cuckoo Hashing"
A Dictionary is a fundamental data structure in computer science, that
provides a mapping from keys to elements. One implementation is the
d-ary Cuckoo Hashing Table, which uses d hash functions and guarantees
that each key present be stored in one of the locations it hashes to.
Cuckoo hashing is known to have good space efficiency and worst case
access time, but insertion of items into the table is harder. A depth
first search tree algorithm is known to take expected constant time,
but its worst case performance can be polynomial. Most practical
implementations use a random walk heuristic to insert items, which is
known to work well in practice but previous to this work no
theoretical bounds were known. We present an analysis of the random
walk heuristic by analyzying matchings in random graphs, and show it
runs in expected and worst case polylogarithmic time. The talk will be
accessible a general math audience and no prior knowledge of data
structures is necessary.
I hope to see you there.
More information about the seminar-coll