Indexación y procesamiento de consultas
La indexación y el procesamiento de consultas comprenden las estructuras de datos y los algoritmos que permiten a un sistema de búsqueda responder rápidamente a consultas sobre grandes colecciones de texto, principalmente a través del índice invertido.
Definition
La indexación es la construcción de estructuras de datos, principalmente el índice invertido que mapea los términos a los documentos que los contienen, que soportan una búsqueda eficiente, mientras que el procesamiento de consultas es el conjunto de algoritmos que atraviesan estas estructuras para calcular los documentos que coinciden o están mejor clasificados para una consulta.
Scope
Esta área cubre cómo las colecciones de texto se transforman en estructuras buscables y cómo se evalúan las consultas en ellas: la construcción del índice invertido, las decisiones de tokenización y vocabulario de términos que lo sustentan, la compresión de las listas de ocurrencias para ahorrar espacio y acelerar el acceso, el procesamiento eficiente de consultas, incluyendo la recuperación clasificada y la terminación temprana, y las técnicas de recuperación tolerante como los comodines, la corrección ortográfica y la coincidencia fonética. Aborda la ingeniería de sistemas de recuperación rápida, distinta de los modelos de recuperación que definen la clasificación y los métodos de evaluación que miden la calidad.
Sub-topics
Core questions
- ¿Cómo se construye y actualiza un índice invertido para una colección grande y cambiante?
- ¿Cómo se pueden comprimir las listas de ocurrencias sin ralentizar la evaluación de consultas?
- ¿Cómo se evalúan las consultas de manera eficiente, especialmente las consultas clasificadas sobre millones de documentos?
- ¿Cómo puede un sistema recuperar buenos resultados sin puntuar cada documento?
- ¿Cómo maneja un sistema los errores ortográficos, los comodines y las coincidencias aproximadas?
Key concepts
- índice invertido
- lista de ocurrencias (postings list)
- tokenización y vocabulario de términos
- construcción de índices (BSBI, SPIMI)
- compresión de índices
- evaluación documento-a-la-vez y término-a-la-vez
- poda dinámica y terminación temprana
- recuperación tolerante
Key theories
- El índice invertido como estructura de datos central
- Mapear cada término a una lista de ocurrencias de los documentos (y posiciones) donde aparece permite que la recuperación solo acceda a los documentos que contienen los términos de la consulta, lo que la convierte en la estructura fundamental para la búsqueda de texto escalable.
- Compromiso entre compresión y eficiencia
- La codificación de las brechas de ID de documento y las frecuencias de términos con códigos enteros compactos reduce drásticamente el índice y, al reducir la entrada/salida y mejorar el comportamiento de la caché, también puede acelerar el procesamiento de consultas.
- Evaluación eficiente de consultas clasificadas
- Las estrategias documento-a-la-vez y término-a-la-vez, combinadas con técnicas de poda dinámica y terminación temprana, permiten a los sistemas devolver los resultados mejor clasificados sin puntuar completamente toda la colección.
Clinical relevance
Los índices invertidos y el procesamiento eficiente de consultas son la sala de máquinas de todo sistema de búsqueda en producción, desde los motores de búsqueda web y las plataformas de búsqueda de código abierto hasta la búsqueda de texto completo empresarial y de bases de datos. Su eficiencia determina directamente la latencia de las consultas, el costo del hardware y la escala de las colecciones que se pueden buscar interactivamente.
History
Los archivos invertidos se han utilizado para la búsqueda de texto desde los primeros sistemas de información, pero la teoría moderna de la construcción de índices, la compresión y la evaluación eficiente se consolidó en la década de 1990, notablemente con el trabajo "Managing Gigabytes" de Witten, Moffat y Bell. La revisión de Zobel y Moffat de 2006 sintetizó dos décadas de investigación sobre índices invertidos, ya que la búsqueda a escala web hizo que la eficiencia fuera primordial.
Key figures
- Justin Zobel
- Alistair Moffat
- Ian H. Witten
- W. Bruce Croft
Related topics
Seminal works
- zobel2006
- wittenmgb1999
- manning2008
Frequently asked questions
- ¿Por qué se prefiere el índice invertido en lugar de escanear documentos?
- Escanear cada documento para cada consulta es demasiado lento a escala. El índice invertido permite que el sistema salte directamente al pequeño conjunto de documentos que contienen los términos de la consulta, por lo que el tiempo de consulta depende de las listas de ocurrencias involucradas en lugar del tamaño de toda la colección.
- ¿La compresión del índice ralentiza la búsqueda?
- Generalmente, ocurre lo contrario. Un índice más pequeño reduce el tráfico de disco y memoria, y los códigos enteros modernos se descomprimen muy rápido, por lo que el tiempo ahorrado en entrada/salida y la mejora en el comportamiento de la caché suelen compensar el costo de decodificación, haciendo que los índices comprimidos sean más pequeños y más rápidos.