Title: LEARNING-AUGMENTED DATA STREAM ALGO-RITHMS

Abstract: The data stream model is a fundamental model for processing massive data sets with limited memory and fast processing time. Recently Hsu et al. (2019) incorporated machine learning techniques into the data stream model in order to learn relevant patterns in the input data. Such techniques led to the training of an oracle to predict item frequencies in the streaming model. In this paper we explore the full power of such an oracle, showing that it can be applied to a wide array of problems in data streams, sometimes resulting in the first optimal bounds for such problems, and sometimes bypassing known lower bounds without such an oracle. We apply the oracle to counting distinct elements on the difference of streams, estimating frequency moments, estimating cascaded aggregates, and estimating moments of geometric data streams. For the distinct elements problem, we bypass the known lower bound and obtain a new space-optimal algorithm. For estimating the p-th frequency moment for 0 < p < 2 we obtain the first algorithms with optimal space and update time. For estimating the p-th frequency moment for p > 2 we obtain a quadratic savings in memory, bypassing known lower bounds without an oracle. We empirically validate our results, demonstrating also our improvements in practice.

1. INTRODUCTION:

Processing data streams has been an active research field in the past two decades. This is motivated by the increasingly common scenario where the size of the data far exceeds the size of the available storage, and the only feasible access to the data is to make a single or a few passes over the data. This situation occurs, for example, in network applications with high-speed packets being sent through routers with limited resources. Other examples include processing internet search logs, sensor networks, and scientific data streams. For an introduction to data streams, see, e.g., Muthukrishnan (2005) .

Formally, in the data stream model, we assume there is an underlying frequency vector x ∈ Z n , initialized to 0 n , which evolves throughout the course of a stream. The stream consists of updates of the form (i, w), meaning x i ← x i + w. Suppose M is such that x ∞ = max i∈{1,...,n} |x i | ≤ M throughout the stream. At the end of the stream, we are asked to approximate f (x) for a function f : Z n → R. Because of the sheer size of the stream, most algorithms are approximate and randomized. Typically, such algorithms output an estimate Z for which Pr{(1 -)f (x) ≤ Z ≤ (1 + )f (x)} ≥ 2/3, where the probability is over the randomness used by the algorithm, and not of the input stream, which may be a worst-case stream. The success probability 2/3 can be replaced with any constant greater than 1/2 by independently repeating the algorithm a constant number of times and taking the median estimate. The space complexity of the algorithm is measured in bits and the goal is to use much less than the trivial n bits of space required to store x.

A common difficulty in designing algorithms in the data stream model is that the coordinates i for which |x i | is large, i.e., the heavy hitters, are not known in advance. Such coordinates usually require very accurate estimates in order to achieve an accurate final estimate of the function value. A number of techniques have emerged for identifying such coordinates, such as the Count-Min and CountSketch. These techniques are often used at multiple scales by subsampling the input coordinates and finding heavy items in the subsample, and have found applications to estimating frequency moments, cascaded aggregates, earthmover distance, and empirical entropy, among other statistics (Indyk & Woodruff, 2005; Chakrabarti et al., 2006; Jayram & Woodruff, 2009; Andoni et al., 2009; McGregor et al., 2016) .

In many applications, however, the worst-case input is rarely seen; in fact, there is usually a pattern inside the underlying vector. For instance, in network traffic monitoring, the large or "elephant" flows fluctuate on a daily basis, but the actual source and destination servers of those flows do not vary much. In our formulation, this implies the value x i fluctuates while whether or not x i is a heavy coordinate remains stable. Motivated by this as well as related work on learning oracles for algorithm design (Gupta & Roughgarden, 2016; Dick et al., 2017; Balcan et al., 2018a; b) , Hsu et al. (2019) introduced the notion of a heavy hitter oracle into the data stream model. The heavy hitter oracle, trained on past data, receives a coordinate index i and returns a prediction of whether x i will be heavy or not. They showed that such an oracle simplifies classical heavy hitter algorithms such as COUNT-MIN and COUNT-SKETCH. We note that similar oracles were also studied in previous work, e.g., membership oracles for Bloom filters by Kraska et al. (2017) . These works demonstrate the feasibility of creating such an oracle using machine learning techniques. Recently, learned oracles for low rank approximation, which can be viewed as an analogue of heavy hitters for heavy directions, was explored by Indyk et al. (2019) .

The work of Hsu et al. (2019) is the starting point of our work. While Hsu et al. (2019) showed applications of the heavy hitter oracle to frequency estimation, the full power of such an oracle remained largely unexplored. Our main goal is to understand if such an oracle is more broadly useful, and whether it can give memory and time improvements to the large number of data stream problems mentioned above. Accurately estimating the heavy hitters in a vector is the bottleneck of existing algorithms for numerous data stream problems, and one cannot help but ask:

Can a heavy hitter oracle be applied to a large number of problems in the data stream model to obtain significantly improved bounds for these problems?

