Meta-sketch: A Neural Data Structure for Estimating Item Frequencies of Data Streams
Authors: Yukun Cao
Yuan Feng
Xike Xie
Venue: NeurIPS 2022 Submitted (2022)
Keywords: Data streams
Sketches
Meta-learning
Memory-augmented neural network

Abstract: To estimate item frequencies of data streams with limited space, sketches are widely used in real applications, including real-time web analytics, network monitoring, and self-driving. Sketches can be viewed as a model which maps the identifier of a stream item to the corresponding frequency domain. Starting from the premise, we envision a neural data structure, which we term the meta-sketch, to go beyond the basic structure of conventional sketches. The meta-sketch learns basic sketching abilities from meta-tasks constituted with synthetic datasets following Zipf distributions in the pre-training phase and can be fast adapted to real (skewed) distributions in the adaption phase. Extensive experiments demonstrate the performance gains of the meta-sketch and offer insights into our proposals.


Meta-sketch: A Neural Data Structure for Estimating Item Frequencies of Data Streams
Anonymous Author(s)
Affiliation Address email
Abstract
To estimate item frequencies of data streams with limited space, sketches are widely used in real applications, including real-time web analytics, network monitoring, and self-driving. Sketches can viewed as a model which maps the identifier of a stream item to the corresponding frequency domain. Starting from the premise, we envision a neural data structure, which we term the meta-sketeh to go beyond the basic structure of conventional sketches. The meta-sketch learns basic sketching abilities from meta-tasks constituted with synthetic datasets following Zipf distribu- tions in the pre-training phase, and can be fast adapted to real (skewed) distributions in the adaption phase. Extensive experiments demonstrate the performance gains of the meta-sketch and offer insights into our proposals.
3
5
7
Introduction
11
12 Estimating item frequency basic topic in data stream processing, which finds applications in the fields of networking, databases, and machine learning, such as real-time data analyzing (TA)) network traffic monitoring 75 natural language processing infinite data streams, a common class of solutions [5) use compact structure taking sublinear space for counting the number of occurrences of each stream item, called the sketch.
13
and search ranking (9) Towards
15
16
17
Under the prevalent evidence of skewed distributions in data streams, basic sketches achieve the space compactness by hashing and approximately aggregating stream items. Basic sketches, including CM-sketch [0]. C-sketch [11] and CU-sketch [12), use 2D array counters as the core structure. To optimize the sketching performance, there arise augmented sketches [13]14), which attach filters to basic sketches, to capture the preliminary patterns of skewed distributions (e.g., high/low-frequenee items). By separately maintaining the filtered gigh/low-frequence items, augmented sketches strive
19
21
22
23 to eliminate the estimation error incurred by hash collisions between the high- and low-frequency
24 items. Further, learned augmented sketches (15) improve the filters of the augmented sketches by memorizing short-term hige/uow-rr items via pre- rre-trained neural network (NN in short) 26 classifier. But it clear how the pre-trained NN can be adapted dynamic streaming scenarios. where the correspondence between items and frequencies varies. In a nutshell, sketches are structures compactly summarizing stream distributions to count item frequencies with limited space budgets.
25
27
28
29 From the retrospective analysis of sketches, an observation can be drawn that the evolution of sketches conforms with the exploitation of data distributions. is thus natural evolution consider 31 a sketch that generally and automatically captures more distribution patterns with limited space
30
32 budgets. In this paper, envision a novel neural sketch, called the meta-sketch, with techniques neural networks. The meta-sketch learns the sketching 34 abilities from automatically generated meta-tasks. Depending on the types of meta-tasks, we study
33 of meta-learning and
35 two versions of the meta-sketch, called basic and advanced meta-sketches.
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

