algorithm - El algoritmo de lucene

indexing information-retrieval

Question

Leí el periódico de Doug Cutting; " Optimizaciones de espacio para el ranking total ".

Como se escribió hace mucho tiempo, me pregunto qué algoritmos usa Lucene (en relación con el recorrido de la lista de publicaciones y el cálculo de puntaje, clasificación).

En particular, el algoritmo de clasificación total descrito allí implica atravesar la lista de publicaciones para cada término de consulta, por lo que en el caso de términos de consulta muy comunes como "perro amarillo", cualquiera de los 2 términos puede tener una lista de publicaciones muy larga en el caso de búsqueda Web. ¿Están todos realmente atravesados ​​en el actual Lucene / Solr? ¿O hay alguna heurística para truncar la lista empleada?

En el caso de que solo se devuelvan los mejores resultados de k, puedo entender que distribuir la lista de publicaciones en múltiples máquinas y luego combinar la k superior de cada una funcionaría, pero si se nos solicita que devolvamos "la página de resultados número 100", es decir, los resultados se clasificaron del 990 al 1000, entonces cada partición aún tendría que encontrar los 1000 principales, por lo que la partición no ayudaría mucho.

En general, ¿hay alguna documentación detallada actualizada sobre los algoritmos internos utilizados por Lucene?

Answer 1

No tengo conocimiento de dicha documentación, pero como Lucene es de código abierto, le recomiendo que lea el código fuente. En particular, la versión troncal actual incluye una indexación flexible , lo que significa que el recorrido y el recorrido de la lista de publicación se han desacoplado del resto del código, lo que permite escribir códecs personalizados.

Las suposiciones son correctas con respecto al recorrido de la lista de publicaciones, de forma predeterminada (depende de su implementación de Scorer ) Lucene recorre toda la lista de publicaciones para cada término presente en la consulta y coloca los documentos correspondientes en un montón de tamaño k para calcular los documentos de la parte superior ( ver TopDocsCollector ). Así que devolver los resultados de 990 a 1000 hace que Lucene ejemplifique un montón de tamaño 1000. Y si particiona su índice por documento (otro método podría ser dividir por término), cada fragmento deberá enviar los primeros 1000 resultados al servidor, que es responsable de combinar los resultados (vea Solr QueryComponent por ejemplo, que traduce una consulta de N a P> N a varias solicitudes de fragmentos de 0 a P sreq.params.set(CommonParams.START, "0"); ). Esta es la razón por la que Solr puede ser más lento en el modo distribuido que en el modo independiente en caso de paginación extrema.

No sé cómo Google logra obtener resultados de manera eficiente, pero Twitter publicó un artículo en su motor de recuperación Earlybird en el que explican cómo parchearon a Lucene para hacer un recorrido eficiente de orden cronológico inverso de las listas de publicación, lo que les permite devolver el los tweets más recientes que coinciden con una consulta sin atravesar la lista de publicación completa para cada término.

Actualización: Encontré esta presentation de Googler Jeff Dean , que explica cómo Google creó su sistema de recuperación de información a gran escala. En particular, se refiere a estrategias de fragmentación y codificación de listas de publicaciones.