We consider estimating the following common functions f (x) in the data stream model:

• Distinct Elements: f (x) = x 0 , where x 0 is the number of nonzero coordinates of x, defined as x 0 = |{i : x i = 0}|. This quantity is useful for detecing denial of service attacks and database query optimization (Kane et al., 2010b) .

• the F p -Moment: f (x) = x p p

, where x p is the usual p -norm of x, defined as x p = ( i |x i | p ) 1/p . For 0 < p < 2, these are often more robust than the Euclidean norm (Indyk, 2000) . For p > 2 these are used to estimate skewness and kurtosis (Indyk & Woodruff, 2005) .

• the (k, p)-Cascaded Norm: in this problem x is an n × d matrix that receives updates to its individual entries, and f (x) = x k,p := ( i ( j |x ij | p ) k/p ) 1/k . These are useful for executing multiple databse queries (Cormode & Muthukrishnan, 2005; Jayram & Woodruff, 2009) .

These problems have also been studied for non-numerical data, such as geometric data. For example, the F p -moment problem was studied on a stream of rectangles in Tirthapura & Woodruff (2012) .

One can think of an underlying ∆ d -dimensional vector x, identified with a d-dimensional rectangle {1, . . . , ∆} d . Without loss of generality, we assume that ∆ is a power of 2. Each item in the stream is a pair of the form (R, w), where R is a d-dimensional rectangle and w is an integer, meaning Andoni et al. (2011) Theorem 7

F p Moment (p > 2) S O(n 1-2/p ) O(n 1/2-1/p ) e.g.,

F p Moment Fast Update (p < 2) Update T amortized O(log 2 1 log log 1 ) expected amortized O(1) Reporting T O( 1 2 log 2 1 log log 1 ) O( 1 2 ) Kane et al. (2011) Theorem 17 Cascaded Norm S O(n 1-2/k d 1-2/p ) O(n 1-1/k-p/(2k) d 1/2-1/p ) (k ≥ p ≥ 2) Jayram & Woodruff (2009) Corollary 20 Rectangle F p S O(∆ d(1-2/p) poly( d )) O(∆ d(1/2-1/p) poly( d )) Moment (p > 2) Tirthapura & Woodruff (2012) Theorem 23

Table 1 : Summary of previous results and the results obtained in this work. We assume that m, M = poly(n). In the column of result type, S denotes space complexity and T denotes time complexity. We view as a constant for the listed results of the F p Moment and Cascaded Norm problems.

Problem:

Heavy Hitter Oracle Distinct Elements x i ← x i + w for all points i ∈ R. The goal is to estimate f (x) = x p p . This is called the Rectangle F p -Moment problem, which occurs in spatial data streams and constraint databases.

|x i | ≥ 2 poly(1/ ) F p Moment (p > 2) |x i | p ≥ 1 √ n x p p F p Moment Fast Update (p < 2) |x i | p ≥ 2 x p p |x i | p ≥ 2 log 2 (1/ ) log log(1/ ) x p p Cascaded Norm (k ≥ p ≥ 2) |x i | p ≥ x p p /(d 1 2 n 1-p 2k ) Rectangle F p Moment (p > 2) |x i | p ≥ x p p /∆ d/2

Our Results:

We show that a heavy hitter oracle can greatly improve the complexity of a wide array of commonly studied problems in the data stream model, leading to the first optimal bounds for several important problems, and shattering lower bounds that have stood in the way of making further progress on important problems. We note that not only do we give new algorithms, we also give several lower bounds for algorithms equipped with the oracle, that show optimality of our algorithms even with an oracle. Our algorithms not only give practically better, theoreticallygrounded improvements to these problems with an oracle, they also shed light on what exactly the difficulties are of making further progress on data stream problems without an oracle. We consider both perfect oracles and oracles that may sometimes make mistakes.

We summarize in Table 1 our improvements to existing algorithms using appropriate heavy hitter oracles, whose conditions are summarized in Table 2 . Throughout, we make the conventional assumption that m, M = poly(n).

Distinct Elements: For the problem of estimating x 0 , we improve the prior memory bound of O( 1 2 log n(log 1 + log log n)) to O( 1 2 log n log 1 ). For constant , this gives an optimal O(log n) bits of memory, breaking a recent Ω(log n log log n) bit lower bound shown in Woodruff & Yang (2019) . Examining the lower bound argument in Woodruff & Yang (2019) , the hard instance is precisely when there are many items of large frequency, namely, the product of the first small number of primes. This prevents hashing-based algorithms, such as the one in Kane et al. (2010b) , from working with O(log n) bits of space, since hash values are typically taken modulo a small prime and such heavy items necessitate the use of a large enough prime. Surprisingly, we show that with a heavy hitter oracle, we can separately handle such items and thus bypass this lower bound. We note that our O(log n)-bit algorithm is optimal even given a heavy hitter oracle; see the Ω(log n) lower bound in Alon et al. (1999) , which holds even if all item frequencies are in the set {0, 1, 2}.

