Frequency Estimation in Data Streams: Learning the Optimal Hashing Scheme
arXiv:2007.09261 · doi:10.1109/TKDE.2021.3103819
Abstract
We present a novel approach for the problem of frequency estimation in data streams that is based on optimization and machine learning. Contrary to state-of-the-art streaming frequency estimation algorithms, which heavily rely on random hashing to maintain the frequency distribution of the data steam using limited storage, the proposed approach exploits an observed stream prefix to near-optimally hash elements and compress the target frequency distribution. We develop an exact mixed-integer linear optimization formulation, which enables us to compute optimal or near-optimal hashing schemes for elements seen in the observed stream prefix; then, we use machine learning to hash unseen elements. Further, we develop an efficient block coordinate descent algorithm, which, as we empirically show, produces high quality solutions, and, in a special case, we are able to solve the proposed formulation exactly in linear time using dynamic programming. We empirically evaluate the proposed approach both on synthetic datasets and on real-world search query data. We show that the proposed approach outperforms existing approaches by one to two orders of magnitude in terms of its average (per element) estimation error and by 45-90% in terms of its expected magnitude of estimation error.
arXiv commentSubmitted to IEEE Transactions on Knowledge and Data Engineering on 07/2020. Revised on 05/2021
References in corpus (9)
- Learning Combinatorial Optimization Algorithms over Graphs
- Fast Supervised Hashing with Decision Trees for High-Dimensional Data
- A Deep Learning Approach to Structured Signal Recovery
- Improving Online Algorithms via ML Predictions
- Learning to Optimize Join Queries With Deep Reinforcement Learning
- Learning to Branch
- A Model for Learned Bloom Filters, and Optimizing by Sandwiching
- Fast Exact k-Means, k-Medians and Bregman Divergence Clustering in 1D
- (Learned) Frequency Estimation Algorithms under Zipfian Distribution