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

Hajebi, Kiana; Abbasi-Yadkori, Yasin; Shahbazi, Hossein; Zhang, Hong

doi:10.5591/978-1-57735-516-8/IJCAI11-222

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

Kiana Hajebi, Yasin Abbasi-Yadkori, Hossein Shahbazi, Hong Zhang

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 1312-1316.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-222

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.

Kiana Hajebi, Yasin Abbasi-Yadkori, Hossein Shahbazi, and Hong Zhang. 2011. Fast Approximate Nearest-Neighbor Search with k-Nearest Neighbor Graph. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 1312–1316. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-222

@inproceedings{ijcai2011p222,
  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 = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {1312--1316},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-222},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-222},
}

TY  - CPAPER
TI  - Fast Approximate Nearest-Neighbor Search with k-Nearest Neighbor Graph
AU  - Hajebi, Kiana
AU  - Abbasi-Yadkori, Yasin
AU  - Shahbazi, Hossein
AU  - Zhang, Hong
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 1312
EP  - 1316
DO  - 10.5591/978-1-57735-516-8/IJCAI11-222
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-222
ER  -