F p -Moment Estimation, 0 < p < 2: There is a long line of work on this problem with the best known bounds given in Kane et al. (2011) , which achieve an optimal O( -2 log n) bits of space, and O(log 2 (1/ ) log log 1/ ) time to process each element. The existing algorithm is based on separately handling those elements i for which |x i | p ≥ 2 x p p , i.e., the heavy hitters, from the remaining "light items". Although we can simply store the heavy hitters given a heavy hitter oracle, unfortunately, the large O(log 2 (1/ ) log log 1/ ) processing time in the algorithm of Kane et al. (2011) also comes from running a fast multipoint evaluation on the light elements.

We observe that if we instead train two oracles, one for detecting heavy hitters, and one for detecting items

x i with |x i | p ≥ 2 log 2 (1/ ) log log(1/ ) x p

p , then we can also separate out "medium items", i.e., items that are detected with this oracle but not our heavy hitter oracle. There are only O( -2 log 2 (1/ ) log log(1/ )) medium items and so assuming log n ≥ poly(log(1/ )), one could perfectly hash all such items and maintain their hashed identities in the optimal O( -2 log n) bit of space. However, one cannot maintain their counts, since each count is O(log n) bits, and approximate counts do not work if the stream can increment or decrement the coordinate values x i . This is too much memory, as it would lead to O( -2 (log n) log 2 (1/ ) log log(1/ )) bits of space, even worse than without the oracle. We could also maintain a so-called p-stable random variable for each medium item, and use it to estimate the F p -moment of the medium items, but this would again be O( -2 (log n) log 2 (1/ ) log log(1/ )) bits of space to store one random variable per medium item. We instead observe that most of the p-stable random variables are small, and so can be stored with many fewer than log n bits, and therefore globally we can get by with only O( -2 log n) bits in total for estimating the medium items. Finally, for the light items, the critical observation is that we can sub-sample a 1 log 2 (1/ ) log log(1/ ) fraction of them, and still accurately estimate their contribution. But this means we can run the multipoint evaluation algorithm of Kane et al. (2011) on such items, since while that has update time O(log 2 (1/ ) log log(1/ )), on average it is only executed on one out of every log 2 (1/ ) log log(1/ ) items.

In summary, with the aid of our oracles and by separately handling these three types of items, we are able to achieve the optimal O(1) amount of update time per item, while retaining the optimal O( -2 log n) bits of memory.

F p -Moment Estimation for p > 2: It is well-known (Bar-Yossef et al., 2004 ) that a hard input distribution for this problem is when a random coordinate of x has absolute value n 1/p , and all other coordinates have value 0 or 1. In this case, one needs to certify that there is indeed a coordinate of value n 1/p , as it contributes a constant fraction of x p p . There is a known Ω(n 1-2/p ) bits of space lower bound for this. However, a heavy hitter oracle exactly allows us to overcome this, as it can be used to separately identify such items. Our idea is to separate out every item i for which |x i | p ≥ 1 n 1/2 x p p with the oracle, and run an existing F p -estimation algorithm on such items. Since there are at most n 1/2 items, existing algorithms give (n 1/2 ) 1-2/p poly(log n) = n 1/2-1/p poly(log n) bits of memory for this problem. For the remaining light elements, one can show that if one subsamples only a 1/n 1/2 fraction of them and then runs an existing F p -estimation algorithm on them, one can use this to accurately estimate their contribution. This again takes n 1/2-1/p poly(log n) bits of memory, balancing the memory with the other part of our algorithm and giving a quadratic improvement in memory in the case without a heavy hitter oracle. Overall our algorithm uses O(n 1/2-1/p poly(log n)) bits with an oracle and we can in fact show that this is tight up to logarithmic factors as there exists a lower bound of Ω(n 1/2-1/p ) bits provided the same oracle.

We describe our algorithms for cascaded norms and rectangle F p -moments in the appendix.

We conduct experiments for the distinct elements and the F p moment (p > 2) problems, on both real-world and synthetic data, which demonstrate significant practical benefits.

2. PRELIMINARIES:

Notation We let [n] denote the set {1, . . . , n}. The function lsb(x) denotes the index of the least significant bit of a non-negative integer x.

Space and Time Complexity For streaming algorithms, the efficiency is characterized by the space (memory) complexity and the time complexity. The time is further divided into update time and reporting time. A data stream algorithm maintains a data structure D while processing the data stream and at the end of the stream, it outputs an approximation Z to f (x). The space complexity refers to the size, in bits, of D. The update time refers to the time spent to update the data structure D upon receiving a single stream update. The reporting time refers to the time to output the approximation Z at the end of the stream.

Heavy Hitter Oracle:

We assume access to a heavy hitter oracle, which receives an input i ∈ [n], and outputs whether x i will be a heavy hitter at the end of the stream. The definition of heavy hitter varies for different data stream problems. There are two kinds of oracles. The first kind indicates whether or not |x i | ≥ T and the second kind indicates whether or not

