¿Existe una implementación de la idea se describe en "Detección NearDuplicates de rastreo web"

Question

El papel: http://www2007.org/papers/paper215.pdf

Me pregunto ¿existen implementaciones del capítulo 3 de dicho papel. Me refiero a consultar entre grandes conjuntos de datos, NO solo el simhash (es fácil encontrar implementaciones simhash).

Gracias ~

Answer 1

Esto es one aunque no he probado que funciona. Lo bueno es opensource.

Answer 2

Esto es un problema en Data mining y similarity search. Existen numerosos artículos que describen cómo se puede hacer eso y escalar a grandes cantidades de datos.

Tengo una implementación (github : mksteve, clustering, con algunos comentarios al respecto en mi blog) de wikipedia : Metric tree. Esto requiere que las medidas que está realizando cumplan con la desigualdad del triángulo (wikipedia : Metric space). Es decir, la distancia métrica del elemento A al elemento C es menor o igual que la distancia A a B + la distancia B a C.

Dado esa desigualdad, es posible recortar el espacio de búsqueda, por lo que solo se buscan los subárboles que pueden superponerse con el área objetivo. Sin esa característica es verdadera (espacio métrico)

Posiblemente el número de bits de diferencia en el simhash sería un espacio métrico.

El uso general de estos conjuntos de datos, se alude en el documento cuando se menciona mapReduce, que generalmente se ejecuta en un hadoop cluster. Cada nodo de procesamiento recibe un subconjunto de datos y encuentra un conjunto de coincidencias objetivo de sus conjuntos de datos locales. Estos se combinan para dar una lista completamente ordenada de elementos similares.

Hay algunos documentos (inseguros de referencias) que aluden al uso de m-trees en un clúster, donde se dan diferentes partes del espacio de búsqueda a diferentes clústeres, pero no estoy seguro de si la infraestructura de hadoop sería compatible usando una abstracción de alto nivel.