Skip to yearly menu bar Skip to main content


Poster

Learning-Based Frequency Estimation Algorithms

Chen-Yu Hsu · Piotr Indyk · Dina Katabi · Ali Vakilian

Great Hall BC #42

Keywords: [ count-sketch ] [ count-min ] [ heavy-hitters ] [ streaming algorithms ]


Abstract:

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.

Live content is unavailable. Log in and register to view live content