English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The paradigm of many choices has influenced significantly the design ofefficient data structures and, most notably, hash tables. Cuckoo hashing is atechnique 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 beinserted chooses randomly k>1 locations and has to be placed in any one ofthem. How much load can cuckoo hashing handle before collisions prevent thesuccessful assignment of the available items to the chosen locations? Practicalevaluations of this method have shown that one can allocate a number ofelements that is a large proportion of the size of the table, being very closeto 1 even for small values of k such as 4 or 5.  In this paper we 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, theallocation becomes impossible. We give explicitly for each k>1 this criticalvalue. This answers an open question posed by Mitzenmacher (ESA '09) andunderpins theoretically the experimental results. Our proofs are based on thetranslation of the question into a hypergraph setting, and the study of therelated typical properties of random k-uniform hypergraphs.

Sharp Load Thresholds for Cuckoo Hashing