stream lib
1.0.0
Eine Java-Bibliothek zum Zusammenfassen von Daten in Streams, für die es nicht möglich ist, alle Ereignisse zu speichern. Genauer gesagt gibt es Klassen zum Schätzen von: Kardinalität (dh Dinge zählen); Mitgliedschaft festlegen; Top-k-Elemente und Frequenz. Eine besonders nützliche Funktion besteht darin, dass Kardinalitätsschätzer mit kompatiblen Konfigurationen sicher zusammengeführt werden können.
Diese Klassen können direkt in einem JVM-Projekt oder mit den bereitgestellten Shell-Skripten und der guten alten Unix-IO-Umleitung verwendet werden.
Die Ideen hier sind für uns nicht originell. Wir haben uns bemüht, aus der Iteration der vorhandenen wissenschaftlichen Literatur nützliche Implementierungen zu erstellen. Daher ist diese Bibliothek stark auf die Arbeit anderer angewiesen. Bitte lesen Sie die Abschnitte „Quellen“ und „Referenz“.
$ echo -e "foonfoonbar" | ./bin/topk
item count error
---- ----- -----
foo 2 0
bar 1 0
Item count: 3
$ echo -e "foonfoonbar" | ./bin/cardinality
Item Count Cardinality Estimate
---------- --------------------
3 2
< dependency >
< groupId >com.clearspring.analytics</ groupId >
< artifactId >stream</ artifactId >
< version >2.9.5</ version >
</ dependency >Vorausgesetzt, Sie haben Apache Maven installiert und konfiguriert:
mvn package
Und Sie sollten bereit sein.
Mailingliste: http://groups.google.com/group/stream-lib-user
Der festgelegte Mitgliedschaftscode ist die Bloom Filter-Implementierung von Apache Cassandra, etwa im Dezember 2009. Die Änderungen hier sind minimal und dienten dem Testen und der unabhängigen Verwendung. Die Header der Apache Software Foundation wurden in diesen Dateien beibehalten. Als Erweiterung schließen wir auch Murmurhash ein.
Die Inspiration für die Verwendung dieses Codes hat uns Jonathan Ellis‘ Beitrag „Alles, was Sie schon immer über das Schreiben von Bloom-Filtern wissen wollten“ gegeben.
Es gibt Javadoc-Verweise auf bestimmte Artikel. Dies waren diejenigen, die wir während unserer Recherche als am relevantesten empfanden.
Min Cai, Jianping Pan, Yu K. Kwok und Kai Hwang. Schnelle und genaue Messung der Verkehrsmatrix mithilfe der adaptiven Kardinalitätszählung. In MineNet '05: Tagungsband des ACM SIGCOMM-Workshops 2005 zu Mining-Netzwerkdaten, Seiten 205–206, New York, NY, USA, 2005. ACM.
Ahmed Metwally, Divyakant Agrawal und Amr E. Abbadi. Warum logarithmisch vorgehen, wenn wir linear vorgehen können?: Auf dem Weg zu einer effektiven, eindeutigen Zählung des Suchverkehrs. In EDBT '08: Tagungsband der 11. internationalen Konferenz zur Erweiterung der Datenbanktechnologie, Seiten 618–629, New York, NY, USA, 2008. ACM.
Nikos Ntarmos, Peter Triantafillou und Gerhard Weikum. Zählen im Großen und Ganzen: Effiziente Kardinalitätsschätzung in Internet-Scale-Datennetzwerken. In ICDE '06: Proceedings of the 22nd International Conference on Data Engineering, Seiten 40+, Washington, DC, USA, 2006. IEEE Computer Society.
Marianne Durand und Philippe Flajolet. LogLog-Zählung großer Kardinalitäten. In ESA03, Band 2832 von LNCS, Seiten 605–617, 2003.
Kyu Y. Whang, Brad T. Vander Zanden und Howard M. Taylor. Ein probabilistischer Zählalgorithmus mit linearer Zeit für Datenbankanwendungen. ACM Trans. Database Syst., 15(2):208–229, 1990.
Moses Charikar, Kevin Chen und Martin F. Colton. Häufige Elemente in Datenströmen finden. In ICALP '02: Proceedings of the 29th International Colloquium on Automata, Languages and Programming, Seiten 693–703, London, UK, 2002. Springer-Verlag.
Stefan Heule, Marc Nunkesser, Alex Hall. HyperLogLog in der Praxis: Algorithmische Entwicklung eines hochmodernen Algorithmus zur Kardinalitätsschätzung. Tagungsband der EDBT-Konferenz 2013, ACM, Genua, Italien
Cheqing Jin, Weining Qian, Chaofeng Sha, Jeffrey X. Yu und Aoying Zhou. Dynamische Verwaltung häufiger Elemente über einen Datenstrom. In CIKM '03: Proceedings of the Twelfth International Conference on Information and Knowledge Management, Seiten 287–294, New York, NY, USA, 2003. ACM. 10.1145/956863.956918 http://dl.acm.org/citation.cfm?id=956918
Ahmed Metwally, Divyakant Agrawal und Amr Abbadi. Effiziente Berechnung häufiger und Top-k-Elemente in Datenströmen. Seiten 398–412. 2005. 10.1007/978-3-540-30570-5_27 http://link.springer.com/chapter/10.1007/978-3-540-30570-5_27
