Nearly Optimal Static Las Vegas Succinct Dictionary

DOI10.1145/3357713.3384274MaRDI QIDQ6328490arXivFDO

Authors Huacheng Yu

Publication date 4 November 2019

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10)

Abstract: Given a set $S$ of $n$ (distinct) keys from key space $[U]$, each associated with a value from $Sigma$, the emph{static dictionary} problem asks to preprocess these (key, value) pairs into a data structure, supporting value-retrieval queries: for any given $xin[U]$, $mathttvalRet(x)$ must return the value associated with $x$ if $xinS$, or return $$ if $xotinS$. The special case where $|Sigma|=1$ is called the emph{membership} problem. The "textbook" solution is to use a hash table, which occupies linear space and answers each query in constant time. On the other hand, the minimum possible space to encode all (key, value) pairs is only $$ bits, which could be much less. In this paper, we design a randomized dictionary data structure using $mathttOPT+mathrmpolylgn+O(lglglglglgU)$ bits of space, and it has emph{expected constant} query time, assuming the query algorithm can access an external lookup table of size $n^{0.001}$. The lookup table depends only on $U$, $n$ and $|Sigma|$, and not the input. Previously, even for membership queries and $Uleq{n}^{O(1)}$, the best known data structure with constant query time requires $mathttOPT+n/mathrmpolylgn$ bits of space (Pagh [Pag01] and Pv{a}trac{s}cu [Pat08]); the best-known using $mathttOPT+n^{0.999}$ space has query time $O(lgn)$; the only known non-trivial data structure with $mathttOPT+n^{0.001}$ space has $O(lgn)$ query time and requires a lookup table of size $geq{n}^{2.99}$ (!). Our new data structure answers open questions by Pv{a}trac{s}cu and Thorup [Pat08,Tho13]. We also present a scheme that compresses a sequence $XinSigm{a}^n$ to its zeroth order (empirical) entropy up to $|Sigma|cdotmathrmpolylgn$ extra bits, supporting decoding each $X_i$ in $O(lg|Sigma|)$ expected time.

This page was built for publication: Nearly Optimal Static Las Vegas Succinct Dictionary

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6328490)