5 ms·

Counting Billion Distinct Objects Using Only 1.5KB of Memory (2012)

ec109685 5y ago
These are in use within a lot of production systems: https://datasketches.apache.org/ https://datasketches.apache.org/
- ignoramous 5y ago
  See also: http://mmds.org/ http://mmds.org/ and their youtube channel https://www.youtube.com/channel/UCmLB71obuOBLMdWCQUI-DiA https://www.youtube.com/channel/UCmLB71obuOBLMdWCQUI-DiA
dafelst 5y ago
Just to be that guy, the title of the article should include the word "approximately" as HyperLogLog and other probabilistic sketches are all (albeit often quite accurate) approximation methods.
- slver 5y ago
  Nah we need that guy, because I'm sick of clickbait titles.
  - killingtime74 5y ago
    The article like you pointed out is comparing apples to oranges. I could use 0 bits of memory to count if I’m able to accept 100% error to take the extreme case
    - makapuf 5y ago
      You could even be statistically better with a probabilistic guess from the size of the entry and still no memory used.
- nimchimpsky 5y ago
  Its the key point, the title is misleading - they are not counting, they are guessing.
hangonhn 5y ago
This article is old but really good at explaining HyperLogLog: http://blog.notdot.net/2012/09/Dam-Cool-Algorithms-Cardinality-Estimation http://blog.notdot.net/2012/09/Dam-Cool-Algorithms-Cardinali...
- wallacoloo 5y ago
  > Specifically, by throwing out the 30% of buckets with the largest values, and averaging only 70% of buckets with the smaller values, accuracy can be improved from 1.30/sqrt(m) to only 1.05/sqrt(m)! How do you do this without sorting? Or, do you approximate again by throwing out everything < 0.3 * max_hash? It’s not obvious to me how that approach would actually give any better results: the spacing between 0.3 * max_hash and the next lowest hash is just as prone to variance as the distance between 0 and the absolute lowest hash, and it’s that distance which feeds the estimate.
Radim 5y ago
For Python, there's Bounter, "Efficient Counter that uses a limited (bounded) amount of memory regardless of data size." https://github.com/RaRe-Technologies/bounter https://github.com/RaRe-Technologies/bounter Apart from HyperLogLog, Bounter implements a bunch of other nifty (fast) approximate counting algorithms like CountMinSketch.
LittlePeter 5y ago
> Here is an example: 4f67bfc603106cb2. These 16 characters represent 128 bits. These look like hex digits. 16 hex digits is 8 bytes which is 64 bits. What am I missing?
- hansvm 5y ago
  The author was probably viewing those as some sort of byte-per-character encoding rather than hex.

These are in use within a lot of production systems: https://datasketches.apache.org/ https://datasketches.apache.org/

ignoramous 5y ago
See also: http://mmds.org/ http://mmds.org/ and their youtube channel https://www.youtube.com/channel/UCmLB71obuOBLMdWCQUI-DiA https://www.youtube.com/channel/UCmLB71obuOBLMdWCQUI-DiA

Just to be that guy, the title of the article should include the word "approximately" as HyperLogLog and other probabilistic sketches are all (albeit often quite accurate) approximation methods.

slver 5y ago
Nah we need that guy, because I'm sick of clickbait titles.
- killingtime74 5y ago
  The article like you pointed out is comparing apples to oranges. I could use 0 bits of memory to count if I’m able to accept 100% error to take the extreme case
  - makapuf 5y ago
    You could even be statistically better with a probabilistic guess from the size of the entry and still no memory used.
nimchimpsky 5y ago
Its the key point, the title is misleading - they are not counting, they are guessing.

hangonhn 5y ago

This article is old but really good at explaining HyperLogLog: http://blog.notdot.net/2012/09/Dam-Cool-Algorithms-Cardinality-Estimation http://blog.notdot.net/2012/09/Dam-Cool-Algorithms-Cardinali...

wallacoloo 5y ago
> Specifically, by throwing out the 30% of buckets with the largest values, and averaging only 70% of buckets with the smaller values, accuracy can be improved from 1.30/sqrt(m) to only 1.05/sqrt(m)! How do you do this without sorting? Or, do you approximate again by throwing out everything < 0.3 * max_hash? It’s not obvious to me how that approach would actually give any better results: the spacing between 0.3 * max_hash and the next lowest hash is just as prone to variance as the distance between 0 and the absolute lowest hash, and it’s that distance which feeds the estimate.

Radim 5y ago

For Python, there's Bounter, "Efficient Counter that uses a limited (bounded) amount of memory regardless of data size." https://github.com/RaRe-Technologies/bounter https://github.com/RaRe-Technologies/bounter Apart from HyperLogLog, Bounter implements a bunch of other nifty (fast) approximate counting algorithms like CountMinSketch.

LittlePeter 5y ago

> Here is an example: 4f67bfc603106cb2. These 16 characters represent 128 bits. These look like hex digits. 16 hex digits is 8 bytes which is 64 bits. What am I missing?

hansvm 5y ago
The author was probably viewing those as some sort of byte-per-character encoding rather than hex.