Indexamiento en espacios no-métricos

Abstract

La mayoría de los sistemas de recuperación de información multimedia utilizan algún esquema de indexamiento para acelerar las búsquedas por similitud en una colección de datos, evitando un análisis detallado de grandes porciones de la colección. Estos enfoques suelen utilizar la desigualdad triangular para descartar elementos. Esto requiere que la distancia de comparación satisfaga los postulados métricos. Sin embargo, estudios recientes muestran que para ciertas aplicaciones resulta apropiado el uso de distancias no métricas, que pueden entregar mejores juicios de la similitud de dos objetos. En esos casos, la falta de la desigualdad triangular hace imposible el uso de los enfoques tradicionales para el indexamiento. En esta tesis se estudian, implementan y prueban las principales técnicas del estado del arte para indexar espacios no métricos genéricos, en un ambiente que permite concluir acerca de varios aspectos y las ventajas de las diferentes estrategias probadas. Las técnicas consideradas fueron DynDex, LCE, QIC y TriGen, aunque la técnica QIC no es comparada con las demás pues falla en ser adecuadamente aplicable a los diferentes espacios en estudio. Se utilizan varios espacios no métricos con distintas características tanto en el índice de fallo de la desigualdad triangular, como en la capacidad de indexamiento. Adicionalmente, se propone e implementa CP-Index, una técnica de indexamiento aproximado original. Esta técnica hace uso de Clustering y de Pivotes para acelerar las búsquedas en espacios no métricos, sin comprometer significativamente la calidad de la respuesta. CP-Index se adapta dinámicamente a las condiciones del espacio no métrico, usando pivotes cuando la fracción de tríos que rompen la desigualdad triangular es pequeña, pero buscando secuencialmente los candidatos más prometedores cuando el uso de pivotes se vuelve inútil para descartar elementos. Una conclusión importante de esta investigación es que la mayoría de las técnicas que tratan de generar un resultado exacto durante las búsquedas por similitud resultan ser demasiado costosas para los conjuntos de datos utilizados. En su lugar, las técnicas aproximadas tienden a generar un mucho mejor trade-off de trabajo y calidad. Por ejemplo, LCE resulta ser una técnica excesivamente costosa tanto en tiempo de construcción como en tiempo de consulta pues modifica la distancia reduciendo mucho el poder de descarte de los índices tradicionales. Por otro lado, CP-Index obtiene resultados ligeramente superiores a los de DynDex y TriGen, pero con la ventaja de no necesitar exhaustivas pruebas y ajustes para adaptarse a las características del espacio. De este modo, en aquellos espacios en los que DynDex supera a TriGen, CP-Index se comporta igual o mejor que el primero, mientras que en los espacios en los que TriGen funciona mejor, CP-Index también obtiene resultados ligeramente superiores.