A comprehensive analysis of delayed insertions in metric access methods. Issue 95 (January 2021)

• Record Type: Journal Article
• Authors: Razente, Humberto; Barioni, Maria Camila N.; Santos Sousa, Regis M.
• Is Part Of: Information systems. Issue 95(2021)
• Publication Date: 2021-01
• Subjects: Metric access methods -- M-tree -- Ball-partitioning -- Metric spaces -- Short-term memory -- Forced reinsertion; Database management -- Periodicals; Electronic data processing -- Periodicals; Bases de données -- Gestion -- Périodiques; Informatique -- Périodiques; Database management; Electronic data processing; Periodicals; 005.7
• DOI: 10.1016/j.is.2020.101492
• Languages: English
• ISSNs: 0306-4379

Abstract

Abstract: Similarity queries are fundamental operations for applications that deal with complex data. This paper presents MIA (Metric Indexing Assisted by auxiliary memory with limited capacity), a new delayed insertion approach that can be employed to create enhanced dynamic metric access methods through short-term memories. We present a comprehensive evaluation of delayed insertion methods for metric access methods while comparing MIA to dynamic forced reinsertions. Our experimental results show that metric access methods can benefit from these strategies, decreasing the node overlap, the number of distance calculations, the number of disk accesses, and the execution time to run k-nearest neighbor queries. Highlights: MIA technique: a detailed description of a new indexing algorithm. A comprehensive analysis of delayed insertions strategies. Several experiments with real data allowed the evaluation of the methods.