stream lib

Description

Une bibliothèque Java permettant de résumer les données dans des flux pour lesquels il est impossible de stocker tous les événements. Plus spécifiquement, il existe des classes pour estimer : la cardinalité (c'est-à-dire compter des choses) ; définir l'adhésion ; éléments top-k et fréquence. Une fonctionnalité particulièrement utile est que les estimateurs de cardinalité avec des configurations compatibles peuvent être fusionnés en toute sécurité.

Ces classes peuvent être utilisées directement dans un projet JVM ou avec les scripts shell fournis et la bonne vieille redirection IO Unix.

Les idées ici ne nous sont pas originales. Nous nous sommes efforcés de créer des implémentations utiles en parcourant la littérature académique existante. En tant que telle, cette bibliothèque s'appuie fortement sur le travail des autres. Veuillez lire les sections Sources et Références.

Exemples

 $ 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

Artefact Maven

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

Bâtiment

En supposant qu'Apache Maven soit installé et configuré :

 mvn package

Et vous devriez être prêt.

Où les gens traînent

Liste de diffusion : http://groups.google.com/group/stream-lib-user

Sources

Le code d'adhésion défini est l'implémentation de Bloom Filter d'Apache Cassandra vers décembre 2009. Les modifications ici sont minimes et étaient destinées à des tests et à une utilisation indépendante. Les en-têtes Apache Software Foundation ont été conservés sur ces fichiers. Par extension, nous incluons également murmurhash.

Nous avons été inspirés pour utiliser ce code par l'article de Jonathan Ellis Tout ce que vous avez toujours voulu savoir sur l'écriture de filtres Bloom.

Références

Il existe des références javadoc à des articles spécifiques. Ce sont ceux que nous avons trouvés les plus pertinents lors de nos recherches.

Cardinalité

• Min Cai, Jianping Pan, Yu K. Kwok et Kai Hwang. Mesure rapide et précise de la matrice de trafic grâce au comptage de cardinalité adaptatif. Dans MineNet '05 : Actes de l'atelier ACM SIGCOMM 2005 sur les données des réseaux miniers, pages 205-206, New York, NY, États-Unis, 2005. ACM.

• Ahmed Metwally, Divyakant Agrawal et Amr E. Abbadi. Pourquoi adopter une approche logarithmique si nous pouvons adopter une approche linéaire ? : vers un comptage distinct et efficace du trafic de recherche. Dans EDBT '08 : Actes de la 11e conférence internationale sur l'extension de la technologie des bases de données, pages 618-629, New York, NY, États-Unis, 2008. ACM.

• Nikos Ntarmos, Peter Triantafillou et Gerhard Weikum. Comptage au sens large : estimation efficace de la cardinalité dans les réseaux de données à l'échelle Internet. Dans ICDE '06 : Actes de la 22e Conférence internationale sur l'ingénierie des données, pages 40+, Washington, DC, États-Unis, 2006. IEEE Computer Society.

• Marianne Durand et Philippe Flajolet. LogLog comptage de grandes cardinalités. Dans ESA03, volume 2832 du LNCS, pages 605-617, 2003.

• Kyu Y. Whang, Brad T. Vander Zanden et Howard M. Taylor. Un algorithme de comptage probabiliste en temps linéaire pour les applications de bases de données. ACM Trans. Système de base de données, 15(2):208-229, 1990.

• Moses Charikar, Kevin Chen et Martin F. Colton. Recherche d'éléments fréquents dans les flux de données. Dans ICALP '02 : Actes du 29e Colloque international sur les automates, les langages et la programmation, pages 693-703, Londres, Royaume-Uni, 2002. Springer-Verlag.

• Stefan Heule, Marc Nunkesser, Alex Hall. HyperLogLog en pratique : ingénierie algorithmique d'un algorithme d'estimation de cardinalité de pointe. Actes de la conférence EDBT 2013, ACM, Gênes, Italie

Top-K

• Graham Cormode et S. Muthukrishnan. Un résumé amélioré du flux de données : le croquis Count-Min et ses applications. pages 29 à 38.

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

• Cheqing Jin, Weining Qian, Chaofeng Sha, Jeffrey X. Yu et Aoying Zhou. Maintenir dynamiquement les éléments fréquents sur un flux de données. Dans CIKM '03 : Actes de la douzième conférence internationale sur la gestion de l'information et des connaissances, pages 287-294, New York, NY, États-Unis, 2003. ACM. 10.1145/956863.956918 http://dl.acm.org/citation.cfm?id=956918

• Ahmed Metwally, Divyakant Agrawal et Amr Abbadi. Calcul efficace des éléments fréquents et top-k dans les flux de données. pages 398 à 412. 2005. 10.1007/978-3-540-30570-5_27 http://link.springer.com/chapter/10.1007/978-3-540-30570-5_27

Fréquence

• Graham Cormode et S. Muthukrishnan. Un résumé amélioré du flux de données : le croquis Count-Min et ses applications. 2004. 10.1016/j.jalgor.2003.12.001 http://dl.acm.org/citation.cfm?id=1073718