Selección dinámica de índices métricos para consultas de proximidad

Abstract

El modelo de Espacios Métricos permite formalizar el concepto de búsqueda por similitud en bases de datos no tradicionales. El objetivo es construir estructuras de datos o índices que permitan reducir el tiempo necesario para resolver una búsqueda por similitud. Uno de los enfoques para la construcción de índices es el usado por los algoritmos basados en pivotes. En este trabajo abordamos el estudio de este grupo de algoritmos, enfocándonos en el diseño de heurísticas para la selección dinámica de un buen grupo de pivotes, y por lo tanto de un buen índice. Para ello, en lugar de construir un único índice para resolver todas las búsquedas, construimos varios índices sobre el espacio con distintos grupos de pivotes y elegimos durante la búsqueda aquel índice que sea más adecuado. Hemos desarrollado y evaluado varias heurísticas que permiten realizar esta selección, las que han mostrado experimentalmente ser competitivas. La aplicación mas importante de esta técnica es la paralelización de las consultas, si mantenemos cada uno de los índices creados en distintas máquinas de una red.