Pith. sign in

REVIEW 3 major objections 5 minor 43 references

LMQ-Sketch: Lagom Multi-Query Sketch for High-Rate Online Analytics

T0 review · 3 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A single composite sketch can answer frequency, F1, and F2 queries concurrently with updates, keeping global query latency under 100 microseconds and update throughput above 2 billion per second.

desk verdict A genuinely useful engineering contribution to concurrent multi-query sketching, but the F2 accuracy claim is relative to a heuristic estimator, not to true F2; the paper still deserves a serious referee. read the letter →

arxiv 2506.16928 v2 pith:BJQ7LCBE submitted 2025-06-20 cs.DS

Martin Hilgendorf , Marina Papatriantafilou This is my paper · ORCID
classification cs.DS
keywords concurrentdatastructuressketchesintermediatevaluelinearizabilityfreshnesssynchronizationfrequencymomentsCount-MinSketchstreamingalgorithms
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper claims that a single, small data sketch can answer three kinds of questions—frequency of individual keys, total item count $F_1$, and second frequency moment $F_2$—while updates keep arriving at very high rate; previously, designs either used several separate sketches or could not run queries concurrently with updates. The proposed LMQ-Sketch partitions the input among threads, delegates updates into small buffers, and maintains per-partition partial results so that global queries touch only a few numbers instead of rescanning the whole sketch. A lightweight handshake between query and updater gives every query intermediate-value linearizability, meaning the returned value lies between the values a sequential query would return at the start and at the end of its execution. The authors report update throughput above 2 billion per second on 128 threads, F2 query latency below 100 microseconds, and memory use roughly an order of magnitude below the separate-sketch baseline. If these results hold, high-rate analytics systems could maintain one structure instead of several, with fresher concurrent answers.

What carries the argument

The central object is LMQ-Sketch's composite structure: the domain is split into P partitions, each owned by one thread and carrying an Augmented Sketch (an ASketch filter for heavy keys in front of a Count-Min Sketch), delegation filters that buffer updates for other partitions, an $F_1$ partial counter, and per-row $F_2$ partial sums. The load-bearing mechanism is Lagom—"just enough"—which synchronizes global queries with updates through a version-pair handshake and replaces expensive full scans with the projection $H_{\mathrm{Lagom}}(a)=(AF[a]+P\cdot AF_{\mathrm{mavg}}[a]/2)^2 - AF_{\mathrm{old}}[a]^2$. A geometric argument treats $F_2$ contributions as areas of frequency-squares: the estimator adds the square of the current filter count, subtracts the square of the old count to avoid double-counting what is already in the Count-Min Sketch, and compensates for unmerged buffered occurrences by assuming filters are on average half full. This keeps global queries to a few reads per partition while preserving the one-sided error behavior of CM+.

What would settle it

Record the true occupancy of the small update buffers at the moment a global F2 query scans a partition, replay a bursty stream in which one heavy key floods the buffers just before the query, and compare the returned $\hat{F}_2$ with the exact $F_2$ computed offline; if the estimate deviates by more than the sequential $(\epsilon,\delta)$ bounds whenever buffers are far from half full, the projection's core assumption fails.

Watch

Extended reading notes

Core claim

The paper's central claim is that point queries, $F_1$, and $F_2$ can all be served from one composite, partitioned sketch under concurrent updates, with intermediate-value linearizability (IVL) semantics and accuracy close to the sequential $(\epsilon,\delta)$ bounds. For $F_2$, the estimator LMQ-proj+ forms a CM+ estimate per partition from incrementally maintained row sums, then adds for each heavy key $a$ the compensation term $H_{\mathrm{Lagom}}(a)=(AF[a]+P\cdot AF_{\mathrm{mavg}}[a]/2)^2 - AF_{\mathrm{old}}[a]^2$, which accounts for occurrences still buffered in delegation filters without scanning them. A version-counter handshake ($V_1/V_2$ plus a being-scanned flag) stops a global query from reading a partition while a filter flush is moving data, giving an atomic per-partition snapshot without deadlock. The paper proves that this query is an IVL implementation of LMQ-proj+, that the $F_1$ query is an IVL implementation of exact $F_1$, and that the point query is an IVL implementation of the ASketch point query, along with explicit monotonicity-of-scans relations between query types.

