2007, English, Article edition: HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm Flajolet, Philippe; Fusy, Eric; Gandouet, Olivier; ...

User activity

Share to:
 
Bookmark: http://trove.nla.gov.au/version/208333
Physical Description
  • text
Published
  • HAL - CCSD
  • 2007
Language
  • English

Edition details

Title
  • HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm
Author
  • Flajolet, Philippe
  • Fusy, Eric
  • Gandouet, Olivier
  • Meunier, Frédéric
Published
  • HAL - CCSD
  • 2007
Physical Description
  • text
Subjects
Notes
  • This extended abstract describes and analyses a near-optimal probabilistic algorithm, HYPERLOGLOG , dedicated to estimating the number of distinct elements (the cardinality) of very large data ensembles. Using an auxiliary memory of m units (typically, “short bytes”), HYPERLOGLOG performs a single pass over the data and produces an estimate of the cardinality such that the relative accuracy (the standard error) is typically about 1.04/​√m. This improves on the best previously known cardinality estimator, LOGLOG, whose accuracy can be matched by consuming only 64% of the original memory. For instance, the new algorithm makes it possible to estimate cardinalities well beyond 10^9 with a typical accuracy of 2% while using a memory of only 1.5 kilobytes. The algorithm parallelizes optimally and adapts to the sliding window model.
  • HAL:hal-00406166, version 1
  • HAL:http:/​/​hal.archives-ouvertes.fr/​hal-00406166/​en/​
Language
  • English
Contributed by
OAIster

Get this edition

  • Set up My libraries

    How do I set up "My libraries"?

    In order to set up a list of libraries that you have access to, you must first login or sign up. Then set up a personal list of libraries from your profile page by clicking on your user name at the top right of any screen.

  • All (1)
  • Unknown (1)
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.

User activity


e.g. test cricket, Perth (WA), "Parkes, Henry"

Separate different tags with a comma. To include a comma in your tag, surround the tag with double quotes.

Be the first to add a tag for this edition

Be the first to add this to a list

Comments and reviews

What are comments? Add a comment

No user comments or reviews for this version

Add a comment