Parametrización local de espacios métricos

Abstract

Muchas aplicaciones en computación tienen por objetivo buscar objetos en una base de datos que sean similares a uno dado. Todas estas aplicaciones pueden tratarse en abstracto con el formalismo de espacio métrico. Este método encapsula las propiedades de los objetos de la base de datos y permite construir índices genéricos. Existen muchas técnicas de construcción de índices para realizar búsquedas de proximidad, todas las técnicas tienen parámetros que dependen de la geometría del espacio. Estos parámetros balancean el tiempo de construcción, el tiempo de búsqueda y la memoria utilizada por el índice. En este trabajo presentamos un método de parametrización local que permite segmentar la base de datos de tal manera que a cada segmento se le pueden seleccionar de manera óptima sus parámetros adecuados. Ilustramos la técnica probando con un índice particularmente difícil de parametrizar, el GNAT. Para este efecto seleccionamos el espacio métrico de cadenas de palabras bajo la distancia de edición. La base de datos se divide en dos segmentos, los cuales se indizan por separado. Para satisfacer una consulta se busca en ambos índices. Esta operación resulta mas eficiente que buscar en el índice original.