|x i | p ≥ 1 T x p p ,

where T is a pre-determined threshold associated with the problem. We shall use an oracle of the first kind for the distinct elements problem and oracles of the second kind for all other problems.

In the experiments, the heavy hitter oracle receives an i ∈ [n] and outputs the predicted value of x i . The implementation of the first kind of oracle is thus straightforward. For the second kind of oracle, there are at most T coordinates x i satisfying |x i | p ≥ 1 T x p p . We shall regard the largest T coordinates in the predicted vector x as the heavy hitters in our implementation (instead of calculating the x p p of the predicted vector x), which is in conformity with the implementation in the prior experiments of Hsu et al. (2019) .

3. DISTINCT ELEMENTS:

The current best algorithm for estimating L 0 = x 0 , in the presence of additions and deletions to coordinates of x, is due to Kane et al. (2010b) . A key component of their algorithm is a constantfactor approximation algorithm, called ROUGHL0ESTIMATOR, which returns a value L 0 satisfying 1 110 L 0 ≤ L 0 ≤ L 0 with probability at least 2/3. The space is O(log n log log(mM )) bits and the update and reporting times are O(1). In this section, we improve the space of ROUGHL0ESTIMATOR to O(log n) bits with the help of a trained oracle. All proofs are postponed to Section A.

The algorithm first picks a pairwise hash function h : [n] → [n] and subsamples n coordinates at log n scales, where the j-th scale consists of the coordinates i for which lsb(h(i)) = j. In each scale, it uses a small-space counting algorithm EXACTCOUNT to obtain, with probability at least 1 -η, the exact value of x 0 at that scale. Then it finds the deepest scale, i.e., the largest j, with x 0 above some fixed constant threshold, and returns L 0 = 2 j as the estimate. If such a j does not exist, it returns L 0 = 1.

The EXACTCOUNT procedure in Kane et al. (2010b) uses a hash function h : [n] → [B]:

, where B = Θ(c 2 ) for some constant c for which h is a perfect hashing of a set of size at most c. Each bucket ∈ [B] is a counter which keeps track of ( h(i)= x i ) mod p for some large prime p. The estimate is the number of nonzero buckets, and EXACTCOUNT returns the maximum estimate of Θ(log(1/η)) parallel repetitions. Now, with the trained oracle, we can pick p to be a smaller poly(1/ ) value in EXACTCOUNT. In the higher-level ROUGHL0ESTIMATOR algorithm, whenever an update is made to a heavy coordinate i identified by the oracle, the corresponding bucket inside EXACTCOUNT is marked as nonempty regardless of the counter value, since we know the heavy item will never be entirely deleted, since by definition it is heavy at the end of the stream (note this is not true of non-heavy elements). In the end, ROUGHL0ESTIMATOR finds the deepest scale with at least one nonempty bucket.

The following is our new guarantee of EXACTCOUNT. Lemma 1. Assume that L 0 ≤ c and suppose that B = Θ(c 2 ). The subroutine EXACTCOUNT returns the exact value of L 0 with probability at least 1 -η using O(B log(1/ )) bits of space, in addition to storing O(log(1/η)) independently chosen pairwise-independent hash functions from Theorem 2. The algorithm ROUGHL0ESTIMATOR outputs a value L 0 , which satisfies 1 110 L 0 ≤ L 0 ≤ L 0 with probability at least 13/16. The space complexity is O(log(n) log(1/ )) bits, and the update and reporting times are O(1).

With a constant-factor estimate R to L 0 , the high-level idea is to subsample each index in [n] with probability K/R. Then the number of distinct surviving items is Θ(K). To estimate the number of distinct surviving items efficiently, one hashes them into Θ(K) buckets and counts the number T of non-empty buckets, which is simulated by updating a bit vector of length Θ(K). The final estimate can be deduced from the number of distinct surviving items, which can be shown to be a (1 + eps)-approximation to F 0 when K = Θ(1/ 2 ). Since we do not know L 0 in advance, we have to guess its value using log n geometrically increasing values, and so our memory can be thought of as a bucket matrix A of dimension (log n) × K. In parallel we run the ROUGHL0ESTIMATOR above, so at the end of the stream, we will obtain a constant-factor estimate R, allowing us to look into the appropriate row of A (the appropriate buckets). A problem is how to efficiently maintain a bucket. In Kane et al. (2010b) , each bucket stores the dot product of frequencies hashing to it with a random vector over a large finite field of order poly(K log(nM )), using O(log K +log log(nM )) = O(log(1/ ) + log log(nM )) bits. Now, using a similar argument to the proof of Lemma 1, with the help of our heavy hitter oracle, we can mark the buckets containing a heavy hitter as nonempty and reduce the order of the finite field to O(poly(1/ )). This improves the space complexity of each bucket to O(log(1/ )) bits. Combined with the complexity of ROUGHL0ESTIMATOR, we conclude with the following theorem. Theorem 3. There is an algorithm for (1± )-approximating L 0 using space O( -2 (log n) log(1/ )) with success probability at least 2/3, and with O(1) update and reporting times.