Load-bearing premise

The F2 estimate's accuracy rests on an unproven heuristic: the small buffers that hold updates before they are merged into the sketch are assumed to be on average half full when a global query looks at them, and the compensation term uses P times the moving average of buffered counts divided by two; if real buffer occupancy is not centered at half, the estimate is biased and the paper supplies no formal bound for that bias.

Editorial extensions

If this is right

  • If the central claim holds, one small structure suffices for the three most common stream queries concurrently, replacing disjoint sketches and cutting the memory budget by about an order of magnitude on the tested skewed workloads.
  • Global F2 queries answer in under 100 microseconds even at 128 threads, so the interval of possible answer values is small and reported results stay fresh relative to the update stream.
  • Update throughput remains above 2 billion per second under concurrent query load on synthetic skewed streams, implying the consistency machinery does not become the bottleneck.
  • Every supported query is covered by a formal consistency statement—IVL for point, F1, and F2 (the last against the projected estimator), plus bounded monotonicity between query types—so users can reason about what a returned value means during concurrent runs.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: the half-full projection is the most workload-sensitive component; a testable extension is to replace the fixed $P\cdot AF_{\mathrm{mavg}}[a]/2$ compensation with per-filter occupancy measured at query time, which would remove the main heuristic while keeping the same handshake.
  • Editorial inference: the same technique—per-partition partial aggregates plus a version-pair handshake—should transfer to other expensive global aggregates, such as quantile or entropy estimates, as long as each partition can maintain an incremental contribution, potentially broadening the impact beyond the three query types tested.
  • Editorial inference: the claimed memory advantage is contingent on comparing against a baseline that keeps separate sketches per query; a baseline whose separate sketches are optimized for exactly this mixed workload could narrow the gap, so the order-of-magnitude figure is workload- and baseline-dependent.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper presents LMQ-Sketch, a partitioned, concurrent sketch data structure that supports point queries, the first frequency moment F1, and the second frequency moment F2 from a single memory footprint while updates are being processed. The high-level claims are: point queries are an IVL implementation of the ASketch point query, F1 is an IVL implementation of exact F1, and F2 is handled by a new 'Lagom' synchronization scheme that returns an IVL implementation of a quantity the authors call LMQ-proj+. The authors report F2 query latency below 100 microseconds, update throughput above 2 billion updates per second on 128 threads, and an order-of-magnitude memory reduction relative to the SW-SKT multi-sketch baseline. The paper contains formal-sounding lemmas for the concurrency semantics, a geometric explanation of the F2 compensation, and an extensive evaluation on synthetic Zipfian data and CAIDA traces.

Significance. If the central claims hold, this is a valuable contribution to concurrent data structures for streaming analytics. The paper offers a concrete design that combines partitioning, delegation filters, and a lightweight handshake to achieve IVL semantics for multiple query types, and it ships an open-source implementation that is evaluated on a 128-core machine. The strongest parts are the point-query and F1 arguments, which are plausibly rigorous, and the empirical demonstration that the Lagom synchronization overhead is small. The main significance of the contribution, however, rests on the F2 accuracy claim, and that part is currently supported only by a heuristic projection and by an IVL statement relative to that same heuristic. The experimental evaluation is careful in several dimensions, and the open-source artifact is a clear strength, but the theoretical basis for the F2 accuracy pillar is not yet established.

