Repository files navigation

A Java library for summarizing data in streams for which it isinfeasible to store all events. More specifically, there are classesfor estimating: cardinality (i.e. counting things); set membership;top-k elements and frequency. One particularly useful feature is thatcardinality estimators with compatible configurations may be safelymerged.

These classes may be used directly in a JVM project or with theprovided shell scripts and good old Unix IO redirection.

The ideas here are not original to us. We have endeavored to createuseful implementations from iterating over the existing academicliterature. As such this library relies heavily on the work ofothers. Please read theSources andReference sections.

$ echo -e "foo\nfoo\nbar" | ./bin/topkitem count error---- ----- ----- foo     2     0 bar     1     0Item count: 3$ echo -e "foo\nfoo\nbar" | ./bin/cardinalityItem Count Cardinality Estimate---------- --------------------         3                    2

<dependency>  <groupId>com.clearspring.analytics</groupId>  <artifactId>stream</artifactId>  <version>2.9.5</version></dependency>

Assuming you haveApache Maven installedand configured:

mvn package

And you should be all set.

Mailing list:http://groups.google.com/group/stream-lib-user

The set membership code is the Bloom Filter implementation from ApacheCassandra circa December 2009. The changes here are minimal and werefor the purpose of testing and independent use. Apache SoftwareFoundation headers have been retained on these files. By extension wealso includemurmurhash.

We were inspired to use this code by Jonathan Ellis' postAll you ever wanted to know about writing bloom filters.

There are javadoc references to specific papers. These were the oneswe found most relevant during out research.

• Min Cai, Jianping Pan, Yu K. Kwok, and Kai Hwang. Fast and accuratetraffic matrix measurement using adaptive cardinality counting. InMineNet ’05: Proceedings of the 2005 ACM SIGCOMM workshop onMining network data, pages 205–206, New York, NY, USA, 2005. ACM.

• Ahmed Metwally, Divyakant Agrawal, and Amr E. Abbadi. Why gologarithmic if we can go linear?: Towards effective distinct counting ofsearch traffic. In EDBT ’08: Proceedings of the 11th internationalconference on Extending database technology, pages 618–629, New York,NY, USA, 2008. ACM.

• Nikos Ntarmos, Peter Triantafillou, and Gerhard Weikum. Counting atlarge: Efficient cardinality estimation in Internet-Scale data networks.In ICDE ’06: Proceedings of the 22nd International Conference on DataEngineering, pages 40+, Washington, DC, USA, 2006. IEEE ComputerSociety.

• Marianne Durand and Philippe Flajolet. LogLog counting of largecardinalities. In ESA03, volume 2832 of LNCS, pages 605–617, 2003.

• Kyu Y. Whang, Brad T. Vander Zanden, and Howard M. Taylor. Alinear-time probabilistic counting algorithm for database applications.ACM Trans. Database Syst., 15(2):208–229, 1990.

• Moses Charikar, Kevin Chen, and Martin F. Colton. Finding frequentitems in data streams. In ICALP ’02: Proceedings of the 29thInternational Colloquium on Automata, Languages and Programming,pages 693–703, London, UK, 2002. Springer-Verlag.

• Stefan Heule, Marc Nunkesser, Alex Hall. HyperLogLog in Practice:Algorithmic Engineering of a State of The Art Cardinality EstimationAlgorithm. Proceedings of the EDBT 2013 Conference, ACM, Genoa, Italy

• Graham Cormode and S. Muthukrishnan. An improved data streamsummary: The Count-Min sketch and its applications. pages 29–38.

2004. 10.1016/j.jalgor.2003.12.001http://dl.acm.org/citation.cfm?id=1073718

• Cheqing Jin, Weining Qian, Chaofeng Sha, Jeffrey X. Yu, and AoyingZhou. Dynamically maintaining frequent items over a data stream. InCIKM ’03: Proceedings of the twelfth international conference onInformation and knowledge management, pages 287–294, New York,NY, USA, 2003. ACM. 10.1145/956863.956918http://dl.acm.org/citation.cfm?id=956918

• Ahmed Metwally, Divyakant Agrawal, and Amr Abbadi. Efficientcomputation of frequent and top-k elements in data streams. pages398–412. 2005. 10.1007/978-3-540-30570-5_27http://link.springer.com/chapter/10.1007/978-3-540-30570-5_27

• Graham Cormode and S. Muthukrishnan. An improved data streamsummary: The Count-Min sketch and its applications. 2004. 10.1016/j.jalgor.2003.12.001http://dl.acm.org/citation.cfm?id=1073718