4. F p ESTIMATION, p > 2:

We start with a well-known algorithm for estimating x p p in a stream. Lemma 4 (Precision Sampling, Andoni et al. (2011) ). There is a randomized algorithm, called the Precision Sampling algorithm, which returns an estimate X to x p p such that it holds with probability at least 0.9 that (1 -) x p p ≤ X ≤ (1 + ) x p p . The algorithm uses B(n) = O(p 2 -2-4/p n 1-2/p log(n) log(M )) bits of space.

In the rest of the section, we assume that there is an oracle which can tell us if |x i | p ≥ 1 s x p p is a heavy hitter. The main idea is that we separately estimate the F p -moment of the heavy hitters, and for the remaining light elements, we use sub-sampling to estimate their contribution with sampling rate 1/ρ.

Let I H , I L ⊆ [n] denote the subsets of indices of the heavy hitters and the light elements, respectively. Since |I H | ≤ s, we can use an F p estimator to (1 + )-approximate x I H p p with space B(s). For the light elements, we use a sub-sampling algorithm: we set a sampling rate 1/ρ, and for each item i ∈ I L , with probability 1/ρ we choose it. For each item i we choose, we calculate To analyze it, we let Y = ρF S , and we have the following lemmas. All proofs in this section are postponed to Section B.

F s = |x i | p

Lemma 5. E[Y ] = x I L p p , Var[Y ] ≤ ρ s x 2p

p . Lemma 6. If we repeat the sub-sampling kρ/s times independently with sub-sampling rate ρ 2 , we can get a (1 ± )-approximation of F p with probability at least 1 -1/k.

If we use the estimator in Lemma 4 in both parts (heavy part and light part), The total space complexity is B(s) + -2 ρ s B( n ρ 2 ). Letting ρ = s = √ n, we obtain an F p estimation algorithm with space O( -4 n 1/2-1/p log(n) log(M )). We remark that this bound is tight in n up to logarithmic factors as there is a lower bound of Ω(n 1/2-1/p ) bits even in the presence of the oracle. Theorem 7. Under the assumption of a heavy hitter oracle, we can estimate x p p within a factor 1 ± 2 in O( -4 n 1/2-1/p log(n) log(M )) bits with success probability at least 3/5.

The above analysis is based on the assumption that the oracle is perfect. In practice, sometimes the oracle makes mistakes. Here we assume that for each item i, the probability the oracle gives us an incorrect prediction is δ. We have the following theorem for noisy oracles.

Theorem 8. With a noisy heavy hitter oracle with error probability δ, we can estimate x p p within a factor 1 ± 2 in O( -4 n 1/2-1/p log(n) log(M )) bits of space when δ = O(1/ √ n), or in O( -4 (nδ)

1-2/p log(n) log(M )) bits of space otherwise. Both guarantees hold with success probability at least 3/5.

5. EXPERIMENTS:





5.1.1. INTERNET TRAFFIC DATA:

For this experiment, the goal is to estimate the number of distinct packets for each network flow. A flow is a sequence of packets between two machines on the Internet. It is identified by the IP addresses of its source and destination and the application ports.

Dataset: The traffic data is collected at a backbone link of a Tier1 ISP between Chicago and Seattle in 2016 (CAIDA). Each recording session is around one hour. Within each minute, there are around 30 million packets (meaning 30 million updates) and 1 million unique flows. The distribution of packet counts over Internet flows is heavy tailed, see Hsu et al. (2019) .

Model: We use the prediction results in Hsu et al. (2019) , which predict the logarithm of the packet counts for each flow. In Hsu et al. (2019) , the authors use two RNNs to encode the source and destination IP addresses separately and additionally use two-layer fully-connected networks to encode the source and destination ports. Then they concatenate the encoded IP vectors, encoded port vectors, and the protocol type as the final features to predict the packet counts. They use the first 7 minutes for training, the following minute for validation, and estimate the packet counts in subsequent minutes.

Results: We plot the estimation error vs. total number of buckets for the 20th minute in the CAIDA data. We run the estimation algorithm 5 times and calculate the average estimation error. The result is shown in Figure 2 . The total number of unique flows appearing in a single test minute is about 1.1 × 10 6 . For every light coordinate, we make an extra update that makes this coordinate 0 with probability 0.5.

