Relative Error Streaming Quantiles with Seamless Mergeability via Adaptive Compactors
Tomáš Domes and Pavel Veselý · 2025
Read Relative Error Streaming Quantiles with Seamless Mergeability via Adaptive Compactors by Tomáš Domes and Pavel Veselý (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-17396.txt.
Introduction
Tomáš Domes and Pavel Veselý refine ReqSketch, a data structure that summarizes huge data streams well enough to answer quantile questions with relative error guarantees. Such sketches matter when data is spread across machines or sensor networks, because summaries from different sources must merge cleanly. ReqSketch, already adopted in the Apache DataSketches library, is the most space-efficient design with both relative error control and mergeability, but its mergeability proof was notoriously intricate.
The authors introduce adaptive compactors, a refinement that yields a far simpler proof of the error guarantees in the most general merging setting. The refinement keeps the same space bound, update time, and simple algorithm. In specific scenarios, such as merging sketches of comparable size, the new analysis even gives near-optimal space bounds. The paper strengthens a tool practitioners already rely on.
Catalog record
| CREATOR | Tomáš Domes and Pavel Veselý |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 78 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-17396
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Relative Error Streaming Quantiles with Seamless Mergeability via Adaptive Compactors Thanks: Supported by the ERC CZ project LL2406 of the Czech Ministry of Education, Youth and Sports, by the grant SVV–2025–260822 and by Center for Foundations of Modern Computer Science (Charles Univ. project UNCE 24/SCI/008). Tomáš Domes and Pavel Veselý Abstract \DeclareDelimFormat [textcite]multinamedelim, \DeclareDelimFormat [textcite]finalnamedelim and 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. ReqSketch [ 2 ] is currently the most space-efficient summary with two key properties: relative error guarantees , offering increasingly higher accuracy towards the distribution’s tails, and mergeability , allowing distributed or parallel processing of datasets. Due to these features and its simple algorithm design, ReqSketch has been adopted in practice, via implementation in the Apache DataSketches library. However, the proof of mergeability in [ 2 ] is overly complicated, requiring an intricate charging argument and complex variance analysis. In this paper, we provide a refined version of ReqSketch, by developing so-called adaptive compactors . This enables a significantly simplified proof of relative error guarantees in the most general mergeability setting, while retaining the original space bound, update time, and algorithmic simplicity. Moreover, the adaptivity of our sketch, together with the proof technique, yields near-optimal space bounds in specific scenarios – particularly when merging sketches of comparable size. 1 Introduction Quantile summaries, or sketches, are data structures of sublinear size, typically just polylogarithmic in the input length, allowing to efficiently process large streaming or distributed datasets, and approximate their distribution, by estimating ranks and quantiles. Here, the rank of an item y with respect to \mathcal{S} , denoted \rank(y,\mathcal{S}) , is the number of items in \mathcal{S} that are smaller than or equal to y , and quantiles are essentially the inverse of ranks, i.e., a \varphi -quantile for \varphi\in[0,1] is the \lceil\varphi\cdot|\mathcal{S}|\rceil -th smallest input item. Quantile summaries are essential for many applications in network monitoring, e.g., tracking latencies [ 16 , 19 ] or round trip times [ 3 ] , or in sensor networks [ 18 , 13 ] . Many of these applications require two main properties from the summaries that are both challenging to achieve while preserving high space efficiency: First, the quantile summary should provide an accurate distribution approximation, especially for the tails. In particular, network latencies are typically heavily long-tailed [ 16 ] , and understanding the tail requires increasingly more accurate estimates of the 95-th, 99-th, 99.5-th, etc., percentiles. The notion of relative error captures this scenario by requiring that the rank error for an item of rank R is at most \varepsilon\cdot R , for an accuracy parameter \varepsilon>0 ; equivalently, for a quantile query \varphi\in[0,1] , the summary should return an \hat{\varphi} -quantile, for \hat{\varphi}=(1\pm\varepsilon)\cdot\varphi . While this yields lower error for items of small rank, high accuracy for the other tail, as desired in monitoring latencies, can be achieved by simply flipping the comparator. A long line of work [ 11 , 3 , 4 , 21 , 20 , 2 ] studied relative-error quantile summaries, and recently Gribelyuk et al. [ 10 ] developed a randomized streaming algorithm using near-optimal space of \widetilde{O}(\varepsilon^{-1}\cdot\log\varepsilon N) 1 1 1 Notation \widetilde{O}(f) hides factors poly-logarithmic in f , and the dependency on \delta , the probability of a too large error. . Second, it is in many cases not feasible to process the dataset in one pass as it may be distributed across many machines or consist of observations aggregated by sensors [ 18 ] . To allow for distributed or parallel processing of large datasets, the sketch should come with a merge operation that takes two sketches representing datasets \mathcal{S}_{1} and \mathcal{S}_{2} and outputs one sketch representing the multiset union of \mathcal{S}_{1} and \mathcal{S}_{2} . A quintessential property of summaries is full mergeability [ 1 ] , stating that even when the sketch is built by any sequence of pairwise merge operations on single-item sketches obtained from a set \mathcal{S} , its error should be bounded, ideally achieving the same accuracy-space trade-off as in the streaming model. The mergeability setting is more general, since the streaming model can be seen as a repeated merge with a single-item sketch. The state-of-the-art relative-error and fully-mergeable quantile summary is ReqSketch [ 2 ] that consists of a sequence of relative compactors . These are buffers that randomly subsample the stream in a way that facilitates the relative error; see Section 1.1 . Due to its overall simplicity, mergeability, and fast update time, compared to widely-used t -digest [ 5 ] , ReqSketch has been implemented within the Apache DataSketches library [ 17 ] . While ReqSketch only achieves a suboptimal space bound of \mathcal{O}(\varepsilon^{-1}\cdot\log^{1.5}\varepsilon N) [ 2 ] , the recent improvement in [ 10 ] does not come with any mergeability guarantees (or even a merge operation) and moreover, the new algorithm from [ 10 ] is also arguably much more involved than ReqSketch. Indeed, to the best of our knowledge, there is no implementation, and it seems likely that ReqSketch would still perform better than the algorithm of [ 10 ] for data streams in practice. Overall, it is still open how to achieve full mergeability for relative-error sketches in space close to the lower bound of \Omega(\varepsilon^{-1}\cdot\log\varepsilon N) memory words that holds for any sketch, even if computed offline [ 2 ] . The key obstacle to progress appears to be proving mergeability for relative-error sketches. Indeed, despite the simplicity of the ReqSketch algorithm and its relatively accessible analysis in the streaming setting, the proof of full mergeability in [ 2 ] involves an intricate charging argument and even more complex bounds on the variance across relative compactors. The especially tricky part is that the internal parameters of the sketch change as the sketch summarizes a larger and larger input. This makes it difficult to either improve the space bound for fully-mergeable sketches or generalize the proof for other error guarantees. Here, we develop adaptive compactors that, when used instead of relative compactors in ReqSketch, allow for a significantly simplified proof of full mergeability while preserving its other properties like space requirements, update time, and relative-error guarantees. The new compactors naturally capture the charging required to bound the error, and in effect make the analysis of the error in the full mergeability setting as accessible as in the streaming model. Furthermore, the adaptivity of the compactors allows for getting better space bounds in special cases, obtained as a simple corollary of our analysis. We demonstrate it by showing that for a reverse-sorted input stream, the required space is optimal with respect to both \varepsilon and N . Nevertheless, the adaptivity makes bounding the space used by the compactors less straightforward compared to ReqSketch; we present an analysis of space requirements using a suitable potential function, yielding the same bound of \mathcal{O}(\varepsilon^{-1}\cdot\log^{1.5}\varepsilon N) as in [ 2 ] . Finally, we confirm the intuition that certain “nice” cases of the mergeability setting admit better space bounds than streaming. Specifically, we prove that our sketch created using merge operations organized in an approximately balanced merge tree (i.e., always