A comprehensive analysis of delayed insertions in metric access methods. Issue 95 (January 2021) - Razente, Humberto; Barioni, Maria Camila N.; Santos Sousa, Regis M.
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.