github.com/seiflotfy/count-min-log
Package cml implments the Count-Min-Log datastructure. It is based on Count-Min-Log sketch: Approximately counting with approximate counters - Guillaume Pitel & Geoffroy Fouquier http://iswag-symposium.org/2015/pdfs/shortpaper1.pdf TL;DR: Count-Min-Log Sketch for improved Average Relative Error on low frequency events Count-Min Sketch is a widely adopted algorithm for approximate event counting in large scale processing. However, the original version of the Count-Min-Sketch (CMS) suffers of some deficiences, especially if one is interested in the low-frequency items, such as in text- mining related tasks. Several variants of CMS have been proposed to compensate for the high relative error for low-frequency events, but the proposed solutions tend to correct the errors instead of preventing them. In this paper, we propose the Count-Min-Log sketch, which uses logarithm-based, approximate counters instead of linear counters to improve the average relative error of CMS at constant memory footprint.
Readme
TL;DR: Count-Min-Log Sketch for improved Average Relative Error on low frequency events
Count-Min Sketch is a widely adopted algorithm for approximate event counting in large scale processing. However, the original version of the Count-Min-Sketch (CMS) suffers of some deficiences, especially if one is interested in the low-frequency items, such as in text- mining related tasks. Several variants of CMS have been proposed to compensate for the high relative error for low-frequency events, but the proposed solutions tend to correct the errors instead of preventing them. In this paper, we propose the Count-Min-Log sketch, which uses logarithm-based, approximate counters instead of linear counters to improve the average relative error of CMS at constant memory footprint.
This version implements the 16 bit register version. Will add back the 8-bit version soon.
import cml
...
sk, err := cml.NewDefaultSketch()
sk.IncreaseCount([]byte("scott pilgrim"))
...
sk.Frequency([]byte("scott pilgrim")) // ==> 1
FAQs
Package cml implments the Count-Min-Log datastructure. It is based on Count-Min-Log sketch: Approximately counting with approximate counters - Guillaume Pitel & Geoffroy Fouquier http://iswag-symposium.org/2015/pdfs/shortpaper1.pdf TL;DR: Count-Min-Log Sketch for improved Average Relative Error on low frequency events Count-Min Sketch is a widely adopted algorithm for approximate event counting in large scale processing. However, the original version of the Count-Min-Sketch (CMS) suffers of some deficiences, especially if one is interested in the low-frequency items, such as in text- mining related tasks. Several variants of CMS have been proposed to compensate for the high relative error for low-frequency events, but the proposed solutions tend to correct the errors instead of preventing them. In this paper, we propose the Count-Min-Log sketch, which uses logarithm-based, approximate counters instead of linear counters to improve the average relative error of CMS at constant memory footprint.
Did you know?
Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.
Security News
Git dependencies in open source packages can introduce significant risks, including lack of version control, stability issues, dependency drift, and difficulty in auditing, making them potential targets for supply chain attacks.
Security News
Node.js has added experimental support for TypeScript, a move that highlights the growing importance of TypeScript in modern development.
Product
Check out what's new at Socket with our Product Changelog. It tracks all public-facing updates, improvements, and fixes so you can take full advantage of our features.