Cracking KD-Tree : o primeiro índice adaptativo multidimensional = Cracking KD-Tree : the first multidimensional adaptive indexing

Abstract

Resumo: A criação de índices é um das decisões mais difíceis no processo de criação de esquemas em bancos de dados. Dada uma carga de trabalho, o administrador do banco de dados precisa decidir quais índices criar levando em consideração os custos para construção e manutenção deles. Esse problema se torna ainda mais difícil quando é necessário lidar buscas em múltiplas dimensões em sistemas exploratórios, onde não se tem uma carga de trabalho disponível e o número de possíveis índices é ainda maior. Técnicas de indexação adaptativas, como Sideways Cracking e Quasii, são capazes de responder buscas de intervalo em múltiplas dimensões. Nessa dissertação nós propomos uma alternativa, a Cracking KD-Tree, que é uma estrutura de dados adaptativa usada para buscas em múltiplas dimensões. Comparando-a com outras técnicas adaptativas de indexação, nossa estrutura de dados teve eficiência melhor ou comparável, com respeito a tempo total de resposta para executar a carga de trabalho. Com 2 atributos nós fomos 6.7x mais rápidos que o Sideways Cracking e 1.4x que o Quasii. Com 16 atributos, a Cracking KD-Tree foi 19x mais rápida que o Sideways Cracking e 1.7x mais rápida que o Quasii.

Abstract: Index creation is one of the main difficult decisions in database schema design. Given a workload, the database administrator has to decide which indexes to create taking into consideration the costs to build and maintain them. This problem becomes even more difficult when dealing with multidimensional queries in exploratory systems, where there is no workload available and the number of possible indexes is bigger. State of the art adaptive indexing techniques, such as Sideways Cracking and Quasii, are capable of answering multidimensional range queries. In this dissertation we propose an alternative, the Cracking KD-Tree, which is an adaptive data structure used for multidimensional queries. Comparing it with other adaptive indexing techniques, our data structure had more or comparable efficiency with respect to total workload response time. With 2 attributes we were 6.7x faster than Sideways Cracking and 1.4x than Quasii. With 16 attributes, the Cracking KD-Tree was 19x faster than Sideways Cracking and 1.7x faster than Quasii.