Lego Sketch: A Scalable Memory-augmented Neural Network for Sketching Data Streams
Authors: Yuan Feng
Yukun Cao
Hairu Wang
Xike Xie
S Kevin Zhou
Venue: ICML 2025 poster (2025)
Keywords: Data Streams; Memory Augmented Neural Networks; Data Compression
Primary area: deep_learning->everything_else
TL;DR: A Scalable Memory-augmented Neural Network for Sketching Data Streams

Abstract: Sketches, probabilistic structures for estimating item frequencies in infinite data streams with limited space, are widely used across various domains. Recent studies have shifted the focus from handcrafted sketches to neural sketches, leveraging memory-augmented neural networks (MANNs) to enhance the streaming compression capabilities and achieve better space-accuracy trade-offs.
However, existing neural sketches struggle to scale across different data domains and space budgets due to inflexible MANN configurations. In this paper, we introduce a scalable MANN architecture that brings to life the Lego sketch, a novel sketch with superior scalability and accuracy.
Much like assembling creations with modular Lego bricks, the Lego sketch dynamically coordinates multiple memory bricks to adapt to various space budgets and diverse data domains.
Theoretical analysis and empirical studies demonstrate its scalability and superior space-accuracy trade-offs, outperforming existing handcrafted and neural sketches.