gadd
ri
0|0=
A
M
Store
f
Query
X;
9emb
21
N
9dec
Figure 1: The Framework of the Meta-sketch
36
The basic meta- meta--kketch implements the simulation of basic sketches, through the training process with basic meta-tasks following Zipf distributiios, which are prevalent in the scenes of real data streams [16] 20). The advanced meta-sketch extends the hasic version fast adapt the specific runtime of stream processing, through the training with adaptive meta-tasks, which are generated by online sampling of real data streams. Our work follows typical setting where the distribution of item frequencies follows a skewed distribution, but the correspondence between items and frequencies varies. For example, in software-defined networks (SDN), sketches are deployed to programmable switches to collect per-flow statistics, where IP packets follow heavy-tailed distributions [1]. In distributed databases, it gives advances collect statistics of data shards to optimize data placement and query caching, where query phrases follow approximate Zipf distributions [TS] Given that the item population follows specific distribution, the local distributions, i.e., itte--tteeuuuee frequency correspondences on shards or flows, are different. Instead of retraining learned augmented sketches on each local distribution, the advanced-skett can be quickly adapted to different local distributions once trained.
37
38
39
41
42
43
44
45
46
47
48
49 As a member of the neural data structure family 15 22 24). the meta-sketch significantly differs from conventional sketches, in terms of the structure and working mechanism. The meta-sketch capabilities to perceive data distributions and express
51
utilizes NN's powerful encoding/decodiin and compress explicit or implicit information to retrieve item frequencies with better accuracies. Meanwhile, the meta-sketch is differentiable to fully perceive frequency patterns for self-optimization.
52
53
Our contributions problem of item frequency estimation, based on meta mnetallerriing 2) The basic meta-sketch acquires sketching abilities by learning from synthetic datasets, and outperforms basic sketches in real datasets. The advanced meta-sketch automatically encompasses the ability analogous to the auxiliary structures deliberately devised in (leamed) augmented sketches, yet yielding better accuracies and robustness when adapted to dynamic scenes. 3) Through extensive empirical studies on real and synthetic datasets, we evaluate our proposed meta-sketches and analyze the mechanism of major modules.
follows. 1) We propose the meta-sketch, the first neural data structure for the
55
56
57
59
60
61
2
Meta-sketch Structure
2.1
Preliminaries
63 We consider a standard data stream scenario [19]
Suppose a data stream SN : fei.... eN with N 64 items and distinct items. Each item e SN takes value from the item domain X {ar1, -0r Inl
65 where r; # zzz The frequency Si is equal to the number of times that item x; appears in SN.
To leverage learning techniques for item frequency estimation, naïve way is train a NN model (c.g., MLP/LSTM) that lcarns/memorizes the mapping relationship between items and frequencies with multiple training iterations, similar to [15 22 24
87
However, it violates the typical setting of 69 stream processing where item observations are transient and are therefore handled in one pass [18]. More, the costly procedure has to be repeated from the scratch for new data stream. Inspired by the
71 meta-bloom filter [23). we consider a case of one-shot learning (fitting for one-pass stream processing) by using meta-learning 25 (6) and memory memory-augmented augmented networks [27[2)). Meta-learning employs 73 sampled meta-tasks to learn the ability to solve a class of domain tasks rather than memorizing patterns
74 for specific task. The memory- eagneee- networks incorporate external memories into NN models, significantly enhancing the potentials of NN models with more learnable parameters. Meanwhile, it
75
78 performs efficient and explicit operations (i.e., reading and storing) for external memories, allowing NN models to process information similarly to conventional data structures.
77
78
The framework of the meta-sketch consists of 4 functional modules, Embedding (Fg), Sparse addressing (Fsa), Compressed storage matrix (M), and Decoding (Faec), as shown in Figure T Like traditional sketches, the meta-skete encodes and memorizes online stream items in one pass, and answers queries by decoding corresponding item hem-frequency information from the structure.
79
81
Thus, we define 2 operations, Store and Query. Specifically, the Store operation first passes each 83 incoming stream item to FF for the embedding representation, and then writes the embedding vector into M, according to the address derived by Fs When estimating the frequency of item, the
2

---

85
Query operation calculates the item's address in M via Fsa- reads the corresponding information vector from M, and decodes the item frequency by Fdee from the retrieved information vector.
86
2.2
Modules
88
Embedding. The module FE has two purposes: 1) performing representational transformation for an incoming item e; and mapping it into dense embedding vector 2; that holds implicit features about item-freee -enefreuuency distributions and serves as the basis for identifying stream items; 2) decoupling the embedding vector 2; to obtain refined vector ri, which is used to derive the address for reading/writing on the compressed storage matrix M.
89
90
91
92
93
Accordingly. Fr consists of the embedding network Jomb and the address network godd- We assume that an item e E Sy is numerically encoded for the unique identification, following the conventions of stream processing [8 19]. Thus, we have 2; Pi < FF(e:), where < Demb(es) and r; <- Iada(Z;) Here, 2; E - is an embedding vector of length 4,, and T; E RR' is a refined vector of length 4,. The vector 2; serves multiple intents: 1) it makes basis for deriving the address of an item in Fsa; 2) it serves as the compressed vector of an item written into M; 3) it works as partial input of Face for decoding the item frequency; 4) it also plays the role of perceiving/compprssingg patterns of specific frequency distribution, as discussed in Section 5 In addition, to enhance the addressing functionality and eliminate other interference factors, we decouple 2; to generate refined vector rs
94
95
96
97
98
99
100
101
102
instead of using 2; directly for the addressing.
103
Sparse addressing. The module Fsa aims derive the address o; for storing the embedding vector 2 into the storage matrix: a; + (ri) In terms of functionality, Fsa is analogous to the hash functions of traditional sketches, except that Fsa parameterized and differentiable. Specifically, the addressing of the meta-sketch is done via a 3D addressing matrix A of parameters to be learned and a sparse SoftMax function: a, f Sparse (r A). where
104
105
106
1d,ixl,xx, Then, the batch matrix multiplication of A and the transpose of r2 results in the addressing vector a, 1 x1xd2,
107
108
109
The setting of dj and d2 determines the size of address space for storing the embedding vectors. Typical addressing methods [2 28 use a 2D matrix (l, x d2) for recording the mapping of an embedding vector to a slot (d2 is the number of slots). In contrast, we add one more dimension di to simulate the multi-hash setting of traditional sketches, in view of that 2D addressing matrix can reach a differentiable simulation of a hash function (23 Matrix A simulates multiple hash functions, yielding robust frequency decoding and the rationality of the learning optimization. Note that each 2D slice A of A is stacked from d2-unit vectors by E RR by normalizing the parameters of A at each gradient update of the training process. Normalized A can avoid overflowing when compressing its size by reducing data precisions and enhance the interpretability (see Section (5).
111
112
113
114
115
116
117
118 In addition, we utilize sparse SoftMax 29 30 instead of SoftMax to normalize the address a;- brings the following benefits by constraining some bits of a, to zero, which 1) promotes quick derivation during the pocpprrop:gttion; 2) reduces the overhead of storage matrix accessing by skipping the slots of M corresponding to the "O" bits of a;; 3) leads to de-noising with the vector compression.
119
120
121
122
Compressed storage matrix. We use a matrix M E Rdxx d to store an embedding vector E R in accordance to its address a; E gdix1xd, The functionality of M is similar to the 2D array of counters in traditional sketches, yet yielding better capabilities in the storage compression. Traditional sketches store item counts. Differently, MM stores embedding vectors, which have richer information compression capabilities, due to the diversity of value changes on different bits.
123
124
125
127
128
Decoding, Given a query item K, the module Fdec. consisting of one NN component Idec. decodes the information corresponding to Fi, in order to obtain the estimated frequency ft. The vector fed into Idee is the concatenation vector (M@
129
130
@ (z). vector 2,, and the current number of items (i.e., N) recorded in a counter, ft + gdee((AM e a 24, N). 2,, for the storage matrix. The basic form of e gives the operation as M e a, Mafp (7 28 For
131
The operator S refers to the reading operation
132
133
optimization, we consider two optimized forms of e inspired by the "count-min" mechanism of the CM-sketch. The first one gives the minimum value of each row in Maf', aiming remove the noise a normalized
134
135
of other items. The second one gives the minimum value of each row in Ma." x,
In this paper, we control I, : 12 R 1 : 5 to compress A. oo means transpose operation for dim and d2
3

---

form of Ma.. Here, o denotes the Hadamard product, and 2, requires broadcast operations to comply 138
137 with its requirements. So. {M @ a;} refers to the concatenation of vectors generated by the basic form and the two optimized forms. Please refer to supplement materials for more details.
139
2.3
Operations
Operation Store is performed by feeding incoming item 6, to FE and Fsa to obtain embedding vector 2; and address G; and then additively writing 2; to M, weighted by az: M +- M + 2,0g- Here, other writing types (6) can also be employed, but simple additive writing is more efficient and allows to compute gradients in parallel [23] In addition, additive writing also allows to define an optional Delete operation for the meta-sketch (see the supplement materials).
141
142
143
144
145
Operation Query estimates the frequency of a given query item T₁. First, 2; and a; are obtained, similar to that of operation Store. Then, the vectors {M è a are retrieved from M and N can be casily obtained by a small counter. Finally, {M @ J. 2, and N are jointly fed into Idec to get the estimated frequency ft of as the returned value. The two operations are shown in Algorithm
147
148
Algorithm 1: Operations
Algorithm 2: Training Framework
Operation Stara(e;, M):
Data: Meta-sketch with all learnable parameters 0, Meta-task sampler R; while i not reach training steps do
zi FF(e:):
- Fra(r:) 2Aass
Sample a meta task t, {Si, Q+) ~ R and count N;
ei s. Store ( M):
149
Operation Qu.ry #1 < Jz(xi):
for (. 5(4 E qe f(() Query (x,))) M.N); C+ =osssuuu (1)) f500)
Backprop through: d.C./ /d and update parameters: Optimizent6. dC/d8). Normalize A:
a: Fsa (Fi):
f +- Face (ec N);
return fi:
end
3 Meta-sketch training
150
3.1
Training Framework
152
The meta-sketch employs an efficient one-shot meta-training method (31). The training process thus contains two phases, pre-training and adaption phases. In the pre-training phase, the meta-sketch
153
154
learns an initial set of module parameters, including Jemb, Iodd- A, and Idec- The pre-training goes offline across training units, i.e., basic meta-tasks, acquire the ability of stream frequency estimation. Then, the adaption phase, the pre-trained meta-sketch goes fast across a set of light- weighted training units, i.e., adaptive meta-tasks, to quickly acquire the task-specific knowledge, i.e., parameters for sketching real data streams at runtime.
196
158
159
The training units, i.c., meta- meta-tasks, tasks, are crucial for both phases. The training process of the meta-sketch on single meta-task is equivalent to simulating storing and querying an instance of data streams while computing the estimation error to optimize the learnable parameters. Thus, meta-task f; consists of store set 8; (also called a support set) and query set 9:- The store set 8; can be viewed as an instance of data streams, {e ..... CN, }. where N, is the number of stream items in s,. The query set qi can be represented by set of items from the stream instance with paired frequencies in {<= )()). )()),..
160
162
163
184
165
the store set s;, formally,
...., (xh) ), where n: is the number of distinct items in 8;. In this work, we define types of meta-tasks, basic (Section 3.2) and adaptive (Section 3.3
166
187
meta-tasks, corresponding to the pre-training and adaption phases, respectively.
The two training phases. that based different types of meta-tasks, follow the same training framework, as shown in Algorithm 2 except for the sampler and initial parameters. To optimize on reducing both absolute and relative frequency estimation errors" we devise an adaptive hybrid loss function 32 for the meta-sketch: 2477 (ft fA + + f + logo 102, where a and 02 learned parameters, and fa and f, are the true and estimated frequencies of item v,, respectively.
169
171
172
Average Absolute Error: AAE 1 Eim Is
Ail: Average Relative Error: ARE 1 D"

---

173
3.2 Basic Meta-task Generation
In the pre-training phase, basic meta-tasks should make the meta-sketch to simulate traditional sketches and preserve certain generality without relying too much on the patterns of specific distribu- tions (Section 5). Therefore, we generate meta-tasks based on the Zipf distribution, which is found to be prevalent in real scenes of data streams 20).
175
176
177
A meta-task is essentially data stream instance with item size which can be determined by the total number items N and the relative frequeney distribution p. Alternatively, we can generate meta-tasks by presupposing different f and p. where f is the frequency mean, since N=fxn. Thus, basic meta-task generation based on a sampler
179
181
{1, L, P). as follows.
182
An item pool 1 is a subset of the item domain X. The cardinality of I is in relevance to the identification capability of the meta-sketch. If the item domain is known a-priori, it can be directly taken the item pool. Otherwise, in applications where the item domain is only partially known or even unknown, the item pool can be constructed by sampling from the historical records. Even in the case that the item pool does not completely cover the item domain, the "missing" item can still be identified, due to the homogeneity of the domain domain-specific embedding space, given that the number of distinct items does not meet the item pool capacity [.].
183
184
185
186
187
189
frequency mean range L is the range for the frequency mean ʃ. One can get the value of by statistics of each sampled stream instance and extract the minimum and maximum fs to build L.
190
A distribution pool P consists of many instances generated according to different parameters of relative frequency distributions. varied parameter a, the base for constructing P. be selected from wide range to have good coverage of different distributions.
192
this paper, we consider family of Zipf distributions (33) with
194
Notice that the meta-tasks are for the meta-sketch to learn the sketching ability, instead of spoon- feeding the meta-sketch to mechanically memorize the parameters of R. means that the trained meta-sketch has the generalization ability to handle the case not covered in R (see Section 4.2).
196
198
The generation of meta-task to can be done based on sampler as follows. We first randomly sample a subset of nı items from I, and a frequency mean fa E L. Then, we sample a distribution instance ps E P and make the ni items' frequencies conform pl and ft. For example, the frequencies of n; items can be set as x fs x Pt, where ps ~ Zapf(a) is random variable. The above steps are repeated until the store set 8; and query set qi are built.
199
200
201
202
3.3 Adaptive Meta-task Generation
204
While processing real data streams, we can get the item set I, and its distribution p, by online sampling. I, and p, are then used for generating the set of adaptive meta-taske For each adaptive meta-task, an item subset is sampled from I,., and the relative frequency corresponding to each item is sampled from pr. The process is similar to the generation of basic meta-tasks. The only difference from basic meta-task generation is that, there no distribution pool anymore, because the real data stream is unique. Also, we intentionally randomize the correspondence between an item and its real relative frequency on the original data records. It is equivalent to constructing meta-tasks where
205
206
208
209
210
the item frequencies dynamically change. For example, the frequency of item may first increase, then suddenly drop [2T]. With adaptive meta-tasks, the meta-sketch learns to quickly adapt to the distribution Pr, while being flexible against the item frequency change. The detailed algorithms of generating basic/adaptive masks are shown in supplement materials.
212
214
Experiments
215
216
4.1
Basic Setup
217
Dataset. We use two real datasets. Word-query is a streaming record of search queries, where each
query contains multiple words (e.g.. "News today") [15] IP-trace consists of IP packets, where each packet is identified by a unique source/destination address pair (e-g.. 192.168.1 1/112. (1]
219
We assume that query phrases and IP addresses are numerically encoded, similar to 15
5

---

Table I: Results of Basic Meta-sketch (T₂)
Word-query
IParnee
Method
Metrics
n=5K.
n=I0K.
n0K
n=
n=SK,
n=1KK.
n=20K.
n=
B-9KB
R-1IKB
B-13BB
B-15KB
R=9KB
B- IKB
B-13KT
B- B515KB
ARE:
12.3
14.74
10.98
13.79
3.00
1.51
2.97
1,13
Basic MS
AAE
31.54
38.54
40.63
53.67
5,57
5.01
6.94
5.56
CS
ARE:
32.94
57.97
96.01
162.43
6.08
9.94
15.57
24,49
AAE
57.54
101.44
172.44
282.59
10:42
16.82
26.46
41.91
ARE
21.34
48.35
111.82
239.11
8.12
16.07
32.77
65.19
CMS
AAE
38.04
84.62
195.61
416.01
13.67
27.39
55,29
110.65
Table 2: Results of Basic Meta- Meta-sketch (T.)
Method
Motrics
D-KKBB-OKB
D- BOT.BB-TTKB
0.5
1.1
1.3
0.5
1.1
1.5
0.5
1.1
1.5
0.5
1.1
1.5
Basic
ARE
1,05
2.63
3,25
3.14
1.35
2.58
9.65
query)
AAE
24.7
17.72
8.93
31.24
27.02
9.41
27.29
22.19
9.2
25.04
26.95
19.87
Basic MS
ARE
0.59
2.27
9.38
11.33
1.36
1,02
0.72
1.73
7.52
0.73
0.79
2.33
(IP-troo))
AAE
26.45
21.49
14.73
19.32
7.95
35,48
22.28
39.57
21.75
CS
ARE
1.98
6.72
10.99
2.7
12:12
16.9
3.73
20.8
27.16
5.17
37.96
43.76
AAE
74,96
47.98
15.89
102.05
75.83
23.8
140.65
118.29
38.7
194.32
198.4
$9.96
CMS
ARE
9.44
32.
27.89
AAE
187.52
53.81
8.17
350.08
99.82
13.58
651.63
185.51
22.88
1213.38
347,32
38.18
221
Baseline. We hereby evaluate the basic and advanced meta-sketches. From now on, we use MS to represent the term meta-sketch for brevity. We compare basic MS (after the pre-training phase) with CM-sketch (CMS) and C-sketch (CS). We compare the advanced MS (after the adaptation phase) with learned augmented sketch (LS) and cold filter (CF), which are two variants of CM/C sketches with auxiliary structures. According to the default setting [I] the number of hash functions for all sketches is 3. We adopt two commonly accepted metrics for evaluating the accuracies of stream frequency estimation, AAE and ARE
222
223
224
225
227
228
Parameters. We implement gemb or Iadd in MLP with 2-layers of sizes 128 and 48, followed by batch normalization, and gdee an MLP with 3-layers of 256 with residual comnections. We use the relu function for layer connections. The space budget B is spent storing M, the same as the setting in neural data structures [23] Other modules, like hashing libraries, are commonly accepted as reusable and amortizable resources for multi mepli-deeloymmnt of sketches [21]23) Note that due to space limitations, the details and methods of parameter settings of (A)), the ablation experiments and some parameter discussions are shown in the supporting material.
229
231
232
233
4.2
Basic Meta-sketch
236
Settings. For each dataset, we train the basic MSs under 4 item pools with {5K, 10K, 20K, 40K}
different items, respectively. The meta-task sampler are with Zipf distributions. We build the distribution pools set with a E [0.8, 1.3] and set frequency mean range L = [50, 500). For basic meta-sketch training, the default maximum number of training steps & is 5 million, the learning rate is 0.0001, and the Adam optimizer is used. For evaluation, we consider two types of tasks, T, and T. T. are directly obtained by random sampling on two real data streams with different values of n, iee. the number of distinct items. Note that the frequency distributions of T, are not necessarily obey Zipf distributions. T, are the synthetic tasks, where the item frequency follows the Zipf distribution
238
240
241
242
243
244
with a E {0.5, 1.1, 1.5). To evaluate the generability and stability of basic MS, both T, (0.5) and T. distributions are not covered by the distribution pool of the meta-task samplers.
245
246
Performance Table [ shows the performance of all competitors based on real dataset T,. It shows that the basic MS outperforms traditional basic sketches, i.e., CMS and CS, all testing cases. For example,the results on IP-trace show that, when n=40K and B=15KB, the ARE of basic MS is 1.13, while AREs of CMS and CS are 65.19 and 24.49, respectively. The advantage of meta-sketch is significant when testing on T, with different as, as shown in Table Note that we use random choices to simulate the ideal hash functions for traditional sketches like [5] so that CS and CMS
248
250
251
252
have the same result on test tasks with the same a in both datasets.
We show the trend of ARE w.r.t. the space budget. in Figure (T,,, n=5K, Word-query). Compared to the dramatic performance degrading of traditional sketches, basic MS holds stable performance. We show that the trend of ARE w.r.t. the number of distinct items in Figure 3 (T, B=9KB, Word-query). Compared to traditional sketches, the ARE of basic MS increases sub- limerll w.r.t. the value of n. Note that AAE has similar results for the above experiments, see the supplement materials.
254
256
258
Generalization. We test the generality of basic MS to new items that are not in the item pool of the meta-task sampler in Figure a). We make the experiments (n=5K, B-9KB, Word-query) by replacing some items in T, with new items, and vary the fraction of new items to observe the trend of the performance. It shows that the ARE/AAE moderately increases w.r.t. the ratio
260