major comments (3)
  1. [Sec. 4.3, Eq. (5) and Observation 18] The F2 compensation is the load-bearing step of the paper, but it rests on two unproven assertions: that delegation filters are 'on average half full' at any scan, and that the EWMA AFmavg[a] tracks the number of buffered occurrences of a. Observation 18 is stated without a derivation, and its phrase 'up to r/2 ignored occurrences per heavy key' is not justified because r=PB from Observation 9 is a total-buffer bound over all keys and all delegation filters, not a per-key bound. The projection P*AFmavg[a]/2 enters the squared term in Eq. (5), so a constant-factor error in the assumed occupancy is not benign. For example, if the P delegation filters of a heavy key fill and flush in phase, the actual buffered count can be near P*AFmavg[a] at query time, not P*AFmavg[a]/2, and the squared term can be off by a factor close to four. The paper needs either a concrete error bound for the projection under stated assumptions, or an explicit and prominent statement that the F2 accuracy of LMQ-proj+ is a heuristic that is validated only empirically.
  2. [Sec. 5.3, Lemma 19 and Corollary 20] Lemma 19 only establishes that the concurrent query is an IVL implementation of LMQ-proj+, where LMQ-proj+ is defined by Eqs. (4)-(5), i.e., by the same heuristic formula whose accuracy is at issue. This does not connect the returned number to the true F2 of the stream. The manuscript needs a separate argument that LMQ-proj+ approximates F2, for example by bounding its deviation from CM+ or PartAS+ under the stated skew assumptions, or by proving an (epsilon, delta) bound for the projection. As written, Corollary 20(3) overstates what the lemmas imply: the reader is given an IVL guarantee about a reference value that is itself unproven as an estimator of F2.
  3. [Sec. 6.4 and abstract] The abstract and introduction claim that F2 query latency between 1 and 100 microseconds 'implies freshness with error below 0.01%'. This claim is not supported by the evaluation in Sec. 6.4. Figure 8 measures the return value of the concurrent query relative to reconstructed IVL interval endpoints Qstart and Qend; it does not measure error against the true F2 of the prefix observed by the query. To support the sub-0.01% claim, the paper would need to report, for concurrent executions, the distance between the returned value and the true F2 computed over the queried prefix, with a clear definition of the error metric. Without that evidence, the accuracy implication from latency should be removed or substantially weakened.
minor comments (5)
  1. [Table 1 and Algorithm 1, line 1.4] The description of AFmavg as 'Projected count of buffered occurrences' is imprecise. From Algorithm 1, AFmavg is an exponentially weighted moving average of the flush sizes observed for a key, not a direct projection of the current buffer contents. The table and surrounding text should be aligned with the actual update rule.
  2. [Fig. 8] The y-axis label 'Relative error (%)' is misleading because the plotted quantity is the distance to the IVL-permitted interval boundaries, not an error relative to the true F2. Renaming the axis to something like 'Relative deviation from IVL bounds (%)' would avoid overinterpreting the figure.
  3. [Section 2, Definition 1] The probability expression '1−δ = 1− 3 4 −H' appears to have a typesetting error; it should presumably read '1−(3/4)^H'. Please correct this so the definition is unambiguous.
  4. [Reference [3]] The reference list entry for the LMQ-Sketch software is attributed to 'Anonymous author(s)', while the title page lists the authors. For an arXiv version with author names, the reference should be updated to avoid confusion.
  5. [Section 4.4, Lemma 10] The table in Lemma 10 uses symbolic entries such as 'P -relaxed monotonic' and 'r-relaxed monotonic' without defining these terms in the main text. Since the paper introduces these notions only inline, a short definition before the lemma would improve readability.

Circularity Check

1 steps flagged · score 4.0 of 10

F2 accuracy chain contains a self-definitional step: Obs. 18's r/2 compensation restates the half-full ansatz of Eq. 5, and Lemma 19 ties F2Lagom only to the self-defined LMQ-proj+ reference.

  1. self definitional [Sec. 4.3 (Eq. 5) and Sec. 5.3 (Observation 18)]
    "there are P delegation filters for a partition, projected to contain AFmavg[a] counts of a once full and getting flushed. At any point when the query scans a partition, filters are on average half full. This yields LMQ-proj+ (Eq. 5). ... Observation 18. HLagom (Eq. 5) projection compensates for up to r/2 ignored occurrences per heavy key, bringing the query result closer to the actual F2, based on the reasoning of the geometric argument and observations 12 and 14."

    The P·AFmavg[a]/2 term in Eq. 5 is introduced by the paper's own 'filters are on average half full' assumption. Observation 18 then asserts that this projection compensates for r/2 ignored occurrences, where r=PB is the maximum number of buffered increments (Obs. 9). The r/2 figure is exactly the half-full average baked into Eq. 5, so the compensation is the ansatz restated as an 'observation' rather than a derived accuracy result. Moreover, Lemma 19 only proves that F2Lagom is an IVL implementation of LMQ-proj+, and LMQ-proj+ is defined by Eq. 4-5 with that same projection; thus the formal chain does not independently connect the query result to the true F2.

