HackerPapers

arXiv:1612.02284cs.DS

LogLog-Beta and More: A New Algorithm for Cardinality Estimation Based on LogLog Counting

Jason Qin, Denys Kim, Yumei Tung

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

Abstract

The information presented in this paper defines LogLog-Beta. LogLog-Beta is a new algorithm for estimating cardinalities based on LogLog counting. The new algorithm uses only one formula and needs no additional bias corrections for the entire range of cardinalities, therefore, it is more efficient and simpler to implement. Our simulations show that the accuracy provided by the new algorithm is as good as or better than the accuracy provided by either of HyperLogLog or HyperLogLog++. In addition to LogLog-Beta we also provide another one-formula estimator for cardinalities based on order statistics, a modification of an algorithm developed by Lumbroso.

arXiv comments
Journal reference
DOI
Subjects
cs.DSData Structures and Algorithms

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from Dec 2016 to Dec 2016.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. Cardinality Estimation (2011) [pdf] 1 comment

    • See the Arxiv paper[0] on it. Found this from the Redis code[1] (I was curious, too). [0]:https://arxiv.org/abs/1612.02284 [1]:https://github.com/antirez/redis/blob/87538cb7fe19b567118944...

      octernionView on HNParent context

Submitted to Hacker News

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