• 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
 
 
Disertación de Maestría
DOI
https://doi.org/10.11606/D.55.2021.tde-27012022-123001
Documento
Autor
Nombre completo
Andre Toshio Asanome Moriyama
Dirección Electrónica
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Carlos, 2021
Director
Tribunal
Traina Junior, Caetano (Presidente)
Becker, Karin
Sousa, Elaine Parros Machado de
Valle Junior, Eduardo Alves do
Título en portugués
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
Palabras clave en portugués
Busca por similaridade
Diagrama de Voronoi
Métodos de acesso métricos
Slim-tree
Resumen en portugués
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.
Título en inglés
VD-tree: A strategy to reduce the overlapping nodes in Metric Access Methods using Voronoi Diagrams
Palabras clave en inglés
Metric access methods
Similarity search
Slim-tree
Voronoi diagram
Resumen en inglés
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.
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
Fecha de Publicación
2022-01-27
 
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
CeTI-SC/STI
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2022. Todos los derechos reservados.