2016/04/19 by Guillaume Pitel, Geoffroy Fouquier, Pitel, Guillaume +5 · 1 voice
Computer Science · #Advanced Database Systems and Queries #Data Management and Algorithms #FOS: Computer and information sciences #Information Retrieval (cs.IR) #Web Data Mining and Analysis #cs.IR
paper · pdf · doi:10.48550/arxiv.1604.05492
submitted to the second International Symposium on Web Algorithms (iSwag'2016). arXiv admin note: text overlap with arXiv:1502.04885, In the proceedings of the Second International Symposium on Web Algorithms (iSWAG 2016), June 9-10, 2016, Deauville, Normandy, France
openalex publication_date 2016/04/19 · arxiv published 2016/04/19 · arxiv created 2016/06/15 · arxiv updated 2016/06/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Count-Min Sketch is a widely adopted structure for approximate event counting in large scale processing. In a previous work we improved the original version of the Count-Min-Sketch (CMS) with conservative update using approximate counters instead of linear counters. These structures are computationaly efficient and improve the average relative error (ARE) of a CMS at constant memory footprint. These improvements are well suited for NLP tasks, in which one is interested by the low-frequency items. However, if Log counters allow to improve ARE, they produce a residual error due to the approximation. In this paper, we propose the Count-Min Tree Sketch (Copyright 2016 eXenSa. All rights reserved) variant with pyramidal counters, which are focused toward taking advantage of the Zipfian distribution of text data.