Una implementación completa del FQTrie

Abstract

La próxima generación de manejadores de bases de datos deberá 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. Numerosas técnicas de indización han sido diseñadas para espacios métricos. Una de ellas es el Trie de Consulta Fija (FQTrie), que ha demostrado experimentalmente tener un buen desempeño para resolver búsquedas por proximidad en espacios métricos. En investigaciones anteriores hemos realizado trabajos en torno a mejorar la eficiencia del FQTrie desde dos tópicos diferentes: tiempo extra de CPU y tiempo de I/O. Con respecto al tiempo de CPU, 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. Nos proponemos lograr una implementación completa del FQTrie que funcione tanto en memoria principal como en memoria secundaria combinando las técnicas antes mencionadas.