Approximate counting algorithm: Difference between revisions

Revision as of 16:50, 24 December 2022

Revision as of 20:21, 21 July 2023

Line 53:

While using powers of 2 as counter values is memory efficient, arbitrary values tend to create a dynamic error range, and the smaller values will have a greater error ratio than bigger values. Other methods of selecting counter values consider parameters such as memory availability, desired error ratio, or counting range to provide an optimal set of values.<ref>Tsidon, Erez, Iddo Hanniel, and Isaac Keslassy. "Estimators also need shared values to grow together." INFOCOM, 2012 Proceedings IEEE. IEEE, 2012.</ref>

However, when several counters share the same values, values are optimized according to the counter with the largest counting range, and produce sub-optimal accuracy for smaller counters. Mitigation is achieved by maintaining Independent Counter Estimation buckets,<ref>{{Cite journalbook|last1=Einziger|first1=G.|last2=Fellman|first2=B.|last3=Kassner|first3=Y.|date=April 2015|title=Independent counter estimation buckets|journal=2015 IEEE Conference on Computer Communications (INFOCOM) |chapter=Independent counter estimation buckets |date=April 2015|pages=2560–2568|doi=10.1109/INFOCOM.2015.7218646|isbn=978-1-4799-8381-0|s2cid=15673730 }}</ref> which restrict the effect of a larger counter to the other counters in the bucket.

==Algorithm==