CS Paper Radar

Optimal-Time Independent Subset Sampling over Acyclic Joins

Xuyang Liu, Zijian Zhang, Zhen Li

cs.DB cs.DS ·submitted 2026-11-11 16:15 UTC · v1
benchmark

Abstract

Join results can greatly exceed their inputs even when applications need only a small random subset. We study sampling that includes each result independently with a prescribed probability given by the product of its input-tuple weights (PRODUCT). For fixed full acyclic joins with static weights, we achieve input-linear preprocessing and index space together with output-linear expected sampling work, eliminating logarithmic factors from previous bounds. A shared join-tree index supports weighted draws over the entire join and locates high-probability results. Direct Bernoulli trials handle high-probability results, allowing Poisson thinning to generate the remaining independent inclusion decisions with bounded overhead. Our exact sampler uses expected $O(N)$ preprocessing, $O(N)$ index space, and expected $O(1+mμ)$ time per call including output construction. Here $N$ is the input size, $m$ counts relation occurrences, and $μ$ is the expected sample size. The guarantees hold on a real random-access machine with unit-cost exact arithmetic and logarithms, continuous uniform randomness, and expected-time hashing. The time bounds are optimal, matching input reading and explicit output writing. Our floating-point prototype has lower sampling latency than the fastest applicable baseline in 17 of 18 PRODUCT settings on three queries over the STATS benchmark. Construction savings on large joins can offset indexed materialization's faster sampling over a limited number of calls. On a real-data path at $μ=100$, our sampler achieves a $20.5\times$ speedup over indexed materialization for construction plus 300 calls, measured after common data preparation and loading.

Comment
14 pages, 4 figures, 4 tables

Closest papers

Nearest neighbours by meaning across the whole index.

Fast Perfect $L_2$ Sampling

cs.DS ·2026-10-28 ·David P. Woodruff, Samson Zhou
published similarity 0.58
Abstract · PODS 2027

Perfect $L_2$ sampling is a powerful primitive for turnstile data streams, allowing algorithms to extract an index with probability proportional to its squared frequency, with applications to dynamic join size estimation, query optimization, heavy-hitters, sampling from self-joins, and real-time monitoring of evolving datasets. The setting $p=2$ is also the largest $p$ for which $L_p$ sampling can be achieved in polylogarithmic space. However, existing space-optimal perfect samplers rely on explicit polynomial duplication, requiring inefficient polynomial update times per stream arrival. Resolving a open question left by Swartworth, Woodruff, and Zhou [FOCS 2025], we present a perfect $L_2$ sampler that achieves an expected $\text{polylog}(n)$ update time while maintaining an optimal $\tilde{\mathcal{O}}(\log^3 n)$ bits of space.

0.34

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

cs.DS ·2026-08-18 ·Philip Bille, Johannes Fischer, Inge Li Gørtz, Filippo Lari
publishedtheoryhot direction similarity 0.57
Abstract · Accepted at SPIRE 2026. Full version

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.

0.39

Bipartite Matching with Few Rounds of Demand Queries

cs.DS cs.CC ·2026-10-13 ·Shravan Mehra, Sagnik Mukhopadhyay, Vihan Shah
theory similarity 0.56
Abstract · 60 pages 1 figure

