Funciones de discretización para índices métricos basados en pivotes

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 í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. Dentro de los índices basados en pivotes de mejor desempeño, se encuentra el Trie de Consulta Fija (FQTrie por sus siglas en inglés). La eficiencia del FQTrie depende fuertemente del tipo de discretización y de la calidad de los pivotes empleados. En este trabajo atacamos el problema de diseño de funciones de discretización para el FQTrie, cuando el mismo se utiliza para indizar espacios métricos con funciones de distancia continuas. Presentamos una nueva función de discretización δ_ma basada en los histogramas de distancias de los pivotes usados en la construcción del índice. Mostramos experimentalmente que δ_ma es altamente competitiva en los espacios considerados