CS Paper Radar

Average-Case Optimal Encodings and Efficient Worst-Case Indices for Element Distinctness Queries

Philip Bille, Johannes Fischer, Inge Li Gørtz, Filippo Lari

cs.DS ·submitted 2026-08-18 15:39 UTC · v2
publishedtheoryhot direction

Abstract

We study the data structure version of the \emph{element distinctness problem}: preprocess an array of $n$ elements from an alphabet of size $σ$ to answer \textsc{All-Distinct} queries, asking whether a given range contains only distinct elements. We first focus on \emph{uniformly random arrays}: in the encoding model, where access to the input at query time is not allowed, we prove a lower bound on the expected space; for instance, the lower bound is $n$, $1.3627n$, $1.5153n$, $1.5824n$ bits for $σ= 2,3,4,5$, and approximately $n\sqrt{π/(2σ)}\,\logσ$ bits for $σ=ω(1)$. We complement this by designing different average-case optimal encodings, supporting \textsc{All-Distinct} queries in worst-case time $O(1)$, $o(\log^{2}{\log{n}})$, or $O(\log\log{n})$ depending on $σ$, and $O(1)$ expected time for any $σ= ω(1)$. We then switch to worst-case (non-random) arrays: in the indexing model, where access to the input is allowed, we prove a cell-probe space-time tradeoff lower bound showing that any index using $n/b$ bits must have $Ω(b/\log{b})$ query time. We conclude by presenting a simple index almost matching this lower bound.

Comment
Accepted at SPIRE 2026. Full version

Closest papers

Nearest neighbours by meaning across the whole index.

Optimal Encodings for Next/Previous Larger/Smaller Value Queries: A Unified Approach

cs.DS ·2026-10-28 ·Seungbum Jo, Geunho Kim, Kunihiko Sadakane, Srinivasa Rao Satti
similarity 0.69
Abstract

Given a 1D array over a total order and a query position in the array, a next larger value query returns the nearest position to the right whose value is larger than the value at the query position. Next smaller value queries and previous larger/smaller value queries are defined analogously. These queries are closely related to the $k$-th range minimum/maximum problem, which asks for the position of the $k$-th leftmost minimum/maximum value when the query range contains multiple minimum/maximum values. In this paper, we consider the encoding problem for answering any arbitrary subfamily of these four queries, where the queries must be answered without accessing the input array. We give a unified approach for obtaining space lower bounds for such encodings. We also obtain data structures for the query subfamilies that match the lower bounds up to lower-order additive terms, while supporting the queries in constant time. Our results generalize and improve several previous results on this problem [Gawrychowski and Nicholson, ICALP-2015; Jo and Satti, TCS-2016; Tsur, IPL-2019; Jo and Kim, Algorithmica-2025]. In addition, these results give tight bounds on the encoding complexity of all subfamilies of these queries for (1) permutations, (2) arrays without consecutive equal elements, and (3) general arrays.

0.19

Improved lower bounds for decomposable randomized encoding

cs.CC cs.CRcs.DM ·2026-09-16 ·Justin Holmgren, Kewen Wu
theory similarity 0.67
Abstract · 24 pages

A decomposable randomized encoding (DRE) for a function $f$ allows $n$ parties, using shared randomness, to encode their individual inputs locally so that the collection of encodings reveals $f(x_1,\ldots,x_n)$ and nothing else. DREs are widely used in efficient multiparty computation. Their main complexity measure is size, the total bit length of the local encodings. Yet the optimal DRE size remains poorly understood even for the $n$-bit OR function. We prove the first superlinear lower bound for OR and, more generally, for every non-periodic symmetric function. Under an additional symmetry assumption, we prove a sharp $Ω(n\log n)$ lower bound for OR, matching the classic construction of Feige, Kilian, and Naor (STOC 1994). We also prove the first $Ω(n^2)$ lower bound on DRE size for non-explicit Boolean functions.

0.46

Constant-Time Inverse Suffix Array Queries in Compact Space and Sublinear-Time Construction of Suffix Array Indexes

cs.DS ·2026-08-19 ·Dominik Kempa, Tomasz Kociumaka
theory similarity 0.66
Abstract