There are two parts to our algorithm. For ROUGHL0ESTIMATOR, we set c = 10 and η = 1/4. We use the heavy hitter oracle to predict whether the coordinate will be larger than 2 10 . We randomly select a prime from [11, 31] for the hash buckets. The total number of buckets in this part is about 4 × 10 3 (each bucket can store a number in {0, 1, . . . , 31} and has an extra bit to indicate whether it has been marked). For the other part of our algorithm, we create a bucket matrix A of dimension (log n) × K with K ranging from 2 6 to 2 9 . Each entry in A can also store a number between 0 and 31 and with an additional bit to indicate whether it has been marked. From the plot we can see that the algorithm achieves an approximation error of about 2.5% using at most 1.5 × 10 4 buckets, approximately 1.5% of the space needed if we were to keep an individual counter for each flow.

5.1.2. SYNTHETIC DATA:

To further demonstrate the advantage of having a heavy hitter oracle, we run the previous algorithm due to Kane et al. (2010b) (where we randomly choose a prime p ∈ [11, 31] as the divisor for each bucket) and our modified algorithm on the synthetic data designed as follows: first, we generate an input vector x of dimension n = 10 6 with i.i.d entries uniform on {0, 1, . . . , 100}. Then for each coordinate i and each prime p ∈ [11, 31], we multiply x i by p with probability 0.2. We set the threshold to be a heavy hitter to be 2 10 , that is, the oracle reports x i as a heavy hitter if |x i | > 2 10 .

Results::

We use the optimal parameters in the last experiment (c = 10, η = 1/4 and K = 2 9 ) and vary the total number of buckets from 7000 to 15000. The results are shown in Figure 1 . We see that having an oracle significantly reduces the estimation error. For this experiment, the goal is to estimate the frequency moments of the vector indicating the number of occurrences each search query appears.

Dataset: We use the AOL query log dataset, which consists of 21 million search queries collected from 650 thousand users over 90 days. There are 3.8 million unique queries. Each query is a search phrase with multiple words. The distribution of the search query frequencies is Zipfian, see Hsu et al. (2019) .

Model: We use the prediction result in Hsu et al. (2019) , which predicts the number of times each search phrase appears. In Hsu et al. (2019) , the authors train an RNN with LSTM cells that takes characters of a search phrase as input. The final states encoded by the RNN are fed to a fullyconnected layer to predict the query frequency. They use the first 5 days for training, the following day for validation, and estimate the number of times different search queries appear in subsequent days. We use this prediction result as an indicator of which search phrases are the heavy hitters.

Results: We plot the estimation error versus the total number of buckets for the 50th and 80th day (p = 3 or p = 4). For the same data, we run the estimator 10 times and calculate the average estimation error. The results are shown in Figure 3 .

For our algorithm, we notice that the total number of search phrases that appear in a single day is about n = 1.5 × 10 5 and so √ n < 400. We can store the heavy coordinates identified by the heavy hitter oracle directly. Given the budget of the number of buckets, we divide them into two parts. Half of them were used to store the heavy items, and the other half are used by the sub-sampling algorithm with the precision sampling estimators to estimate the frequency moment of the light elements.

In comparison, we also run the classical precision sampling estimators. Our results show a larger estimation error owing to the constraint of relatively few buckets. Note that for a fixed bucket budget B tot , there is a trade-off between the number k of repetitions and the number B = B tot /k of buckets allotted for the hash function in each repetition. We plot the results for different values of k = 10, 20, 30.

It is clear from the plots that the estimation error of the oracle-aided algorithm is about 1% even when the total number of buckets is small, demonstrating a strong advantage over classical precision sampling estimators.

A number of real-world datasets have the property that the heavy coordinates contribute a large fraction of the F p -moment, as p increases, and so one needs only to obtain a good approximation of the F p -moment of the heavy coordinates. This is indeed one of the reasons why we achieved low error for search query estimation. In order to show that our subsampling algorithm also achieves a good approximation for the light coordinates, we considered the following data set.

We generated an input vector x of dimension n = 10 8 with the first √ n coordinates being heavy and the remaining coordinates being light. Each coordinate is a uniform random variable in (0, 1), later renormalized such that the heavy and the light parts contribute equally to the total F p -moment, i.e., x I H p p = x I L p p . Hence, a good approximation of x p p requires a good approximation of both parts.

Results: We plot the estimation error vs. total number of buckets for p = 3 in Figure 4 . For our algorithm and classical precision sampling, we fixed the number k of repetitions to 100 and varied the total number of buckets from 10 6 to 2 × 10 6 (1% to 2% of the length of x). We repeated the sub-sampling algorithm 9 times. In each of the 9 repetitions, we also used the precision sampling estimators, repeating 100 times.

From the plots we see that our algorithm achieves significantly smaller relative approximation error than the classical precision sampling algorithm for every number of buckets. In particular, using 2 • 10 6 buckets, i.e., 2% space of what is needed to store the entire vector x, our algorithm achieves a 15% relative estimation error while the classical precision sampling obtains only a 27% relative error. Another observation is that since subsampling reduces the space consumption, our algorithm has a faster update time when n is large. Proof of Lemma 1. If a bucket contains a heavy hitter, it is marked nonempty and it is indeed nonempty. It suffices to show that a bucket containing only light coordinates is nonempty modulo p. Since the light coordinates are at most 2 poly(1/ ) , there are at most c of them by assumption, their sum S is thus at most 2 poly(1/ ) . This implies that S has at most poly(1/ ) prime factors. If we choose a random prime p of size poly(1/ ), then S mod p = 0 with probability at least 1 -poly( ) if S = 0. Taking a union bound over Θ(c 2 ) buckets proves the correctness. The space and time complexity are immediate from the description of the algorithm.

