HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm

HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm

This extended abstract describes and analyses a near-optimal probabilistic algorithm, HYPERLOGLOG, dedicated to estimating the number of \emphdistinct elements (the cardinality) of very large data ensembles. Using an auxiliary memory of m units (typically, "short bytes''), HYPERLOGLOG...

Full description

Bibliographic Details
Main Authors: Philippe Flajolet, Éric Fusy, Olivier Gandouet, Frédéric Meunier
Format: Article
Language:English
Published: Discrete Mathematics & Theoretical Computer Science 2007-01-01
Series:Discrete Mathematics & Theoretical Computer Science
Subjects:
cardinality estimation
probabilistic algorithm
[info.info-ds] computer science [cs]/data structures and algorithms [cs.ds]
[info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
[math.math-co] mathematics [math]/combinatorics [math.co]
[info.info-cg] computer science [cs]/computational geometry [cs.cg]
Online Access:https://dmtcs.episciences.org/3545/pdf

Internet

https://dmtcs.episciences.org/3545/pdf

Similar Items