For a text $T\in[0..σ)^n$ with $2\leqσ\leq n$, its suffix array orders the suffix starting positions lexicographically, while its inverse suffix array maps each position to its suffix's rank. Since compressed suffix arrays and FM-indexes appeared in 2000, a central goal has been to support both queries in $O(n\logσ)$ bits. Thankachan recently reduced inverse suffix array query time to $O(\log\log n/\log\logσ)$, but constant time remained open. We give the first inverse suffix array structure with optimal space and query time: $O(n\logσ)$ bits and $O(1)$ time. For binary texts, this unconditionally separates the two queries for deterministic structures, since every $O(n)$-bit suffix array structure in the cell-probe model with $Θ(\log n)$-bit cells has worst-case query time $Ω(\log\log n/\log\log\log n)$. Construction is a second challenge: linear time can take $Θ(\log_σ n)$ times as long as reading the input or writing a compact index. Previously, sublinear construction was known for only one such index supporting both queries. In the word RAM with $Θ(\log n)$-bit words, we deterministically construct the new structure and two suffix array families from the packed text in $O(n\min(1,\logσ/\sqrt{\log n}))$ time. For $B\geq2$, the first family uses $O(n\logσ(1+\log_B\log_σn))$ bits and has query time $O(B(1+\log_B\log_σn))$, whereas the second uses $O(Bn\logσ(1+\log_B\log_σn))$ bits and has query time $O(1+\log_B\log_σn)$. Each has peak preprocessing space bounded by its index size. For binary texts, the second family matches the deterministic cell-probe time-space lower bound whenever $B\geq(\log\log n)^{Ω(1)}$, and, outside the slowest-query regimes, improving the deterministic construction time to $o(n/\sqrt{\log n})$ would yield an equally fast Dictionary Matching algorithm.

0.44

Cell-Probe Lower Bounds and Complexity-Preserving Reductions for Suffix Array Queries

cs.DS ·2026-08-19 ·Dominik Kempa, Tomasz Kociumaka
publishedtheory similarity 0.65
Abstract · Full version of a SODA 2027 paper

For a text $T$ of length $n$ over an alphabet of size $σ$, its suffix array lists the starting positions of the suffixes of $T$ in lexicographic order, and its inverse suffix array gives the lexicographic rank of the suffix starting at each position. Since the introduction of the FM-index and the compressed suffix array in 2000, both queries have been supported in $O((\log_σn)^ε)$ time using $O(n\logσ)$ bits, for any constant $ε>0$. Yet no nontrivial time-space lower bound for suffix-array queries in compact space was known. We give the first such lower bound: in the cell-probe model with $Θ(\log n)$-bit words, every deterministic $S$-bit data structure with $S\ge n$ answering suffix-array queries on binary strings of length at most $n$ has worst-case query time $Ω(\log\log n/\log((S/n)\log\log n))$. Hence, structures with $O(n(\log\log n)^{O(1)})$ bits need $Ω(\log\log n/\log\log\log n)$ query time, while constant query time requires $Ω(n\log^εn)$ bits for some constant $ε>0$, matching known upper bounds. In particular, no such $O(n)$-bit structure supports constant-time queries, answering the 25-year-old question of Grossi and Vitter. We also give exact complexity-preserving equivalences between suffix-array access and simpler prefix queries on short strings. For every $2\leqσ\leq n$, suffix-array queries are equivalent to prefix-select queries, and inverse-suffix-array queries are equivalent to prefix-special-rank queries. The reductions in both directions preserve all four standard measures up to constant factors: space, query time, preprocessing time, and preprocessing space. Unlike previous reductions, they incur no additive $O(\log\log n)$ query-time term. Thus, the corresponding prefix-query problems capture suffix-array and inverse-suffix-array access without asymptotic loss in any of the four measures.

0.48

Catalan Hashing: Efficient Linear Probing for Variable-Length Items

cs.DS ·2026-11-03 ·Alex Conway, Hanna Komlós, William Kuszmaul
similarity 0.63
Abstract

A defining feature of the linear-probing hash table is its spatial locality: at load factor $1 - \varepsilon$, the hash table can be implemented so that each operation scans a single contiguous region of expected size $O(1/\varepsilon)$ (this is known as the \emph{scan cost}). This guarantee, however, relies on all items having unit size. In this paper, we ask whether it is possible to achieve a similar guarantee, but in a hash table that stores items of arbitrary lengths $|x| \ge 1$. The main result of the paper is a new hash table called \emph{Catalan hashing}, which supports amortized expected scan cost $O(|x|/\varepsilon)$ for positive queries, $O(1/\varepsilon)$ for negative queries, and $O(|x|\varepsilon^{-1}\log^{1+δ}|x|)$ for insertions/deletions, for any constant $δ> 0$. As a corollary, we obtain the same bounds in the cache-oblivious model, with a scan cost of $S$ translating to $1 + O(S/B)$ I/Os. Along the way, we introduce several high-level techniques that may be of independent interest; this includes a novel way of using erasure codes in order to perform write optimization within a hash table, and a connection to scheduling that allows us to place elements in a way which avoids clustering at high load factors.