We study the randomised and deterministic demand-query complexity of approximate bipartite matching with few query rounds. The demand-query model, introduced in [Blumrosen and Nisan SICOMP 2009; Nisan SODA 2021], is inspired by combinatorial auctions and welfare maximisation, where an oracle returns the first neighbouring vertex (item) of a vertex u (agent) according to a given permutation pi (preference ordering of the agent over the items). For randomised algorithms, our main result gives a trade-off between the number of rounds k, the per-round query budget q=n^{1+δ}, and the achievable approximation ratio. Let 1 <= k <= log n, and -1 <= delta <= 1/k. Every k-round randomised algorithm using O(q) demand queries per round has a worst-case expected-size approximation factor of Omega(n^{1/2k-delta/2}/k). Conversely, we give a randomised algorithm achieving approximation factor O(n^{(1-k*delta)/(k+1)}/k) in expectation. For deterministic algorithms, for k*q >= n, we show that the optimal deterministic approximation factor is ~Theta(n^2/(q*k^2)), thereby improving the previous lower bound of [Nisan SODA 2021] by a polynomial factor over a wide range of parameters. In particular, for q=Theta(n), we improve the deterministic round-complexity lower bound for constant-factor approximation from ~Omega(n^{1/3}) to ~Omega(sqrt n). Our algorithms produce matching and vertex-cover certificates; the deterministic trade-off also extends to minimum vertex cover and maximum fractional matching. We extend the randomised upper bounds to the weaker Demand-OR model [Nisan 2021]. We prove a non-adaptive simulation of uniform random-neighbour queries using known techniques, avoiding the O(log n)-round penalty of the trivial binary-search simulation. Consequently, our upper bounds yield the same k-round approximation guarantees using O(q * log^2 n) Demand-OR queries per round.

0.28

Linear-Query Deterministic Approximation for Non-monotone Submodular Maximization under a Knapsack Constraint

cs.DS ·2026-09-22 ·Zihui Liu, Zhijie Zhang
similarity 0.55
Abstract · ISAAC 2026

Submodular maximization under a knapsack constraint (SMK) is a fundamental combinatorial optimization problem with broad applications across machine learning and data mining. Motivated by large-scale applications where query efficiency is paramount, we study non-monotone SMK and focus on deterministic algorithms with linear query complexity. Prior deterministic linear-query algorithms achieve at best a $1/5-\varepsilon$ approximation, falling short of the $1/4-\varepsilon$ ratio attainable by randomized algorithms. We close this gap by presenting a deterministic $(1/4-\varepsilon)$-approximation with $O(n\log^2(1/\varepsilon)/\varepsilon^2)$ queries. Our approach partitions the analysis based on the cost of the largest optimal element $r$: when the cost of $r$ is moderate, we refine the threshold-twin-greedy framework via residual-budget enumeration to tighten the analysis; when the cost of $r$ is large, we reduce the problem to bicriteria submodular maximization. As a secondary contribution, we obtain a $(1/2-\varepsilon, O(1/\varepsilon))$-bicriteria approximation with $O(n\log(1/\varepsilon)/\varepsilon^2)$ queries, improving over the previous $O(n^2/\varepsilon)$ query bound.

0.37

Algorithms, Complexity, and Entropy of the Bernard-Letac Fair-Sampling Construction

cs.IT math.PR ·2026-08-20 ·Claude Gravel
theory similarity 0.55
Abstract · 42 pages, 1 figure

Bernard and Letac (1971) introduced a method for uniform random sampling among $m$ outcomes from an unknown biased source of independent and identically distributed symbols. The process terminates when the multinomial coefficient of the cumulative symbol counts equals zero modulo $m$. This study extends the computational and information-theoretic analysis of their construction by presenting five algorithms with formal correctness guarantees and comprehensive complexity analyses. For prime $m=p$, the Bernard-Letac framework is analyzed in greater detail. The Rényi entropies of the source yield an exact product formula for the expected number of draws. A first-order approximation consistently overestimates this value, and the entropy lower bound is never attained. As $p$, treated as a continuous parameter, approaches 1, the expected cost converges to a constant greater than 1, determined by the entire source distribution. Furthermore, for every prime modulus $p$ and every finite alphabet $I$, an explicit automaton with $p + |I| + 3$ states computes the mod-$p$ first-passage kernel of the walk from the base-$p$ digits of its arguments, reducing the fair assignment cost from quadratic to nearly linear.

0.34

The Power of Two-Choice Linear Probing

cs.DS ·2026-09-30 ·Amir Azarmehr, Michael A. Bender, William Kuszmaul, Rose Silver
top venuetheory similarity 0.55
Abstract

