Métodos de paginación paraíndices métricos basados en pivotes

Abstract

El problema de buscar objetos en una base de datos que sean similares a uno dado puede formalizarse por medio del modelo de Espacios Métricos. La mayoría de las soluciones existentes para búsquedas por similitud en espacios métricos suponen que tanto el espacio como el índice completo entran en memoria principal. En este artículo presentamos una implementación del Fixed Queries Trie (FQtrie) que permite manejar espacios métricos cuyo índice completo y/o datos exceda la capacidad de la memoria principal. Para ello, en lugar de modificar la estructura para que sea eficiente en memoria secundaria, particionamos el espacio de manera tal que cada una de las partes entre en memoria principal, las que posteriormente se indexan en forma separada. Luego, una búsqueda se resuelve buscando en cada parte, lo que puede ser hecho en memoria principal y en paralelo. Para particionar el espacio hemos diseñado un método basado en la distancia LCS (longest common subsequence). Mostramos experimentalmente que esta forma de particionar, ante una búsqueda, implica menor cantidad de accesos a disco que si el espacio se particiona en forma totalmente aleatoria.