Target-Stratified Fair Range Summaries: Improved Fair $\epsilon$-Nets and Geometric Hitting Sets

Compact summaries are a key tool for approximate query processing over large datasets. For range-query workloads, an $\epsilon$-net provides a small summary that hits every sufficiently large range. However, classical $\epsilon$-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 $\epsilon$-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_{\epsilon })$, coinciding with the standard $\epsilon$-net bound, improving previous bound of $O\left(A_{\epsilon }\log \frac{k}{\phi }\right)$. For custom-ratio targets (in which the ratio of fairness is determined by manually defined proportion), our sample size is $O(A_{\Gamma })$, where $\Gamma$ is a parameter measuring the gap between the customized ratio and the demographic parity; we prove that this dependence on $\Gamma$ is unavoidable, with a worst-case lower bound of $\Omega (\Gamma /\epsilon )$. 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 $\epsilon$-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.