LEARNING-BASED FREQUENCY ESTIMATION ALGORITHMS
Estimating the frequencies of elements in a data stream is a fundamental task in data analysis and machine learning. The problem is typically addressed using streaming algorithms which can process very large data using limited storage. Today's streaming algorithms, however, cannot exploit patterns in their input to improve performance. We propose a new class of algorithms that automatically learn relevant patterns in the input data and use them to improve its frequency estimates. The proposed algorithms combine the benefits of machine learning with the formal guarantees available through algorithm theory. We prove that our learning-based algorithms have lower estimation errors than their non-learning counterparts. We also evaluate our algorithms on two real-world datasets and demonstrate empirically their performance gains.
Quality/clarity:
- The problem setting description is neither formal nor intuitive which made it very hard for me to understand exactly the problem you are trying to solve. Starting with S and i: I guess S and i are both simply varying-length sequences in U.
- In general the intro should focus more on an intuitive (and/or formal) explanation of the problem setting, with some equations that explain the problem you want to work on. Right now it is too heavy on 'related work' (this is just my opinion).
Originality/Significance:
I have certainly never seen a ML-based paper on this topic. The idea of 'learning' prior information about the heavy hitters seems original.
Pros:
It seems like a creative and interesting place to use machine learning. the plots in Figure 5.2 seem promising.
Cons:
- The formalization in Paragraph 3 of the Intro is not very formal. I guess S and i are both simply varying-length sequences in U.
- In general the intro should focus more on an intuitive (and/or formal) explanation of the problem setting, with some equations that explain the problem you want to work on. Right now it is too heavy on 'related work' (this is just my opinion).
-In describing Eqn 3 there are some weird remarks, e.g. "N is the sum of all frequencies". Do you mean that N is the total number of available frequencies? i.e. should it be |D|? It's not clear to me that the sum of frequencies would be bounded if D is not discrete.
- Your F and \tilde{f} are introduced as infinite series. Maybe they should be {f1, f2,..., fN}, i.e. N queries, each of which you are trying to be estimate.
- In general, you have to introduce the notation much more carefully. Your audience should not be expected to be experts in hashing for this venue!! 'C[1,...,B]' is informal abusive notation. You should clearly state using both mathematical notation AND using sentences what each symbol means. My understanding is that that h:U->b, is a function from universe U to natural number b, where b is an element from the discrete set {1,...,B}, to be used as an index for vector C. The algorithm maintains this vector C\in N^B (ie C is a B-length vector of natural numbers). In other words, h is mapping a varying-length sequence from U to an *index* of the vector C (a.k.a: a bin). Thus C[b] denotes the b-th element/bin of C, and C[h(i)] denotes the h(i)-th element. 
- Still it is unclear where 'fj' comes from. You need to state in words eg "C[b] contains the accumulation of all fj's such that h(j)=b; i.e. for each sequence j \in U, if the hash function h maps the sequence to bin b (ie $h(j)=b$), then we include the *corresponding frequency* in the sum."
- What I don't understand is how fj is dependent on h. When you say "at the end of the stream", you mean that given S, we are analyzing the frequency of a series of sequences {i_1,...,i_N}?
- Sorry, it's just confusing and I didn't really understand "Single Hash Function" from Sec 3.2 until I started typing this out.
- The term "sketch" is used in Algorithm1, like 10, before 'sketch' is defined!!
-I'm not going to trudge through the proofs, because I don't think this is self-contained (and I'm clearly not an expert in the area).
Conclusion:
Honestly, this paper is very difficult to follow. However to sum up the idea: you want to use deep learning techniques to learn some prior on the hash-estimation problem, in the form of a heavy-hitter oracle. It seems interesting and shows promising results, but the presentation has to be cleaned up for publication in a top ML venue.
******
Update after response:
The authors have provided improvements to the introduction of the problem setting, satisfying most of my complaints from before. I am raising my score accordingly, since the paper does present some novel results.