Málstofa í stærðfræði
Fyrirlesari: Páll Melsted
Titill: Space Utilization of Cuckoo Hashtables
Staðsetning: V-157, VRII.
Tími: Föstudagur 23. október, klukkan 15:00-16:00.
Ágrip:
We study the space requirements for Cuckoo Hashing. This can be reduced to
the following question in Random Graphs.
We are given two disjoint sets L,R with |L|=n=alpha*m and |R|=m. We construct a random graph G by allowing each x in L to choose d random neighbours in R. The problem is to find m(G), the size of the largest matching in G.
From the point of view of Cuckoo Hashing, a key question is to locate the threshold for when m(G)=n with high probability, since if m(G) < n it is impossible to store all items. We answer this question exactly for all values of d.