algorithm - example - bitset java

Estructura de índice para consultas top-k en cadenas de bits

Question

Dado un conjunto de bitstrings (todos de la misma longitud) y cadena de consulta Q, encuentre top-k cadenas más similares a Q, donde la similitud entre las cadenas A y B se define como número de 1 en A y B (operación y se aplica en modo bit) .

Creo que debe haber un resultado clásico para este problema.

k es pequeño, en cientos, mientras que el número de vectores en cientos de millones y la longitud de los vectores es 512 o 1024

Answer 1

Este problema se puede resolver escribiendo un trabajo simple de Mapa y Reducir. No pretendo que esta sea la mejor solución, ni afirmo que esta es la única solución.

Además, ha revelado en los comentarios que k está en cientos, hay millones de bitstrings y que el tamaño de cada uno de ellos es 512 o 1024.

Pseudocódigo de Mapper:

• Dado Q ;
• Para cada cadena de bits b , similitud de cálculo = b & Q
• Emitir (similitud, b)

Ahora, el combinador puede consolidar la lista de todas las cadenas de bits de cada asignador que tienen la misma similitud.

Pseudocódigo reductor:

• Consume (similitud, listOfBitStringsWithThisSimilarity) ;
• Déles salida en orden decreciente para el valor de similitud.

Desde la salida del reductor puede extraer las cadenas de bits top-k.

Entonces, el paradigma MapReduce es probablemente la solución clásica que estás buscando.

Answer 2

Una forma de abordar este problema es construir un K-Nearest Neighbor Graph (K-NNG) (dígrafo) con una función de similitud Russell-Rao.

Tenga en cuenta que la construcción eficiente de K-NNG sigue siendo un problema abierto, y ninguna de las soluciones conocidas para este problema es general, eficiente y escalable [citando de Efficient K-Neighbor Nearest Graph Construction for Generic Similarity Measures - Dong, Charikar, Li 2011] .

Su función de distancia a menudo se denomina similitud de Russell-Rao (consulte, por ejemplo, una Encuesta de similitud binaria y medidas de distancia - Choi, Cha, Tappert 2010 ). Tenga en cuenta que la similitud de Russell-Rao no es una métrica (consulte Propiedades de las medidas de disimilitud de vectores binarios - Zhang, Srihari 2003 ): la parte " si " de " d (x, y) = 0 iff x == y " es falsa.

En Un algoritmo rápido para encontrar k-Vecinos más cercanos con disimilitud no métrica - Zhang, Srihari 2002 , los autores proponen un algoritmo de búsqueda jerárquico rápido para encontrar k-NN utilizando una medida no métrica en un espacio vectorial binario. Usan una función paramétrica de distancia de vector binario D (β). Cuando β = 0, esta función se reduce a la función de distancia Russell-Rao. No lo llamaría un "resultado clásico", pero este es el único documento que pude encontrar que examina este problema.

Es posible que desee consultar estas dos encuestas: sobre problemas de búsqueda de similitudes no métricas en dominios complejos: Skopal, Bustos 2011 y una encuesta sobre métodos de búsqueda de vecinos más cercanos - Reza, Ghahremani, Naderi 2014 . Tal vez encuentres algo que extrañé.