# Graph-based nearest neighbor search

## Graph-based approaches

## Scalability

## Discovering graph structures and search algorithms

## Theoretical guarantees

### Euclidean space

### Hyperbolic space

## Summary

## References

- Muja M., Lowe D. G. “Fast approximate nearest neighbors with automatic algorithm configuration.” VISSAPP 2009.←
- Dasgupta S., Sinha K. “Randomized partition trees for exact nearest neighbor search.” COLT 2013.←
- Jégou H., Douze M., Schmid C. “Product quantization for nearest neighbor search.” TPAMI 2011.←
- Babenko, A., Lempitsky, V. S. “The inverted multi-index.” CVPR 2012.←
- Andoni A., Indyk P., Laarhoven T., Razenshteyn I., Schmidt L. “Practical and optimal LSH for angular distance.” NeuriPS 2015.←
- Malkov Y. A., Yashunin D. A. “Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs.” TPAMI 2018.←
- Fu C., Xiang C., Wang C., Cai D. “Fast approximate nearest neighbor search with the navigating spreading-out graph.” VLDB 2019.←
- Iwasaki M., Miyazaki D. “Optimization of indexing based on k-nearest neighbor graph for proximity.” 2018.←
- Morozov S., Babenko A. “Non-metric similarity graphs for maximum inner product search.” NeurIPS 2018.←
- Prokhorenkova L., Baranchuk D., Bogachev N., Demidovich Y., Kolpakov A. “Graph-based nearest neighbor search in hyperbolic spaces.” ICLR 2022.←
- Morozov S. and Babenko A. “Relevance proximity graphs for fast relevance retrieval.” 2019.←
- Baranchuk D., Babenko A., Malkov Y. “Revisiting the inverted indices for billion-scale approximate nearest neighbors.” ECCV 2018.←
- Baranchuk D., Persiyanov D., Sinitsin A., Babenko A. “Learning to route in similarity graphs.” ICML 2019.←
- Baranchuk D., Babenko A. "Towards similarity graphs constructed by deep reinforcement learning.” 2019.←
- Prokhorenkova L., Shekhovtsov A. “Graph-based nearest neighbor search: From practice to theory.” ICML 2020.←