Distinct Element Estimation (F0)


My draf

Bitmap algorithm


  1. Whang, K.-Y., Zanden, B. T. V., and Taylor, H. M. A linear-time probabilistic counting algorithm for database applications. TODS 15, 2 (1990), 208–229.
  2. Cristian Estan, George Varghese, Mike Fisk. “Bitmap Algorithms for Counting Active Flows on High Speed Links”, IEEE/ACM Transactions on Networking, October 2006

Power-2


  1. Philippe Flajolet and G. Nigel Martin. “Probabilistic Counting Algorithms for Data Base Applications”. Journal of Computer and Systems Sciences, 31:182–209, 1985
  2. Marianne Durand and Philippe Flajolet, “Loglog Counting of Large Cardinalities”, In the "Engineering and Applications Track" of the 11th Annual European Symposium on Algorithms (ESA03). Proceedings published by Springer, Lecture Notes in Computer Science, vol 2832, pp.605-617.

Randomized uniformed

  1. Ziv Bar-Yossef, T.S. Jayram, Ravi Kumar, D. Sivakumar, and Luca Trevisan. “Counting distinct elements in a data stream”. In Proceedings of the 6th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM’02), Cambridge, Massachusetts, September 2002. My analysis of the above algorithm [pdf]
  2. Noga Alon, Yossi Matias, and Mario Szegedy. “The Space Complexity of Approximating the Frequency Moments”. In Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, pages 20–29, Philadelphia, Pennsylvania, May 1996.
  3. Johnny Chen, naveen Sunkavally and David Woodruff. "Space efficient algorithms for distinct elements in a data stream".