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

We consider the dynamic dictionary problem for multisets. Given an upperbound $n$ on the total cardinality of the multiset (i.e., includingmultiplicities) at any point in time, the goal is to design a data structurethat supports multiplicity queries and allows insertions and deletions to themultiset (i.e., the dynamic setting). The data structure must bespace-efficient (the space is $1+o(1)$ times the information-theoretic lowerbound) and support all operations in constant time with high probability.  In this paper, we present the first dynamic dictionary for multisets thatachieves these performance guarantees. This answers an open problem ofArbitman, Naor and Segev (FOCS 2010). The previously best-known construction ofPagh, Pagh and Rao (SODA 2005) supports membership in constant time,multiplicity queries in $O(\log n)$ time in the worst case, and insertions anddeletions in constant expected amortized time. The main technical component ofour solution is a strategy for efficiently storing variable-length binarycounters using weighted balls-into-bins experiments in which balls havelogarithmic weights.  We also obtain a counting filter that approximates multiplicity queries witha one sided error, using the reduction of Carter et al. (STOC 1978). Countingfilters have received significant attention over the years due to theirapplicability in practice.We present the first counting filter with constanttime operations.

A Space-Efficient Dynamic Dictionary for Multisets with Constant Time Operations