ML Anthology

Fast Approximate Nearest-Neighbor Search with K-Nearest Neighbor Graph

Kiana Hajebi, Yasin Abbasi-Yadkori, Hossein Shahbazi, Hong Zhang
IJCAI 2011 pp. 1312-1317
doi:10.5591/978-1-57735-516-8/IJCAI11-222 /ijcai/2011/hajebi2011ijcai-fast/

Abstract

We introduce a new nearest neighbor search al-gorithm. The algorithm builds a nearest neighborgraph in an offline phase and when queried witha new point, performs hill-climbing starting froma randomly sampled node of the graph. We pro-vide theoretical guarantees for the accuracy and thecomputational complexity and empirically showthe effectiveness of this algorithm.

PDF IJCAI Semantic Scholar

Cite

Text

Hajebi et al. "Fast Approximate Nearest-Neighbor Search with K-Nearest Neighbor Graph." International Joint Conference on Artificial Intelligence, 2011. doi:10.5591/978-1-57735-516-8/IJCAI11-222

Markdown

[Hajebi et al. "Fast Approximate Nearest-Neighbor Search with K-Nearest Neighbor Graph." International Joint Conference on Artificial Intelligence, 2011.](https://mlanthology.org/ijcai/2011/hajebi2011ijcai-fast/) doi:10.5591/978-1-57735-516-8/IJCAI11-222

BibTeX

@inproceedings{hajebi2011ijcai-fast,
  title     = {{Fast Approximate Nearest-Neighbor Search with K-Nearest Neighbor Graph}},
  author    = {Hajebi, Kiana and Abbasi-Yadkori, Yasin and Shahbazi, Hossein and Zhang, Hong},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2011},
  pages     = {1312-1317},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-222},
  url       = {https://mlanthology.org/ijcai/2011/hajebi2011ijcai-fast/}
}