The role of local dimensionality measures in benchmarking nearest neighbor search. Issue 101 (November 2021)

• Record Type: Journal Article
• Authors: Aumüller, Martin; Ceccarello, Matteo
• Is Part Of: Information systems. Issue 101(2021)
• Publication Date: 2021-11
• Subjects: Nearest neighbor search -- Benchmarking; 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.2021.101807
• Languages: English
• ISSNs: 0306-4379

Abstract

Abstract: This paper reconsiders common benchmarking approaches to nearest neighbor search. It is shown that the concepts of local intrinsic dimensionality (LID), local relative contrast (RC), and query expansion allow to choose query sets of a wide range of difficulty for real-world datasets. Moreover, the effect of the distribution of these dimensionality measures on the running time performance of implementations is empirically studied. To this end, different visualization concepts are introduced that allow to get a more fine-grained overview of the inner workings of nearest neighbor search principles. Interactive visualizations are available on the companion website. 1 The paper closes with remarks about the diversity of datasets commonly used for nearest neighbor search benchmarking. It is shown that such real-world datasets are not diverse: results on a single dataset predict results on all other datasets well. Highlights: Local dimensionality measures allow to build query sets of different degrees of difficulty. Local Intrinsic Dimensionality is the most effective at selecting queries. Using average performance measures hides interesting behavior of algorithms. Datasets commonly used as benchmarks are not diverse enough.