full rationale

The paper's central concurrency and multi-query claims are largely self-contained: the point-query IVL proof builds on published Delegation Sketch arguments, F1 is an exact sum of per-thread counters, and the empirical evaluation compares LMQ-proj+ against true F2 in Fig. 4, which is independent support. The self-citations to [40] and [18] are prior published results with their own arguments, so they are not load-bearing circularity here. The one genuine circular step is in the analytical derivation of F2 accuracy: Observation 18 presents the half-full projection as if it were a derived compensation, but it is the same assumption used to define HLagom in Eq. 5. Lemma 19 then certifies F2Lagom only as an implementation of the self-defined LMQ-proj+ reference, so the analytical chain does not bridge to true F2 without the independent empirical measurements. The unsupported 'latency implies error below 0.01%' statement is better classified as a correctness/evidence gap than as circularity. Overall the circularity is partial and confined to the F2 justification, not the whole derivation.

Assumptions & free parameters 3 free parameters · 6 assumptions · 1 invented entities

The central accuracy claim for F2 depends on the invented AFmavg projection and the half-full buffer heuristic, both internal design choices without independent falsifiable evidence. The concurrency semantics rest on standard shared-memory assumptions and on prior results from [15, 37, 40], which are reasonable but not re-proven here.

free parameters (3)
  • w (EWMA weight in AFmavg) = 0.8
    Alg. 1 line 1.4 sets AFmavg[a] = w*v + (1-w)*AFmavg[a] with w=0.8, described as 'bias towards recent changes in skew'. It is hand-chosen and directly shapes the F2 projection HLagom (Eq. 5), so the accuracy of the compensation depends on it.
  • B (delegation filter buffer cap) = 1000
    Alg. 2 line 2.3/2.7/2.11 bounds buffered updates; B=1000 is used in the evaluation and determines the r=PB relaxation in Lemma 16 and Observation 9. It is a tunable knob, not derived.
  • C (ASketch and delegation filter size) = 16
    Filter capacity is set to 16 following [40], as stated in Sec. 6. It affects the scan cost of point queries and the number of heavy keys tracked.
assumptions (6)
  • domain assumption CM+ provides an F2 estimate with relative error 1+epsilon with probability 1-delta (Def. 1, cited from [15]).
    Used in Sec. 5 to argue per-partition F2 estimation inherits CMS error bounds.
  • domain assumption Delegation Sketch point query correctness (Claims 2 and 3 of [40]) holds.
    Lemma 5 relies on [40, Claim 2,3] that PQ observes all completed updates and never double-counts.
  • domain assumption IVL is a local property, from [37].
    Corollary 17 and Lemma 19 compose per-partition IVL guarantees into global IVL; this locality result is cited from [37].
  • ad hoc to paper At any F2 scan, each delegation filter is on average half full, so P times AFmavg divided by 2 approximates the number of buffered occurrences of a heavy key.
    Eq. 5 replaces the exact sum of delegation filter counts with P*AFmavg[a]/2, justified by 'filters are on average half full' (Sec. 4.3). No bound on the error of this approximation is proven; it is load-bearing for the claimed F2 accuracy.
  • domain assumption The system model: shared-memory with atomic fetch-and-add and CAS, coherent memory, no crash failures.
    Standard for the concurrency semantics, stated in Sec. 3.
  • ad hoc to paper The EWMA AFmavg[a] tracks the projected full-filter count of buffered occurrences of a.
    Alg. 1 line 1.4 updates AFmavg at flush time; the claim that it represents the count when a delegation filter is full is heuristic, used in Eq. 5.
invented entities (1)
  • AFmavg (per-key exponentially weighted moving average in the ASketch filter)
    purpose: Project the number of buffered occurrences of a heavy key in delegation filters so F2 queries need not scan them (Eq. 5).
    Internal state variable introduced in Alg. 1 with a hand-chosen weight w=0.8; no external empirical handle outside the paper's own evaluation.

how reviews work

0 comments
Cite this review

Pith. "Pith review of LMQ-Sketch: Lagom Multi-Query Sketch for High-Rate Online Analytics." pith.science (2026). https://pith.science/paper/BJQ7LCBE

@misc{pith2026250616928,
  author       = {Pith},
  title        = {Pith review of: LMQ-Sketch: Lagom Multi-Query Sketch for High-Rate Online Analytics},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BJQ7LCBE}},
  note         = {Machine review of arXiv:2506.16928}
}
read the original abstract

Data sketches balance resource efficiency with controllable approximations for extracting features in high-volume, high-rate data. Two important points of interest are highlighted separately in recent works; namely, to (1) answer multiple types of queries from one pass, and (2) query concurrently with updates. Several fundamental challenges arise when integrating these directions, which we tackle in this work. We investigate the trade-offs to be balanced and synthesize key ideas into LMQ-Sketch, a single, composite data sketch supporting multiple queries (frequency point queries, frequency moments F1, and F2) concurrently with updates. Our method 'Lagom' is a cornerstone of LMQ-Sketch for low-latency global querying (<100 us), combining freshness, timeliness, and accuracy with a low memory footprint and high throughput (>2B updates/s). We analyze and evaluate the accuracy of Lagom, which builds on a simple geometric argument and efficiently combines work distribution with synchronization for proper concurrency semantics -- monotonicity of operations and intermediate value linearizability. Comparing with state-of-the-art methods (which, as mentioned, only cover either mixed queries or concurrency), LMQ-Sketch shows highly competitive throughput, with additional accuracy guarantees and concurrency semantics, while also reducing the required memory budget by an order of magnitude. We expect the methodology to have broader impact on concurrent multi-query sketches.

Figures

Figures reproduced from arXiv: 2506.16928 by the authors.

Figure 1
Figure 1. This is done within the enhanced CMS update in Alg. 1, with incremental (associative) [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

43 extracted references · 25 canonical work pages

  1. [1]

    Gibbons, Yossi Matias, and Mario Szegedy

    Noga Alon, Phillip B. Gibbons, Yossi Matias, and Mario Szegedy. Tracking join and self-join sizes in limited storage. In Proceedings of the Eighteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems , PODS '99, pages 10--20, New York, NY, USA, May 1999. Association for Computing Machinery. https://doi.org/10.1145/303976.303978 doi:10....

    work page arXiv 1999

  2. [2]

    The Space Complexity of Approximating the Frequency Moments

    Noga Alon, Yossi Matias, and Mario Szegedy. The Space Complexity of Approximating the Frequency Moments . Journal of Computer and System Sciences , 58(1):137--147, February 1999. https://doi.org/10.1006/jcss.1997.1545 doi:10.1006/jcss.1997.1545

    arXiv 1999

  3. [3]

    LMQ-Sketch

    Anonymous author(s) . LMQ-Sketch . URL: https://gitlab.com/disc2025-380/lmq-sketch

    work page

  4. [4]

    URL: https://datasketches.apache.org/

    DataSketches Apache DataSketches . URL: https://datasketches.apache.org/

    work page

  5. [5]

    URL: https://druid.apache.org/

    Apache Druid Apache Druid . URL: https://druid.apache.org/

    work page

  6. [6]

    Zero-one frequency laws

    Vladimir Braverman and Rafail Ostrovsky. Zero-one frequency laws. In Proceedings of the Forty-Second ACM Symposium on Theory of Computing , STOC '10, pages 281--290, New York, NY, USA, June 2010. Association for Computing Machinery. https://doi.org/10.1145/1806689.1806729 doi:10.1145/1806689.1806729

    arXiv 2010

  7. [7]

    Quantiles on Streams

    Chiranjeeb Buragohain and Subhash Suri. Quantiles on Streams . In Encyclopedia of Database Systems , pages 2235--2240. Springer US, Boston, MA, 2009. https://doi.org/10.1007/978-0-387-39940-9_290 doi:10.1007/978-0-387-39940-9_290

    work page doi:10.1007/978-0-387-39940-9_290 2009

  8. [8]

    URL: https://www.caida.org/catalog/datasets/passive_dataset

    The CAIDA UCSD Anonymized Internet Traces - 2018. URL: https://www.caida.org/catalog/datasets/passive_dataset

    work page 2018

Show all 43 references
  1. [9]

    The origins of the Gini index: Extracts from Variabilit \`a e Mutabilit \`a (1912) by Corrado Gini

    Lidia Ceriani and Paolo Verme. The origins of the Gini index: Extracts from Variabilit \`a e Mutabilit \`a (1912) by Corrado Gini . The Journal of Economic Inequality , 10(3):421--443, September 2012. https://doi.org/10.1007/s10888-011-9188-x doi:10.1007/s10888-011-9188-x

    1912 doi

  2. [10]

    Finding Frequent Items in Data Streams

    Moses Charikar, Kevin Chen, and Martin Farach-Colton . Finding Frequent Items in Data Streams . In Automata, Languages and Programming , Lecture Notes in Computer Science , pages 693--703, Berlin, Heidelberg, 2002. Springer. https://doi.org/10.1007/3-540-45465-9_59 doi:10.1007...

    2002 doi

  3. [11]

    Preu er, and Gustavo Alonso

    Monica Chiosa, Thomas B. Preu er, and Gustavo Alonso. SKT : A one-pass multi-sketch data analytics accelerator. Proceedings of the VLDB Endowment , 14(11):2369--2382, July 2021. https://doi.org/10.14778/3476249.3476287 doi:10.14778/3476249.3476287

    2021

  4. [12]

    Sketching streams through the net: Distributed approximate query tracking

    Graham Cormode and Minos Garofalakis. Sketching streams through the net: Distributed approximate query tracking. In Proceedings of the 31st International Conference on Very Large Data Bases , VLDB '05, pages 13--24, Trondheim, Norway, August 2005. VLDB Endowment

    2005

  5. [13]

    Fast Approximate Wavelet Tracking on Streams

    Graham Cormode, Minos Garofalakis, and Dimitris Sacharidis. Fast Approximate Wavelet Tracking on Streams . In Advances in Database Technology - EDBT 2006 , pages 4--22, Berlin, Heidelberg, 2006. Springer. https://doi.org/10.1007/11687238_4 doi:10.1007/11687238_4

    2006 doi

  6. [14]

    Muthukrishnan

    Graham Cormode and S. Muthukrishnan. An improved data stream summary: The count-min sketch and its applications. Journal of Algorithms , 55(1):58--75, April 2005. https://doi.org/10.1016/j.jalgor.2003.12.001 doi:10.1016/j.jalgor.2003.12.001

    2005 doi

  7. [15]

    Muthukrishnan

    Graham Cormode and S. Muthukrishnan. Summarizing and Mining Skewed Data Streams . In Proceedings of the 2005 SIAM International Conference on Data Mining , pages 44--55. Society for Industrial and Applied Mathematics , April 2005. https://doi.org/10.1137/1.9781611972757.5 doi:...

    2005 doi

  8. [16]

    Small Summaries for Big Data

    Graham Cormode and Ke Yi. Small Summaries for Big Data . Cambridge University Press, Cambridge, 2020. https://doi.org/10.1017/9781108769938 doi:10.1017/9781108769938

    2020 doi

  9. [17]

    Sketch- Based Multi-Query Processing over Data Streams

    Alin Dobra, Minos Garofalakis, Johannes Gehrke, and Rajeev Rastogi. Sketch- Based Multi-Query Processing over Data Streams . In Data Stream Management : Processing High-Speed Data Streams , Data- Centric Systems and Applications , pages 241--261. Springer, Berlin, Heidelberg, ...

    2016 doi

  10. [18]

    Time- Lapse Snapshots

    Cynthia Dwork, Maurice Herlihy, Serge Plotkin, and Orli Waarts. Time- Lapse Snapshots . SIAM Journal on Computing , 28(5):1848--1874, January 1999. https://doi.org/10.1137/S0097539793243685 doi:10.1137/S0097539793243685

    1999 doi

  11. [19]

    Quancurrent: A Concurrent Quantiles Sketch

    Shaked Elias Zada, Arik Rinberg, and Idit Keidar. Quancurrent: A Concurrent Quantiles Sketch . In Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures , SPAA '23, pages 15--25, New York, NY, USA, June 2023. Association for Computing Machinery. h...

    2023

  12. [20]

    Discrete Wavelet Transform and Wavelet Synopses

    Minos Garofalakis. Discrete Wavelet Transform and Wavelet Synopses . In Encyclopedia of Database Systems , pages 857--863. Springer US, Boston, MA, 2009. https://doi.org/10.1007/978-0-387-39940-9_539 doi:10.1007/978-0-387-39940-9_539

    2009 doi

  13. [21]

    Gilbert, Y

    A.C. Gilbert, Y. Kotidis, S. Muthukrishnan, and M.J. Strauss. One-pass wavelet decompositions of data streams. IEEE Transactions on Knowledge and Data Engineering , 15(3):541--554, May 2003. https://doi.org/10.1109/TKDE.2003.1198389 doi:10.1109/TKDE.2003.1198389

    2003 arXiv

  14. [22]

    Gilbert, Yannis Kotidis, S

    Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, and Martin J. Strauss. How to summarize the universe: Dynamic maintenance of quantiles. In Proceedings of the 28th International Conference on Very Large Data Bases , VLDB '02, pages 454--465, Hong Kong, China, August 2002. VL...

    2002

  15. [23]

    Variabilit \`a e Mutabilit \`a

    Corrado Gini. Variabilit \`a e Mutabilit \`a . Reprinted in Memorie Di Metodologia Statistica ( Ed . E . Pizetti and T . Salvemini .) 1955. Libreria Eredi Virgilio Veschi, Rome, 1912

    1955

  16. [24]

    Count- Min Sketch : The Art and Science of Estimating Stuff , March 2022

    Itamar Haber. Count- Min Sketch : The Art and Science of Estimating Stuff , March 2022. URL: https://redis.io/blog/count-min-sketch-the-art-and-science-of-estimating-stuff/

    2022

  17. [25]

    Henzinger, Christoph M

    Thomas A. Henzinger, Christoph M. Kirsch, Hannes Payer, Ali Sezgin, and Ana Sokolova. Quantitative relaxation of concurrent data structures. In Proceedings of the 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages , POPL '13, pages 317--328, New Yo...

    2013

  18. [26]

    The Art of Multiprocessor Programming

    Maurice Herlihy, Nir Shavit, Victor Luchangco, and Michael Spear. The Art of Multiprocessor Programming . Elsevier, Morgan Kaufmann Publishers, Cambridge, MA, United States, second edition, 2021

    2021

  19. [27]

    T-digest: A New Probabilistic Data Structure in Redis Stack , March 2023

    Lior Kogan. T-digest: A New Probabilistic Data Structure in Redis Stack , March 2023. URL: https://redis.io/blog/t-digest-in-redis-stack/

    2023

  20. [28]

    Sketch-based change detection: Methods, evaluation, and applications

    Balachander Krishnamurthy, Subhabrata Sen, Yin Zhang, and Yan Chen. Sketch-based change detection: Methods, evaluation, and applications. In Proceedings of the 3rd ACM SIGCOMM Conference on Internet Measurement , IMC '03, pages 234--247, New York, NY, USA, October 2003. Associ...

    2003

  21. [29]

    Concurrent reading and writing

    Leslie Lamport. Concurrent reading and writing. Communications of the ACM , 20(11):806--811, November 1977. https://doi.org/10.1145/359863.359878 doi:10.1145/359863.359878

    1977

  22. [30]

    One Sketch to Rule Them All : Rethinking Network Flow Monitoring with UnivMon

    Zaoxing Liu, Antonis Manousis, Gregory Vorsanger, Vyas Sekar, and Vladimir Braverman. One Sketch to Rule Them All : Rethinking Network Flow Monitoring with UnivMon . In Proceedings of the 2016 ACM SIGCOMM Conference , pages 101--114, Florianopolis Brazil, August 2016. ACM. htt...

    2016

  23. [31]

    Enabling efficient and general subpopulation analytics in multidimensional data streams

    Antonis Manousis, Zhuo Cheng, Ran Ben Basat, Zaoxing Liu, and Vyas Sekar. Enabling efficient and general subpopulation analytics in multidimensional data streams. Proceedings of the VLDB Endowment , 15(11):3249--3262, July 2022. https://doi.org/10.14778/3551793.3551867 doi:10....

    2022

  24. [32]

    Gon c alo Matos, Salvatore Signorello, and Fernando M. V. Ramos. Generic change detection (almost entirely) in the dataplane. In Proceedings of the Symposium on Architectures for Networking and Communications Systems , ANCS '21, pages 113--120, New York, NY, USA, January 2022....

    2022

  25. [33]

    A Consistency Framework for Iteration Operations in Concurrent Data Structures

    Yiannis Nikolakopoulos, Anders Gidenstam, Marina Papatriantafilou, and Philippas Tsigas. A Consistency Framework for Iteration Operations in Concurrent Data Structures . In 2015 IEEE International Parallel and Distributed Processing Symposium , pages 239--248, May 2015. https:...

    2015 doi

  26. [34]

    Probabilistic Data Structures in Redis , August 2022

    Savannah Norem. Probabilistic Data Structures in Redis , August 2022. URL: https://redis.io/blog/streaming-analytics-with-probabilistic-data-structures/

    2022

  27. [35]

    Lock- Free Data-Structure Iterators

    Erez Petrank and Shahar Timnat. Lock- Free Data-Structure Iterators . In Proceedings of the 27th International Symposium on Distributed Computing - Volume 8205 , DISC 2013, pages 224--238, Berlin, Heidelberg, October 2013. Springer-Verlag. https://doi.org/10.1007/978-3-642-415...

    2013 doi

  28. [36]

    Punter, Odysseas Papapetrou, and Minos Garofalakis

    Wieger R. Punter, Odysseas Papapetrou, and Minos Garofalakis. OmniSketch : Efficient Multi-Dimensional High-Velocity Stream Analytics with Arbitrary Predicates . Proc. VLDB Endow. , 17(3):319--331, November 2023. https://doi.org/10.14778/3632093.3632098 doi:10.14778/3632093.3632098

    2023

  29. [37]

    Intermediate Value Linearizability : A Quantitative Correctness Criterion

    Arik Rinberg and Idit Keidar. Intermediate Value Linearizability : A Quantitative Correctness Criterion . Journal of the ACM , 70(2):17:1--17:21, April 2023. https://doi.org/10.1145/3584699 doi:10.1145/3584699

    2023 doi

  30. [38]

    Fast Concurrent Data Sketches

    Arik Rinberg, Alexander Spiegelman, Edward Bortnikov, Eshcar Hillel, Idit Keidar, Lee Rhodes, and Hadar Serviansky. Fast Concurrent Data Sketches . ACM Transactions on Parallel Computing , 9(2):6:1--6:35, April 2022. https://doi.org/10.1145/3512758 doi:10.1145/3512758

    2022 doi

  31. [39]

    Augmented Sketch : Faster and More Accurate Stream Processing

    Pratanu Roy, Arijit Khan, and Gustavo Alonso. Augmented Sketch : Faster and More Accurate Stream Processing . In Proceedings of the 2016 International Conference on Management of Data , SIGMOD '16, pages 1449--1463, New York, NY, USA, June 2016. Association for Computing Machi...

    2016

  32. [40]

    Delegation sketch: A parallel design with support for fast and accurate concurrent operations

    Charalampos Stylianopoulos, Ivan Walulya, Magnus Almgren, Olaf Landsiedel, and Marina Papatriantafilou. Delegation sketch: A parallel design with support for fast and accurate concurrent operations. In Proceedings of the Fifteenth European Conference on Computer Systems , Euro...

    2020

  33. [41]

    Prasanna

    Da Tong and Viktor K. Prasanna. Sketch Acceleration on FPGA and its Applications in Network Anomaly Detection . IEEE Transactions on Parallel and Distributed Systems , 29(4):929--942, April 2018. https://doi.org/10.1109/TPDS.2017.2766633 doi:10.1109/TPDS.2017.2766633

    2018

  34. [42]

    Frequency Moments

    David Woodruff. Frequency Moments . In Encyclopedia of Database Systems , pages 1518--1519. Springer, New York, NY, 2018. https://doi.org/10.1007/978-1-4614-8265-9_167 doi:10.1007/978-1-4614-8265-9_167

    2018 doi

  35. [43]

    Woodruff

    David P. Woodruff. Sketching as a Tool for Numerical Linear Algebra . Foundations and Trends in Theoretical Computer Science , 10(1--2):1--157, October 2014. https://doi.org/10.1561/0400000060 doi:10.1561/0400000060

    2014 doi

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.