arXiv preprint ·
Target-Stratified Fair Range Summaries: Improved Fair $\varepsilon$-Nets and Geometric Hitting Sets
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Compact summaries are a key tool for approximate query processing over large datasets. For range-query workloads, an $\varepsilon$-net provides a small summary that hits every sufficiently large range. However, classical $\varepsilon$-nets only guarantee range validity and do not control the group composition of the selected tuples. As a result, the summary may be range-valid but poorly representative, which can propagate imbalance to downstream query results. Motivated by recent work on fair $\varepsilon$-nets and fair geometric hitting sets \cite{dehghankar2025fair}, we study fairness-aware range summaries under prescribed target group ratios. Different from previous sample-and-repair approach, we propose a target-stratified sampling method. For demographic parity (in which the ratio of fairness is determined by group proportion), our sample size is $O(A_{\varepsilon})$, coinciding with the standard $\varepsilon$-net bound, improving previous bound of $O\!\left(A_\varepsilon\log\frac{k}{\varphi}\right)$. For custom-ratio targets (in which the ratio of fairness is determined by manually defined proportion), our sample size is $O(A_Γ)$, where $Γ$ is a parameter measuring the gap between the customized ratio and the demographic parity; we prove that this dependence on $Γ$ is unavoidable, with a worst-case lower bound of $Ω(Γ/\varepsilon)$. Using our target-stratified sampling method, we could improve the previous approximation ratio for the fair geometric hitting set problem by a logarithmic factor, and making use of this result, we could in turn improve the size of custom-ratio fair $\varepsilon$-net. Experiments on real and synthetic datasets demonstrate that our method constructs smaller fair summaries than existing approaches, scales to large datasets and fine-grained group constraints, and improves downstream range query processing.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Spectral Gap of Down-Up Walks via Trickle-Down: A Simplified and Sharpened Analysis
Local Representatives and Shortest Completions for Next-to-Shortest Paths in Directed Graphs
Improved Algorithms for Beck--Fiala with Bounded Sets
Counting and Covering in Nearest-Neighbour Representations of Boolean Functions
Integrality gap preserving reductions
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.