Lego Sketch: A Scalable Memory-augmented Neural Network for Sketching Data Streams
Yuan Feng 12 Yukun Cao * 12 Hairu Wang' 12 Xike Xie 32 S. Kevin Zhou 32
Abstract
Derivatives
-HHaderratted) Cibaketchh (Neural) Lego-sketch
Sketches, probabilistic structures for estimating item frequencies in infinite data streams with lim- ited space, are widely used across various do- mains. Recent studies have shifted the focus from handcrafted sketches to neural sketches, leveraging memory-angmenteed neural networks (MANNs) to enhance the streaming compression capabilities and achieve better space-accuracy trade-offs. However, existing neural sketches struggle to scale across different data domains and space budgets due to inflexible MANN con- figurations. In this paper, we introduce a scalable MANN architecture that brings to life the Lego sketch, a novel sketch with superior scalability and accuracy. Much like assembling creations with modular Lego bricks, the Lego sketch dy- namically coordinates multiple memory bricks to adapt various space budgets and diverse data domains. Our theoretical analysis guaran- tees its high scalability and provides the first er- ror bound for neural sketch. Furthermore, exten- sive experimental evaluations demonstrate that the Lego sketch exhibits superior space-aceuracy trade-offs, outperforming existing handcrafted and neural sketches. Our code is available https//ggiiibbboooo////oollooooo
2018 2016
2013
2010 2024
Error
Core Structure
Handcralted vs. Neural Sketches
sketch
Cokeecch
Lago shatch
Space Budget
Figure 2:
Space-accuracy
Figure 1: Sketch Literatures
Trade-off (Aol Dataset)
2014), network measurements Yuu et al. 2013 Yang et al. 2018 and big data analytics (Cormode et al. 2012 Zaharia et al. 2016). Sketches, a typical probabilistic structure, have become essential for representing data streams with sub-linear space and linear time while maintaining accu- rate item frequency estimates. Two major research direc- tion in sketching techniques have emerged: handcrafted
sketches (Cormode & Muthukrishnan
Charikkr et al.
2002
Estan & Varghese 2002 Deng & Rafei 2007) and
neural sketches (Rae et al. 2019 Feng et al. 2024 Cao
ct al. 2023 2024).
Handcrafted sketches rely on core structures, such as the CM-sketch (Cormode & Muthukrishhani (0005) and C- sketch (Charikar et al. (2002), which are comprised of com- pact 2D arrays, hash functions, and predefined strategies. These handcrafted core structures have since formed the foundation for numerous variants or derivatives (Estan & Varghese 2002: Deng & Rafiei 2007). designed to bet- ter adapt to the skewed distributions in data streams In contrast the decade-old core structures of handcrafted sketches, recent advancements in neural sketches (Cao et al., 2023 2024 Feng et al. 2024 Rae et al. 2019) have intro- neural networks (MANNs) as a new class of core structures. The MANN-based cores im- prove sketching performance by leveraging their capability of memory compression and adaptability to distributional patterns of data streams, Figure provides an overview of the literatures sketches.
1. Introduction
The estimation of item frequency in continuous and never- ending data stream stands as a pivotal task in supporting a broad spectrum of applications in machine learning (Goa
duced memory-augmente
ct al. 2012 Aghazadeh et al. 2018 Talukdar & Cohen
Equal contribution 'School of Computer Science, University of Science and Technology of China (USTC), China Data Darkness Lab, MIRACLE Center, Suzhou Institute for Advanced Research, USTC, China 'School of Biomedical Engineering, USTC, China. Correspondence to: Xike Xie <xkxie@ ust...du.en>>
Despite recent advancements, existing neural sketches face practical challenges when deployed in real-world settings, particularly scaling effectively to data streams across diverse domains and varying space budgets. A major seal- ability issue is that they require retraining when there is a
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Lego Sketch; A Scalable Memory-augmented Neural Network for Sketching Data Streams
Specifically, we propose novel self-guided weighting loss (Section (.22)oon332)))) for dynamically weighting different meta-tasks during self-supervised meta-learning, effectively address- ing issues of diminished advantage. Moreover, pioneer- ing module termed memory scanning (Section (3.1). which autonomously reconstructs stream features from the com- pressed memory, along with other optimization techniques, significantly aids in the estimation, thereby achieving supe- rior space-accuracy trade-offs, as shown in Figure
Addressing
Decoaing
Boalable Senozy
Frequency
An Item
A Stream
Subeading
Frequency
uub-streams Mul Multi-bricks
A brick
The Lego sketch enables scalable and unified framework capable of adapting to different domains and space budgets, mirroring the modular design in dedicate creations built from multiple Lego bricks.
Figure 3: Lego Sketch Overview:
Contributions. 1) We introduce the Lego sketch, novel neural sketch equipped with a scalable MANN architecture designed for sketching data streams. 2) The Lego sketch re- solves scalability limitations and achieves a superior space- accuracy trade-off through key technical innovations, in- cluding normalized multi-hash embedding, scalable mem- ory, memory scanning, and self-guided weighting loss. 3) We also provide theoretical support for the scalability and estimation error analysis, areas previously unexplored in existing neural sketches, 4) Extensive empirical studies on both real-world and synthetic datasets confirm that the Lego sketch significantly outperforms oftte-ofthheaar methods.
shift in data domains or changes in space budgets. This requirement stems from their reliance on a sample MLP- based embedding module and a fixed-size memory module within the traditional MANN architecture. Also, as demon- strated in F the accuracy advantage of existing neural sketches, i.e., meta-sketches, in terms of estimation error over handcrafted sketches, tends to decrease the space budget increases.
2. Related Works
In this paper, we propose a novel neural sketch, called the Lego sketch, designed to significantly enhance scalability and improve the space-accuracy trade-offs of existing neural sketches, thereby setting new benchmarks in performance As depicted in Figure 3 the Lego sketch is initially trained on single memory brick to acquire basic sketching capa- bilities across data domains. When dealing with a large- scale data stream, it divides the stream into manageable sub-streams, each controlled by an independent memory brick. The Lego framework is achieved by devising a new MANN architecture from two aspects.
Sketch techniques fall into two categories: core sketches and their derivatives, as shown in Figure I Core sketches
(Cormode & Muthukrishnan 2005 Charikar et al. 2002
Estan & Varghese 2002 Deng & Rafiei 2007 Liu & Xie
2021 Cao et al.) 2023 2024). also referred to as core struc-
tures, provide the fundamental structure for stream process- ing, where (Estan & Varghese| 2002 Deng & Rafeii 2007) are variants of (Cormode & Muthukrishhan 20055] Charikar
ct al. 2002) under specific conditions. Subsequent deriva-
tives (Zhou et al.) 2018 Roy et af.. 2016 Yang et al. 2018
Aamand et al.
2024 Hsu et al., 2019 Zhao el al.
2023
Ma
For scalability, the Lego sketch overcomes the shortcom- ings of existing neural sketches under conventional MANN architecture, particularly when used across different data domains and space budgets. First, we propose novel nor- malized multi-hash embedding technique to enable theoret- ically provable domain- domain-agnostic scalability (Section [41).. without necessitating retraining for different data domains. Second, with theoretical foundations (Section 2 our ap- proach leverages scalable memory strategy to coordinate multiple memory bricks, avoiding the need for retraining when adapting memory sizes to fit different space budgets.
et al.
2024 Gao et al. 2024a Liu & Xie 2023
Liu et al.
2024
Gao al., 2024b Huang et al. 2023) of core struc-
tures, depend on the core structure for their foundational performance and incorporate external enhancement with orthogonal add-ons like filters. Notably, recent advances in neural sketches, i.e., the meta-sketch (Cao et al., 2023 2024], have shown improved accuracy under tight space budgets but face scalability challenges. Our Lego sketch tackles the scalability challenges and optimizes the space- accuracy trade-offs. Moreover, we study how subsequent derivatives can utilize the Lego sketch as their core, detailed in Section B.3
For accuracy, the Lego sketch not only addresses the is- sue of diminished advantage of existing neural sketches in high budgets but also offers enhancement in accuracy.
Counter-based summarization is also a common method for summarizing data streams, identifying frequent items through techniques like MG summary (Misra & Gries) 1982) and SpaceSaving (Metwally et al. 2005). These methods typically excel in insertion-only stream models, with some research also exploring learning- based enhancements (Sha
'This paper focuses on the core structure of sketches. Deriva- tives of core structure typically incorporates external enhance- ments, such as filters (discussed in Section 2). Section (exxxlorsss derivatives of the Lego sketch, which use the core structure, providing a comprehensive analysis.
2

---

Lego Sketch; A Scalable Memory-augmented Neural Network for Sketching Data Streams
Table I: MANN Architecture in Neural Sketches
through single forward pass of several network modules, ensuring that the computational complexity of single op- eration remains constant, independent of the data stream's 's length. This aligns well with the efficiency requirements for sketching data streams (Charikar et al. 2002 Cormodee & Muthukrishnan 2005 Cao et al.. 2023). A high-level overview of these operations is presented in Figure
MANN Arch.
Embedding
Momory Scanning
Loss
Meta-Skeich
MLP-based Fixed
Regular Loss Co Self guided Loss g
Lego Sketch Scalable
Scalable
Deepsets based
hout& & Mitzenmacher 2024). However, compared to sketch techniques, counter-based methods struggle with dynamic streams that allow deletions negative weights, while sketch methods naively handle unbounded deletions, mak- ing them suitable for broader applications (Cormode & Hadjieleftheriou 2008 Berinde et al.) 2010). Given these differences, counter-based summarization and sketch tech- niques should not be directly compared: nonetheless, future research could explore the development of an end-to-end neural framework for counter-based summarization.
Scalable Embedding(E)) The primary function of the em- bedding module is to obtain an embedding vector e2 for given item x; during Store and Query operations. Previ- ous MANN based neural sketches, the meta-sketch (Cao et al.
2024 and other related works (Rae et al. Vinyals et al. 2016 Santoro et al., 2016 Feng et al.
2023
2019
2024).
leverage conventional encoders like ML.Ps and CNNs.
These encoders embed features of data items within spe- cific domains, aim to extract
Memory-augmenter neural networks (MANNs) (Graves ctt al., 2016; Danihelka et al. 2016 Weston et al. 2014 Graves et al. 2014) are designed for efficient interaction with external memory through neural networks. Leveraging meta-learning, MANNs facilitate one-shot learning capa- bility of certain tasks across various datasets, avoiding be limited to specific dataset (Santoro al. 2016)] Vinyals et al. 2016, Hospedales et al., 2021). Previous efforts on neural sketches (Cao et al., [02332202: implement this MANN ar- chitecture in four functional modules: Embeddingg, Address- ing, Memory, and Decoding, where the one-shot learning paradigm inherited for the single-past pass storage procedure in stream processing. As aforementioned, neural sketches struggle with the scalability challenge. Our Lego sketch addresses the challenge by devising novel MANN archi- tecture. A comparison of our architecture with traditional MANNs is outlined in Table
knowledge, such as identifying high- and low-frequency items in spe- cific data stream. However, this approach presents several limitations. As highlighted in the meta-sketch (Cao et al., 2023). dynamic streaming scenarios can lead to robustness challenges, due to shifts between high and low-frequency items. Most importantly, these encoders face domain scala- bility challenges, which require encoder retraining or even model retraining, while deploying models across diverse data domains. For example, a model trained for web-elick stream domain cannot be directly adapted to textual stream domain, letting alone the domain of other modalities. To address these challenges, we propose to adjust the "target" of the embedding module as follows. Without extracting any domain-specific features, we generate embedding vec- tors {u} conforming to a specific skewness range, making the embedding module domain-agnostie This strategy en- hances both the robustness and scalability of models across varied domains.
3. Methodology
Inspired by the Hash Embeddings (Tito Svenstrup et al., 2017) in NLP fields, we introduce a novel embedding tech- nique, termed normalized multi-hash embedding, as below:
We consider standard data stream model outline the problem of stream item frequency estimation. Consider data stream X' = (#1...., EN) consisting of N data items with n distinct elements. Each data item z; E X assumes a value from the item domain set X = fei...., e, where elements in X are unique. The frequency Ji of element 6, indicates its occurrence in X. Thus, the total frequencies for all fis add up to N, representing the length of the stream. Without causing any ambiguity, we use 2; to refer to either a data item for storing or an element for querying.
Vwa, (1)) 0y = E(x;) = I[VV,, Paatog VHa, (e;))]l
Specifically, it comprises a learnable vector V and a set of di independent hash functions (HI, J. Each hash function maps 2; to an index of V. retrieving correspond- ing values from V based on di indices, yielding v E Rd, Finally, v; undergoes
L1 normalization. The idea lies in the utilization of hash-based random mappings, ensur- ing
3.1. Lego Framework
scalability as the analysis in Section Furthermore, the L, normalization effectively main- tains the stability of L1 accumulation across different items in additive memory storage, thereby enhancing estimation accuracy F
Overview. The Lego sketch consists of five modules: Scal- able Embedding(E), Hash Addressing(A)) (A), Scalable Mem- ory (M), Memory Scanning (S), and Ensemble Decod- ing( These modules collaborate to provide two types of operations: Store and Query, controlling the writing and reading of external memory. Each operation is carried out
"Related ablation studies are detailed in Section 5.5
3

---

Lego Sketch: A Scalable Memory-augmentted Neural Network for Sketching Data Streams
Lego
Hash Addressing A
SKE KETCH
Hash
5
3
Scalable Memory M
mi
Rule-based fi Neural- based
11
Store Query Only Store Only Query
Hesh
aii
T i
Distribute items
Vi
Vi
f
Norm.
M1
Hash
$
/nsembbe Decoding D
Scalable Embedding E
Data Stream
M2
Memory Scanning S
MK
Figure 4: Framework of the Lego Sketch (When an item is stored, it undergoes E and A. obtaining the embedding vector and address vector o,, which are subsequently stored into the distributed memory brick M within M. When querying item 2,, its embedding vector 2s and address vector a, are obtained the same way. These, combined with stream characteristics reconstructed from the current memory brick by S, are input into D for frequency estimation fa.)
Hash Addressing (AA). To align with scalable hash embed- dings, our approach simplifies the learning- based addressing in the meta-sketch by employing an additional set of dj hash functions {7() igd, for addressing. This method seeks out dj positions within the range of [1, d2), subsequently trans- forming them into sparse address vector E Rd xd In the sparse address vector a, positions mapped by the hash functions are assigned a value of 1, while all other positions retain a value of O.
Algorithm Operations
1: Operation Store(x;;:
v + E(x)): : ai f- A(z;)
Mz(n.)) = MH(a.) + 04 a;
4: Operation Query(z;):
5: U/ + E(x);; at f A(zz); m, = MH(.)
6: sH((z)): (H()))' MH(ss) + S(MM((z))
R. D(m,, Us 8H(z))) HH(rr)) (H(ar))
(n) (a)
a. = A(x,) = Sparse (ecto Hd, (z:))
Algorithm 2 Ensemble Decoding
With conventional MANNs, the neural structures (Cao et al. 2023 2024, Rae et al. 2019 Feng et al. 2024) employ a single, fixed- size dense memory store embedding vectors. Com- pared to the counter array used in handcrafted sketches, M offers a superior dense compression capability. However, the fixed size of M presents challenges for the scalabil- ity in terms of varied space budgets (i.e. the size of M): the retraining necessity and increasing cost for training on larger budget. Thus, we introduce the Scalable Memory, which offers training-independent memory scalability for the Lego sketch. This module manages K memory bricks, Mi...,, Mr. using a hash function to uniformly distribute items in streams across these bricks. This approach allows for memory resizing by simply increasing K, thereby elim- inating the need for retraining when adjusting the space budget. For example, in Section 5.2 we easily scale the overall memory size up 140MB for 100 million-level streams.
Scalable M.mo
1: Module D(m,, U4 SH(m.)) HH(z,)) " H(zz) ):
(n)
(a)
2: = Idee (m,, Ut, SH():)); f. min my
=dee
block M Rdixd2 xd2
if (().))) $ Ia or *H(m.)) S 3: ƒ:
(n)
4: else: f: =
5: return f:
is written into MH(z.). according to the address vector a; E Rd xd2 as follows: MH(x.) =MH(z,) + v; o a;s where represents the element-wiss multiplication. Sim- ilarly, for querying I;, the hash function H. first identi- fies the relevant memory brick Mx{a.)), which preserves x 's frequency information. Then, the relevant information m, E Rd is extracted from MH(aa)) using 2; 's address a;: m, = MT )( a Additionally, we supplement the length of sub-stream into m,, using a counting bucket.
Memory Scanning For any given data stream X, previ- ous sketches typically estimate frequency f. by data items relevant information m, retrieved from storage, while fail- ing to consider global characteristics s of the data stream
Specifically, when storing an item Zi. it is distributed to specific memory brick MH(a:), by a hash function H. In this way, the original data stream X. is partitioned into K sub-streams _",..., X'x, with each sub-stream stored within brick M. Subsequently, its embedding vector o; E Rdd.
Foor batch matrix multiplication, vectors need dimensional broadcast and applies to last two dimensions.
4

---

Lego Sketch; A Scalable Memory-augmentedd Neural Network for Sketching Data Streams
(such as distinct item number n and skewness parameter + as prior knowledge aid frequency estimation. This over- sight arises primarily because handcrafted sketches struggle to infer global stream properties from their compressed stor- age. Although some works have attempted to infer error distributions based on handcrafted rules to assist in decod- ing (Ting) 2018 Chen et al. 2021] Liu et al. 2024), such designs are limited and highly dependent on specific rules. In reality, the error of sketches is fundamentally determined by the characteristies of the stream itself, and further us- ing rule-based methods to infer these characteristics from compressed storage is even more challenging. Moreover, designing estimation strategies that consider global charac- teristics complicates the matter further. Here, we point that, these challenges can be resolved within the MANN architec- ture of neural sketches through end-to-end training, which could effectively reconstructs global stream characteristics. It not only facilities the reconstruction of both explicit and implicit global stream characteristics s by training scanning network Iscan under the supervision of the loss function, but also simultancously trains a decoding network Idee uti- lizing global characteristics s for more accurate frequency e
of the Lego sketch, we enable the straightforward compu- tation of rule-based estimate f min (m//rz). These two estimates are aggregated to produce a final prediction
ft based on the estimated skewness *H(a.) and item num-
(a)
ber s "Hiz,)' i.e., f, = D(m,, 21 *H(,)) HH(z)) detailed in Algorithm 2
(n)
(H())) (H(z)) as
3.2. Training
Since the memory blocks in the memory module M are independent and are extended by multiple copies of a sin- gle memory block, we only need to train the Lego sketch on one memory brick M. Overall, we adopted the same supervuue meta-learning training strategy as previous research (Cao et al. 2024] [023) Rae et al.) 2211)) which iteratively trains on large number of synthetic meta-tasks to acquire the basic sketching capabilities. The meta-tasks are automatically generated based on data streams with dif- ferent skewness under Zipf distributions, and each meta-task corresponds to storing and querying all items from a syn- thetic data stream into the memory block M. As shown in Algorithm Bl in the appendix, the ultimate goal of the meta-learning process is to optimize the parameters through gradient descent based on the query error of all items.
Considering the disorderliness of information caused by hash addressing in memory bricks, these stacked pieces of information can essentially be viewed as a set that satisfies permutation invariance (Kimura et al. 2024). Therefore, we employ a simple set prediction network, Deepsets (Za- heer et al. 2017). to implement Jscan for scanning and reconstructing global stream characteristics from specific MH(Z.). For practical efficiency, we take subset M Mas(ss) comprising one-tenth the size of the memory Mr(Z.)) as we find this fraction sufficient. This subset M H(z.) is then fed into Iscan. producing a reconstruction vector (*(():)-
During the training, we introduce a novel self-guide weight- ing loss that dynamically assigns weights to different error pvetric&Jacroo different meta-tasks, Previous loss functions L. (Cao al.. 2023 2024 Rae et al. 2019) simply employ average across batch b of meta-tasks T using only learnable weights (LW) (Kendall et al., 2018) for different error metrics. Such methods neglect the variability in task difficulty, causing larger errors to overshadow smaller ones across different meta-tasks. Our method resolves this prob- lem by using a "guide error" from a sketch competitor to weight different error metrics across meta-tasks dynamically, i.c. optimizing (error)² / (guide error)² ) Additionally, in- stead of using handcrafted sketch as competitor, the Lego sketch directly use the rule-based f' to guide the neu- ral prediction f", which is produced by D simultaneously for training efficiency, leading to the self-guided weighting loss L' This self self-guided weighting loss L' significantly enhances accuracy for large space budgets, effectively ad- dressing the issues of advantage diminished noted in earlier neural 5
Among the elements of 8H(*.)> the first two, *x(Z)) and
(n)
"H(a,)) regress to the explicit global characteristics n and a under the supervision of an auxiliary reconstruction loss L"
[a)
The remaining elements reconstruct implicit characteristics guided by the main loss L' described in Section 3.2
SH(().)) "H(m:)) H((a:) = =S(M = Iscan (M H(t.))
(n)
Ensemble Decoding (D). Given query item x; and its corresponding m, and 2ú we concatenate m; and v; as the foundation, supplementing them with stream characteristics $H((=.) These vectors are then fed into a decoding network Gdoe to obtain a neural prediction f.. Benefiting from the newly designed and more interpretable MANN architecture
Co = 1 ETE()) LW (AAE(")) MSE(())
L'= = 16] ETEM LW
1
AAE(F'2 A MSE(()) AAE(F"?> ARE(""?" MSE(f")
*In real world streams, the frequency distributions exhibit skewed patterns, which are often approximated by the Zipf distri- butions (Babcock et al. [2002] (Yngg & Zhu] (2066) Breslau et al. 1999 Adamic 2000) using varied parameter known as skew- ness as detailed in Appendix
Additionally, we incorporate an auxiliary reconstruction loss
$AAE= 1 Σ li. - SAk: = Σ" li. -f1//4 MSE- 1 Σn 15. f/
n
"
5

---

Lego Sketch: A Scalable Memory-augmentedd Neural Network for Sketching Data Streams
C" in S, constituting the final loss L:
20.0
1.20a
17.5
L C' 0.1 L", where
15.0
1.15a
t 12.5
C" 1 EreMy LW MSE(s L
(n) R(aa) Hlm)) MSE (a) (Ma)) a))
10.0
1.10a w
7.5
1.05a
2.5
1.00a
20
40
60
80
100
3.3. Derivative with Lego Sketch as Core Structure
As representative of derivatives (Zhou et al., 2018 Roy
Figure 5: Sub-skewness a'
jet al.
2016;
Hsu et al. 2019. Aamand et al. 2024 Zhao
cct al.
2023 Gao et al. 2024b), the clastic sketch deriva-
Table 2: Real Datasets Summary
tive (Ynng al. 2018) comprises two primary components:
Name
Aol
Lkml
Kosarak
Wiki
Webdocs
a heavy part with filtering buckets for high-frequeney items
and a light part, typically a CM-sketch, for low-frequency items. This design reduces estimation errors by effectively segregating high- and cow-freuuency items during data stor- age. We present case study of applying the framework of elastic derivative with the Lego sketch as the core. Results from Sections and 5.3 demonstrate its superior accuracy and robustness, demonstrating the potentials of the Lego sketch in future advancements.
N Domain
n
197,790 361,115
242,976 1,096,439
8,019,015
41,270
24,981,163
9,379,561
299,887.139
5,267,650
Word
Comm.
Click
Edit
Doc.
sequently, the expected sub-skewness as follows:
((ok,x)===>> (D.....))
As numerical simulation in Figure 5 upon excluding the top ten high-frequency items, the sub-skewness surround- ing other items closely approximates the overall skewness a. Given the massive volume of items in data streams, the Lego sketch thereby effectively transfers learned skew- patterns to each sub-stream, thus improving estimation accuracy. Also the experimental evidence in Section 5.2 in- cluding memory resizing exceeding 1400-fold: from single 100KB brick to a maximum of 140MB in Figure [6(c) (Wiki Dataset), underscores its powerful memory scalability.
4. Analysis
4.1. Domain Scalability Analysis
As detailed in the proof provided in Appendix E. Theorem 4.1 demonstrates that embedding vectors from different data domains adhere to the same distribution, confirming that the normalized multi-hash embedding technique is domain- agnostic. In Section [.2] the Lego sketch deploys across datasets from five distinct domains, as shown Table achieves consistently high accuracy.
4.3. Error Analysis
Theorem 4.1. Across all data items (ax} within any data domain X. the embedding vectors {vi} generated by the nor- malized multi embedding technique exhibit the same distribution.
Here, we give the error bound for the rule-based estimation A in Lego sketch as Theorem 4.3 and the detailed proof is provided in Appendix G
Theorem 4.3. The error of J for item x; is bounded by:
P(I."" " A 2 e x N) (e d2)
4.2. Memory Scalability Analysis
Here, the impact of memory scalability generalizability is assessed by quantifying the gap between the sub-skewness a' of sub-stream X' in each brick and the overall skewness of the entire stream X. Assuming the frequency ranking of an item 2; in X' is denoted by ri. and its corresponding sub-ranking in X' is denoted by r/, we can derive Theorem 4.2 the proof of which is in Appendix
In general, formulating error bound for pure neural architecture poses challenges, leading to scarcity of error analysis in prior research. The above analysis shows a wider margin compared to handcrafted sketch boundaries. This discrepancy primarily stems from the normalization within the embedding module, causing non-independent values in eq. Future work may explore adjustments the normalization approach or modeling the distribution of v; to further strengthen the error bound.
Theorem 4.2. Given K memory bricks, the sub-skewness o' around Tú in sub-stream X" is:
*4,x(D, a allog(1 + // /l/([ + 7.), where D~ G(1/K, (rx -() ~ 1B(r).1/K)
5. Experiment
5.1. Setup
D denotes the distance of ranking r between two data items, which are adjacent on the sub-rand ranking r' in same X", Con-
Datasets. Firstly, we employ five real datasets indicating irregular distributions in real applications, Aol (Pass et al.)
6

---

Lego Sketch: A Scalable Memory-augmenter Neural Network for Sketching Data Streams
CMS
CS
LCS
MS
Lego
D-CMS
D-Lego
4
8
8
AAE
AAE
AAE
AAE
2
4
1
1
2
0
0
0
2
0.25 0.50 0. 75 1.001.25 Budget(MBB
25 50
100 125
20
40
60
Budget(MB)
Budget(MBB)
Budget(MBB)
(a) Lkml (AAE)
(b) Kosarak (AAE)
(c) Wiki (AAE)
(d) Wehdocs (AAE)
3
3
4
3
ARE
ARE
ARE
ARE
2
1
1
2
0.25 0.50 0.75 1.00 1.25 Budget(MBB)
25
50
100 125 Budget(MB)
75
20
40 Budget(MBB
60
BMdget(MB)
(c) Lkml (ARE)
(f) Kosarak (ARE)
(g) Wiki (ARE)
(h) Webdocs (ARE)
Figure 6: Errors Four Real Datasets.
2006).
Kosarak (Bodon Wiki (Kunegis] 2013), and Webdocs (Lucchese et al.
Lkml (Homscheid et al. 2015).
sketch(LCS) (Aamand et al. 2024) which only utilizes prior knowledge of n without orthogonal add-ons, making it close variant to the core sketches. Additionally, we consider the latest neural sketch, the meta-sketch (MS) (Cao et al. 2023 2024), as a significant baseline, which renowned for exceptional accuracy in small space budgets. Also, we incorporate scalable memory module into the meta-sketch for memory scalability, facilitating comprehensive com- parison in different budgets. Finally, we evaluate the elastic derivative with Lego sketch, D-Lego, as detailed in Sec- tion 3.3 Accordingly, the elastic derivative with CMS, i.e., D-CMS Yang et al. 2018), considered the competitor.
2003
2004
These five datasets are widely used in sketch litera-
tures
(Roy et al. 2016: Cao et al. 2023 Hsu et al., 2019
Aamand et al. 2024) and encompass a variety of data stream domains and scales for comprehensive evaluation, as shown in Table 2 6 Secondly, we generate six synthetic data streams, each comprising 100, 000 distinct data items, con- forming the Zépf distribution within the skewness a range of [0.5, 1.5] to evaluate the robustness across different skew- nesses comprehensively. All datasets are evaluated using two most widely used error indicators (Cao et al., 2023 Yang et al. 2018 Zhou al. [2018] Roy al. 2016 Deng & Rafeei 2007), specifically Average Absolute Error (AAE) and Average Relative Error S
Parameters. The Lego sketch pretrained with million meta-tasks within the regular skewness range of [0.5, 1.0). It uses 8-layer Deep Sets networks for the Jsean and Jdees featuring a maximum hidden layer size of 32 and employing LeakyReLU for layer connectivity. The initial learning rate is set at 0.001, decreasing linearly to 0.0001. The aggregation threshold 3 consistently set at 10, 000. For all CMS and CS, we employ three hash functions, as standard practice suggests(Aamand al. 2024 Yang al. 2018).
Baselines. In our experiments, we select broad range of baselines for comprehensive evaluations. Key among these are the CM-sketch (CMS) (Cormode & Muthukrishhna 2005) and C-sketch (CS) (Charikar et al., 22002), the most widely used sketches, foundational to subsequent derivatives (Roy et al. 2016 Yang al.) 2018 Zhou et al., 2018 Hsu 2019 We also included the learned augmented C- et al.
Further details are available in the appendix C and code provided in supporting materials.
'Following previous works, we also tested the Aol dataset, where Lego Sketch demonstrated significant advantage. During the review process, the reviewers pointed out its anonymization flaw, Aol Aol log release)); ) therefore, we have excluded the results from experiments and ablation studies revised manuscript.
Budget. In line with previous works (Cao et al. 2023 2024
Rae et al., 2019), the space budget B is determined by the total size of K memory bricks M, which in our experiments is 100KB per brick M (di d2 5120). The budget
7

---

Lego Sketch: A Scalable Memory-augmentedd Neural Network for Sketching Data Streams
CMS
CS
LCS
MS
Lego
D-CMS
D-Lego
B
8
AAE
AAE
AAE
AAE
AAE
1
1.0
1.5
2.0
1.0
1.5
2.0
0.5
1.0
1.5
2.0
0.5
1.5
2.0
0.5
1.0
1.5
2.0
Budget(MB)
Budget(MB)
Budget(MB)
Budget(MB)
Budget(MB)
(a) a 0.5 (AAE)
(b) a = 0.7 (AAE)
(c)
0.9 (AAE)
(d) = 1.3 (AAE)
(c) a = 1.5 (AAE)
ARE
ARE
ARE
ARE
2
ARE
2
1
0.5 1.0
1.5
2.0
0.5
1.0
1.5
2.0
0.5
1.0
1.5
2.0
0.5
1.0
1.5
2.0
0.5
1.0
1.5
2.0
Budget(MB)
Budget(MB)
Budget(MB)
Budget(MB)
Budget(MB)
(f) 0.5 (ARE)
(g) 0.7 (ARE)
(h) 0.9 (ARE)
1.3 (ARE)
1.5 (ARE)
Figure 7: Synthetic Datasets
allocated for filtering buckets in D-CMS and D-Lo is set to one-fourth of B (Yang et al. 2018).
Query
Query
Through Thruug putt/epp)
Through Mutugghuu//oppp
80
5.2. Accuracy
In this section, we conduct comprehensive evaluations us- ing different space budgets on five real datasets in Figure 6, where the Lego sketch consistently outperforms all com- petitors in terms of AAE and ARE, offering superior space- accuracy trade-off. Taking the commonly used Lkml dataset in Figures 6(a) and [6() as an example, we analyze the space-accuracy trade-off characteristics of the Lego sketch and its competitors. CMS and CS, recognized as the most popular handcrafted sketches, demonstrate CMS's superior accuracy in large space budgets, while CS performs better in smaller space budgets. LCS, an adaptation of CS with prior knowledge of n, reduces errors in smaller budgets at the expense of accuracy in larger budgets. MS, leveraging purely neural architecture, significantly outperforms the aforementioned sketches in smaller spaces. However, at larger budgets, such as at 3,2MB, MS falls behind hand- crafted sketches
CMS
Lego
M5
CNS
Lego
MS
(a) CPU
(b) GPU
Figure 8: Throughput
advantage is observed in terms of AAE. For example, as illustrated in Figure 6(a) at budgets of 0.6 MB and 3.6 MB, the AAE of the Lego sketch is only 97% and 13% of that of MS. These results consistently demonstrate signifi- cant reduction in estimation errors across all budget levels, underscoring the effectiveness of our approach.
Moreover, the Lego sketch within framework of elastic derivative, abbreviated as D-Lego, is a case study in the derivative category, exhibiting a better space-accuracy trade- off. For example, at the 3.6MB budget, its AAE dramati- cally reduces an tiny value of 0.03, demonstrating signifi- cantly enhanced accuracy. Additionally, this version notably outperforms the elastic derivative with the traditional CM- sketch, abbreviated as D-CMS, maintaining a consistent lead of approximately 5-folds to 3-folds. These results highlights the immense potential of integrating derivative strategies with the Lego sketch as core sketch the future.
Notably, our Lego sketch, as a novel neural sketch, further addresses the drawbacks of meta sketches in large space bud- gets and comprehensively reduces estimation errors. Specif- ically in Figure 6(e) with the smallest budget of 0.6 MB, the ARE of the Lego sketch is only 0.93, which represents just 85% of the error of the neural architecture MS, and 21% % and 26% of the errors of the traditional CMS and CS, respectively. At the largest budget of 3.6 MB, the ARE fur74, reducing to just 21%, 46%, and 16% of the errors of MS, CMS, and CS, respectively. The similar
5.3. Robustness under Distributional Shift
To verify the robustness of the Lego sketch against potential distributional shifts across varying degrees of skewness, we
8

---

Lego Sketch; A Scalable Memory-augmented Neural Network for Sketching Data Streams
Abl1_e_
Abl3_ Sal__ccaning_s
Base
Embedding Module &. In the first and second ablation tests, we remove the learnable vector V and normalization opera- tion in the normalized multi-hash embedding, respectively. When using a fixed V for embedding instead of learn- able vector, the error increases significantly under higher budgets, highlighting the necessity of end-to-end training for accuracy prediction scenarios. Moreover, removing the normalization operation consistently leads to higher errors across all budgets, underscoring the role of L1 stability in maintaining stable memory increments for embedding.
Abi2_ / Normalization
Abl4_Loss_c
3
3
2
AAE
ARE
1
1
0
0
0.5
1.0
1.5
2.0
0.5
1.0
1.5
2.0
Budget(MB)
Budget(MBB
Scanning Module S. In the third ablation test, we removed the scanning module, which was newly introduced by the Lego Sketch. This change directly causes a significant rise in errors under small budgets, indicating that the novel scan- ning module S effectively captures the global characteristics of data streams through end-to-ent training. Consequently, it significantly improves frequency estimation accuracy for neural sketching in low-budget scenarios.
(a) 0.7 Syn Dataset (AAE)
(b) 0.7 Synthetic Dataset(ARE)
Figure 9: Ablation Study
also assess its accuracy under synthetic streams conform- ing to Zipf distributions with different skewness a. Due to space constraints, some experimental results are shown in Appendix A As shown in Figure 7 as the skewness a increases from a relatively low value of 0.5 to a high value of 1.5, the estimation errors of all sketches progressively rise. The meta-sketch and LCS exhibit poorer robustness; for instance in Figure [ at an extreme skewness of 1.5, their absolute errors predominantly exceed 8, surpassing the upper bound depicted even in large budgets. In contrast, the Lego sketch demonstrates strong estimation robustness with the skewness a increasing, ultimately performing compa- rably to the CM-sketch and surpassing all other baselines. Notably, the elastic derivative with Lego sketch (i.e. D- Lego) shows the best robustness, underscoring the immense potential of future research in derivatives based on Lego sketch.
Self-guided Weighting Loss L. The final ablation exper- iment replaces the self-guided weighting loss L' with the conventional loss L. used in previous work. We observe that without the self-guided weighting optimization, the accuracy of Lego sketch deteriorates under larger budgets, lead to higher errors in such scenarios. This demonstrates that the self- guideddd weighting loss effectively guides the model by dynamically reweighting different meta-tasks ac- cording to varying task difficulty during training, enabling a better space- accuracy trade-off.
6. Conclusion
In this work, we propose the Lego sketch, novel neural sketch crafted to overcome the scalability and accuracy chal- lenges encountered by existing neural sketches in real-world stream applications. Mirroring the sturdy and modular na- ture of Lego bricks, the Lego sketch pioneers a scalable memory-
5.4. Throughput
We evaluate the throughput of Lego Sketch's Store and Query operations the large-scale Wiki dataset using both CPU and GPU platforms. CMS, with its simple structure and high throughput, and MS serve as baselines for com- parison. As shown in Figure g the overall throughput of the Lego sketch is of the same magnitude as that of CMS, reaching millions on CPU and tens of millions with GPU acceleration. In contrast, compared to MS, the Lego sketch, with its more effective MANN architecture, significantly surpasses MS. For instance, the throughput for storing is up to 6.90 times higher and for querying is 12.47 times higher, on CPU, This shows the Lego sketch's 's capability to deliver accurate estimation while efficiently processing streams.
neural network capable of adapting to various data domains, space budgets, and offers favorable space-accurace trade-off, with ease and efficacy. Within the proposed framework of the Lego sketch, a suite of advanced techniques, including hash embedding, scalable memory, memory scanning, and a tailored loss function, collectively ensure the estimation accuracy of the Lego sketch. Exten- sive experiments demonstrate that the Lego sketch outper- forms existing handcrafted and neural sketches, while its potential integration with orthogonal add-ons holds promise in facilitating data stream processing.
5.5. Ablation Study
Figure 9 presents ablation studies conducted on two datasets, evaluating the impact of four techniques across three key modules of the Lego Sketch framework. The results are summarized as follows:
9

---

Lego Sketch: A Scalable Memory-augmentee Neural Network for Sketching Data Streams
Acknowledgements
Cao, Y., Feng, Y., Wang, H., Xie, X., and Zhou, S. K. Learn- ing sketch: A neural approach to item frequency esti- mation in streaming data. IEEE Transactions Pattern Analysis and Machine Intelligence, 2024.
We thank the reviewers for their constructive feedback dur- ing the review process. This work was supported in part by the National Natural Science Foundation of China under Grant 62472400, Grant 62072428, Grant 6227 1465, and in part by the Suzhou Basic Research Program under Grant SYG202338.
Charikar, M., Chen, K. C., and Farach-Colton. M. Finding frequent items in data streams. In ICALP, pp. 693-703, 2002.
Chen, P., Wu, Y., Yang, T., Jiang, J., and Liu, Z. Precise error estimation for aketch-based flow measurement. In Proceedings of the 2 ACM Internet Measurement Con- ference, pp. 113-121, 2021.
Impact Statement
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Cormode, G. and Hadjieleftheriou, M. Finding frequent items in data streams. Proceedings of the VLDB Endow- ment,
2008.
References
Cormode, G. and Muthukrishnan, S. An improved data stream summary: the count-min sketch and its applica- tions. J. Algorithms, 55(1):58-75, 2005.
Aamand, A., Chen, J., Nguyen, H., Silwal, S., and Vakilian, A. Improved frequency estimation algorithms with and without predictions. Advances in Neural Information Processing Systems, 36, 2024.
Cormode, G., Garofalakis, M. N., Haas, J.J and Jermaine, C. Synopses for massive data: Samples, histograms, wavelets, sketches. Foundations and Trends in Databases, 4(1-3):1-294, 2012.
Adamic, L. Zipf. power-law, pareto a ranking tuto- rial. http://www..ggg..cooo/scses///tp 2000.
Danihelka, I., Wayne, G., Uria, B., Kalchbrenner, N., and Graves, A. Associative long short-term memory. In International conference on machine learning, pp. 1986- 1994. PMLR, 2016.
Aghazadeh, A., Spring, R., LeJeune, D., Dasarathy, G., Shrivastava, A., and Baraniuk, R. G. MIS- SION: ultra large-scale feature selection using count- sketches. In ICML, volume 80, pp. 80-88. PMLR, 2018. URL / [BL/:tttp//prroeedinng mlr...r.....m press/ v80 htt//ghazzadel. 8a. html
Deng, F. and Rafiei, D. New estimation algorithms for streaming data: Count-min can do more. Webdocs. Cs. Ualberta. Ca, 2007.
Babcock, B., Babu, S., Datar, M., Motwani, R., and Widom, Models and issues in data stream systems. In PODS, pp. 1-16, 2002.
Estan, C. and Varghese, G. New directions in traffic mea- surement and accounting. In SIGCOMM, pp. 323-336, 2002.
Berinde, R., Indyk, P., Cormode, G., and Strauss, M. Space-optimal heavy hitters with strong error bounds. ACM Transactions on Database Systems (TODS), 35(4): 1-28, 2010.
Feng, Y., Cao, Y., Hairu, W., Xie, X., and Zhou, S. K. Mayfly: neural data structure for graph stream marization. In The Twelfth International Conference on Learning Representations, 2024. URL https:// openreview net. wwt. forum? 1d:nnnnnnnnnr 1
Bodon, fast apriori implementation. In FIMI, volume 3, pp. 63. Citeseer, 2003.
Gao, G., Ma, T. Huang. H., Sun, Y.-E.. Wang, H., Du. Y., and Chen, S. Scout sketch +: Finding both promis- ing and damping items simultaneously in data streams. IEEE/ACM Transactions on Networking, 2024a.
Breslau, L., Cao, Fan, L., Phillips, G., and Shenker, S. Web caching and zipf-like distributions: Evidence and implications. In INFOCOM, pp. 126-134, 1999.
Gao, G., Qian, Z.., Huang, H., Sun, Y.-E., and Du, Y. Tai- loredsketch: a fast and adaptive sketch for efficient per- flow size measurement. IEEE Transactions on Network Science and Engineering, 2024b.
Cao, Y.. Feng, Y., and Xie, X. Meta-sketch: A neural data structure for estimating item frequencies of data streams. Proceedings of the AAAI Conference on Artifi- cial Intelligence, 37(6);6916 0900696669694... Jun. 2023. doi: 10. ht1.://aai.3377.....5888. URL http:::ttts:/sssaatt
Goyal, A., III. H. D., and Cormode, G. Sketch algo- rithms for estimating point queries in NLP. In Tsujii,
10

---

Lego Sketch: A Scalable Memory-augmente Neural Network for Sketching Data Streams
J., Henderson, J., and Pasca, M. (eds.), Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Lan- guage Learning. EMNLP-CONLL 2012, July 12-14, 2012, Jeju Island, Korea, pp. 1093-1103. ACI,, 2012. URL
Kunegis, J. Konect: the koblenz network collection. In Pro- ceedings of the 22nd international conference world wide web, pp. 1343-1350, 2013.
Liu, J., Basat, R. B., De Wardt, L.., Dai, H., and Chen, G. Disco: A dynamically configurable sketch framework in skewed data streams. In 2024 IEEE 40th International Conference on Data Engineering (ICDE), pp. 4801 -814. IEER, 2024.
http:///aaaaaatooooooorroee h
Graves, A., Wayne, G., and Danihelka, I. Neural turing machines. arXiv preprint arXiv:1410.5401, 2014.
Graves, A., Wayne, G., Reynolds, M., Harley, T., Dani- helka, I., Brabska-Barwinska, A., Colmenarejo, S. G., Grefenstette, E., Ramalho, T., Agapiou, J., al. Hybrid computing using neural network with dynamic external memory. Nature, 538(7626::47147777 2016.
Liu, Y. and Xie, X. Xy-sketch: On sketching data streams at web scale. In Proceedings of the Web Conference 2021, pp. 1169-1188 2021.
Liu, Y. and Xie, X. A probabilistic sketch for summarizing cold items of data streams. JEEE/ACM Transactions on Networking, 32(2):2887-1302, 2023.
Gui, J., Song, Y., Wang. Z., He, C., and Huang, Q. Sk- gradient: Efficient communication for distributed ma- chine learning with data sketch. In 2023 IEEE 39th In- lernational Conference on Data Engineering (ICDE), pp. 2372-2388 2385. IEEE, 2023.
Lucchese, C., Orlando, S., Perego, R., and Silvestri, F. Web- docs: a real-life huge transactional dataset. FIMI, volume 126, 2004.
Homscheid, D., Kunegis, J., and Schaarschmidt, M. Private- collective innovation and open source software: Longi- tudinal insights from linux kernel development. In Open and Big Data Management and Innovation: 14th IFIP WG 6.11 Conference on e-Business, e-Services, and Society, 13E 2015, Delft, The Netherlands, October 13-15, 2015, Proceedings 14, pp. 299-313. Springer, 2015.
Ma, T., Gao, G., Huang, H., Sun, Y.-.., and Du, Y. Scout sketch: Finding promising items in data streams. In IEEE INFOCOM 2024-IEEE Conference on Computer Communications, pp. 1561-1570. IEEE, 2024.
Metwally, A., Agrawal, D., and EI Abbadi, Efficient com- putation of frequent and top-k elements in data streams. In International conference database theory, pp. 398- 412. Springer, 2005.
Hospedales, T., Antoniou, A., Micaelli, P., and Storkey, A. Meta-learning in neural networks: A survey. IEEE Iransactions on pattern analysis and machine intelligence, 44(9):5149-5169 2021.
Misra, J. and Gries, D. Finding repeated elements, Science of computer programming, 2(2):143-152, 1982.
Hsu, C.-Y., Indyk, P., Katabi, D., and Vakilian, A. Learning- based frequency estimation algorithms. ICLR, 2019.
Pass, G., Chowdhury, A., and Torgeson, C. picture of search. In Proceedings the 1st international conference on Scalable information systems, pp. 1-es, 2006.
Huang, H., Yu, J., Du, Y., Liu, J., Dai, H., and Sun, Y.-E. Memory-efficien and flexible detection of heavy hitters in high-speed networks. Proceedings of the ACM on Management of Data, 1(3):1-24, 2023.
Rae, J., Bartunov, S., and Lillicrap, T. Meta-learning neural bloom filters. In International Conference Machine Learning, pp. 527 52200. PMLR, 2019.
Ivkin, N., Rothchild, D., Ullah, E.. Stoica, I. Arora, R., al. Communication-efficcee distributed sgd with sketching. Advances in Neural Information Processing Systems, 32, 2019.
Roy, P., Khan, A., and Alonso, G. Augmented sketch: Faster and more accurate stream processing. In SIGMOD, pp. 1449-1463 2016.
Santoro, A., Bartunov, S., Botvinick, M., Wierstra, D.,, and Lillicrap, T. Meta-learning with ral networks. In International conference on machine learning, pp. 1842-1850. PMLR, 2016.
Kendall, A., Gal, Y., and Cipolla, R. Multi-task learning using uncertainty to weigh losses for scene geometry and semantics. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 7482-7491, 2018.
neu-
Shahout, R. and Mitzenmacher, M. Learning-baat heavy hitters and flow frequency estimation in streams. In 2024 IEEE 32nd International Conference on Network Proto- cols (ICNP), pp. 1-13. IEEE, 2024.
Kimura, M.. Shimizu, R., Hirakawa, Y., Goto, R., and Saito, Y. On permutation-invant neural networks, 2024.

---

Lego Sketch: A Scalable Memory-augmenteed Neural Network for Sketching Data Streams
Spring, R., Kyrillidis, A., Mohan, V., and Shrivastava, A. Compressing gradient optimizers via count-sketches. In International Conference Machine Learning, pp. 5946- 5955. PMLR, 2019.
Zhang, H., Zhao, P., Miao, X., Shao, Y., Liu, Z.,, Yang, T., and Cui, B. Experimental analysis of large-scale learnable vector storage compression. arXiv preprint arXi::2311.1577 2023.
Talukdar, P. P. and Cohen, W. W. Scaling graph-based semi supervised learning to large number of labels using count-min sketch. In AISTATS, pp. 940-947. 947. JogR.org, 2014.
Zhao, F., Khan, P. I., Agrawal, D., Abbadi, A. E., Gupta, A., and Liu, Z. Panakos: Chasing the tails for multi- dimensional data streams. Proceedings of the VLDB Endowment, 16(6):1291-1004 2023.
Tang, N., Chen, Q.. and Mitra, P. Graph stream summariza- tion: From big bang to big crunch. In Proceedings of the 2016 International Conference on Management of Data, pp. 1481-1496, 2016.
Zhao, X., Xie, X., and Jensen, C. S. Higgs: Hierarchy- guided graph stream summarization. In 2025 IEEE 41th International Conference Data Engineering (ICDE). IEEE, 2025.
Ting, D. Count-min: Optimal estimation and tight error bounds using empirical error distributions. In Proceed- ings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2319-2328, 2018.
Zhou, Y., Yang, T., Jiang, J., Cui, B., Yu, M., Li, X., and Uhlig, S. Cold filter: A metaaframework for faster and more accurate stream processing. In SIGMOD, pp. 741- 756, 2018.
Tito Svenstrup, D., Hansen, J., and Winther, O. Hash em- beddings for efficient word representations. Advances in neural information processing systems, 30, 2017.
Vinyals, O., Blundell, C., Lillicrap, T., Wierstra, D., al. Matching networks for one shot learning. Advances in neural information processing systems, 29, 2016.
Weston, J., Chopra, S., and Bordes, A. Memory networks. arXiv preprint arXiv: 1410.3916, 2014.
Yang, T., Jiang, J., Liu, P., Huang, Q., Gong, J., Zhou, Y., Miao, R., Li, X., and Uhlig, S. Elastic sketch: Adaptive and fast network wide measurements. In Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication, pp. 561-575, 2018
Yang, Y. and Zhu, J. Write skew and zipf distribution: Evidence and implications. ACM Trans. Storage, 12(4): 21:1-21:19, 2016.
Yu, M., Jose, L.,, and Miao, R. Software (Defined) (Traffic) measurement with (OpenSketch). In 10th USENIX Sym- posium on Networked Systems Design and Implementa- tion (NSDI 13), pp. 29-42, 2013.
Zaharia, M., Xin, R. S., Wendell, P., Das, T., Armbrust, M., Dave, A., Meng, X., Rosen, J., Venkataraman, S., Franklin, M. J., al. Apache spark: unified engine for big data processing. Communications of the ACM, 59
65, 2016.
Zaheer, M., Kottur, S., Ravanbakhsh, S., Poczos, B., Salakhutdinov, R. R., and Smola, A. J. Deep sets. Ad- vances in neural information processing systems, 30, 2017.
12

---

Lego Sketch: A Scalable Memory-augmenteed Neural Network for Sketching Data Streams
CMS
CS
LCS
MS
Lego
D-CMS
D-Lego
AAE
AAE
ARE
ARE
0.5
1.0
1.5
2.0
0.5
1.0
1.5
2.0
0.5
1.0
1.5
2.0
0.5
1.0
1.5
2.0
Budget(MBB
(Mdget(MB)
Budget(MB)
Budget(MB)
(a) a (AAE)
(b) a (AAE)
(c)
0.7 (ARE)
(d)
(ARE)
Figure 10: Absent Results of Synthetic Datasets
Algorithm 3 Training Algorithm
1: Input: Model(K 1) with all learnable parameters 0
2: while reaching the max step do
3: Generating a batch
meta-tasks
4: for meta task T E do
5: Clear the memory M
6: Store all items in T .ssupport set
7: Query all frequencies of distinct items in T .query set end for
8:
9:
Calculate L across all frequencies estimations of
10: Backward propagate through AC100
11: Update all parameter
end while
A. Additional Experimental Results
Figures 10 are provided herein, excluded from the main text due to space constraints.
B. Limitations
Lego sketch, like other existing neural sketches (Cao et al. 2024 2023), faces challenges in error analysis due to the limited interpretability of deep learning techniques (MANN) they employ. While we provide an initial error analysis for Lego sketch, it does not yet match the tightness of the error bounds achieved by handcrafted sketches. Future work should focus improving analysis techniques for neural sketches address this gap. Furthermore, given the broad applicability of sketching techniques, extending the scalable and accurate architectural innovations of Lego sketch to related areas such as graph stream summarization (TTng et al.) 2016 Feng et al. 2024 Zhao et al.) 2025) or vector compression (Ivkin et al.)
2019 Spring et al. 2019 Gui et al. 2023 Zhang et al. 2023 represents a promising direction for future research.
C. Parameter settings
In the embedding module ε, the dimension of the learnable vector is to 80 and all values V are constrained 1] to ensure numerical stability during decoding processes, where = 0.001. I, is set within [1000, 50000] to encompass broad spectrum of data stream scenarios. IN. the other hand, varies up to 10 times the minimum stream length permissible by current n and alpha, ranging from |minlength, 10 x minlength]. All experiments run at a NVIDIA DGX workstation with CPU Xeon-8358 (2.60GHz, 32 cores), and 4 NVIDIA A100 GPUs (6912 CUDA cores and 80GB GPU memory on each GPU). The training time for a single Lego sketch approximately 48 hours, and the relevant code is provided the supporting materials.
13

---

Lego Sketch: A Scalable Memory-augmenteed Neural Network for Sketching Data Streams
D. Zipf Distribution
Definition D.I. The (a) distribution describes the pattern between the frequency ratio pt and the ranking 7; (counting from to of items as below:
P; r
where
The is parameter indicating the skewness of Zipf distribution among the data stream. Thus given the ranking r; of the item F3 and the stream length N, its frequency can be calculated fi Np, NC
E. Proof of Theorem 4.1
Theorem E.1. Across all data items {x:} within any data domain X, the embedding vectors {vi} generated by the normalized embedding technique exhibit the same distribution.
Proof. We can divide the normalized multi-hash embedding technique (x:;) into two stages follows.
o = (VHl(z))) VHa(m.)..... VHLa (a.))
and
0/2
Given that the hash functions H uniformly distribute outputs for any given input, each component of the vector vy associated
with any input 2; is independently and identically distributed (i.id.), with each Plula V = dj 1 Consequently. for any data item, the vector v can derived by normalizing vy as 0; = v Σラ d'y. under the same probability condition Plul, = Vi]+ -.- Therefore, across all data items within any data domain X, the resulting embedding vectors e adhere to consistent distribution, as determined by the normalized multi-hash embedding technique.
F. Proof of Theorem 4.2
Theorem F.1. Given K memory bricks, the sub-skewness de around r, sub-stream X' is as follows:
D d x a + //loo(( + 1/2
r/
where D G(L/K), (r+ r() NB(r', 1/K)
D denotes the distance of ranking between two data items, which are adjacent on the sub-ranking r' in same X'. Conneequently, the expected sub-skewness is as follows:
D Y5
E(a' ( Σ
Σ
log(1 + P) (K 1)rctD-r1-1 1
D=lrmm!! log(1 + 3) K(D+r.) -111
Proof. When the Zipf distribution p; = is transformed into a log-log scale, the relation between log p. and log ry becomes linear, i.e. log log C' a log r; Here, manifests the negative slope of the line, illustrating the skewness in of data stream frequencies. We therefore derive the a/,, к by inferring the negative slope between frequencies log and the sub-ranking log Consider a random variable D that denotes the distance of rank r, between two data items loaded into the same sketch which are adjacent according r'. Without losing generality, we define two items x; and xy satisfying the aforementioned adjacency relationship. Then, we can get the following correspondence:
rj = ry D and r' = r
14

---

Lego Sketch: A Scalable Memory-augmentee Neural Network for Sketching Data Streams
In that case, the negative slope on log-log scale be calculated in the following way characterize the dz K
(og( log(p:) o lr'( (r) log(r' + +1) log(r;) log(1 + p.
log( (r;+ log( (m.)a
log(1 + P
Given the vast number of data items in the data stream, from the perspective of specific sub-stream, the procedure of uniformly distributing data items across K matrices using hash function can be approximated a Bernoulli process with probability of K. Thus D obeys a geometric distribution with parameter K i.e. D ~ G( ,nd rr obeys pascal distribution.ice. (r: - rf) ~ NB(r,, R)
G. Proof of Theorem 4.3
Theorem G.1. The error of rule-based estimation f for item zạ is bounded by: P(] fil 2 EX N) (e d2)
Proof. Let of be the k-th value of the embedding vector for the item æ; Rd and I.j.k be Bernoulli random variable indicating if the item z2 and the item 2; is addressed the same address across d2 slots for the uf. then:
E E d
Recalling the storing operation shows that the error of f. all comes from the address conflict between different of thus:
Injjk * Sj * v
K. 2 Si and vk (J:" Si S
j=ljzi
Ii,jk * fg * ur
f - - k= 1.jiti
of
Considering the normalization operation acting the embedding vectors, the expectation of the error can be expressed as:
EJA"" " fil
n
EL * ff
E
N
21
d2
According to Markov's inequality we have:
P( " - 11 = Elji" - fil
< (e* d2)
cN
15


Reviews:
[{"review_id": "1FloMPGSNW", "reviewer": "Reviewer_MS4A", "summary": "This paper introduces the Lego Sketch, a neural network-augmented sketch for frequency estimation. The sketch consists of several learnable components: a variant of the hash embedding layer, a \"memory scanning\" module that estimates global characteristics of the stream, and an \"ensemble decoding\" module that returns an estimated item frequency using a decoder network. The design of the Lego Sketch allows for the size of the memory data structure to be modified without retraining the learnable components of the sketch. The empirical evaluation compares the proposed sketch against several classical and learned baselines, demonstrating improved frequency estimation at lower memory budgets.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback! Below, we address your concerns in detail.\n\n## Other Comments Or Suggestions:\n\n### Reply to \n> The legibility of the figures in Sec. 5 should be improved. \n\n\n\nThank you for your suggestion. We will improve the readability of the figures accordingly.\n\n## Questions For Authors:\n\n### Reply to  \n>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?\n\nThe 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.\n\n|   LKML Dataset, AAE    | 600KB  | 1100KB | 1600KB | 2100KB | 2600KB | 3100KB | 3600KB |  \n|------|------|------|------|------|------|------|------|\n| Lego Sketch(+20KB) | 2.55 | 1.67 | 1.03 | 0.61 | 0.3  | 0.18 | 0.11 |\n| CM  Sketch | 6.75 | 2.58 | 1.33 | 0.78 | 0.5  | 0.35 | 0.25 |\n| C  Sketch  | 5.36 | 2.95 | 1.95 | 1.41 | 1.08 | 0.85 | 0.69 |\n\nGenerally, 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.\n\n### Reply to  \n>Question2：What is the numerical precision used in the experiments reported in the submission?\n\nLego Sketch uses the default 32-bit precision, and with only 5K parameters, the memory overhead is negligible.\n\n### Reply to \n> 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?\n\n\nNeural 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.\n\nFor 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.\n\nFollowing 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. \n\n\n|  LKML Dataset, AAE    | 600KB  | 1100KB | 1600KB | 2100KB | 2600KB | 3100KB | 3600KB |  \n|------|------|------|------|------|------|------|------|\n| Lego Sketch(+20KB, 32bits) | 2.55 | 1.67 | 1.03 | 0.61 | 0.3  | 0.18 | 0.11 |\n| Lego Sketch(+10KB, 16 bits) | 6.23 | 2.29 | 1.05 | 0.61 | 0.3  | 0.18 | 0.11 |", "claims_and_evidence": "The main claim in the paper is that the proposed sketch improves on previously proposed approaches for the frequency estimation task. This claim is supported by the empirical evaluation, which shows that the Lego Sketch improves on both \"handcrafted\" sketches and the neural network-augmented Meta-sketch in both absolute and relative error metrics.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are reasonable.", "theoretical_claims": "I did not check the correctness of the paper's theoretical claims.", "experimental_designs_or_analyses": "-", "relation_to_broader_scientific_literature": "This paper is related to the literature on memory efficient sketching algorithms for frequency estimation in data streams, and to more recent work on neural network-augmented sketching methods.", "essential_references_not_discussed": "-", "other_strengths_and_weaknesses": "-", "other_comments_or_suggestions": "- The legibility of the figures in Sec. 5 should be improved. With the current scaling of the y-axis, it is difficult to distinguish between the accuracy curves in several subplots.", "questions_for_authors": "1. At lower memory budgets, the memory overhead of the sketch's neural network components becomes a larger fraction of overall memory usage. This is of particular concern when deploying the sketch on resource constrained edge devices. 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?\n2. Given the goal of reducing memory usage, it is natural to consider using lower precision numerical representations. What is the numerical precision used in the experiments reported in the submission?\n3. Following up on the previous question, 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?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uPutwvEuqs", "reviewer": "Reviewer_EjyL", "summary": "This paper proposes a method for estimating the frequency of items in a data stream by means of sketching of embedding vectors of the items. It claims scalable memory use by means of multiple \"bricks\". It compares with hand-crafted and neural sketch methods on a number of datasets.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback! We have provided responses below and would be happy to engage in further discussion if needed.\n\nNeural 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.\n\nMore 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.\n\nLego 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.\n\nMoreover, 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.", "claims_and_evidence": "The proposed method is found to have consistently lower error metrics as a function of memory budget relative to the competing methods, on a number of datasets. It is also found to have superior robustness to distribution shift on synthetic datasets.", "methods_and_evaluation_criteria": "I am not familiar with the datasets in this area, but the metrics are simple and reasonable.", "theoretical_claims": "The proof of Theorem 4.1 appears correct.", "experimental_designs_or_analyses": "I am not expert in this area, but all experiments seem sound. I do not find any issues.", "relation_to_broader_scientific_literature": "I am not an expert on sketching. Thus, I cannot say much on the novelty of the approach, the benchmarks, the competition and the state of the art.\n\nHowever, simply by reading the method, it is hard to see that this is a novel method. Every component is very simple. For example, the authors claim to introduce a novel \"normalized multi-hash embedding\". But this is just some standard embedding followed by some standard hashing followed by normalization. It is extremely difficult to imagine that this is novel. Same goes for all components.\n\nDespite not seeing any novel idea, I rate the paper with weak accept, simply because of my lack of expertise on the subject.\n\n## Post-Rebuttal\n\nGiven my lack of familiarity with the subject and the positive scores of the other reviewers, I am keeping my score.\n\nHowever, on my concern on novelty, I strongly advise the authors to revise their manuscript according to the post-rebuttal discussion and according to their commitments: That they will specify the technical novelty of each component and of the entire approach relative to the state of the art. Not just qualitative properties of the methods, but in terms of ideas, methods and algorithms. For example, \"Scaling\" an existing idea is not really new.", "essential_references_not_discussed": "As I am not an expert on hashing, I cannot say if essential references are missing.", "other_strengths_and_weaknesses": "The text is very well written and easy to follow.", "other_comments_or_suggestions": "None.", "questions_for_authors": "None.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sIR83c5QFn", "reviewer": "Reviewer_m2XT", "summary": "In this paper, authors have proposed the Lego Sketch, a novel neural sketch designed for data streams. LegoSketch utilize hash embeddings, scalable memory (spread the total space budget across multiple memory blocks, and avoid retraining), memory scanning, and ensemble decoding. During the training phase, the authors have also introduced a self-guided weight loss.\nLegoSketch are compared with Count-Min, Count Sketch, Meta-Sketch, D-CMS (Elastic Sketch?) and Learned Augmented Count-Sketch on five real-world datasets and six synthetic data streams (following Zipf distribution but with different skewness). As shown in Figure 6, Lego Sketch has achieved 12% - 80% lower estimation errors. In addition, under distribution shift,  Lego Sketch has demonstrated much better robustness compared to previously learned linear sketch (Meta-Sketch and Learned Augmented Count Sketch).", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and constructive feedback! We have addressed your concerns below and are happy to discuss further if needed.\n## Claims \n### Reply to \n> ...I agree that use sketches to reconstruct global statistic... There are such studies.....\n\nThank 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. \nThat 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.\n\n### Reply to \n> While Lego Sketch has shown good accuracy in practice, from the theory side, it does not offer \"superior space-accuracy trade-offs\"..\n\nAs 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. \n\n## References:\n### Reply to \n>Add references to insertion-only model and consider to add discussions on the streaming model for LegoSketch.\n\nLego 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).\n\n### Reply to \n> ... The author should also consider to add references [1-3].\n\nAs 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).\n\nFollowing 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.\n\n### Reply to \n>Add discussion on Shahout, \"Learning-based heavy hitters and flow frequency estimation in streams.\"\n\nThank 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.\n\n## Other Comments Or Suggestions:\n### Reply to  \n> I prefer the authors to use the original name of Elastic Sketch.\n\nThank you. We will adopt the original naming convention and refer to them as Elastic Sketch (CMS/Lego) to improve clarity.\n\n## Questions:\n### Reply to \n\n>Discussion on whether memory block size can be determined based on frequency or cardinality.\n\nWe 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.\n\nIndeed, memory block size does not have to be determined solely by cardinality. \nA 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.\n\n## Ethical Concerns：\n### Reply to\n>  AOL dataset has leaked user information...\n\nThank you for pointing this out! \nThis 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.", "claims_and_evidence": "The methodology is sound and I find most of the claims to be supported.\nHowever, there are a few claims that are problematic.\n\n1) At page 4, the authors claim that \"handcrafted sketches face challenges in reconstructing stream global characteristics from the compressed storage\". I agree that use sketches to reconstruct global statistic and utilize the statistic to improve query accuracy is challenging. There are such studies. I think these works need to be discussed in the paper.\nPlease see: Ting, Daniel. \"Count-min: Optimal estimation and tight error bounds using empirical error distributions.\" SIGKDD 2018, and Chen, Peiqing, et al. \"Precise error estimation for sketch-based flow measurement.\" IMC 2021.\n\n2) Based on Theorem 4.3: $P(Err > \\epsilon N) < (\\epsilon d_{2})^{-1}$. If we denote the failure probability to be $\\delta$, then $d_{2}$ is $(\\epsilon \\delta)^{-1}$. To solve the frequency estimation problem, the total space required for lego sketch is $K$ $d_{1}$ $(\\epsilon \\delta)^{-1}$ which is larger than the $1/\\epsilon log(1/\\delta)$ space requirement for Count-Min and Count Sketch. While Lego Sketch has shown good accuracy in practice, from the theory side, it does not offer \"superior space-accuracy trade-offs, outperforming existing Sketches\" (in abstract).", "methods_and_evaluation_criteria": "The evaluation looks good to me. and lego sketch has demonstrate high accuracy in different data domains.", "theoretical_claims": "I didn't not check the proofs in detail, but the theorem 4.1-4.3 are sound.", "experimental_designs_or_analyses": "Is D-CMS (page 6) referring to Elastic Sketch?", "relation_to_broader_scientific_literature": "Although some of the techniques are not new, given the strong accuracy advantage of Lego Sketch compared with other learned sketches (Meta Sketch and Learned Augmented Sketch), this work can spark novel research directions in scalable, modular neural architectures for real-time data stream processing.", "essential_references_not_discussed": "This paper has several foundational work in this space. Please add references to data summaries in the insertion-only model (e.g., MG summary, SpaceSaving, Lossy Counting), and consider to add discussions on the streaming model for LegoSketch (insertion-only, turnstile, bounded deletion).\n\nIn section 3.3, the author has mentioned sketches using filtering framework to separate cold and hot items and discussed Elastic Sketch. The author should also consider to add references to related works [1-3].\n\nIn addition to Learned Augmented Count Sketch and Meta Sketch, please also add discussion on learning-based frequency estimation [4].\n\n[1] Roy, Pratanu, Arijit Khan, and Gustavo Alonso. \"Augmented sketch: Faster and more accurate stream processing.\" Proceedings of the 2016 International Conference on Management of Data. 2016.\n[2] Zhou, Yang, et al. \"Cold filter: A meta-framework for faster and more accurate stream processing.\" Proceedings of the 2018 International Conference on Management of Data. 2018.\n[3] Zhao, Fuheng, et al. \"Panakos: Chasing the tails for multidimensional data streams.\" Proceedings of the VLDB Endowment 16.6 (2023): 1291-1304.\n[4] Shahout, Rana, and Michael Mitzenmacher. \"Learning-based heavy hitters and flow frequency estimation in streams.\" 2024 IEEE 32nd International Conference on Network Protocols (ICNP). IEEE, 2024.", "other_strengths_and_weaknesses": "S1. The methodology of Lego Sketch is sound.\n\nS2. The authors have conducted extensive experiments and demonstrate the strong estimation accuracy of Lego Sketch.\n\nS3. Comparing to other learned sketch, LegoSketch is both robust to distribution shift through hash embedding and avoid diminishing return using self-guided loss.\n\nW1. Some of the claim are not supported. (see `Claims And Evidence`)\n\nW2. Missing important references.", "other_comments_or_suggestions": "If D-CMS is Elastic Sketch, then I prefer the authors to use the name proposed by the original author.", "questions_for_authors": "1) At the Scalable Memory section, the authors state \"using a hash function to uniformly distribute items in streams across these bricks.\" The uniform distribution is on the cardinality and not on the frequency. Should the memory block size be dependent on the item's aggregated count (i.e., have memory block of varying sizes and use larger block for larger sub-stream)? I can also see the argument for it to be only dependent on cardinality, but I'm curious about the authors opinion.\n\n2) Please also see W1 and W2.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_flag": "Flag this paper for an ethics review.", "ethics_expertise_needed": ["Privacy and Security"], "ethical_review_concerns": "Given AOL dataset has leaked user information (See https://en.wikipedia.org/wiki/AOL_search_log_release), can experimental results based on AOL be included in the paper?"}}, {"review_id": "bsOCRkXSpe", "reviewer": "Reviewer_o8J2", "summary": "The paper presents a new approach to solving the frequency estimation problem on a data stream using small space. The idea is to use a neural network to create a sketch that is tuned to the distribution of the input stream. Experiments show that the average frequency error of the approach is lower than competing randomized sketches, including a recent learning-based approach.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback! We have addressed your concerns as below and welcome any further discussion should you have additional questions.\n\n## Comparison to insertion-only streams algorithm like Misra-Gries\n\n### Reply to \n>...counting-based sketches are often superior for insertion-only streams...\n\n\nCounter-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). \n\nSo, 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.\n\nThe key differences between the two methods are summarized in the table below, based on Cormode’s paper. \n\n\n|**Aspect**|**Counter-Based Methods**| **Sketch-Based Methods**|\n|-|-|-|\n|**Stream Type**|Insertion-only streams.| Dynamic streams (insertions, deletions, weights). |\n|**Primary Use Case**| Identify frequent items (heavy hitters).| Estimate frequency of any item (supports queries). |\n|**Data Structure**| Explicit counters for tracked items.| Compact 2D array with hash-mapped counters.|\n|**Handles Deletions**|No.| Yes.|\n|**Supports Weights**|Limited.| Yes (positive/negative weights).|\n|**Flexibility**|Optimized for tracking frequent items.|Extendable to quantiles, entropy, inner products.|\n|**Examples**| Misra-Gries, SpaceSaving, LossyCounting.|Count-Min Sketch, CountSketch.|\n|**Strengths** | High precision, low space, fast updates. |Versatile, handles deletions, broader applications.|\n|**Weaknesses**|Limited to insertions. |Higher space/time costs;|\n|**Common Error Metric**|ARE (Average Relative Error), AAE (Average Relative Error)  | ARE, AAE  |\n\n\n\n## Methods And Evaluation Criteria:\n### Reply to\n> ... This error measure becomes questionable ... since small errors on non-occurring elements will tend to dominate.\n\nWe 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.\n\nMoreover, 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.\n\n\n|CM Sketch |Syn stream (skewness$ \\alpha=0.6$) |Syn stream (skewness$\\alpha=0.8$)|Syn stream (skewness$\\alpha=1.0$)|Syn stream (skewness$\\alpha=1.2$)|  Syn stream (skewness$\\alpha=1.4$)|\n|-|-|-|-|-|-|\n|AAE 10K occurring elements|2.98|1.87|1.33|1.04| 0.89|\n|AAE 10K non-occurring elements|3.09|1.88|1.31|1.05| 0.89|\n|ARE 10K occurring elements|0.70|0.49|0.41|0.40| 0.36|\n|ARE 10K non-occurring elements (Infeasible)|n/a|n/a|n/a|n/a| n/a|\n\n\n## Other Comments Or Suggestions:\n### Reply to \n> The comment (page 4) that sketches typically do not consider skew is misleading...\n \nThank you for pointing this out. We agree that our original phrasing could be clearer in explaining how existing sketches handle skewness.\n\n\n\nWhile 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.\n\n\nWe will revise the text for clarity:\n\n\"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.\"\n\n## Questions For Authors:\n### Reply to \n> Would your approach be able to support merging of sketches? \n\n 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.", "claims_and_evidence": "The claim that the proposed sketch outperforms existing sketches can be questioned since there is no comparison to the class of counting-based sketches such as Misra-Gries.\n\nThe authors have a point that randomized linear sketches are usually not compared to deterministic sketches in the literature, and this can be justified in some application scenarios where the power of linear sketches is needed. I think the suggestion to mention deterministic sketches such as MG, and include a discussion of when they are applicable, is acceptable.", "methods_and_evaluation_criteria": "The choice of error measures can be debated since an average is taken over the domain from which stream elements come. This error measure becomes questionable when the size of the domain is much larger than the size of the sketch since small errors on non-occurring elements will tend to dominate.", "theoretical_claims": "I did not check the proofs in the appendix but have no reason to suspect any errors.", "experimental_designs_or_analyses": "The experiments seem sound.", "relation_to_broader_scientific_literature": "While the paper makes a detailed comparison to related, hashing-based sketches, it is known that counting-based sketches are often superior for insertion-only streams, especially for datasets that are skewed and where the distribution over time is relatively stable. Furthermore, these sketches are mergeable.", "essential_references_not_discussed": "I would like to see a comparison to Misra-Gries and related sketches, e.g., the implementation in the DataSketches library (https://arxiv.org/abs/1705.07001). Such algorithms should be superior for large domains since items with no occurrences will alway have an estimate of zero.", "other_strengths_and_weaknesses": "Nothing particular comes to mind.", "other_comments_or_suggestions": "The comment (page 4) that sketches typically do not consider skew is misleading: As shown by Charikar, Chen, and Farach-Colton CountSketch performs better for skewed distributions. Similar results are known for Count-Min sketch.\n\nThe use of three hash functions for CS is further supported by https://icml.cc/virtual/2021/poster/9691", "questions_for_authors": "Would your approach be able to support merging of sketches? This would make it applicable outside of streaming settings.\n\nUpdate after rebuttal:\nRegarding mergeability I am not sure I managed to convey to the authors what my concern was. If the same models are used to two sketches they are of course mergeable, but in general you may want to use different models for different parts of a dataset, to exploit that they have different characteristics. However, merging sketches having different models seems difficult. It would be good to have some discussion of this aspect.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper proposes a modular, memory-augmented neural network architecture for frequency estimation on data streams. There were some concerns raised about the novelty of the proposed approach, and comparison to work in the insertion-only model such as Misra-Gries. On further discussion, the reviewers were generally comfortable with the comparison baselines, provided some more discussion is added to the paper. Regarding novelty, though the paper uses existing components, it achieves good results in practice, and the resulting modular framework could be useful for future work. Therefore, I recommend the paper to be accepted.
Decision: Accept (poster)