---

44
564-6
60
Bidic H5
30
5e+5
50
CNS
2 28
Se1-3
Se+
Sc+2 See3
5c+4 5e+5 Sc+t
#
2 15
20
18
mean
20
10
ARE
10
5k
9k
budget
13k
17K
Item_ $22e
5080
*0% 40% jiem__atiii
92 5ee3 5644 Seb5 Seié
Tru
(a) New Items
(b) New frequency means
Figure 2: ARE w.r.t. B
Figure 3: ARE w.r.t.
Figure 4: Generality of Meta-sketch
Table 3: Results of Advanced Meta-sketch
Method
Metriss
Word-query
IP-trace
n=5K
TOK.
n=20K B=13KB
n=40K
n=5K
TOK
n=20K B=13KB
n=40K
B-9KB
B=11KB
B=15KB
B-9KB
B=1]KB
B=15KB
Advanced
0.87
MS
AAE
21.42
26.11
35,00
43.81
3,77
4,46
5,13
6,55
ARE
3.58
14.53
141.70
1127.11
0.85
2.74
4.20
16.71
CF90
AAE
21.13
381.65 66
2217.28
1.32
3.01
7.71
31.20
ARE
7.95
29.02
139.87
$41.37
1.51
3.10
8.95
46,79
CF70
2.57
ARE
91.16
138.64
244.24
407.83
12.62
33.50
103.76
155.61
CF40
174.86
252.22
421 85
693.47
24.16
279.72
LCMS(1%)
ARE
20.52
48.69
111.85
266.50
8.34
17.09
35,22
77.79
AAE
37,80
81.93
194.15
451
13.72
28.39
59. 10
129.80 86
LCS(1%)
25.53
104.54
5.20
17.12
AAE
44.53
78.17
122.57
180.56
8.78
13.10
18.97
28.38
of new items. The performance is acceptable considering the fact that the item domain is often stable in practical applications. We then test the generality of meta-sketches to varied frequency means that not in range T. of the meta-task sampler, shown in Figure hb). The experiment done by sampling a series of T, tasks with frequency means in (500, 5K, 50K, 500K, 5000 It shows that the mean of the true frequencies increases, the estimated frequencies of the meta-sketch increase linearly, so that the ARE keeps stable.
263
265
(n=5K, B-9KB, Word-query)
267
268
Advanced Meta-sketch
269
Settings.
The generation of adaptive meta-task similar to that of basic meta-tasks (Section 3.2). ex- cept that each item pool reads real frequency distributions for the adaption as described in Section 3.3 In the adaption phase, the maximum number of training steps 0.002 *
270
271
272
the performance advanced MS with traditional sketches and their variants, LS and CF, real dataset T,. We implement two LSs according [15). learned CM-sketch (LCMS) and learned C-sketch (LCS), following the default setting that (top 1 1%) high-frequency
Performance. VableeJcompaar
274
275
items are separately stored. For CF, we follow the parameter setting [14), and use CF40, CF70, and CF90 for setting the filter percentages to 40%, 70%, and 90% of the total size, respectively. It shows
276
277
that the advanced MS achieves better performance than LSs and CFs. Also, AAE/ARE of advanced
278
MS increases more moderately w.r.t. the number of distinct items compared to its competitors.
Furthermore, compare the performance of the advanced MS and the LS under dynamic streaming scenarios, as shown in Figure 5 We select a set of T, (n=5K,B09KB. Wordyquery), and gradually
280
shuffle the correspondence between items and frequencies. Here, the shuffle ratio is increased from 0
282
to 100%. It shows that the average ARE of advanced MS only slightly fluctuates between 3.26 and
4.0, and the average AAE is in the range of 21.28 and 21.68. In contrast, AAE of LCS LCMS starts above 37, and increase significantly w.r.t. the increase of the shuffle ratio. Actually, the classifier of
284
285
LS tends to incur more errors due the gradual shift of high- and low-frequency items, resulting in an increased number of hash collisions, thus deteriorating the estimation accuracy.
286
Analysis
287
The meta-sketch is trained based on meta-tasks, consisting of various stream distributions. We expected that the meta- sketch can learn the ability to sketch item frequencies. Somehow, it is unavoidable that the meta-sketch's 's ability is limited by patterns of given meta-tasks. Thus, setting trade-offs. In the pre-training phase, we select the most representative Zipf distribution to form basic meta-tasks, making the basic meta-sketch adaptable to a wide range of data streams. the adaptation phase, we sample adaptive meta-tasks
289
290
291
up the two training phases benefits the balance
293
from raw data streams to make the advanced meta meta-sketch more specialized. Next, analyze the
7

---

45
Advenced MS
Advenced MS
<
35
25
LOMS
50
60
Nerm
50
40
30
13
15
15
20
20
0.0 0.2 0.4 0.6 0.8
1.0
0.0
0.2 0.4 0.6 0.8
1.0
2
3
3 Train_ste step
2
Shuffle_rathe
Shufflee ratio
Train_ste step
(a) ARE
(b) AAE
(a) [r] and
(b) Sparsity of
Figure 5: Learned sketch vs. Meta-sketch
Figure 6: |r] and |2| w.r.t. Sparsity of a
35
Advansed Eireann
Stnnder devlacton
1:00
20
loso
love
loved
20
22
18
lowa
20
lootl lests loaD
12:
10
1000 2000 3003 4000 5600
Novanced
Kmizra
Tandom
0.0 0,5 1.0
2.0 2.5
85
2.0 3.0
1.0
155 2.5
Train stop
Train Step
Train Stop
(a) AAE
(b) Standard deviations
(a) Zipf
(b) Triangular
(c) Uniform
Figure 7: Three addressing matrices
Figure The sparsity of embedding vectors
working mechanism of the three modules of the meta-sketch as well as their roles in acquiring the two abilities.
296
297
Sparse Addressing Module. We take a 2D slice A (size is 4, x d2) of the A matrix to analyze the process of a refined vector r getting addressing a through this module. First, we have a + SparseMaz(r" A") = t- SparseMaz((
298
299
b,, r. by,.... F bag)). Since b; are unit vectors, we can get 4 SSaassareaarar (ar()))())))))))))).)))) (cosft, cos82, ..., costld,), where 02 is the angle between r and
300
b, We continue to transform the form to get addressing a t Spar apparsegen(ee u,
|-|-1) (30). where a component-wise transformation function applied on c. in this paper, we set u(c)-c.
302
Based on the principle of Sparsegen (30), |r] mainly affects the sparsity (i.e., the proportion of
303
non-zero bits in the vector) of a during training process, while determines the positions and values of non- sparse bits. The Figure 6 shows a strong correlation between the average |r| and the sparsity of during training from scratch (n=5K, B=9KB, Word-query Basic MS). Since the embedding vector z does not directly participate in the addressing process, the average |z| remains stable. Further, observe that the sparsity of will eventually converge to around 1, which means that each item 309 is generally stored in a slot corresponding to the refined vector r and the unit vector in A" with the maximum cosine similarity.
305
307
311 Therefore, the role of A" is to map refined vectors to the addressing vectors. The d2 unit vectors in A are the reference standard for mapping, which is equivalent to the mutually exclusive d2 -divisions of the refined vector space. Follow this point, we construct two matrices K* and R² of the same size as A Among them, the d2 unit vectors in K* come from the cluster centers of the sampled refined vectors. To achieve mutually exclusive division, we perform K Kmeans clustering with K = d2 and Cosine similarity criterion. Then, we normalize the resulting d2 cluster centers and stack them K*, In contrast, the unit vectors in R are entirely randomly generated.
313
315
317
318
Figure 7 (a) shows the results of replacing A on the trained meta-sketch with K* and R The meta-sketchh with R" shows the worst performance, but the performance of the meta-sketer with K* is close to the original A". Furthermore, We count the number of items mapped in every slot of A",
319
321 K R and show their standard deviation in Figure 7 (b). The standard deviation of R is much higher than 4 and K", and a better meta-sketch tends to store items more evenly in each slot. Thus, The addressing module simulates the traditional sketch mechanism. Its principal function is to store the embedding vectors of items as evenly possible in multiple memory slots, and an item is written to only one slot.
323
325
326
Embedding Module. The major source of conflicts in the meta-sketch is the stacking of different
327
embedding vectors in single slot. Thus, the sparsity of the embedding vector becomes an important indicator to determine the degree of conflicts. Figure 8 shows the relation between the sparsity of embedding vectors and the stream distributions (n=5K, B-9KB, Word-query, advanced MS). We
328
329
select the meta-tasks under Zipf. Triangular, and Uniform distributions with different skewness levels (the definition of skewness and corresponding distribution parameters are shown in the supplement materials). The results show that the sparsity of the embedding vector is positively proportional to
331
8

