Técnicas de selección de centros basadas en histogramas de distancia

Abstract

El diseño de índices en espacios métricos para el procesamiento eficiente de consultas por similitud es un tema de investigación emergente. Una amplia clase de índices en espacios métricos se construyen 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. Si bien los centros seleccionados no afectan la efectividad del índice, son cruciales para su eficiencia. En este artículo presentamos nuevas políticas para la selección de centros basándonos en la información que brindan los histogramas de distancia. Mostramos que las mismas son competitivas evaluando su desempeño sobre el índice Geometric Near-neighbor Access Tree (GNAT).