Lego Sketch: A Scalable Memory-augmented Neural Network for Sketching Data Streams

Thank you for your feedback! We have addressed your concerns as below and welcome any further discussion should you have additional questions.

Comparison to insertion-only streams algorithm like Misra-Gries

Reply to

...counting-based sketches are often superior for insertion-only streams...

Counter-based methods (e.g., Misra-Gries) and sketch-based methods (e.g., Count-Min Sketch, Lego Sketch) represent two distinct lines of research in streaming algorithms, as classified by Cormode and Hadjieleftheriou in their foundational work "Finding Frequent Items in Data Streams" (VLDB 2008).

So, we respectfully argue that directly comparing sketch-based methods (e.g., Count-Min Sketch, Lego Sketch) with counter-based methods (e.g., Misra-Gries Algorithm) is inappropriate, due to their inherently different design goals: counter-based methods identify frequent items in insertion-only streams with minimal overhead, while sketch-based methods focus on probabilistic frequency estimation for dynamic streams (supporting deletions/weights). This methodological separation is well-recognized in the literature (see papers in reference for details), where sketch-based studies explicitly avoid benchmarking against counter-based methods, due to their fundamentally distinct problem formulations and guarantees.

The key differences between the two methods are summarized in the table below, based on Cormode’s paper.

Methods And Evaluation Criteria:

Reply to

... This error measure becomes questionable ... since small errors on non-occurring elements will tend to dominate.

We respectfully argue that AAE(Average Absolute Error) and ARE(Average Relative Error) have been well-established standards since the early 2000s (see papers in reference). To ensure fair evaluation and comparison, we adhere to these established practices.

Moreover, non-occurring elements are often excluded in prior sketch-based literature for two reasons: 1) They lack true frequency, making ARE computation infeasible; 2) Hash collisions introduce similar absolute errors for both occurring and non-occurring elements, leading to minimal impact on AAE.

Other Comments Or Suggestions:

Reply to

The comment (page 4) that sketches typically do not consider skew is misleading...

Thank you for pointing this out. We agree that our original phrasing could be clearer in explaining how existing sketches handle skewness.

While traditional sketches like CM-Sketch and C-Sketch exhibit different performance under skewed data, this behavior results from their static design rather than active skewness detection. In contrast, Lego Sketch introduces a scanning module that dynamically estimates stream skewness and uses it as prior knowledge to enhance accuracy, as shown in our experiments.

We will revise the text for clarity:

"Handcrafted sketches face challenges in inferring global stream properties (e.g., distinct item count, skewness) from their compressed storage. While some perform differently under varied skewness, this stems from static design rather than adaptive inference."

Questions For Authors:

Reply to

Would your approach be able to support merging of sketches?

Like Meta Sketch, Count-Min Sketch, and other sketch-based methods, our Lego Sketch maintains additive properties that fully support sketch merging operations. We will explicitly clarify this consistency in the revised manuscript.

def join(self, second: "CountMinSketch") -> None:
    ...
    size = self.width * self.depth
    for i in range(size):
        tmp_els = self._bins[i] + second._bins[i]
        ...
        self._bins[i] = tmp_els

Thank you for your detailed review and constructive feedback! We have addressed your concerns below and are happy to discuss further if needed.

Claims

Reply to

...I agree that use sketches to reconstruct global statistic... There are such studies.....

Thank you. While these methods rely on handcrafted rules to infer error distributions from bucket values, our Scanning Module leverages end-to-end training to directly reconstruct global stream characteristics, such as skewness and cardinality, from bucket values. Intuitively, directly reconstructing global stream characteristics is more effective, as they are the root cause of error distributions. That said, we may also explore adapting our end-to-end approach for error distribution reconstruction in the future. We will revise the descriptions to include discussions of these related methods.

Reply to

While Lego Sketch has shown good accuracy in practice, from the theory side, it does not offer "superior space-accuracy trade-offs"..

As discussed in Section 4.3 and the Limitations Section (Appendix A), our theoretical bounds are indeed looser than those of handcrafted sketches. However, our key theoretical contribution is establishing the first formal bounds for pure neural sketches, unlike meta-sketches, which don't have theoretical guarantees. Following your suggestion, we will revise the abstract to clarify the "superior space-accuracy trade-offs" is empirically supported.

References:

Reply to

Add references to insertion-only model and consider to add discussions on the streaming model for LegoSketch.

Lego Sketch, like Meta Sketch, Count-Min Sketch, and Count Sketch, operates in the turnstile model using additive memory buckets, which naturally support arbitrary deletions. We will make this clearer in the revised manuscript. And we will add a dedicated subsection in the Related Work section to discuss insertion-only data summarization techniques (e.g., MG summary, SpaceSaving, Lossy Counting).

Reply to

... The author should also consider to add references [1-3].

As noted in Section 3.3 (References in Lines 502 and 510), we have already included references to derivatives like Augmented Sketch and Cold Filter, citing representative works (Zhou et al., 2018; Roy et al., 2016; Hsu et al., 2019; Aamand et al., 2024).

Following your suggestion, we will additionally cite: Zhao, Fuheng, et al. "Panakos: Chasing the tails for multidimensional data streams." This will help readers better understand the technical lineage and connections between these approaches.

Reply to

Add discussion on Shahout, "Learning-based heavy hitters and flow frequency estimation in streams."

Thank you for bringing this recent work to our attention. The paper employs learning-based methods to separate high/low-frequency items, thereby improving the insert-only SpaceSaving algorithm. However, this approach operates in a different streaming model (insertion-only) with our proposed sketch method (turnstile). We will include it in the revised Related Work section as an learning-enhanced variant of the insertion-only methods.

