Composable Sketches for Functions of Frequencies: Beyond the Worst Case

Understand

Recently there has been increased interest in using machine learning techniques to improve classical algorithms.

• In this paper we study when it is possible to construct compact, composable sketches for weighted sampling and statistics estimation according to functions of data frequencies.
• Such structures are now central components of large-scale data analytics and machine learning pipelines.
• However, many common functions, such as thresholds and p-th frequency moments with p > 2, are known to require polynomial-size sketches in the worst case.