VD-Tree: How to build an efficient and fit metric access method using Voronoi Diagrams

Autor(es)

Moriyama, Andre ; Rodrigues, Lucas S. ; Scabora, Lucas C. ; Cazzolato, Mirela T. ; Traina, Agma J. M. ; Traina, Caetano, Jr.

• Tipo de documento: Artigo Científico
• Fonte: 36TH ANNUAL ACM SYMPOSIUM ON APPLIED COMPUTING, SAC 2021; v. N/A, p. 9-pg., 2021-01-01.

Resumo

Efficient similarity search is a core issue for retrieval operations on large amounts of complex data, often relying on Metric Access Methods (MAMs) to speed up the Range and k-NN queries. Among the most used MAMs are those based on covering radius, which create balanced structures, and enable efficient data retrieval and dynamic maintenance. MAMs typically suffer from node overlapping, which increases retrieval costs. Some strategies aim to reduce node overlapping by employing global pivots to improve the filtering process during queries, but result at significant costs to maintain the pivots, whereas not completely removing the overlaps, which impacts queries over large databases. Other strategies use hyper-planebased MAMs, which can get rid of overlaps but with large costs to create and update the index. We propose VD-Tree, a MAM which combines a covering radius strategy with a Voronoi-like organization. VD-Tree retains index flexibility for updates whereas reducing the node overlap using dynamic swap of elements among nodes. The method relies on only the solid organization fostered by Voronoi, and does not require storing further information to the tree. Experimental analysis using five real-world image datasets and four feature extractors shows that VD-Tree reduced node overlaps up to 43% and the average time needed to answer similarity queries by up to 28%, when compared to its closest competitor. (AU)

• Processo FAPESP: 16/17330-1 - Armazenamento e Operações de Navegação em Grafos em SGBDs Relacionais
• Beneficiário: Lucas de Carvalho Scabora
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Processo FAPESP: 20/10902-5 - Tratamento de consulta por similaridade em dados incompletos em um SGBD Relacional
• Beneficiário: Lucas Santiago Rodrigues
• Modalidade de apoio: Bolsas no Brasil - Programa Capacitação - Treinamento Técnico
• Processo FAPESP: 18/24414-2 - Ambiente para integração de técnicas para a extração de características e bases de dados complexos para o projeto MIVisBD
• Beneficiário: Mirela Teixeira Cazzolato
• Modalidade de apoio: Bolsas no Brasil - Programa Capacitação - Treinamento Técnico
• Processo FAPESP: 20/11258-2 - Consultas por similaridade e interoperabilidade em bases de dados médicos
• Beneficiário: Mirela Teixeira Cazzolato
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Processo FAPESP: 16/17078-0 - Mineração, indexação e visualização de Big Data no contexto de sistemas de apoio à decisão clínica (MIVisBD)
• Beneficiário: Agma Juci Machado Traina
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 20/07200-9 - Analisando dados complexos vinculados a COVID-19 para apoio à tomada de decisão e prognóstico
• Beneficiário: Agma Juci Machado Traina
• Modalidade de apoio: Auxílio à Pesquisa - Regular