arXiv preprint ·
Almost Optimal Relative Error Streaming Quantiles with Full Mergeability
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Quantile summaries provide a scalable way to estimate the distribution of individual attributes in large datasets that are often distributed across multiple machines or generated by sensor networks. The state-of-the-art summaries with \emph{relative error guarantees} of $\pm \varepsilon\cdot \mathrm{rank}$, offering increasingly higher accuracy towards the distribution's tails, are ReqSketch (Cormode et al., JACM 2023) and the recent streaming algorithm by Gribelyuk et al. (SODA 2025). For inputs of size $N$ and probability $δ$ of exceeding the error bound, ReqSketch achieves space of $O(\varepsilon^{-1}\cdot \log^{1.5}(\varepsilon N)\cdot \sqrt{\log δ^{-1}})$ memory words, and offers \emph{full mergeability}, allowing distributed or parallel processing of datasets. In contrast, the latter algorithm exceeds the lower bound of $Ω(\varepsilon^{-1}\cdot \log(\varepsilon N)\cdot \log\logδ^{-1})$ from (Cormode \& Veselý, PODS 2020) only by a factor of $O(\log\varepsilon^{-1}\cdot (\log \varepsilon^{-1} + \log\log N)\cdot\log^2\logδ^{-1})$, but it lacks the mergeability property, is substantially more involved than ReqSketch, and has unclear practical performance. Both of these data structures consist of relative compactors from ReqSketch that subsample the stream in a structured way and work well in the streaming setting but are difficult to analyze under mergeability. We design a new relative-error quantile summary that achieves full mergeability and also improves the state-of-the-art streaming space bound to $$O(\varepsilon^{-1}\cdot \log(\varepsilon N) \cdot\log \log δ^{-1} \cdot (\log \varepsilon^{-1} + \log \log(\varepsilon N) + \log \log δ^{-1})),$$ which is substantially closer to the lower bound. At the same time, our data structure is simpler than the algorithm from (Gribelyuk et al., SODA 2025) and therefore more suitable for implementation.
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
Improved Combinatorial Auctions with and without Samples
Learning-Augmented Streaming Algorithms for Approximating Boolean Max-CSPs
Certifying Capacity and Gaps of the Rank-Dependent Gain-Sharing Framework for Ranking
Approximation Algorithms for Emergency Vertex Cover with Few Stations and Fault-Tolerant Coverage
Query Complexity of Densest Sub(hyper)graph Problems
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.