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

Author(s)

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

• Document type: Journal article
• Source: 36TH ANNUAL ACM SYMPOSIUM ON APPLIED COMPUTING, SAC 2021; v. N/A, p. 9-pg., 2021-01-01.

Abstract

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)

• FAPESP's process: 16/17330-1 - Storage and Navigation Operations on Graphs in Relational DBMS
• Grantee: Lucas de Carvalho Scabora
• Support Opportunities: Scholarships in Brazil - Doctorate
• FAPESP's process: 20/10902-5 - Handling similarity queries over incomplete data in a Relational DBMS
• Grantee: Lucas Santiago Rodrigues
• Support Opportunities: Scholarships in Brazil - Technical Training Program - Technical Training
• FAPESP's process: 18/24414-2 - A framework for integration of feature extraction techniques and complex databases for MIVisBD
• Grantee: Mirela Teixeira Cazzolato
• Support Opportunities: Scholarships in Brazil - Technical Training Program - Technical Training
• FAPESP's process: 20/11258-2 - Interoperability and similarity queries on medical databases
• Grantee: Mirela Teixeira Cazzolato
• Support Opportunities: Scholarships in Brazil - Post-Doctoral
• FAPESP's process: 16/17078-0 - Mining, indexing and visualizing Big Data in clinical decision support systems (MIVisBD)
• Grantee: Agma Juci Machado Traina
• Support Opportunities: Research Projects - Thematic Grants
• FAPESP's process: 20/07200-9 - Analyzing complex data from COVID-19 to support decision making and prognosis
• Grantee: Agma Juci Machado Traina
• Support Opportunities: Regular Research Grants