Proof of Theorem 2. The proof is almost identical to that in Kane et al. (2010b) . The space and time complexities are follow from the description of the algorithm.

Next we show correctness. Let L 0 (j) denote the true number of distinct elements in the j-th scale. Then E L 0 (j) = L 0 /2 j . Let j * = max{j : E L 0 (j) ≥ 1} and j * * = max{j < j * : E L 0 (j) ≥ 55}. As shown in Kane et al. (2010b) , if j * * exists, it holds that 55 ≤ E L 0 (j * * ) < 110 and Pr{32 < L 0 (j * * ) < 142} ≥ 8/9. With our choices of c = 141 and η = 1/16, EXACTCOUNT returns a nonzero value for the j * * -th scale with probability 8/9 -1/16 > 13/16 by Lemma 1. It follows that the deepest scale j we find satisfies j * * ≤ j ≤ j * . Hence, L 0 = 2 j * * E L 0 (j * * ) ≤ 110 • 2 j and L 0 = 2 j * E L 0 (j * ) ≥ 2 j as desired. If j * * does not exist, then L 0 < 55, and L 0 = 1 is a 55-approximation in this case.

B OMITTED PROOFS IN SECTION 4:

Proof of Lemma 5. We let Y = ρF s = ρ i f i |x i | p , where f i = 1 if i was chosen, and

f i = 0 otherwise. So we have that E[f i ] = 1 ρ . It thus follows that E[Y ] = x I L p p , that is, Y is an unbiased estimate. Then, Var[Y ] = E[Y 2 ] -E[Y ] 2 = ρ 2   E[ i f i |x i | 2p + i =j f i f j |x i | p |x j | p ]   -x 2p p ≤ ρ 2   E[ i f i |x i | 2p ] + i,j 1 ρ 2 |x i | p |x j | p   -x 2p p = ρ i∈I L |x i | 2p .

To bound this, we notice that we have the fact that x i < 

√ n) + O -2 )B( √ n 2 ) = O( -4 n 1 2 -1 p log(n) log(M )).

Proof of Theorem 8. For an element x i which the oracle indicates as light, we know that with probability 1 -δ, it is truly light. Combined with Theorem 5, we obtain that

Var[Y ] ≤ ρ(1 -δ) i∈I L |x i | 2p + ρδ i∈I H |x i | 2p ≤ (1 -δ) ρ s x 2p p + ρδ x 2p p .

Hence, when δ = O( 1 √ n ), Theorem 7 continues to hold. Otherwise we can let s = nδ and ρ = 2 δ -1 , and the space complexity becomes O( -4 (nδ) 1-2 p log(n) log(M )) bits.

Lower Bound The upper bound in Theorem 7 is asymptotically tight in n up to logarithmic factors, since we have the following matching lower bound even in the presence of an oracle which indicates whether |x i | > 1 √ n x p p . Theorem 9. Suppose that 1/ √ n < < 1/4 and that a heavy hitter oracle indicates whether |x i | > 1 √ n x p p for the whole underlying vector x. Any randomized streaming algorithm that estimates x p p with a factor (1 ± ) with probability ≥ 9/10 requires Ω( -2/p n 1/2-1/p ) bits of space.

