He estado jugando en el trabajo con algunos conjuntos muy grandes de datos, por lo general, varios miles de millones de elementos, que se mantienen en una nube memcached y periódicamente arrojados a los archivos, y para una de mis tareas estoy tratando de contar el cardinalidad de este conjunto.¿Cómo se puede contar la cardinalidad de conjuntos de datos muy grandes de manera eficiente en Python?
Por algún contexto, cada elemento contiene una IP y algunos otros atributos que identifican a una persona y están codificados en base64, el tamaño del elemento es de 20 bytes. No es posible reducir el tamaño de un elemento eliminando algunos campos.
Aquí es algo que emula mi conjunto de datos como una versión en memoria (gracias a this post para la generación de la cadena):
import base64, os
dataset_size = 10000000000 # that's 10 billion, be careful if you run it !
big_dataset = [base64.b64encode(os.urandom(10)) for i in range(dataset_size)]
Mi primer acercamiento fue utilizar un hashset así:
uniques = set(big_dataset)
print "Cardinality: %d" % len(uniques)
Si bien esto, en teoría, funciona bien en un pequeño conjunto de datos, como se puede adivinar, hay un tropiezo:
- No puedo hacer ninguna suposición sobre la exclusividad de mis datos. Podría tener el 50% de mi conjunto de datos que es único, o podría tener el 100% igual de bien. Esto se genera dinámicamente en intervalos de tiempo regulares y varía según muchos factores (por ejemplo, la hora del día)
- Tamaño del conjunto de datos en 10 mil millones. Cada elemento codificado en la base 64 es de 20 bytes, multiplicado por 10 mil millones en algunos cientos de gigabytes en promedio. Desafortunadamente, ¡no tengo acceso a una máquina con tanta RAM!
He hecho mi tarea y he encontrado, en el mejor de los casos, algunos trabajos de investigación, o algunas bibliotecas oscuras, pero parte del objetivo es entender qué enfoque funciona y por qué.
Así que les llamo usuarios de Python, ¿conocen algún algoritmo que me ayude a estimar la cardinalidad de manera eficiente? Por complejidad quiero decir que no me importa mucho la complejidad del tiempo de ejecución, pero estoy más centrado en la complejidad del espacio. No me importa sacrificar un poco la precisión si aumenta el rendimiento tremendamente (por lo que no necesariamente necesito saber el número exacto de muestras únicas, incluso si eso fuera ideal, pero probablemente no sea un enfoque viable). Yo diría que hasta un 5% sería aceptable. Estoy buscando algo específicamente en Python para este proyecto.
¡Gracias por cualquier ayuda que pueda proporcionar!
Como señalaron algunas personas, podría usar Hadoop/MR, pero para este tipo de proyectos específicos no queremos utilizar MR, y nos gustaría explorar algoritmos para hacer esto en una sola máquina de manera eficiente, ya que esto podría ser aplicado a algunos otros proyectos diferentes.
Solo una sugerencia, pero esto suena como algo que podría ser bueno para el marco Map-Reduce - asignando elementos en sus datos a cuentas en un diccionario o algo . Para esto, puede usar [MRJob] (https://github.com/Yelp/mrjob), el marco Python Map-Reduce creado por Yelp. Ejecutarlo en Amazon EC2 con MRJob también podría ser una buena idea para ti. Lo he usado para conteos de frecuencia de palabras en corpras grandes antes. Supongo que depende exactamente de cómo analizaría los elementos de datos individuales. – ely
Gracias por la sugerencia, sí, he pensado en MR (de hecho, lo estoy usando mucho en otros proyectos), pero para este problema específico MR/Hadoop no es una opción, nos gustaría buscar algoritmos para haz esto en una sola máquina como parte de una prueba de concepto. –
Si el 100% de precisión no es importante, ¿quizás un filtro de floración que le dará un 5% de error encajaría en la memoria? Si no es así, y se necesita una sola máquina, simplemente puede usar una base de datos simple de nosql con claves únicas, que almacena en el disco y elimina los duplicados. será lento, pero funcionará con la cantidad de ram que tengas. Todavía puede paralelizar el trabajo de inserción real. –