• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Master's Dissertation
DOI
https://doi.org/10.11606/D.55.2021.tde-27012022-123001
Document
Author
Full name
Andre Toshio Asanome Moriyama
E-mail
Institute/School/College
Knowledge Area
Date of Defense
Published
São Carlos, 2021
Supervisor
Committee
Traina Junior, Caetano (President)
Becker, Karin
Sousa, Elaine Parros Machado de
Valle Junior, Eduardo Alves do
Title in Portuguese
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
Keywords in Portuguese
Busca por similaridade
Diagrama de Voronoi
Métodos de acesso métricos
Slim-tree
Abstract in Portuguese
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.
Title in English
VD-tree: A strategy to reduce the overlapping nodes in Metric Access Methods using Voronoi Diagrams
Keywords in English
Metric access methods
Similarity search
Slim-tree
Voronoi diagram
Abstract in English
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.
 
WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
Publishing Date
2022-01-27
 
WARNING: Learn what derived works are clicking here.
All rights of the thesis/dissertation are from the authors
CeTI-SC/STI
Digital Library of Theses and Dissertations of USP. Copyright © 2001-2022. All rights reserved.