Proof of Theorem 9. We assume √ n to be an integer and define our hard instance as follows: for every 1 ≤ i ≤ √ n, we let x i = 1 with probability 1-1/ √ n, and x i = (4 ) 1/p n 1/2p with probability 1/ √ n. And for i > √ n, x i = x i mod √ n . In this case, x p p ≥ n, so any coordinate will not be a heavy hitter. We note that if our algorithm can outputs an (1 ± ) approximation of x p p , it can also output an (1 ± ) approximation of x [ 

√ n. Otherwise, Y ≥ (1 -)( √ n -1 + 4 √ n) > (1 + ) √ n.

By this reduction, we can finally get an Ω(m/k 2 ) = Ω( -2/p n 1/2-1/p ) bits space lower bound under the oracle assumption.

C FAST MOMENT ESTIMATION, 0 < p < 2 When 0 < p < 2, the F p estimation problem can be done in an optimal O( -2 log n) bits of space.

Here we show how to improve the update time while maintaining this amount of space.

In the rest of the section, we assume there are two oracles: one can tell us whether |x i | p ≥ 2 x p p , and the other can tell us whether |x i | p ≥ 2 log 2 (1/ ) log log(1/ ) x p p . We call these 3 categories of elements heavy elements, medium elements, and light elements. Let I H , I M , I L ⊆ [n] denote the subset of indices of the heavy elements, medium elements, and the light elements, respectively.

For the heavy elements, we can use O( -2 log(M )) space to store them. We now turn to the other two parts. For the light elements, we will use the LightEstimator in Section 3 in Kane et al. (2011): 

:



Figures and Tables:

[n]  to[B]. The update and reporting times are O(1). Now we specify some details of the algorithm ROUGHTL0ESTIMATOR. It chooses c = 141 and η = 1/16 for EXACTCOUNT, and the EXACTCOUNT algorithms for different scales all share the same O(log(1/η)) hash functions. The following is our new guarantee.

, and use ρF s to estimation x I L p p . By a Chernoff bound, with high probability, we sample at most 3n/ρ elements.

Figure 1: The estimation error of the L 0norm in the synthetic data Figure 2: The estimation error of the L 0norm in the 20th minute of the CAIDA data

Figure 3: The estimation error of the moment of search queries. The left figure corresponds to p = 3 (80th test day) and the right p = 4 (50th test day).

Figure 4: Estimation error for the F 3moment on synthetic data

lower bound, we will use the k ∞ communication problem inBar-Yossef et al. (2004): there are two parties, Alice and Bob, holding vectors a, b ∈ Z m respectively, and their goal is todecide if a -b ∞ ≤ 1 or a -b ∞ ≥ k. FromBar-Yossef et al. (2004), we can get an Ω(m/k 2 ) bits lower bound. Now we claim that: if we set m = √ n, k = (4 ) 1/p n 1/2p and make a-b = x [ √ n] , then any streaming algorithm outputs a (1 ± ) approximation Y of x [ √ n] pp can be used to build a communication protocol for solving this k ∞ problem with communication proportional to the algorithm's space complexity. In this case, if a -b ∞ = 1, then we have Y ≤ (1 + ) x [

Summary of the threshold of the heavy hitter oracles used in each problem. Note that two oracles are used for the F p Moment Fast Update problem.

Table content: <table/>

7  8 by independently running 9 estimators and then taking the median.For the light elements, for every sub-sample round i, we independently run O(1) estimators with rate √ n 2 and use their median Z i to be the estimate of this level of sub-sampling. Let Y i be the true F p -moment of this sub-sample. Then with probability at least 99 100 it holds that |Y i -Z i | ≤ Y i . Taking a union bound, we get that if we do the sub-sampling 10 times, with probability at least 9 10 , |Y i -Z i | ≤ x I L p p holds for every i. Using Lemma 6 we can get that with probability at least 9 10 , |Z -x I L

Table content: <table><tr><td>p p | ≤ x I L</td><td colspan="6">p p + x p p . The overall success probability of this part is at least 4 5 .</td></tr><tr><td colspan="4">So we get that |H + Z -x p p | ≤ x I L</td><td colspan="3">p p + x p p + x I H</td><td>p p = 2 x p p with success probability at</td></tr><tr><td colspan="5">least 3/5. The total space complexity is B(</td><td/></tr><tr><td/><td/><td/><td/><td/><td/><td>x p p s and p &gt; 2, so</td></tr><tr><td/><td>ρ</td><td>i∈I L</td><td colspan="2">x 2p ≤ ρs</td><td colspan="2">x 2p p s 2 =</td><td>ρ s</td><td>x 2p p .</td></tr><tr><td colspan="5">So finally we have that Var[Y ] ≤ ρ s x 2p p .</td><td/></tr><tr><td colspan="7">Proof of Lemma 6. By Chebyshev's inequality, we have that</td></tr><tr><td/><td colspan="5">Pr |Y -x p p | &gt; x p p ≤</td><td>ρ 2 ks |x 2p p ρ s 2 x 2p p</td><td>=</td><td>1 k</td><td>.</td></tr></table>

Peer review (iclr2020):
The paper talks about calculating various statistics over data streams. This is a very popular topic and is very relevant in big data analysis. A lot of work has been done in this general area and on the problems that are discussed in the paper. The new idea in the paper is better streaming algorithms under the assumption that there is a “heavy hitters” oracle that returns data items that have a lot of representation in the stream. The authors give provably better algorithms for the distinct elements problem, F_p moment problem (p > 2), and some more problems. These are important problems in streaming data analysis. They improve the space bounds and interestingly in some cases the bounds are better than what is possible without the oracle assumption. This also shows the power of such an oracle. There are experimental results to demonstrate the efficiency of the algorithms. At a high level the work seems good and interesting for a large audience interested in streaming data analysis. I have not gone over the proofs in detail (much of which is in the appendix). - Even though oracle results are interesting, to make it practical it may make sense to talk about a more realistic, weaker oracle where some of the queries may be incorrect. - It may even make sense to minimise the number of oracle calls which can be thought of as a resource and discuss the relationship between number of oracle calls and other resources such as space.