stream lib

Descripción

Una biblioteca Java para resumir datos en secuencias para las cuales no es factible almacenar todos los eventos. Más específicamente, existen clases para estimar: cardinalidad (es decir, contar cosas); establecer membresía; elementos top-k y frecuencia. Una característica particularmente útil es que los estimadores de cardinalidad con configuraciones compatibles pueden fusionarse de forma segura.

Estas clases se pueden usar directamente en un proyecto JVM o con los scripts de shell proporcionados y la antigua redirección IO de Unix.

Las ideas aquí no son originales para nosotros. Nos hemos esforzado por crear implementaciones útiles a partir de la iteración de la literatura académica existente. Como tal, esta biblioteca depende en gran medida del trabajo de otros. Por favor lea las secciones de Fuentes y Referencias.

Ejemplos

 $ 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

Artefacto experto

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

Edificio

Suponiendo que tenga Apache Maven instalado y configurado:

 mvn package

Y deberías estar listo.

Donde la gente pasa el rato

Lista de correo: http://groups.google.com/group/stream-lib-user

Fuentes

El código de membresía establecido es la implementación del filtro Bloom de Apache Cassandra alrededor de diciembre de 2009. Los cambios aquí son mínimos y fueron para fines de prueba y uso independiente. Los encabezados de Apache Software Foundation se han conservado en estos archivos. Por extensión también incluimos murmurhash.

Nos inspiramos para usar este código en la publicación de Jonathan Ellis Todo lo que siempre quisiste saber sobre cómo escribir filtros de floración.

Referencias

Hay referencias javadoc a artículos específicos. Estos fueron los que encontramos más relevantes durante nuestra investigación.

Cardinalidad

• Min Cai, Jianping Pan, Yu K. Kwok y Kai Hwang. Medición de matriz de tráfico rápida y precisa mediante conteo de cardinalidad adaptativa. En MineNet '05: Actas del taller ACM SIGCOMM de 2005 sobre datos de redes mineras, páginas 205–206, Nueva York, NY, EE. UU., 2005. ACM.

• Ahmed Metwally, Divyakant Agrawal y Amr E. Abbadi. ¿Por qué volvernos logarítmicos si podemos ir lineales?: Hacia un conteo distinto y efectivo del tráfico de búsqueda. En EDBT '08: Actas de la 11.ª conferencia internacional sobre ampliación de la tecnología de bases de datos, páginas 618–629, Nueva York, NY, EE. UU., 2008. ACM.

• Nikos Ntarmos, Peter Triantafillou y Gerhard Weikum. Contando en general: estimación eficiente de la cardinalidad en redes de datos a escala de Internet. En ICDE '06: Actas de la 22ª Conferencia Internacional sobre Ingeniería de Datos, páginas 40+, Washington, DC, EE. UU., 2006. IEEE Computer Society.

• Marianne Durand y Philippe Flajolet. Recuento LogLog de cardinalidades grandes. En SEC03, volumen 2832 de LNCS, páginas 605–617, 2003.

• Kyu Y. Whang, Brad T. Vander Zanden y Howard M. Taylor. Un algoritmo de conteo probabilístico de tiempo lineal para aplicaciones de bases de datos. Transmisión ACM. Sistema de base de datos, 15(2):208–229, 1990.

• Moisés Charikar, Kevin Chen y Martin F. Colton. Encontrar elementos frecuentes en flujos de datos. En ICALP '02: Actas del 29º Coloquio Internacional sobre Autómatas, Lenguajes y Programación, páginas 693–703, Londres, Reino Unido, 2002. Springer-Verlag.

• Stefan Heule, Marc Nunkesser, Alex Hall. HyperLogLog en la práctica: ingeniería algorítmica de un algoritmo de estimación de cardinalidad de última generación. Actas de la Conferencia EDBT 2013, ACM, Génova, Italia

Top-K

• Graham Cormode y S. Muthukrishnan. Un resumen mejorado del flujo de datos: el boceto de Count-Min y sus aplicaciones. páginas 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 y Aoying Zhou. Mantener dinámicamente elementos frecuentes a través de un flujo de datos. En CIKM '03: Actas de la duodécima conferencia internacional sobre gestión de la información y el conocimiento, páginas 287–294, Nueva York, NY, EE. UU., 2003. ACM. 10.1145/956863.956918 http://dl.acm.org/citation.cfm?id=956918

• Ahmed Metwally, Divyakant Agrawal y Amr Abbadi. Cálculo eficiente de elementos frecuentes y top-k en flujos de datos. páginas 398–412. 2005. 10.1007/978-3-540-30570-5_27 http://link.springer.com/chapter/10.1007/978-3-540-30570-5_27

Frecuencia

• Graham Cormode y S. Muthukrishnan. Un resumen mejorado del flujo de datos: el boceto de Count-Min y sus aplicaciones. 2004. 10.1016/j.jalgor.2003.12.001 http://dl.acm.org/citation.cfm?id=1073718