HackerPapers

arXiv:1604.05492cs.IR

Count-Min Tree Sketch: Approximate counting for NLP

Guillaume Pitel, Geoffroy Fouquier, Emmanuel Marchand, Abdul Mouhamadsultane

HN submission. Found in a submission link or body. Submitters do not count as commenters in the main ranking; a submission is not an endorsement.

Abstract

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.

arXiv comments
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
Journal reference
DOI
Subjects
cs.IRInformation Retrieval

On Hacker News

No comments linking this paper were found in the collected sources. Found in 1 HN submission from Apr 2016 to Apr 2016. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments0 threads

No comments linking this paper were found in the collected sources. Open submission discussions.

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.