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. Classical algorithms provide formal guarantees over their performance, but often fail to leverage useful patterns in their input data to improve their output. On the other hand, deep learning models are highly successful at capturing and utilizing complex data patterns, but often lack formal error bounds. The last few years have witnessed a growing effort to bridge this gap and introduce algorithms that can adapt to data properties while delivering worst case guarantees. Deep learning modules have been integrated into the design of Bloom filters (Kraska et al., 2018; BID18 , caching algorithms (Lykouris & Vassilvitskii, 2018) , graph optimization BID12 , similarity search BID22 BID29 ) and compressive sensing BID3 . This paper makes a significant step toward this vision by introducing frequency estimation streaming algorithms that automatically learn to leverage the properties of the input data.Estimating the frequencies of elements in a data stream is one of the most fundamental subroutines in data analysis. It has applications in many areas of machine learning, including feature selection BID0 , ranking (Dzogang et al., 2015) , semi-supervised learning BID27 and natural language processing (Goyal et al., 2012) . It has been also used for network measurements (Estan & Varghese, 2003; BID30 BID28 and security BID23 . Frequency estimation algorithms have been implemented in popular data processing libraries, such as Algebird at Twitter BID4 . They can answer practical questions like: what are the most searched words on the Internet? or how much traffic is sent between any two machines in a network?The frequency estimation problem is formalized as follows: given a sequence S of elements from some universe U , for any element i ∈ U , estimate f i , the number of times i occurs in S. If one could store all arrivals from the stream S, one could sort the elements and compute their frequencies. However , in big data applications, the stream is too large (and may be infinite) and cannot be stored. This challenge has motivated the development of streaming algorithms, which read the elements of S in a single pass and compute a good estimate of the frequencies using a limited amount of space.1 Over the last two decades, many such streaming algorithms have been developed, including Count-Sketch BID7 , Count-Min BID11 ) and multistage filters (Estan & Varghese, 2003) . The performance guarantees of these algorithms are wellunderstood, with upper and lower bounds matching up to O(·) factors (Jowhari et al., 2011) .However, such streaming algorithms typically assume generic data and do not leverage useful patterns or properties of their input. For example, in text data , the word frequency is known to be inversely correlated with the length of the word. Analogously, in network data, certain applications tend to generate more traffic than others. If such properties can be harnessed, one could design frequency estimation algorithms that are much more efficient than the existing ones. Yet, it is important to do so in a general framework that can harness various useful properties, instead of using handcrafted methods specific to a particular pattern or structure (e.g., word length, application type).In this paper, we introduce learning-based frequency estimation streaming algorithms. Our algorithms are equipped with a learning model that enables them to exploit data properties without being specific to a particular pattern or knowing the useful property a priori. We further provide theoretical analysis of the guarantees associated with such learning-based algorithms.We focus on the important class of "hashing-based" algorithms, which includes some of the most used algorithms such as Count-Min, Count-Median and Count-Sketch. Informally, these algorithms hash data items into B buckets, count the number of items hashed into each bucket, and use the bucket value as an estimate of item frequency. The process can be repeated using multiple hash functions to improve accuracy. Hashing-based algorithms have several useful properties. In particular, they can handle item deletions , which are implemented by decrementing the respective counters. Furthermore, some of them (notably Count-Min ) never underestimate the true frequencies, i.e., f i ≥ f i holds always. However, hashing algorithms lead to estimation errors due to collisions: when two elements are mapped to the same bucket, they affect each others' estimates. Although collisions are unavoidable given the space constraints, the overall error significantly depends on the pattern of collisions. For example, collisions between high-frequency elements ("heavy hitters") result in a large estimation error, and ideally should be minimized. The existing algorithms, however, use random hash functions, which means that collisions are controlled only probabilistically.Our idea is to use a small subset of S, call it S , to learn the heavy hitters. We can then assign heavy hitters their own buckets to avoid the more costly collisions. It is important to emphasize that we are learning the properties that identify heavy hitters as opposed to the identities of the heavy hitters themselves. For example, in the word frequency case, shorter words tend to be more popular. The subset S itself may miss many of the popular words, but whichever words popular in S are likely to be short. Our objective is not to learn the identity of high frequency words using S . Rather, we hope that a learning model trained on S learns that short words are more frequent, so that it can identify popular words even if they did not appear in S .Our main contributions are as follows:• We introduce learning-based frequency estimation streaming algorithms, which learn the properties of heavy hitters in their input and exploit this information to reduce errors• We provide performance guarantees showing that our algorithms can deliver a logarithmic factor improvement in the error bound over their non-learning counterparts. Furthermore, we show that our learning-based instantiation of Count-Min, a widely used algorithm, is asymptotically optimal among all instantiations of that algorithm. See Table 4 .1 in section 4.1 for the details.• We evaluate our learning-based algorithms using two real-world datasets: traffic load on an Internet backbone link and search query popularity. In comparison to their non-learning counterparts, our algorithms yield performance gains that range from 18% to 71%. We have presented a new approach for designing frequency estimation streaming algorithms by augmenting them with a learning model that exploits data properties. We have demonstrated the benefits of our design both analytically and empirically. We envision that our work will motivate a deeper integration of learning in algorithm design, leading to more efficient algorithms.
Data stream algorithms can be improved using deep learning, while retaining performance guarantees.
{"src": "scitldr-AIC_train", "paper_id": "r1lohoCqY7"}