pith. sign in

arxiv: 1907.00236 · v1 · pith:QTWM5JW7new · submitted 2019-06-29 · 💻 cs.DS · cs.DB· cs.LG

Streaming Quantiles Algorithms with Small Space and Update Time

Nikita Ivkin , Edo Liberty , Kevin Lang , Zohar Karnin , Vladimir Braverman This is my paper

Pith reviewed 2026-05-25 12:44 UTC · model grok-4.3

classification 💻 cs.DS cs.DBcs.LG
keywords streaming quantilessketch algorithmsdata streamsapproximation algorithmsKLL algorithmupdate timeerror boundsweighted streams
0
0 comments X

The pith

Practical changes to the KLL quantile sketch halve its error bound for any fixed size and drop worst-case update time to logarithmic.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops practical variants of the asymptotically optimal KLL algorithm for estimating quantiles over data streams. These variants cut the proven error upper bound in half while using the same sketch size. They also replace the linear dependence on one over epsilon in update time with a logarithmic dependence. Separate constructions handle weighted streams with better asymptotic costs than direct adaptations, and a custom data structure trims both memory and per-item work. The net result is more accurate and faster quantile approximation under tight space limits.

Core claim

Constant-factor and data-structure modifications to the KLL algorithm reduce the upper bound on sketch error by a factor of two for any given sketch size while preserving the original probabilistic invariants. The same modifications lower worst-case update time from O(1/ε) to O(log(1/ε)). Two new algorithms for weighted streams achieve improved asymptotic update times relative to naive extensions, and a specialized data structure further reduces both memory footprint and update time.

What carries the argument

The modified KLL sketch obtained by constant-factor improvements and data-structure changes that keep the base probabilistic invariants intact.

Load-bearing premise

The original KLL probabilistic invariants survive the constant-factor and data-structure modifications without new failure modes.

What would settle it

A stream and epsilon value where the modified sketch's observed error exceeds half the error of the unmodified KLL sketch of equal size.

Figures

Figures reproduced from arXiv: 1907.00236 by Edo Liberty, Kevin Lang, Nikita Ivkin, Vladimir Braverman, Zohar Karnin.

