2019/07/17 by Martin Aumüller, Aumüller, Martin, Matteo Ceccarello +1 · 1 citation
Computer Science · #Advanced Image and Video Retrieval Techniques #Data Management and Algorithms #Databases (cs.DB) #FOS: Computer and information sciences #Information Retrieval (cs.IR) #Machine Learning and Data Classification #cs.DB #cs.IR
paper · pdf · doi:10.48550/arxiv.1907.07387
Preprint of the paper accepted at SISAP 2019
arxiv created 2019/07/17 · openalex publication_date 2019/07/17 · arxiv updated 2019/07/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
This paper reconsiders common benchmarking approaches to nearest neighbor search. It is shown that the concept of local intrinsic dimensionality (LID) allows to choose query sets of a wide range of difficulty for real-world datasets. Moreover, the effect of different LID distributions 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. 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.