---

28
24
32
36
VSIfrozon
WBiho frezen
Advanced MS
MSifrozon Rosd
Advanced
MSING frozen Stod)
Sparsity
10.5
10.0
9.5
Unioatle
Statie
220
Unstable_memorry mwmory.mmmr.ooo ssot
16
9.0
12
8.5
8.0
1000 2000 3000 4000 5000
Se+2 5e+3 5e+4 5e+5 Se+6
10
20
30
40
60
100
item_siee
True_een mean
Stable wwm.rymmoor.ooo slot
Sort. frequeccyy
(a) Item size
(b) Frequency mean
(a) Multiple slots
(b) A single slot
Figure 9: Generality w.r.t. Decoding module
Figure 10: Unstable case vs. Stable case
333
the skewness of a distribution. Therefore, we speculate that the meta-sketch memorizes the pattern information of the distribution being adapted by self-tuning the sparsity of embedding vectors.
334
335
Decoding Module. The decoding module, as the deepest NNs in the meta-sketch, integrates various information to predict the item frequency and achieves generalization ability. To verify this, we adapt the advanced MS (n=5K, B-9KB, Word-query) to a special adaptive meta-task. The meta-task was sampled from the real data stream but with fixed item size (5000) and frequency mean (250). Meanwhile, we do not change the correspondence between items and frequencies. Such meta-task forces the meta-sketch pay more attention the fixed patterns and thus limit its generalization.
337
339
340
341 Thus, we train the advanced MS with (or without) freezing the decoding module parameters based on the above meta-task. Figure (a) shows the performance changes of the three models (advanced MS as baseline) on the evaluation tasks (T2) of different item sizes. Without the frozen decoding module, the meta-sketch loses generalization ability at extended item sizes other than 5000. On the contrary, the meta-sketch with the frozen decoding module still retains the generalization ability and further utilizes the data stream pattern compared to the advanced MS, achieving the best performance. Similarly, as shown in Figure 9 (b), the meta-sketch without the frozen decoding module also loses a certain generalization ability terms of frequency mean.
343
345
347
348
349
Actually, the above meta-task (termed as the stable case) can be viewed as a special case of an ordinary adaptive meta-task (termed as the unstable case). As a matter of fact, augmented sketches utilize frequency patterns similar to the stable case. For example, the learned augmented sketch memorizes (relatively) stable correspondence between items and frequencies, for filtering high-frequence items. To understand the meta-sketch's 's self-optimizing mechanism from the unstable case to the stable case, analyze the storage of high/low-frequeee
350
351
353
items between multiple slots and single slot in the memory. In Figure|TO) (a), we show density heat-maps of low-frequency (below the top 20% high frequencies) items, stored by meta-sketches of stable and unstable cases on 2D slice (dl 22) of the storage matrix M, where the x-axis is the index of slots. The two heat-maps show that the meta-sketch under the stable case can store the low-frequency items concentratedly in some slots to avoid the conflicts with high-frequency items. Interestingly, the meta-sketch does not intentionally do this like
355
357
358
359
380
augmented sketches. Instead, it is achieved by self-optimization during the training. Furthermore,
381
Figure (b) shows the relation between the sparsity of the embedding vector of items stored in a
382
single slot and the frequency order, where the æ-axis represents the frequencies in the ascending order.
383
We speculate that the meta-sketch autonomously adjusts the sparsity of the embedding vector within
384
single slot in the stable case, so that the high/low-frequeee items are automatically separated.
6
Conclusion
In this paper, we propose neural data structure, called the meta-sketch, for estimating item fre- quencies in data streams. Unlike traditional sketches, the meta-sketch utilizes meta-learning and 367
neural networks. The meta-sketch is pre-trained with Zipf distributions and can be fast adapted to specific runtime streams. We study a series of techniques for constructing the sketch We also devise the generation of basic and adaptive meta-tasks corresponding to the pre- traiiiann and adaption phases, respectively. Extensive empirical studies on real datasets are done to evaluate our proposals. In the future, it is interesting extend proposal to other sketching tasks that are supported by traditional sketches
memory-augmente
369
371
373
374 References
375
[1] Tobias Weller. Compromised account detection based on clickstream data, In WWW, pages 819-823, 2018

