VD-Tree: Uma estratégia para redução da sobreposição de nós em Métodos de Acesso Métricos utilizando o Diagrama de Voronoi

Os avanços na tecnologia proporcionaram o aumento crescente na geração de dados e nos novos tipos de dados, tornando necessário estender os SGBDs para possibilitar armazenar, recuperar e organizar novos tipos de dados como imagens, vídeos e áudios, sendo estes conhecidos como dados complexos. Para as consultas em dados complexos, não é adequado comparar objetos utilizando as relações de Ordem e Identidade, sendo então a opção mais utilizada a comparação por similaridade. Dessa maneira, com a necessidade de desenvolver novos índices para as comparações baseadas em similaridade, surgiram os Métodos de Acesso Métricos (MAMs). Entre as diversas estratégias para indexar os dados, as baseadas em árvore se destacam por possibilitar um equilíbrio entre o tempo de construção do índice e a aceleração da consulta, sendo utilizada junto com a estratégia de árvore, uma estratégia para definir a região dos nós. Entre as diversas estratégias para definir regiões, o raio de cobertura está dentre as mais comumente utilizadas por flexibilizar a posição do objeto na estrutura, possibilitando o controle da ocupação dos nós e a redução no custo da construção da estrutura. Porém, esta estratégia possui o problema da sobreposição de nós, que aumenta o custo para obter as respostas exatas ao realizar as consultas por similaridade. Outra estratégia que não possui o problema da sobreposição, mas que sofre com o alto custo de construção, é a baseada no Diagrama de Voronoi. Buscando reduzir o problema da sobreposição de nós, aumentando o mínimo possível o custo da construção da árvore, neste projeto de mestrado foi proposto o MAM VD-Tree que busca acelerar as consultas por similaridade por meio da redução da sobreposição, obtida com reorganizações baseadas no Diagrama de Voronoi. Resultados experimentais mostraram que o método é capaz de acelerar consultas por similaridade e reduzir a sobreposição de nós na maioria dos casos, em comparação com seu principal competidor, o Slim-Tree. A melhora no tempo gasto ocorre devido ao método criar organizações melhores dos objetos na estrutura e reduzir a sobreposição dos nós, com o custo de criar mais nós para indexar os dados. Advances in the information technology have increased the amount of data generated daily and new types of data, making it necessary to extend DBMS to enable storing, retrieving, and organizing new types of data such as images, videos, and audio, known as complex data. It is not suitable for queries on complex data to compare objects using Order or Identity relations, so comparisons by similarity are the most employed option. With the necessity of developing new indices for comparisons based on similarity, many studies proposed several Metric Access Methods (MAMs). One of the most commonly used strategies to index complex data, tree-based strategies are commonly employed since they maintain a balance between the cost to create the index and the cost to execute the queries. Accordingly, together with the tree strategy, it is necessary to use a strategy to define the region of the nodes. Among the several strategies to define regions, the coverage radius strategy is commonly used to make the objects position in the structure more flexible, making it possible to control the occupation of nodes and reduce the cost of building the structure. However, this strategy has the problem of overlapping nodes, which increases the cost of getting the exact answers when performing similarity queries. Another strategy that does not have the overlap problem but suffers from the high construction cost is based on the Voronoi Diagram. Seeking to reduce the problem of overlapping nodes, increasing as little as possible the cost of constructing the tree, we propose here the VD-Tree MAM to speed up similarity queries by reducing the overlap between nodes, obtained with reorganizations based on the Voronoi Diagram. Experimental results showed that the method could speed up similarity queries with better distributions of the objects in the structure and reduce overlapping nodes in most cases, compared to its main competitor Slim-Tree, with the cost of requiring more nodes to index the data.