A Smoothed-Bayesian Approach to Frequency Recovery from Sketched Data

• 成果类型: Article; Early Access
• 署名作者: Beraha, Mario; Favaro, Stefano; Sesia, Matteo
• 署名单位: University of Milano-Bicocca; University of Turin; Collegio Carlo Alberto; University of Southern California; University of Southern California
• 刊物名称: JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION
• ISSN/ISSBN: 0162-1459
• DOI: 10.1080/01621459.2025.2490302
• 发表日期: 2025
• 关键词: priors

摘要

We provide a novel statistical perspective on a classical problem at the intersection of computer science and information theory: recovering the empirical frequency of a symbol in a large discrete dataset using only a compressed representation, or sketch, obtained via random hashing. Departing from traditional algorithmic approaches, recent works have proposed Bayesian nonparametric (BNP) methods that can provide more informative frequency estimates by leveraging modeling assumptions about the distribution of the sketched data. In this article, we propose an alternative smoothed-Bayesian approach, inspired by existing BNP methods but designed to overcome their computational limitations when dealing with large-scale data from realistic distributions, including those with power-law tail behaviors. For sketches obtained with a single hash function, our approach is supported by precise theoretical guarantees, including unbiasedness and optimality under a Bayesian framework within an intuitive class of linear estimators. For sketches with multiple hash functions, we introduce an approach based on multi-view learning to construct computationally efficient frequency estimators. We validate our method on synthetic and real data, comparing its performance to that of existing alternatives. Supplementary materials for this article are available online, including a standardized description of the materials available for reproducing the work.