Análisis de la separabilidad de clusters y filtrado de pivotes para el D-Index

Abstract

En este trabajo implementamos y evaluamos la estructura denominada D-Index, que combina técnicas de clustering con estrategias de búsqueda basada en pivotes para acelerar la ejecución de consultas por similitud en rango y de vecinos más cercanos. Primero mostramos experimentalmente las ventajas de la estructura D-Index. En particular, nos enfocaremos en el problema de la separabilidad entre los objetos, que es un problema abierto y no esta tan explorado como el problema de selección de pivotes. Segundo mostramos experimentalmente como la técnica de filtrado de pivotes permite reducir los costos de los algoritmos comparada con la estructura D-Index sin filtrado de pivotes ya que la resolución de consultas sobre este tipo de índice tiende a ser muy costosa por la dificultad que implica le ejecución de la función de similitud.