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 (2021)
- Authors:
- Autor USP: MORIYAMA, ANDRÉ TOSHIO ASANOME - ICMC
- Unidade: ICMC
- Sigla do Departamento: SCC
- DOI: 10.11606/D.55.2021.tde-27012022-123001
- Subjects: ANÁLISE DE DADOS; ESPAÇOS MÉTRICOS; ALGORITMOS E ESTRUTURAS DE DADOS; BANCO DE DADOS
- Keywords: Busca por similaridade; Diagrama de Voronoi; Métodos de acesso métricos; Metric access methods; Similarity search; Slim-tree; Slim-tree; Voronoi diagram
- Language: Português
- Abstract: 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 problemada 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.
- Imprenta:
- Publisher place: São Carlos
- Date published: 2021
- Data da defesa: 26.11.2021
- Este periódico é de acesso aberto
- Este artigo é de acesso aberto
- URL de acesso aberto
- Cor do Acesso Aberto: gold
- Licença: cc-by-nc-sa
-
ABNT
MORIYAMA, Andre Toshio Asanome. 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. 2021. Dissertação (Mestrado) – Universidade de São Paulo, São Carlos, 2021. Disponível em: https://www.teses.usp.br/teses/disponiveis/55/55134/tde-27012022-123001/. Acesso em: 14 out. 2024. -
APA
Moriyama, A. T. A. (2021). 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 (Dissertação (Mestrado). Universidade de São Paulo, São Carlos. Recuperado de https://www.teses.usp.br/teses/disponiveis/55/55134/tde-27012022-123001/ -
NLM
Moriyama ATA. 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 [Internet]. 2021 ;[citado 2024 out. 14 ] Available from: https://www.teses.usp.br/teses/disponiveis/55/55134/tde-27012022-123001/ -
Vancouver
Moriyama ATA. 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 [Internet]. 2021 ;[citado 2024 out. 14 ] Available from: https://www.teses.usp.br/teses/disponiveis/55/55134/tde-27012022-123001/
Informações sobre o DOI: 10.11606/D.55.2021.tde-27012022-123001 (Fonte: oaDOI API)
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