Other Comments Or Suggestions:

Reply to

I prefer the authors to use the original name of Elastic Sketch.

Thank you. We will adopt the original naming convention and refer to them as Elastic Sketch (CMS/Lego) to improve clarity.

Questions:

Reply to

Discussion on whether memory block size can be determined based on frequency or cardinality.

We appreciate the insightful question. Our current design of Lego Sketch employs uniform item distribution across fixed-size memory blocks based on cardinality. As formalized in Theorem 4.2, this ensures that the skewness distribution within each sub-block closely matches the global stream skewness. Consequently, all blocks exhibit similar statistical properties (skewness, cardinality, and memory allocation) - a desirable feature for scalable memory design, as it ensures stable statistical characteristics during scaling memory.

Indeed, memory block size does not have to be determined solely by cardinality. A frequency-aware approach could enhance efficiency by assigning larger blocks to high-frequency substreams but may introduce risks under distributional shifts. Although such strategies have potential benefits, they fall outside the scope of our current work. We would be glad to explore this direction in future — for example, using learning-based predictors to separate high- and low-frequency items and adjust block sizes accordingly.

Ethical Concerns：

Reply to

AOL dataset has leaked user information...

Thank you for pointing this out! This dataset has been widely used in prior studies, so we followed this practice without realizing the issues. We will remove the results derived from this dataset. The remaining four real-world datasets and six synthetic datasets would be sufficient to demonstrate the superior performance of our work.

Thank you for your feedback! We have provided responses below and would be happy to engage in further discussion if needed.

Neural sketch represents a promising new direction in the sketch field long dominated by handcrafted designs. Existing neural sketches such as Meta Sketch demonstrate feasibility but suffer from limited scalability, insufficient accuracy, and poor deployability. Lego Sketch takes the critical next step—by introducing architectural and training innovations that make neural sketch accurate, scalable, and practically usable. This transforms neural sketch from a conceptual idea into a deployable core technique for data stream processing.

More specifically, both handcrafted and neural sketch structures are designed to prioritize simplicity and effectiveness, using minimal memory to cope with infinite data streams. For over a decade, even the latest handcrafted sketches have primarily relied on a few hash functions and a two-dimensional array with straightforward decoding rules. Similarly, leading neural sketches like Meta Sketch rely on basic architectures, using simple MLPs across modules. This highlights the core challenge in sketching: achieving practical scalability with limited space and high accuracy.

Lego Sketch introduces significant advancements in this regard, focusing on the emerging domain of neural core sketching. Unlike Meta Sketch, which suffers from limited scalability and frequent retraining needs, Lego Sketch incorporates scalable embedding and memory mechanisms, ensuring seamless deployment without retraining. This fundamental contribution directly addresses a major limitation in the field.

Moreover, Lego Sketch demonstrates technical novelty through its structural design. Modules such as the Ensemble Decoding Scanning Module and the self-guided loss contribute to accuracy improvements, as evidenced by comprehensive ablation studies. Experimental results further validate its competitive throughput, underscoring its balanced performance. By refining all components beyond Meta Sketch, Lego Sketch advances the state of the art in neural sketching.

Thank you for your valuable feedback! Below, we address your concerns in detail.

Other Comments Or Suggestions:

Reply to

The legibility of the figures in Sec. 5 should be improved.

Thank you for your suggestion. We will improve the readability of the figures accordingly.

Questions For Authors:

Reply to

Question 1： How much memory do the Lego Sketch's NN components use, and is the Lego Sketch still competitive with the handcrafted baselines when this memory overhead is included?

The NN components of Lego Sketch are highly space-efficient, containing only around 5K parameters, which equates to a storage size of 20KB with 32-bit precision. Given that the total memory usage in our experiments ranges from 0.3MB to 140MB, the NN components contribute only a negligible fraction, i.e., between 6.7% and 0.014% of the total memory. Even when accounting this overhead, Lego Sketch remains highly competitive and significantly outperforms handcrafted baselines. For example, on the LKML dataset, with a total usage of 620KB (600KB for storage plus 20KB for NN components), Lego Sketch records an AAE of only 2.55, which is lower than CM (2.58) and C Sketch (2.95), even when these baselines use 1100KB of memory.

Generally, the NN overhead for neural sketches is typically not accounted for, similar to other neural network-augmented methods, like learned sketches and Meta sketch. This is because this overhead can be further amortized across multiple deployed instances.

Reply to

Question2：What is the numerical precision used in the experiments reported in the submission?

Lego Sketch uses the default 32-bit precision, and with only 5K parameters, the memory overhead is negligible.

Reply to

Question3：how well does the sketch perform when its NN components are quantized to lower precision to reduce memory consumption (e.g., to 4 bits per parameter)? How well does the sketch perform when the buckets of the "scalable memory" are quantized to lower precision?

Neural sketch's memory module requires frequent updates, which will frequently triggers quantization and dequantization operations when updating the quantized memory. This significantly impacts throughput. Future research could focus on designing efficient quantization algorithms tailored for high-update scenarios.

For the NN components, this could be feasible. However, Lego Sketch has only 5K parameters, which is significantly small—consuming just 0.014% to 6.7% of the total memory storage in experiments. Compared to Meta Sketch, another neural sketch with 52K parameters, Lego Sketch is smaller by an entire order of magnitude. Thus, further quantization of the NN components provides minimal benefit.

Following your suggestion, we attempted reducing precision from 32-bit to 16-bit, saving 10KB in storage of NN components. However, under small memory budgets, the error notably increased—e.g., under 600KB, Lego Sketch's error rose from 2.55 to 6.23. In contrast, for larger memory budgets, such as above 2600KB, the error remained consistent within two decimal places.