← all papers · overview

A Scalable Solution To The Nearest Neighbor Search Problem Through Local-search Methods On Neighbor Graphs

2017 · Eric S. Tellez, Guillermo Ruiz, Edgar Chavez, et al.

Abstract

Near neighbor search (NNS) is a powerful abstraction for data access; however, data indexing is troublesome even for approximate indexes. For intrinsically high-dimensional data, high-quality fast searches demand either indexes with impractically large memory usage or preprocessing time. In this paper, we introduce an algorithm to solve a nearest-neighbor query \(q\) by minimizing a kernel function defined by the distance from \(q\) to each object in the database. The minimization is performed using metaheuristics to solve the problem rapidly; even when some methods in the literature use this strategy behind the scenes, our approach is the first one using it explicitly. We also provide two approaches to select edges in the graph's construction stage that limit memory footprint and reduce the number of free parameters simultaneously. We carry out a thorough experimental comparison with state-of-the-art indexes through synthetic and real-world datasets; we found out that our contribu

Authors

(none)

Tags

  • ANN Search

Stats

  • citations2
  • S2 citations—
  • github stars0
  • HF likes0
  • heat score3.58
  • arxiv keytellez2017a

Related papers

A Scalable Solution To The Nearest Neighbor Search Problem Through Local-search Methods On Neighbor Graphs — learning-to-hash