2021/02/07 by Emanuele Dolera, Dolera, Emanuele, Stefano Favaro +3
Computer Science · #Algorithms and Data Compression #Bayesian Methods and Mixture Models #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Music and Audio Processing #Speech Recognition and Synthesis
paper · pdf · doi:10.48550/arxiv.2102.03743
openalex publication_date 2021/02/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The count-min sketch (CMS) is a randomized data structure that provides\nestimates of tokens' frequencies in a large data stream using a compressed\nrepresentation of the data by random hashing. In this paper, we rely on a\nrecent Bayesian nonparametric (BNP) view on the CMS to develop a novel\nlearning-augmented CMS under power-law data streams. We assume that tokens in\nthe stream are drawn from an unknown discrete distribution, which is endowed\nwith a normalized inverse Gaussian process (NIGP) prior. Then, using\ndistributional properties of the NIGP, we compute the posterior distribution of\na token's frequency in the stream, given the hashed data, and in turn\ncorresponding BNP estimates. Applications to synthetic and real data show that\nour approach achieves a remarkable performance in the estimation of\nlow-frequency tokens. This is known to be a desirable feature in the context of\nnatural language processing, where it is indeed common in the context of the\npower-law behaviour of the data.\n