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 performance of a dynamic dictionary is measured mainly by its updatetime, lookup time, and space consumption. In terms of update time and lookuptime there are known constructions that guarantee constant-time operations inthe worst case with high probability, and in terms of space consumption thereare known constructions that use essentially optimal space. However, althoughthe first analysis of a dynamic dictionary dates back more than 45 years ago(when Knuth analyzed linear probing in 1963), the trade-off between theseaspects of performance is still not completely understood. In this paper wesettle two fundamental open problems: - We construct the first dynamicdictionary that enjoys the best of both worlds: it stores n elements using(1+epsilon)n memory words, and guarantees constant-time operations in the worstcase with high probability. Specifically, for any epsilon = \Omega((\log\log n/ \log n)^{1/2} ) and for any sequence of polynomially many operations, withhigh probability over the randomness of the initialization phase, alloperations are performed in constant time which is independent of epsilon. Theconstruction is a two-level variant of cuckoo hashing, augmented with a"backyard" that handles a large fraction of the elements, together with ade-amortized perfect hashing scheme for eliminating the dependency on epsilon.- We present a variant of the above construction that uses only (1+o(1))B bits,where B is the information-theoretic lower bound for representing a set of sizen taken from a universe of size u, and guarantees constant-time operations inthe worst case with high probability, as before. This problem was open even inthe amortized setting. One of the main ingredients of our construction is apermutation-based variant of cuckoo hashing, which significantly improves thespace consumption of cuckoo hashing when dealing with a rather small universe.

Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation