Pith. sign in

REVIEW 4 major objections 6 minor 25 references

2FA Sketch: Two-Factor Armor Sketch for Accurate and Efficient Heavy Hitter Detection in Data Streams

T0 review · 4 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read Stripping Elastic down to its heavy part and evicting at $\lambda=1$ cuts heavy-hitter error by 5.7–8.1 times and speeds processing by about 2.5 times.

desk verdict The abstract and title describe a different algorithm than the full text, and once you set that aside, the empirical claim is a small tweak confounded by unequal memory allocation. read the letter →

arxiv 1909.02203 v5 pith:IEMQHROB submitted 2019-09-05 cs.NI

Xilai Liu , Xinyi Zhang , Bingqing Liu , Tao Li , Tong Yang , Gaogang Xie This is my paper · ORCID
classification cs.NI
keywords heavyhitterdetectiondatastreamsElasticsketchHHstreamsummarizationevictionstrategynetworkmeasurementtop-kflows
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 argues that a general-purpose streaming sketch can be made much better at one specific task, finding heavy hitters, by tailoring the data structure to that task. The authors take the Elastic sketch, discard its light part, and change the bucket-eviction rule: replace the smallest flow as soon as a bucket's negative-vote count exceeds that flow's positive votes, and give the incoming flow a starting count of one more than the evicted flow's count. On a public Internet trace, this tailored sketch, called Elastic HH, reports 5.7 to 8.1 times smaller average absolute and relative error than the standard Elastic sketch and processes about 2.5 times more packets per second. The gain is purchased by giving up Elastic's generality: Elastic HH only answers heavy-hitter queries.

What carries the argument

The central mechanism is the eviction rule change in a fixed-size bucket of flow counters: instead of Elastic's ratio test $vote^-/vote^+_{min} > \lambda$ with $\lambda=8$, Elastic HH uses $vote^- > vote^+_{min}$ and sets the new flow's initial size to $vote^+_{min}+1$. This is equivalent to $\lambda=1$, makes the replacement decision a single integer comparison, and lets the discarded flow's count carry over into the incoming flow so the new counter does not start from zero. The second piece of machinery is dropping the light part, so the entire memory budget goes to the heavy buckets and each insertion touches only one contiguous bucket.

What would settle it

Run Elastic and Elastic HH on synthetic streams with different levels of skew while giving both sketches the same effective heavy-part memory, and compare AAE and ARE; if any skew value makes Elastic HH no better than Elastic, the claimed generalization of $\lambda=1$ fails. Alternatively, give Elastic a 25 percent larger total memory so its heavy part matches Elastic HH's, and check whether the reported 5.7 to 8.1 times error reduction persists.

Watch

Extended reading notes

Core claim

The central claim is that the Elastic sketch over-invests in generality, and that this generality actively hurts heavy-hitter detection. If the light part is removed and the heavy part alone is kept, with eviction triggered when the shared negative-vote counter exceeds the smallest positive vote and the new flow's counter initialized to that minimum plus one, each bucket behaves like a small top-k tracker whose estimates are closer to true flow sizes. The paper reports that on real traffic, compared with the standard Elastic sketch at the same total memory, Elastic HH reduces average absolute error by 7.3 to 8.1 times and average relative error by 5.7 to 7.5 times, while raising throughput by roughly 2.5 times; precision, recall, and F1 score reach almost 100 percent even at small memory.

Load-bearing premise

The paper's error-reduction numbers assume both that $\lambda=1$ is near-optimal on unseen traffic patterns, which is tested only on one public trace, and that comparing at equal total memory is fair even though the standard Elastic spends 25 percent of that memory on its light part; weakening either assumption shrinks the reported gains.

Editorial extensions

If this is right

  • At equal memory, heavy-hitter detection error drops by roughly 5.7 to 8.1 times compared with the standard Elastic sketch.
  • Throughput is about 2.5 times higher than Elastic on the tested CPU, and more than ten times higher than the other compared sketches when SIMD instructions are used.
  • Precision, recall, and F1 score reach nearly 100 percent on the tested trace even with a 100 KB memory budget.
  • The accuracy and speed advantages are specific to heavy-hitter queries; other measurement tasks supported by Elastic are no longer served by the tailored structure.
  • Setting $\lambda=1$ is reported as near-optimal and costs no extra computation per insertion.

Reading between the lines

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

  • The replace-with-min-plus-one rule makes Elastic HH structurally similar to classic top-k frequent-item algorithms, so it may inherit a formal error bound if the comparison is drawn out explicitly.
  • The same tailoring recipe, removing the general-purpose companion structure and tightening the eviction threshold, could be tested on other multi-purpose sketches to produce task-specific variants for heavy change or cardinality detection.
  • The speed advantage depends on one-bucket cache-friendly access, so re-measuring on programmable switch hardware or with packet reordering would show whether the 2.5 times throughput gain survives outside a software CPU setting.
  • Because $\lambda=1$ is validated on a single trace, the paper's parameter-free claim could be probed by sweeping synthetic flow-size distributions with different skew and checking whether accuracy stays near-optimal.
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

4 major / 6 minor

Summary. The paper proposes Elastic HH, a specialization of the Elastic sketch for the single task of heavy-hitter detection. The design drops the light part of Elastic and changes the eviction rule inside the heavy part: when a bucket is full and an incoming flow is not stored, the smallest flow is evicted once the bucket's negative-vote counter exceeds the smallest flow's positive votes, and the incoming flow is initialized with the evicted flow's count plus one. Experiments on a CAIDA trace report that Elastic HH reduces AAE by 7.3-8.1x and ARE by 5.7-7.5x compared with Elastic, while being about 2.5x faster. The abstract supplied with the submission, however, describes a "2FA Sketch" with a theoretically derived optimal lambda and different performance numbers (2.5-19.7x error reduction and 1.03x speedup), and that content does not appear in the full text.

Significance. If the claimed improvements were established under controlled comparisons, the paper would make a practically useful point: specializing a general-purpose sketch to heavy-hitter detection and simplifying its eviction logic is a plausible way to gain accuracy and speed, and the availability of source code on Github is a concrete strength. The reported F1/PR/RR results and the use of multiple baselines are also in the paper's favor. However, the central quantitative claim is currently confounded by unequal memory allocation between Elastic HH and Elastic, and the key parameter lambda is selected on the same workload used to report the headline accuracy results. These issues prevent the significance from being assessed on the present evidence.

major comments (4)
  1. [Section IV-A and IV-B] The headline accuracy comparison is confounded by unequal heavy-part memory. Section IV-A fixes total memory at 300KB for all algorithms and sets Elastic's heavy:light ratio to 3:1, so Elastic's heavy part receives 225KB while Elastic HH, which has no light part, receives 300KB for its only (heavy) part. Since AAE and ARE in these bucketized sketches are governed largely by collisions in the heavy part, the claimed 7.3-8.1x smaller AAE and 5.7-7.5x smaller ARE in Section IV-B are not cleanly attributable to the algorithmic changes. A controlled comparison should give the two sketches equal heavy-part memory (for example, run Elastic with 300KB heavy plus 100KB light, or run Elastic HH with 225KB total) and report both perspectives.
  2. [Section III-C and Fig. 4] The choice lambda=1 is parameter fitting rather than a validated design decision. Section III-C justifies lambda=1 by "our experimental results on different datasets," and Fig. 4 shows the accuracy comparison across lambda values, but the only dataset described in Section IV-A is the CAIDA Equinix-Chicago trace, which is also the dataset used for the main accuracy results in Section IV-B. The abstract further promises a "theoretically derived optimal lambda," but no such derivation appears in the body. Please provide either an analytic derivation or an out-of-sample validation on held-out traces with distinct traffic characteristics, and report variance across runs.
  3. [Section I vs. Section III-B] The eviction condition is stated inconsistently. Section I says replacement is activated when vote- > vote+_min + 1, while Section III-B defines the rule as vote- > vote+_min with lambda=1, and the worked example in Section III-B follows the latter (vote- becomes 12 and evicts a flow with vote+=11). The text also says "vote+_min is incremented by 1" and then the example sets the new flow's size to vote-, which equals vote+_min+1. Because this rule is the core algorithmic contribution, the exact condition and the initial counter value of the inserted flow must be stated unambiguously and must match the implementation used in the experiments.
  4. [Abstract and title] The submitted abstract and the full text describe different artifacts. The abstract promises a "2FA Sketch" with dual-layer protection, an improved Arbitration strategy, a cross-bucket Avoidance hashing scheme, and a theoretically derived optimal lambda, and it reports error reduction of 2.5-19.7x and speedup of 1.03x. The full text is titled "Elastic HH," contains no "2FA" nomenclature, no Arbitration/Avoidance scheme, no theoretical derivation, and reports 5.7-8.1x error reduction and 2.5x speedup. The title, abstract, and body must be aligned before the paper can be evaluated as a coherent submission.
minor comments (6)
  1. [Section IV-A] Only the throughput experiments are described as repeated 100 times; the accuracy metrics in Figs. 3-5 are reported as single curves with no error bars or run-to-run variability. Please add repetitions for the accuracy metrics or justify why they are deterministic.
  2. [Section III-C] The phrase "on different datasets" is not supported by the experimental setup, which names only the CAIDA Equinix-Chicago trace. Please specify how many traces were used and give their traffic characteristics.
  3. [Section IV-A, metrics] The query set Phi in the AAE and ARE definitions is not specified. Clarify which flows are included in Phi and how they are selected from the stream.
  4. [Figure 5(c)] The label "F1 socre" contains a typo; it should read "F1 score."
  5. [Section II-A] In the Elastic sketch example, the text says no eviction occurs when vote-/vote+ < lambda and eviction occurs when the ratio "equals" lambda; the boundary condition should be stated consistently with the original Elastic reference.
  6. [References] Reference [1] formats the Github repository name as "Elastic HH" with a space, which will not resolve as a URL; please provide the correct repository path.

Circularity Check

0 steps flagged · score 2.0 of 10

No definitional circularity: the claimed gains are empirical, and the λ=1 choice is openly empirical rather than a derived prediction; the main validity threats are a memory-allocation confound and single-trace parameter tuning.

full rationale

The paper's derivation chain is empirical rather than analytical. The only analytical-looking claim is Section III-C's 'According to our experimental results on different datasets, we find when λ = 1, the accuracy is nearly optimal', which is explicitly a data-driven parameter choice, not a first-principles derivation; Figure 4 then confirms that same choice. This is post-hoc model selection on the evaluation trace, and the reported 7.3–8.1x smaller AAE and 5.7–7.5x smaller ARE are therefore not held-out predictions, but the paper does not rename the fit as a prediction, so there is no definitional input/output circularity. Similarly, Section IV-A fixes total memory at 300KB and sets Elastic's heavy:light ratio to 3:1 while Elastic HH keeps only the heavy part, giving Elastic HH 300KB of heavy-part memory versus Elastic's 225KB; this is a serious experimental confound for the accuracy comparison but not a circular reduction. Self-citation to Elastic [23] is used as baseline and background, not as justification of the new algorithm's improvement, and no uniqueness theorem is imported from the authors' prior work. The abstract block preceding the full text claims a 'theoretically derived' optimal λ and a '2FA Sketch' that the full text neither derives nor contains; that is a missing-support and consistency problem, not a circularity. Overall, no load-bearing step reduces to its own input by construction, so the circularity score is low.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The paper's main reported gains rest on an empirically chosen threshold (lambda=1), a single dataset, reused Elastic parameters, and an unproved eviction heuristic. The title and abstract additionally promise a theoretical derivation that the body does not contain, and the full text describes a different algorithm than the abstract.

free parameters (3)
  • lambda (eviction threshold) = 1
    Selected after comparing lambda values in Fig. 4; the abstract promises a theoretical derivation but the full text says 'according to our experimental results'.
  • cells per bucket = 7
    Reused from Elastic's open-source parameters (Section IV-A), not derived for Elastic HH, and it affects accuracy and capacity.
  • heavy to light memory ratio = 3:1 for Elastic, 1:0 for Elastic HH
    Elastic HH receives the full memory budget for its heavy part while Elastic spends a quarter on the light part, which confounds the comparison.
assumptions (4)
  • domain assumption A single CAIDA trace is representative of general network traffic
    All accuracy results come from one dataset described only as the Equinix-Chicago CAIDA trace; no validation on other traces or synthetic streams.
  • ad hoc to paper The eviction heuristic that a new flow's size is probably larger than the smallest flow holds
    Section I-B and III-C assert this without proof, and the algorithm's accuracy depends on it.
  • standard math Hash functions distribute flows uniformly so the per-bucket minimum is a good proxy for the global minimum
    Implicit in the sketch design described in Section III-A and used in Section III-C, standard in sketch papers.
  • domain assumption Elastic's parameter settings are appropriate for Elastic HH
    The paper reuses Elastic's 7 cells per bucket and other settings (Section IV-A) without tuning or justification for the new structure.

how reviews work

0 comments
Cite this review

Pith. "Pith review of 2FA Sketch: Two-Factor Armor Sketch for Accurate and Efficient Heavy Hitter Detection in Data Streams." pith.science (2026). https://pith.science/paper/IEMQHROB

@misc{pith2026190902203,
  author       = {Pith},
  title        = {Pith review of: 2FA Sketch: Two-Factor Armor Sketch for Accurate and Efficient Heavy Hitter Detection in Data Streams},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IEMQHROB}},
  note         = {Machine review of arXiv:1909.02203}
}
abstract

Detecting heavy hitters, which are flows exceeding a specified threshold, is crucial for network measurement, but it faces challenges due to increasing throughput and memory constraints. Existing sketch-based solutions, particularly those using Comparative Counter Voting, have limitations in efficiently identifying heavy hitters. This paper introduces the Two-Factor Armor (2FA) Sketch, a novel data structure designed to enhance heavy hitter detection in data streams. 2FA Sketch implements dual-layer protection through an improved $\mathtt{Arbitration}$ strategy for in-bucket competition and a cross-bucket conflict $\mathtt{Avoidance}$ hashing scheme. By theoretically deriving an optimal $\lambda$ parameter and redesigning $vote^+_{new}$ as a conflict indicator, it optimizes the Comparative Counter Voting strategy. Experimental results show that 2FA Sketch outperforms the standard Elastic Sketch, reducing error rates by 2.5 to 19.7 times and increasing processing speed by 1.03 times.

Figures

Figures reproduced from arXiv: 1909.02203 by the authors.

Figure 1
Figure 1. An example for the Elastic sketch. Data Structure ( [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 3
Figure 3. Accuracy comparison for heavy hitter detection [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figure 4
Figure 4. Accuracy comparison for value of different [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
Figures from the paper (1 more)
Figure 5
Figure 5. Figure 5: Processing speed and accuracy comparison for heavy hitter detection [PITH_FULL_IMAGE:figures/full_fig_p006_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

  1. [1]

    https://github

    The source codes of our and other related algorithms. https://github. com/ElasticHH/Elastic HH

    work page

  2. [2]

    http://www.caida.org/data/ overview/

    The CAIDA Anonymized Internet Traces. http://www.caida.org/data/ overview/

    work page

  3. [3]

    R. B. Basat, X. Chen, G. Einziger, and O. Rottenstreich. Efficient mea- surement on programmable switches using probabilistic recirculation. In Proc. IEEE ICNP , 2018

    work page 2018

  4. [4]

    Ben-Basat, G

    R. Ben-Basat, G. Einziger, R. Friedman, and Y . Kassner. Heavy hitters in streams and sliding windows. In Proc. IEEE INFOCOM , 2016

    work page 2016

  5. [5]

    Ben Basat, G

    R. Ben Basat, G. Einziger, R. Friedman, M. C. Luizelli, and E. Waisbard. Constant time updates in hierarchical heavy hitters. In Proceedings of the Conference of the ACM Special Interest Group on Data Communication, pages 127–140. ACM, 2017

    work page 2017

  6. [6]

    Charikar, K

    M. Charikar, K. Chen, and M. Farach-Colton. Finding frequent items in data streams. Automata, languages and programming , 2002

    work page 2002

  7. [7]

    Cormode and S

    G. Cormode and S. Muthukrishnan. An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms, 55(1), 2005

    work page 2005

  8. [8]

    H. Dai, L. Meng, and A. X. Liu. Finding persistent items in distributed, datasets. In Proc. IEEE INFOCOM , 2018

    work page 2018

Show all 25 references
  1. [9]

    H. Dai, M. Shahzad, A. X. Liu, and Y . Zhong. Finding persistent items in data streams. Proceedings of the VLDB Endowment , 10(4):289–300, 2016

    2016

  2. [10]

    H. Dai, Y . Zhong, A. X. Liu, W. Wang, and M. Li. Noisy bloom filters for multi-set membership testing. In Proc. ACM SIGMETRICS , pages 139–151, 2016. 0.1 0.2 0.3 0.4 0.5 Memory Usage(MB) 0.2 0.4 0.6 0.8 1.0 precision rate CMHeap CountHeap Elastic ElasticHH SS (a) precision rat...

    2016

  3. [11]

    Estan and G

    C. Estan and G. Varghese. New directions in traffic measurement and accounting: Focusing on the elephants, ignoring the mice. ACM Transactions on Computer Systems (TOCS) , 21(3), 2003

    2003

  4. [12]

    Harrison, Q

    R. Harrison, Q. Cai, A. Gupta, and J. Rexford. Network-wide heavy hitter detection with commodity switches. In Proceedings of the Symposium on SDN Research , page 8. ACM, 2018

    2018

  5. [13]

    Homem and J

    N. Homem and J. P. Carvalho. Finding top-k elements in data streams. Information Sciences, 180(24):4958–4974, 2010

    2010

  6. [14]

    Huang, X

    Q. Huang, X. Jin, P. P. Lee, R. Li, L. Tang, Y .-C. Chen, and G. Zhang. Sketchvisor: Robust network measurement for software packet process- ing. In Proceedings of the Conference of the ACM Special Interest Group on Data Communication . ACM, 2017

    2017

  7. [15]

    Huang and P

    Q. Huang and P. P. Lee. Ld-sketch: A distributed sketching design for accurate and scalable anomaly detection in network data streams. In IEEE INFOCOM 2014-IEEE Conference on Computer Communications, pages 1420–1428. IEEE, 2014

    2014

  8. [16]

    Huang, P

    Q. Huang, P. P. Lee, and Y . Bao. Sketchlearn: relieving user burdens in approximate measurement with automated statistical inference. In Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication , pages 576–590. ACM, 2018

    2018

  9. [17]

    D. Li, H. Cui, Y . Hu, Y . Xia, and X. Wang. Scalable data center multicast using multi-class bloom filter. In 2011 19th IEEE International Conference on Network Protocols , pages 266–275. IEEE, 2011

    2011

  10. [18]

    T. Li, S. Chen, and Y . Ling. Per-flow traffic measurement through randomized counter sharing. IEEE/ACM Transactions on Networking (TON), 20(5), 2012

    2012

  11. [19]

    Y . Li, R. Miao, C. Kim, and M. Yu. Flowradar: A better netflow for data centers. In NSDI, 2016

    2016

  12. [20]

    Z. Liu, A. Manousis, G. V orsanger, V . Sekar, and V . Braverman. One sketch to rule them all: Rethinking network flow monitoring with univmon. In Proceedings of the 2016 conference on ACM SIGCOMM 2016 Conference. ACM, 2016

    2016

  13. [21]

    Metwally, D

    A. Metwally, D. Agrawal, and A. El Abbadi. Efficient computation of frequent and top-k elements in data streams. In Proc. Springer ICDT , 2005

    2005

  14. [22]

    Sivaraman, S

    V . Sivaraman, S. Narayana, O. Rottenstreich, S. Muthukrishnan, and J. Rexford. Heavy-hitter detection entirely in the data plane. In Proceedings of the Symposium on SDN Research . ACM, 2017

    2017

  15. [23]

    T. Yang, J. Jiang, P. Liu, Q. Huang, J. Gong, Y . Zhou, R. Miao, X. Li, and S. Uhlig. Elastic sketch: Adaptive and fast network-wide measurements. In Proceedings of the 2018 ACM SIGCOMM Conference . ACM, 2018

    2018

  16. [24]

    M. Yu, L. Jose, and R. Miao. Software defined traffic measurement with opensketch. In NSDI, volume 13, 2013

    2013

  17. [25]

    Y . Zhou, T. Yang, J. Jiang, B. Cui, M. Yu, X. Li, and S. Uhlig. Cold filter: A meta-framework for faster and more accurate stream processing. In Proceedings of the 2018 International Conference on Management of Data, pages 741–756. ACM, 2018

    2018

Pith tools

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