---

377
[2]
Yunyue Zhu and Dennis E. Shasha. Statstream: Statistical monitoring of thousands of data streams in real time. In VLDB, pages 358-369. 2002.
378
[3] Ramine Tinati, Xin Wang, Ian C. Brown, Thanassis Tiropanis, and Wendy Hall. A streaming real-time web observatory architecture for monitoring the health of social machines. In WWW, pages 1449-1154, 2015.
380
381
382
[4] Mohammad Tanvir Irfan and Tucker Gordon. The power of context in networks: Ideal point models with social interactions. In IJCAI, pages 6176-1880, 2019.
385
[5] Qun Huang, Patrick P. C. Lee, and Yungang Bao. Sketchlearn: relieving user burdens in approximate measurement with automated statistical inference. In SIGCOMM, pages 576-590, 2018.
385
386
387
[6] Samuel Madden and Michael J. Franklin. Fjording the stream: An architecture for queries over streaming sensor data. In ICDE, pages 555-566, 2002.
386
Lu Wang, Ge Luo, Ke Yi, and Graham Cormode. Quantiles over data streams: experimental study. In SIGMOD, 2013.
380
391
88]
Amit Goyal, Hal Daumé III, and Graham Cormode. Sketch algorithms for estimating point queries in NLP. In EMNLP-CONLL 2012, July 12-14, 2012, Jeju Island, Korea, pages 1093- 1103. ACL,, 2012.
393
394
Fabon Dzogang, Thomas Lansdall-Welfare Saatviga Sudhahar, and Nello Cristianini. Scalable preference learning from data streams. In WWW 2015, Florence, Italy, May 18-22, 2015 Companion Volume, pages 885-890. ACM, 2015.
385
396
[10]
Graham Cormode and S. Muthukrishnan. An improved data stream summary: the count-min sketch and its applications. J. Algorithmss 55(1):58-75, 2005.
398
389
Moses Charikar, Kevin C. Chen, and Martin Farach-Colton. Finding frequent items in data streams. In ICALP, pages 693-703, 2002.
400
401
[12]
Cristian Estan and George Varghese. New directions in traffic measurement and accounting. In SIGCOMM, pages 323-336, 2002.
403
[13]
Pratanu Roy, Arijit Khan, and Gustavo Alonso. Augmented sketch: Faster and more accurate
404
stream processing. In SIGMOD, pages 1449-1463, 2016.
405
[14] Yang Zhou, Tong Yang, Jie Jiang, Bin Cui, Minlan Yu, Xiaoming Li, and Steve Uhlig. Cold filter: A meta-framework for faster and more accurate stream processing. In SIGMOD, pages 741-756, 2018.
406
408
[15] Chen-Yu Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. Learning-based frequency estimation algorithms. In ICLR, 2019.
409
[16] Taiwo Kolajo, Olawande J. Daramola, and Ayodele Ariyo Adebiyi. Big data stream analysis: systematic literature review. J. Big Data, 6:47, 2019.
411
[17]
Xue- Que-Qiang Zeng and Guo-Zheng Li. Incremental partial least squares analysis of big streaming data. Pattern Recognition, 47(1 1):3726-3735, 2014.
413
414
[18]
Brian Babcock, Shivnath Babu, Mayur Datar, Rajeev Motwani, and Jennifer Widom. Models and issues in data stream systems. In PODS, pages 1-16, 2002.
416
[19] Graham Cormode, Minos N. Garofalakis, Peter J. Haas, and Chris Jermaine. Synopses for massive data: Samples, histograms, wavelets, sketches. Found. Trends Databases, 4(1-3):1-294, 2012.
417
418
419
[20] M. S. B. PhridviRaja and C. V. GuruRao. Data mining: : past present and future a typical 2016.
survey on data streams. CoRR,
421
[11]
Lu Tang, Qun Huang, and Patrick P. C. Lee. Mv-sketch: A fast and compact invertible sketch for heavy flow detection in network data streams. In INFOCOM, pages 2026-2034. IEEE, 2019.
422
423
[22]
Tim Kraska, Alex Beutel, Ed H Chi, Jeffrey Dean, and Neoklis Polyzotis. The case for learned index structures. In SIGMOD, pages 489-504, 2018
424
425
[33
Jack Rae, Sergey Bartunov, and Timothy Lillicrap. Meta-learning neural bloom filters. In ICMI., pages 5271-5280. PMLR, 2019.
428
427
[24] Michael Mitzenmacher. model for learned bloom filters and related structures. arXiv preprint
arXiv:1802.00884, 2018.
10

---

429
[25]
Timothy M. Hospedales, Antreas Antoniou. Paul Micaelli, and Amos J. Storkey. Meta-learning in neural networks: A survey. CoRR, abs/2004.05439, 2020.
430
431
[26] Adam Santoro, Sergey Bartunov, Matthew Botvinick, Daan Wierstra, and Timothy Lillicrap.
432
Meta-learning with memory- neural networks. In ICMI,, pages 1842-1850. PMIRR, 2016.
439
434
[27] Alex Graves, Greg Wayne, and Ivo Danihelka. Neural turing machines. arXiv preprint 1rX:v:1410.540,, 2014.
435
436
[28] Alex Graves, Greg Wayne, Malcolm Reynolds, Tim Harley, Ivo Danihelka, Agnieszka Grabska- Barwifiska, Sergio Gómez Colmenarejo, Edward Grefenstette, Tiago Ramalho, John Agapiou, et al. Hybrid computing using a neural network with dynamic external memory. Nature, 538(7626):471-44
437
438
439
2016.
440
[29] Andre Martins and Ramon Astudillo. From softmax to sparsemax: A sparse model of attention and multi-label classification. In ICML, pages 1614-1623, PMLR, 2016.
442
[30] Anirban Laha, Saneem Ahmed Chemmengath, Priyanka Agrawal, Mitesh Khapra, Karthik Sankaranarayanan, and Harish G Ramaswamy. On controllable sparse alternatives to softmax. NIPS, 31, 2018.
443
444
445
[31] Oriol Vinyals, Charles Blundell, Tim Lillicrap. Koray Kavukcuoglu, and Daan Wierstra. Match- ing networks for one shot learning. In Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett, editors, NIPS, pages 3630-3633 2016.
447
448
[32] Alex Kendall, Yarin Gal, and Roberto Cipolla. Multi-task learning using uncertainty to weigh losses for scene geometry and semantics. In CVPR, pages 7482-7491, 2018
449
450
[33]
Lada A. Adamic. Zipf, power-laws, and pareto- a ranking tutorial.
451
7
Checklist
452
1. For all authors...
453
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
454
455
(b) Did you describe the limitations of your work? [Yes]] Compared with traditional data structures, necral data structures are usually relative weak in term of time latency. In future research, We need study and reduce time cost of meta-sketches' operation or disign a framework to get huge throughput utilizing parallel algebraic operations as a remedy.
456
457
458
459
480
(c) Did you discuss any potential negative societal impacts of your work? [N/A] There is no negative societal impacts of my work, since it is foundational research.
461
462
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
463
464
2. If you are including theoretical results...
465
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
487
3. If you ran experiments..
468
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
470
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] We give the details of the implementation as much as possible,but some of them will put into appendix.
472
473
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [Yes] We visualize the difference in line graphs by drawing shadows, which includes various of comparative experiments with all type of meta- sketches. But due to the huge amount of data erroor bars of table are not included. See section 4 and 5
474
475
476
11

