Selección de centros para un índice métrico basado en particiones compactas

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. Una amplia clase de algoritmos construyen el índice dividiendo el espacio en zonas tan compactas como sea posible. Por cada zona se almacena un elemento representativo, llamado centro , e información adicional que permiten descartar la zona completa durante una búsqueda, sin tener que calcular la distancia entre los elementos de la zona y el objeto de búsqueda. La manera en que se seleccionan los centros afecta el desempeño del índice. En este artículo presentamos dos nuevas políticas para la selección de centros en el Geometric Nearneighbor Access Tree (GNAT), un índice basado en particiones compactas. Experimentalmente mostramos que estas políticas logran un buen desempeño.