---
title: "Fast Approximate Nearest-Neighbor Search with k-Nearest Neighbor Graph"
authors:
  - "Kiana Hajebi"
  - "Yasin Abbasi-Yadkori"
  - "Hossein Shahbazi"
  - "Hong Zhang"
doi: "10.5591/978-1-57735-516-8/IJCAI11-222"
url: "https://ijcai.org/proceedings/2011/222"
pdf: "https://ijcai.org/proceedings/2011/0222.pdf"
venue: "Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence"
year: 2011
pages: "1312-1316"
track: ""
keywords:
---

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

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

*Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence*, pages 1312-1316. DOI: [10.5591/978-1-57735-516-8/IJCAI11-222](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.