Figure 1
Figure 1. Figure 1: One pair compression for (a,b) introduces ±1 rank error to inner queries and no error to outer queries. Felber and Ostrovsky [8] suggested non-trivial techniques of feed￾ing sampled items into sketches from [9] and improved the space complexity to O( 1 ε log 1 ε ). Recently Karnin et al. in [13] presented an asymptotically optimal but non-mergeable data structure with space usage of O( 1 ε log log 1 ε ) an… view at source ↗
Figure 3
Figure 3. Figure 3: Portion of unsaturated memory when compacting [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Compactor saturation: vanilla KLL vs. lazy KLL [PITH_FULL_IMAGE:figures/full_fig_p003_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Error analysis for a single query during a com [PITH_FULL_IMAGE:figures/full_fig_p004_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The inner state of a sweep-compactor during a sin [PITH_FULL_IMAGE:figures/full_fig_p005_6.png] view at source ↗
Figure 8
Figure 8. Figure 8: Compressing pair in the weighted compactor [PITH_FULL_IMAGE:figures/full_fig_p006_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Figures 9b, 9a, 9d, and 9e depict the trade-off between maximum error over all queried quantiles and the sketch [PITH_FULL_IMAGE:figures/full_fig_p008_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: This diagram for Section 6 illustrates the packed [PITH_FULL_IMAGE:figures/full_fig_p009_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Average update time per item in nanoseconds for [PITH_FULL_IMAGE:figures/full_fig_p013_11.png] view at source ↗
read the original abstract

Approximating quantiles and distributions over streaming data has been studied for roughly two decades now. Recently, Karnin, Lang, and Liberty proposed the first asymptotically optimal algorithm for doing so. This manuscript complements their theoretical result by providing a practical variants of their algorithm with improved constants. For a given sketch size, our techniques provably reduce the upper bound on the sketch error by a factor of two. These improvements are verified experimentally. Our modified quantile sketch improves the latency as well by reducing the worst case update time from $O(1/\varepsilon)$ down to $O(\log (1/\varepsilon))$. We also suggest two algorithms for weighted item streams which offer improved asymptotic update times compared to na\"ive extensions. Finally, we provide a specialized data structure for these sketches which reduces both their memory footprints and update times.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 0 minor

Summary. The manuscript presents practical variants of the KLL streaming quantile sketch that claim to provably halve the error bound for fixed sketch size, reduce worst-case update time from O(1/ε) to O(log(1/ε)), supply two weighted-stream algorithms with improved asymptotics, and introduce a specialized data structure that further cuts memory and update cost. The improvements are stated to be experimentally verified.

Significance. If the claimed factor-of-two error reduction and the preservation of KLL tail bounds under the described modifications can be rigorously established, the work would supply immediately usable constant-factor and latency improvements to an asymptotically optimal primitive, with direct impact on streaming analytics pipelines.

major comments (2)
  1. [Abstract] Abstract: the central claim that the techniques 'provably reduce the upper bound on the sketch error by a factor of two' is load-bearing, yet the manuscript supplies neither a proof sketch nor an explicit re-derivation showing that the original KLL rank-error concentration and failure-probability invariants survive the constant-factor changes, merge/compaction modifications, and auxiliary data structures. Without this extension, the factor-of-two guarantee does not follow from the cited KLL analysis.
  2. [Abstract] The description of the O(log(1/ε)) worst-case update time and the weighted-stream algorithms likewise asserts improved asymptotics without indicating how the original KLL probabilistic analysis is adapted to the new data structures; any alteration to the distribution of sampled ranks would invalidate the claimed bounds.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and for highlighting the need for explicit verification of the probabilistic invariants. We agree that the manuscript should contain a self-contained re-derivation showing that the KLL concentration and failure-probability bounds survive our modifications; this will be added in the revision.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim that the techniques 'provably reduce the upper bound on the sketch error by a factor of two' is load-bearing, yet the manuscript supplies neither a proof sketch nor an explicit re-derivation showing that the original KLL rank-error concentration and failure-probability invariants survive the constant-factor changes, merge/compaction modifications, and auxiliary data structures. Without this extension, the factor-of-two guarantee does not follow from the cited KLL analysis.

    Authors: We accept the observation. The factor-of-two improvement follows from a deterministic tightening of the compaction thresholds (halving the number of retained items per level while preserving the geometric decay of level capacities) together with a minor change to the merge rule that does not alter the marginal distribution of retained ranks. In the revised version we will insert a short proof subsection (new Section 3.2) that re-derives the original KLL tail bound under these changes, confirming that the failure probability remains at most δ and that the rank error is therefore halved for any fixed sketch size. revision: yes

  2. Referee: [Abstract] The description of the O(log(1/ε)) worst-case update time and the weighted-stream algorithms likewise asserts improved asymptotics without indicating how the original KLL probabilistic analysis is adapted to the new data structures; any alteration to the distribution of sampled ranks would invalidate the claimed bounds.

    Authors: The O(log(1/ε)) worst-case update time is obtained by replacing the linear scan of a level with a binary heap that only touches O(log(1/ε)) items per compaction; the set of items chosen for retention is identical to the original KLL rule, so the rank distribution is unchanged. For the weighted variants we employ reservoir sampling with weights folded into the selection probability; the resulting inclusion probabilities are identical to those of the unweighted KLL process after a constant-factor rescaling of the level capacities. The revised manuscript will add a paragraph in Section 4 that states these equivalences and invokes the original KLL analysis verbatim. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation extends prior KLL analysis without reducing to self-definition or fitted inputs

full rationale

The paper extends the KLL quantile sketch with constant-factor and data-structure modifications that are claimed to preserve the original probabilistic invariants while halving the error bound for fixed sketch size and improving worst-case update time to O(log(1/ε)). The abstract states the error reduction is 'provable' and 'verified experimentally,' but supplies no equations that equate a derived quantity to a fitted parameter or prior result by construction. The central claim rests on an independent extension of the KLL tail bounds rather than a self-citation chain that is itself unverified or a renaming of known patterns. No load-bearing step matches any enumerated circularity pattern.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The abstract relies on the standard streaming model and the correctness of the base KLL analysis; no new free parameters, axioms, or invented entities are introduced or fitted in the provided text.

axioms (1)
  • domain assumption Items arrive sequentially in a data stream and must be processed with sublinear memory.
    Standard assumption invoked by all streaming quantile work referenced in the abstract.

pith-pipeline@v0.9.0 · 5678 in / 1114 out tokens · 32777 ms · 2026-05-25T12:44:55.569336+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages

  1. [1]

    The CAIDA UCSD Anonymized Internet Traces, 2015-02-19

    2015. The CAIDA UCSD Anonymized Internet Traces, 2015-02-19. (2015). http: //www.caida.org/data/passive/passive_dataset.xml

    work page 2015

  2. [2]

    Page view statistics for Wikimedia projects

    2016. Page view statistics for Wikimedia projects. (2016). https://dumps. wikimedia.org/other/pagecounts-raw/

    work page 2016

  3. [3]

    Pankaj K Agarwal, Graham Cormode, Zengfeng Huang, Jeff M Phillips, Zhewei Wei, and Ke Yi. 2013. Mergeable summaries. ACM Transactions on Database Systems (TODS) 38, 4 (2013), 26

    work page 2013

  4. [4]

    Arvind Arasu and Gurmeet Singh Manku. 2004. Approximate counts and quan- tiles over sliding windows. In Proceedings of the twenty-third ACM SIGMOD- SIGACT-SIGART symposium on Principles of database systems . ACM, 286–296

    work page 2004

  5. [5]

    Tianqi Chen and Carlos Guestrin. 2016. Xgboost: A scalable tree boosting system. In Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining . ACM, 785–794

    work page 2016

  6. [6]

    Graham Cormode, Minos Garofalakis, S Muthukrishnan, and Rajeev Rastogi. 2005. Holistic aggregates in a networked world: Distributed tracking of approximate quantiles. In Proceedings of the 2005 ACM SIGMOD international conference on Management of data. ACM, 25–36

    work page 2005

  7. [7]

    David J DeWitt, Jeffrey F Naughton, and Donovan A Schneider. 1991. Parallel sorting on a shared-nothing architecture using probabilistic splitting. In Parallel and distributed information systems, 1991., proceedings of the first international conference on. IEEE, 280–291

    work page 1991

  8. [8]

    David Felber and Rafail Ostrovsky. 2015. A randomized online quantile summary in O (1/epsilon* log (1/epsilon)) words. In LIPIcs-Leibniz International Proceedings in Informatics, Vol. 40. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik

    work page 2015

  9. [9]

    Michael Greenwald and Sanjeev Khanna. 2001. Space-efficient online computa- tion of quantile summaries. In ACM SIGMOD Record, Vol. 30. ACM, 58–66

    work page 2001

  10. [10]

    Michael B Greenwald and Sanjeev Khanna. 2004. Power-conserving computation of order-statistics over sensor networks. In Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems . ACM, 275–285

    work page 2004

  11. [11]

    Michael B Greenwald and Sanjeev Khanna. 2016. Quantiles and equi-depth histograms over streams. In Data Stream Management. Springer, 45–86

    work page 2016

  12. [12]

    Zengfeng Huang, Lu Wang, Ke Yi, and Yunhao Liu. 2011. Sampling based algo- rithms for quantile computation in sensor networks. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of data . ACM, 745–756

    work page 2011

  13. [13]

    Zohar Karnin, Kevin Lang, and Edo Liberty. 2016. Optimal quantile approximation in streams. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on. IEEE, 71–78

    work page 2016

  14. [14]

    Zhenjiang Li, Mo Li, Jiliang Wang, and Zhichao Cao. 2011. Ubiquitous data collec- tion for mobile users in wireless sensor networks. In INFOCOM, 2011 Proceedings IEEE. IEEE, 2246–2254

    work page 2011

  15. [15]

    Xuemin Lin, Hongjun Lu, Jian Xu, and Jeffrey Xu Yu. 2004. Continuously main- taining quantile summaries of the most recent n elements over a data stream. In Data Engineering, 2004. Proceedings. 20th International Conference on . IEEE, 362–373

    work page 2004

  16. [16]

    Zaoxing Liu, Antonis Manousis, Gregory Vorsanger, Vyas Sekar, and Vladimir Braverman. 2016. One sketch to rule them all: Rethinking network flow monitor- ing with univmon. In Proceedings of the 2016 ACM SIGCOMM Conference . ACM, 101–114

    work page 2016

  17. [17]

    Gurmeet Singh Manku, Sridhar Rajagopalan, and Bruce G Lindsay. 1998. Ap- proximate medians and other quantiles in one pass and with limited memory. In ACM SIGMOD Record, Vol. 27. ACM, 426–435

    work page 1998

  18. [18]

    Gurmeet Singh Manku, Sridhar Rajagopalan, and Bruce G Lindsay. 1999. Random sampling techniques for space efficient online computation of order statistics of large datasets. In ACM SIGMOD Record, Vol. 28. ACM, 251–262

    work page 1999

  19. [19]

    J Ian Munro and Mike S Paterson. 1980. Selection and sorting with limited storage. Theoretical computer science 12, 3 (1980), 315–323

    work page 1980

  20. [20]

    Rob Pike, Sean Dorward, Robert Griesemer, and Sean Quinlan. 2005. Interpreting the data: Parallel analysis with Sawzall. Scientific Programming 13, 4 (2005), 277–298. Ivkin, Liberty, Lang, Karnin and Braverman

    work page 2005

  21. [21]

    Viswanath Poosala, Peter J Haas, Yannis E Ioannidis, and Eugene J Shekita. 1996. Improved histograms for selectivity estimation of range predicates. In ACM Sigmod Record, Vol. 25. ACM, 294–305

    work page 1996

  22. [22]

    Lee Rhodes, Kevin Lang, Alexander Saydakov, Edo Liberty, and Justin Thaler. 2013. DataSketches: A library of stochastic streaming algorithms. Open source software: https://datasketches.github.io/, (in process of moving to datasketches.apache.org). (2013)

    work page 2013

  23. [23]

    P Griffiths Selinger, Morton M Astrahan, Donald D Chamberlin, Raymond A Lorie, and Thomas G Price. 1979. Access path selection in a relational database management system. In Proceedings of the 1979 ACM SIGMOD international conference on Management of data . ACM, 23–34

    work page 1979

  24. [24]

    Nisheeth Shrivastava, Chiranjeeb Buragohain, Divyakant Agrawal, and Subhash Suri. 2004. Medians and beyond: new aggregation techniques for sensor networks. In Proceedings of the 2nd international conference on Embedded networked sensor systems. ACM, 239–249

    work page 2004

  25. [25]

    Lu Wang, Ge Luo, Ke Yi, and Graham Cormode. 2013. Quantiles over data streams: an experimental study. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data . ACM, 737–748

    work page 2013

  26. [26]

    Ke Yi and Qin Zhang. 2013. Optimal tracking of distributed heavy hitters and quantiles. Algorithmica 65, 1 (2013), 206–223. Streaming Quantiles Algorithms with Small Space and Update Time A FIXING THE ORIGINAL KLL PROOF The original paper by Karninet al. [13] contains a mistake regarding the number of compactions performed at a single level. Correcting th...

    work page 2013