Paginación + discretización del fixed queries trie

Abstract

La próxima generación de administradores de bases de datos debería ser capaz de indexar datos multimedia y responder consultas de proximidad con tanta eficiencia como actualmente responden consultas de búsqueda exacta. Estas nuevas bases de datos se pueden modelar como un espacio métrico, sobre los cuales ya se han diseñando numerosas técnicas de indexación. El Fixed Queries Trie (FQTrie) es una de ellas y ha demostrado experimentalmente tener un buen desempeño. En investigaciones anteriores hemos realizado trabajos en torno a mejorar la eficiencia del FQTrie desde varios tópicos diferentes: cantidad de evaluaciones de distancia, tiempo extra de CPU y tiempo de I/O. Con respecto a los dos primeros, hemos encontrado un método de discretización que logra mejorar la eficiencia del FQTrie. Con respecto al tiempo de I/O, hemos diseñado una técnica basada en el particionamiento del espacio que permite reducir el tiempo de I/O. En este trabajo combinamos ambas técnicas a fin de lograr una implementación completa del FQTrie que sea eficiente tanto en memoria principal como en memoria secundaria.