This paper considers the following basic question: If an (ordered) linear-probing hash table is allowed \emph{two} hash functions, instead of one, how does this change the expected insertion and query time, as a function of the load factor $1 - ε$? We prove that the \emph{greedy two-choice insertion strategy} achieves polynomially better bounds than the single choice algorithm, but that one can even do \emph{much better} by using more sophisticated non-greedy strategies. Specifically, we show that there is an insertion strategy that does not evict elements (once an element is inserted, its hash choice is fixed) and that achieves expected query time $O(\log ε^{-1})$ with expected insertion time $O(ε^{-1})$. We then further show that, if one is allowed to evict elements (i.e., to change over time which hash function a given element uses), then it is possible to achieve expected query time $O(1)$ with expected insertion time $O(ε^{-1/2})$. This final result achieves an expected query time of $O(1)$ even when the hash table is filled to $100\%$ full. Combined, the results reveal that there is a surprisingly strong ``power of two choices'' phenomenon for linear-probing hash tables, allowing for a two-choice hash table to achieve significantly better bounds than what might at first seem to be possible.

0.39

Single-or-Sample: Online Fair Allocation for Combinatorial Agents

cs.GT cs.DS ·2026-09-26 ·Shuchi Chawla, Zhiyi Huang, Pooja Kulkarni, Ruta Mehta, Parnian Shahkar
similarity 0.55
Abstract · 48 pages

We study the fair allocation of $m$ indivisible goods among $n$ heterogeneous agents arriving online, under maximin share (MMS) fairness. The key challenge lies in making allocation decisions in an adversarial setting without knowing future agents' valuations. No guarantees were known prior to our work in adversarial settings. Our main positive result is an online allocation algorithm for submodular agents that with probability at least $0.4$ guarantees a $1/24$-approximation to MMS to all agents simultaneously. Our algorithm intersperses a greedy-style adaptive sampling-without-replacement protocol with single-good reduction rounds. For XOS valuations, we adapt this single-or-sample approach to guarantee a $c$-MMS for all agents simultaneously with probability $1-O(c)$ for any parameter $c\in O(1/\log n)$. A key technical contribution of our work is in establishing Chernoff-style tail bounds on item allocation events for this adaptive sampling process despite strong positive correlations among the items, a result that may be of independent interest. The approximation versus success probability tradeoffs achieved by our algorithms are asymptotically tight. We show that even for binary additive valuations, no randomized algorithm can ensure $c$-MMS to all agents with probability exceeding $(1-c^2/5)$, for any $c\in (0,1]$. For XOS valuations, stronger lower bounds hold: no randomized algorithm can ensure $c$-MMS to all agents with probability exceeding $(1-c/3)$, for any $c\in (0,1]$. Furthermore, no algorithm can achieve $ω(1/\log \log n)$-MMS with any constant probability. All our lower bounds hold even for simple binary instances whose MMS values and MMS partitions can be computed in linear time.

0.32

Approximating #BIS in $\exp(\widetilde O(n^{1/3}))$ Time

cs.DS ·2026-11-04 ·Jingcheng Liu, Yitong Yin
similarity 0.55
Abstract

We give randomized algorithms for approximately counting and nearly uniformly sampling independent sets in arbitrary bipartite graphs (#BIS). At fixed accuracy, both algorithms run in $\exp(O(n^{1/3}\log^{4/3}n))$ time on $n$-vertex graphs. More generally, the same running-time dependence on the number of variables holds for approximate counting and sampling with efficiently evaluable positive log-supermodular weights on Boolean variables. A weighted Sinclair-Jerrum walk on the self-reduction tree reduces these tasks to coarse lower estimates of residual log-partition functions. We obtain these estimates by optimizing a concave relaxation of an exact variational principle on the tree; threshold smoothing certifies that the low-degree search suffices.

0.29