---

478
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [Yes] All of our experiments are implemented in python and run at NVIDIA DGX workstation with CPU E5-2698 (2.00GHz, 20 cores), and NVIDIA V100 GPUs (5120 CUDA cores and 16GB GPU memory on each GPU).
479
481
483
4. If you are using existing assets (c.g., code, data, models) or curating/relcasing new assets...
484
(a) If your work uses existing assets, did you cite the creators? [Yes]
485
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
487
488
(d) Did you discuss whether and how consent was obtained from people whose data you're 'e using/curating? [N/A]
490
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
492
5. If you used crowdsourcing or conducted research with human subjects...
495
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals. if applicable? [N/A]
486
497
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
498
12


Reviews:
[{"review_id": "Nq8PlfAtlPP", "reviewer": "Reviewer_4vDr", "summary": "The work considers the problem of estimating item frequencies in data streams. Sketches are probabilistic data structures that solve this problem approximately; e.g., a classical count-min (CM) sketch increments counts resulting from several hash functions for each query (exactly like a Bloom filter, only with integer counts) and outputs the minimal value of these counts as the result; this is a biased estimator that can overestimate but not underestimate. Machine learning models can be used in sketches to exploit the properties of underlying data distributions. For example, it would be better to assign heavy hitters separate buckets in a CM-sketch to avoid collisions, and a machine learning model can be used to identify these heavy hitters when they appear.\n\nThe work presents Meta-Sketch, a neural data structure that emulates a sketch in a neural network. The Meta-Sketch is a neural network with an encoder that produces embeddings $z_i$ and refined embeddings $r_i$ of incoming items, a sparse addressing unit that converts $r_i$ into an address $a_i$ in the storage matrix (this is the neural version of hash functions), a compressed storage matrix $M$ that stores embedding vectors, and a decoder that produces the frequency from a reading from the storage matrix, embedding vector $z_i$, and the total number of stored items $N$. The network supports two kinds of operations: \"Store\" that additively writes $z_i$ to $M$ and \"Query\" that estimates the frequency via the decoder.\n\nThe entire network is both pretrained and fine-tuned (adapted) on a series of meta-tasks; each meta-task is a set of store and query operations; during pretraining, the meta-tasks are synthetic problems generated based on the Zipf distribution (the result is called a basic meta-sketch), and during adaption the network is fine-tuned on real data records (advanced meta-sketch). The idea here is to pretrain the architecture to operate as a sketch while preserving the ability to quickly adapt to a given data distribution.\n\nThe authors evaluate on two real datasets, a stream of search queries (several words each) and an IP trace where packets are identified with source/destination IP addresses. They report improved performance over classical sketches and also over previous attempts of adding ML to sketches: learned CM-sketch and learned C-sketch. The paper also presents an analysis section that studies how different units of the architecture perform.", "questions": "1. There is an ablation study in the supplement but I think the paper would benefit from a discussion of neural network architecture choices. For example, are there gains to be achieved from more involved encoder/decoder architectures?\n\n2. It appears that the authors simply picked the same real datasets that were used in previous work (references [15, 21]). Are there other use-cases and available datasets for evaluation? Are there differences in the data distributions between these two (it appears there should be: IP traces are generally more heavy-tailed) and does it make any difference to Meta-Sketch results?", "limitations": "Limitations of the work and possible extensions have been adequately discussed in the conclusion. The societal impact question is not applicable in this case.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* novel neural data structure with a clear use case\n* analysis section supporting that the components operate as intended\n* convincing experimental evaluation\n\nWeaknesses (see also questions):\n* lack of discussion of the architectural choices for the neural networks\n* only two real datasets with no motivation for this choice and no discussion of their differences", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "L0uN4JbNy6_", "reviewer": "Reviewer_uz3r", "summary": "The paper proposed a neural model to estimate item frequencies of data streams, which is using the thought of meta-learning. And they called the model meta-sketch. It’s said that they are the first to try to solve this problem with neural data structure and gain good performances on real datasets.\n", "questions": "Apart from the above, I have question about the update rule for M, M=M+z_i a_i. Is this adding process derived by some objective? Could the authors give this rule out directly. Please explain that it is representable for all items and streams.", "limitations": "None", "rating": 4, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe paper is well structured and the explanation is easy to understand.\n\nWeakness:\n1.\tIn my view, training data and evaluation data should be isolated completely. That is, there should be a certain mount streams and items haven’t happened in the meta-tasks. Therefore, sampling training set and evaluating set from the same pool is not sufficient enough to prove the generalization.\n2.\tThe references and baselines are out of date, more researches of recent years should be covered. And it is easy to get a lot of results if you search items like “Item Frequencies of Data Streams”.\n3.\tOne advantage of meta-learning is that it could find better params of network faster and more efficiently. So I believe the efficiency is also a good sight of this model and it should be contained in the experiment.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "CEu8a7wAgWL", "reviewer": "Reviewer_XQdP", "summary": "This paper introduces a sketching method where neural networks are used for specific components of the sketching. In particular, a neural network is used to encode stream/query items into an internal representation used to update/retrieve frequency values of items, which is followed by another neural network that decodes this information into actual frequency values. A meta-training procedure is also introduced, whose goal is to train the neural networks to handle the task at hand on a meta level, that is, not tied to a specific dataset. The method and its multiple aspects are experimentally evaluated, showing how its internal mechanisms behave under differing circumstances and improved performance over baseline methods built on Count sketch and Count-min sketch.\n", "questions": "There are two major points where I would appreciate an answer from the authors:\n1. How is the method's robustness to the meta-training step? That is, how much variance is expected in the results under repeated experiments with different initial seeds?\n2. Are there any theoretical results that can be leveraged from existing literature on sketches? It seems to me the proposed method is lacking on the theoretical side.\n\nMinor points:\n- l. 97: what is meant by \"length\"? Perhaps $l_r$ elements has less ambiguous meanings (cf. length vs. norm)\n- Footnote 2 (p. 3): does that mean $a_i^\\top \\in \\mathbb{R}^{d_2 \\times d_1 \\times 1}$? Please write explicitly the space where $a_i^\\top$ comes from to avoid confusion\n- l. 271: $\\phi$ does not seem to be defined\n", "limitations": "I believe the authors have sufficiently addressed the limitations of their method by analyzing its multiple components and how they behave under different circumstances.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, I find this to be a strong submission. The paper is properly motivated, well-organized, and clearly written. The introduced methodology is quite original for sketching, leveraging neural networks and increasing the robustness to changes in distribution significantly, compared to existing approaches, without additional training.\n\nI was also pleased with the experimental evaluation, as it not only compares accuracy in frequency estimates under varied conditions, but also evaluates the different components that comprise the approach. In my view, this helps justifying why certain parts are a positive contributor to the overall performance of the method, shedding also some light on when they might fail. One weakness, however pointed out by the authors, is that the proposed method needs to be extended to other sketching tasks supported by traditional sketches.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject