Home // DATA ANALYTICS 2014, The Third International Conference on Data Analytics // View article

Comparative Analysis of Data Structures for Approximate Nearest Neighbor Search

Authors:
Alexander Ponomarenko
Nikita Avrelin
Bilegsaikhan Naidan
Leonid Boytsov

Keywords: nearest neighbor search; metric space; non-metric search, approximate search; small world graphs

Abstract:
Similarity searching has a vast range of applications in various fields of computer science. Many methods have been proposed for exact search, but they all suffer from the curse of dimensionality and are, thus, not applicable to high dimensional spaces. Approximate search methods are considerably more efficient in high dimensional spaces. Unfortunately, there are few theoretical results regarding the complexity of these methods and there are no comprehensive empirical evaluations, especially for non-metric spaces. To fill this gap, we present an empirical analysis of data structures for approximate nearest neighbor search in high dimensional spaces. We provide a comparison with recently published algorithms on several data sets. Our results show that small world approaches provide some of the best tradeoffs between efficiency and effectiveness in both metric and non-metric spaces.

Pages: 125 to 130

Copyright: Copyright (c) IARIA, 2014

Publication date: August 24, 2014

Published in: conference

ISSN: 2308-4464

ISBN: 978-1-61208-358-2

Location: Rome, Italy

Dates: from August 24, 2014 to August 28, 2013