Hasta hace poco, pensaba que los filtros de floración eran una forma bastante inteligente de contar elementos distintos en un conjunto.
Pero un comentario reciente del usuario de Quora me señaló en la dirección del conteo probabilístico , que estima la cardinalidad mediante el hashing de elementos a un vector de bits, donde la probabilidad de hashing a un bit disminuye exponencialmente a medida que aumenta la importancia del bit. La implicación es que los conjuntos más grandes incluyen elementos “más raros”, y esta relación puede explotarse de manera muy similar al problema del tanque alemán (http://en.wikipedia.org/wiki/Ger…). El documento que Mateusz señaló está aquí:
http://algo.inria.fr/flajolet/Pu…
- ¿Qué se encuentra en la primera línea de Machine Learning Research?
- Estoy en primer año de ciencias de la computación, ¿cómo debo comenzar con mi trabajo de investigación?
- ¿Cómo habría sido diferente la historia si las primeras computadoras fueran significativamente más poderosas para empezar?
- ¿Cuáles son algunos buenos proyectos importantes de ML o AI?
- ¿Las publicaciones innovadoras tienden a ser publicadas por unos pocos o muchos autores?
Así que pensé que esto era bastante bueno durante aproximadamente un día más o menos, hasta que Norman Casagrande señaló un medio aún más efectivo de estimación de cardinalidad para tasas de error muy bajas. Los científicos de Ask.com compararon un montón de métodos de estimación diferentes, tanto teórica como prácticamente (en un gran corpus de datos de búsqueda del mundo real) y descubrieron que el conteo lineal era aún más efectivo. El recuento lineal también divide elementos a bits en un vector de bits, pero todos los valores tienen la misma probabilidad uniforme, y la cardinalidad se estima al observar la probabilidad de que un bit en el vector de bits esté vacío, esencialmente la relación de cero bits en el vector de bits. El papel está aquí:
http://www.edbt.org/Proceedings/…
Entonces, al observar las fechas de publicación de esos dos documentos, de acuerdo con mi propia estimación de cardinalidad interna, ¡probablemente haya una técnica aún mejor ahora! También me interesaría cualquier buena implementación de código abierto de las técnicas anteriores.
