Big Data Counting: How to count a billion distinct objects using only 1.5KB of Memory - High Scalability -

The table shows that we can count the words with a 3% error rate using only 512 bytes of space. Compare that to a perfect count using a HashMap that requires nearly 10 megabytes of space and you can easily see why cardinality estimators are useful. In applications where accuracy is not paramount, which is true for most web scale and network counting scenarios, using a probabilistic counter can res

[suffixarray]

linear countint and hypeloglog and others bit data counting

[gugod]

HyperLogLog 這名字頂酷的啊... // 最難的還是怎麼設計那個 hash function 啊...