0.21

Query-Dependent Reading for Quantized Inner-Product Estimation: A Minimax Separation

cs.IT cs.DScs.LG ·2026-10-17 ·Krishnakumar Balasubramanian, Siddharth Bhandari, Shiva Prasad Kasiviswanathan
theory similarity 0.63
Abstract · 66 pages

We study quantization for inner-product estimation when storage and reading have separate budgets. In the static bit-probe model [Yao, 1981], an encoder stores $w$ bits about $x$ before seeing a query $y$, and a reader probes at most $r<w$ bits to estimate $x^\top y$. Both vectors lie in the $d$-dimensional Euclidean unit ball. Protocols may be randomized, and computation is unrestricted. Performance is measured by $d$ times the worst-case mean-squared error over $x,y$, averaged over protocol randomness. First, we show that query-independent reading cannot benefit from extra storage. Any such reader is equivalent to fully reading an $r$-bit message, even when later reads depend on previously returned bits. At fixed positive rates $W=w/d$ and $R=r/d$, the normalized minimax error converges to $1/(4^R-1)$, independent of $W$. The upper bound was already known [Ordentlich and Polyanskiy, 2025]. We prove the matching lower bound for arbitrary scalar decoders, extending the result for unbiased compressors [Safaryan et al., 2020]. Then, we show that query-dependent reading makes extra storage useful. We construct a two-batch protocol using Gaussian projections and random thresholds, with asymptotic normalized error at most $(π+o(1))/[4R\log(W/R)]$ as $W/R\to\infty$. At fixed $R$, this error vanishes as storage grows, giving an unbounded advantage over query-independent reading. We also prove a finite-dimensional lower bound for arbitrary encoders, decoders, and fully branching readers. In the doubly sparse regime $W/R\to\infty$ and $R\log(W/R)\to0$, it gives normalized error at least $(1-o(1))/[2R\log(W/R)]$. Thus, our protocol is optimal within a factor of $π/2$ in the leading constant.

0.19

Optimal compression with quantum retrieval

cs.DS quant-phcs.IRcs.IT ·2026-10-05 ·Shyam Dhamapurkar, Mohit Garg, Manaswi Paraashar, Jaikumar Radhakrishnan
similarity 0.63
Abstract · 13 pages, 3 figures

We consider the following data compression problem. Given a string $x \in \{0,1\}^m$ of Hamming weight at most $n$, compress it into a shorter string $y \in \{0,1\}^s$ so that any bit $x_i$ of $x$ can be retrieved without any error using at most $t$ quantum queries to the standard oracle encoding of $y$. If queries are allowed to be adaptive we show how optimal compression up to a logarithmic factor can be achieved. If the queries are required to be made non-adaptively, we show schemes whose space is optimal in its dependence on $m$ except for a logarithmic factor, and is at most quadratically worse when compared to the optimum in its dependence on $n$.

0.12

Achieving Optimal Redundancy for Small Dynamic Rank/Select Dictionaries

cs.DS ·2026-10-01 ·Gabriel Marques Domingues
theory similarity 0.63
Abstract · 20 pages; 2 figures

In this paper, we study the number of bits required to construct a dynamic dictionary with optimal time for $\texttt{rank}/\texttt{select}$ operations. Using the standard (multiplication) Word-RAM model with $w$-bit words, we construct a data-structure for a dynamic $\texttt{rank}/\texttt{select}$ dictionary for a set $S\subseteq\{0,1,\cdots,u-1\}$ of $n$ elements that, given a parameter $1\leq k\leq \log^*w$, uses $$\operatorname{lg}\binom{u}{n}+\mathcal{O}(n\log^{(k)}w)\text{ bits}$$ taking optimal $\mathcal{O}(k+\log_w n)$ time (worst-case) for all operations. We show optimality for $n=w^{\mathcal{O}(1)}$ and $\log u=Θ(w)$ by extending the lower bound of Li, Liang, Yu, and Zhou [FOCS 2023] to super-polynomial universes: any dynamic dictionary for $n\leq \sqrt{u}$ elements that uses $\operatorname{lg}\binom{u}{n}+\mathcal{O}(n\log^{(k)}n)$ bits requires $Ω(k)$ time for operations. Lastly, we extend the data-structure to a dynamic fully indexable dictionary (that also supports $\texttt{rank}/\texttt{select}$ on the complement of $S$).

0.26