Elamur Research
☰
home / papers / 2016 / Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs

Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "arXiv — non-exclusive license to distribute" does not allow redistributing the text itself. Original — arxiv.org/pdf/1603.09320

Summary

Many applications, such as image feature matching or semantic document retrieval, need fast similarity lookups over large collections, which makes approximate K-nearest neighbor search (K-ANNS) essential. Earlier proximity-graph methods, including the authors' Navigable Small World (NSW) graphs, perform well on high-dimensional data. However, their routing cost grows polylogarithmically or worse, and they degrade sharply on low-dimensional or heavily clustered data. Hybrid systems address this with vector-only helpers such as kd-trees or product quantization. This paper proposes Hierarchical NSW (HNSW), an index built only from graphs. It is constructed incrementally as a stack of proximity graphs over nested subsets of the data. Each element receives a random top layer drawn from an exponentially decaying distribution, so the sparse upper layers carry long links and the dense lower layers carry short ones. A query moves greedily from the top layer downward, and the local minimum found on each layer becomes the entry point for the next. Limiting the links per node gives logarithmic search complexity. A heuristic for choosing neighbors further improves results at high recall and on clustered data. The method works in general metric spaces and outperformed leading open-source vector-only approaches.

Key points

  • HNSW is fully graph-based and needs no auxiliary coarse-search structure (e.g., kd-trees or PQ) to pick entry points.
  • An element's maximum layer is chosen randomly with exponentially decreasing probability. This separates links by distance scale, and the design can be viewed as a skip list that uses proximity graphs in place of linked lists.
  • The design reduces search complexity from polylogarithmic (NSW) to logarithmic by fixing the number of connections evaluated per element regardless of dataset size.
  • Main contributions are explicit selection of the entry point, separation of links by scale across layers, and an advanced neighbor-selection heuristic.
  • The skip-list analogy allows a straightforward balanced distributed implementation. Specific benchmark figures were in the omitted middle of the provided text and are not reproduced here.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Other

Cited by

164 papers of our library cite it (of the 140673 whose bibliographies we read).

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.1603.09320 · arXiv 1603.09320

@misc{malkov2016efficient,
  title = {{Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs}},
  author = {Malkov, Yu. A. and Yashunin, D. A.},
  year = {2016},
  doi = {10.48550/arxiv.1603.09320},
  eprint = {1603.09320},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1603.09320}
}

References

59 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. D. G. Lowe, "Distinctive image features from scale-invariant keypoints," International journal of computer vision, vol. 60, no. 2, pp. 91-110, 2004. find
  2. S. Deerwester, S. T. Dumais, T. K. Landauer, G. W. Furnas, and R. A. Harshman, "Indexing by Latent Semantic Analysis," J. Amer. Soc. Inform. Sci., vol. 41, pp. 391-407, 1990. find
  3. P. N. Yianilos, "Data structures and algorithms for nearest neighbor search in general metric spaces," in SODA, 1993, vol. 93, no. 194, pp. 311-321. find
  4. G. Navarro, "Searching in metric spaces by spatial approximation," The VLDB Journal, vol. 11, no. 1, pp. 28-46, 2002. find
  5. E. S. Tellez, G. Ruiz, and E. Chavez, "Singleton indexes for nearest neighbor search," Information Systems, 2016. find
  6. M. Muja and D. G. Lowe, "Scalable nearest neighbor algorithms for high dimensional data," Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 36, no. 11, pp. 2227-2240, 2014. find
  7. M. E. Houle and M. Nett, "Rank-based similarity search: Reducing the dimensional dependence," Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 37, no. 1, pp. 136-150, 2015. find
  8. A. Andoni, P. Indyk, T. Laarhoven, I. Razenshteyn, and L. Schmidt, "Practical and optimal LSH for angular distance," in Advances in Neural Information Processing Systems, 2015, pp. 1225-1233. find
  9. P. Indyk and R. Motwani, "Approximate nearest neighbors: towards removing the curse of dimensionality," in Proceedings of the thirtieth annual ACM symposium on Theory of computing, 1998, pp. 604-613: ACM. find
  10. J. Wang, J. Wang, G. Zeng, R. Gan, S. Li, and B. Guo, "Fast neighborhood graph search using cartesian concatenation," in Multimedia Data Mining and Analytics: Springer, 2015, pp. 397-417. find
  11. M. Norouzi, A. Punjani, and D. J. Fleet, "Fast exact search in hamming space with multi-index hashing," Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 36, no. 6, pp. 1107-1119, 2014. find
  12. A. Babenko and V. Lempitsky, "The inverted multi-index," in Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on, 2012, pp. 3069-3076: IEEE. find
  13. H. Jegou, M. Douze, and C. Schmid, "Product quantization for nearest neighbor search," Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 33, no. 1, pp. 117-128, 2011. find
  14. A. Babenko and V. Lempitsky, "Efficient indexing of billion-scale datasets of deep descriptors," in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2016, pp. 2055-2063. find
  15. M. Douze, H. Jégou, and F. Perronnin, "Polysemous codes," in European Conference on Computer Vision, 2016, pp. 785-801: Springer. find
  16. Y. Kalantidis and Y. Avrithis, "Locally optimized product quantization for approximate nearest neighbor search," in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2014, pp. 2321-2328. find
  17. P. Wieschollek, O. Wang, A. Sorkine-Hornung, and H. Lensch, "Efficient large-scale approximate nearest neighbor search on the gpu," in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2016, pp. 2027-2035. find
  18. S. Arya and D. M. Mount, "Approximate Nearest Neighbor Queries in Fixed Dimensions," in SODA, 1993, vol. 93, pp. 271-280. find
  19. J. Wang and S. Li, "Query-driven iterated neighborhood graph search for large scale indexing," in Proceedings of the 20th ACM international conference on Multimedia, 2012, pp. 179-188: ACM. find
  20. Z. Jiang, L. Xie, X. Deng, W. Xu, and J. Wang, "Fast Nearest Neighbor Search in the Hamming Space," in MultiMedia Modeling, 2016, pp. 325-336: Springer. find
  21. E. Chávez and E. S. Tellez, "Navigating k-nearest neighbor graphs to solve nearest neighbor searches," in Advances in Pattern Recognition: Springer, 2010, pp. 270-280. find
  22. K. Aoyama, K. Saito, H. Sawada, and N. Ueda, "Fast approximate similarity search based on degree-reduced neighborhood graphs," in Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, 2011, pp. 1055-1063: ACM. find
  23. G. Ruiz, E. Chávez, M. Graff, and E. S. Téllez, "Finding Near Neighbors Through Local Search," in Similarity Search and Applications: Springer, 2015, pp. 103-109. find
  24. R. Paredes, "Graphs for metric space searching," PhD thesis, University of Chile, Chile, 2008. Dept. of Computer Science Tech Report TR/DCC-2008-10. Available at http://www.dcc.uchile.cl/~raparede/publ/08PhDthesis.pdf, 2008. ↗
  25. Y. Malkov, A. Ponomarenko, A. Logvinov, and V. Krylov, "Scalable distributed algorithm for approximate nearest neighbor search problem in high dimensional general metric spaces," in Similarity Search and Applications: Springer Berlin Heidelberg, 2012, pp. 132-147. find
  26. Y. Malkov, A. Ponomarenko, A. Logvinov, and V. Krylov, "Approximate nearest neighbor algorithm based on navigable small world graphs," Information Systems, vol. 45, pp. 61-68, 2014. find
  27. W. Pugh, "Skip lists: a probabilistic alternative to balanced trees," Communications of the ACM, vol. 33, no. 6, pp. 668-676, 1990. find
  28. C. C. Cartozo and P. De Los Rios, "Extended navigability of small world networks: exact results and new insights," Physical review letters, vol. 102, no. 23, p. 238703, 2009. find
  29. W. Dong, C. Moses, and K. Li, "Efficient k-nearest neighbor graph construction for generic similarity measures," in Proceedings of the 20th international conference on World wide web, 2011, pp. 577-586: ACM. find
  30. A. Ponomarenko, Y. Malkov, A. Logvinov, and V. Krylov, "Approximate Nearest Neighbor Search Small World Approach," in International Conference on Information and Communication Technologies & Applications, Orlando, Florida, USA, 2011. find
  31. J. M. Kleinberg, "Navigation in a small world," Nature, vol. 406, no. 6798, pp. 845-845, 2000. find
  32. M. Boguna, D. Krioukov, and K. C. Claffy, "Navigability of complex networks," Nature Physics, vol. 5, no. 1, pp. 74-80, 2009. find
  33. A. Ponomarenko, N. Avrelin, B. Naidan, and L. Boytsov, "Comparative Analysis of Data Structures for Approximate Nearest Neighbor Search," In Proceedings of The Third International Conference on Data Analytics, 2014. find
  34. B. Naidan, L. Boytsov, and E. Nyberg, "Permutation search methods are efficient, yet faster search is possible," VLDB Procedings, vol. 8, no. 12, pp. 1618-1629, 2015. find
  35. D. Krioukov, F. Papadopoulos, M. Kitsak, A. Vahdat, and M. Boguná, "Hyperbolic geometry of complex networks," Physical Review E, vol. 82, no. 3, p. 036106, 2010. find
  36. A. Gulyás, J. J. Bíró, A. Kőrösi, G. Rétvári, and D. Krioukov, "Navigable networks as Nash equilibria of navigation games," Nature Communications, vol. 6, p. 7651, 2015. find
  37. Y. Lifshits and S. Zhang, "Combinatorial algorithms for nearest neighbors, near-duplicates and small-world design," in Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009, pp. 318-326: Society for Industrial and Applied Mathematics. find
  38. A. Karbasi, S. Ioannidis, and L. Massoulie, "From Small-World Networks to Comparison-Based Search," Information Theory, IEEE Transactions on, vol. 61, no. 6, pp. 3056-3074, 2015. find
  39. O. Beaumont, A.-M. Kermarrec, and É. Rivière, "Peer to peer multidimensional overlays: Approximating complex structures," in Principles of Distributed Systems: Springer, 2007, pp. 315-328. find
  40. O. Beaumont, A.-M. Kermarrec, L. Marchal, and É. Rivière, "VoroNet: A scalable object network based on Voronoi tessellations," in Parallel and Distributed Processing Symposium, 2007. IPDPS 2007. IEEE International, 2007, pp. 1-10: IEEE. find
  41. J. Kleinberg, "The small-world phenomenon: An algorithmic perspective," in Proceedings of the thirty-second annual ACM symposium on Theory of computing, 2000, pp. 163-170: ACM. find
  42. J. Travers and S. Milgram, "An experimental study of the small world problem," Sociometry, pp. 425-443, 1969. find
  43. D. J. Watts and S. H. Strogatz, "Collective dynamics of ‘small-world’networks," Nature, vol. 393, no. 6684, pp. 440-442, 1998. find
  44. Y. A. Malkov and A. Ponomarenko, "Growing homophilic networks are natural navigable small worlds," PloS one, p. e0158162, 2016. find
  45. M. T. Goodrich, M. J. Nelson, and J. Z. Sun, "The rainbow skip graph: a fault-tolerant constant-degree distributed data structure," in Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, 2006, pp. 384-393: Society for Industrial and Applied Mathematics. find
  46. G. T. Toussaint, "The relative neighbourhood graph of a finite planar set," Pattern recognition, vol. 12, no. 4, pp. 261-268, 1980. find
  47. B. Harwood and T. Drummond, "FANNG: fast approximate nearest neighbour graphs," in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2016, pp. 5713-5722. find
  48. R. A. Dwyer, "Higher-dimensional Voronoi diagrams in linear expected time," Discrete & Computational Geometry, vol. 6, no. 3, pp. 343-367, 1991. find
  49. L. Boytsov and B. Naidan, "Engineering Efficient and Effective Non-metric Space Library," in Similarity Search and Applications: Springer, 2013, pp. 280-293. find
  50. L. Boytsov and B. Naidan, "Learning to prune in metric and non-metric spaces," in Advances in Neural Information Processing Systems, 2013, pp. 1574-1582. find
  51. A. Andoni and I. Razenshteyn, "Optimal Data-Dependent Hashing for Approximate Near Neighbors," presented at the Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, Portland, Oregon, USA, 2015. find
  52. J. Pennington, R. Socher, and C. D. Manning, "Glove: Global vectors for word representation," Proceedings of the Empiricial Methods in Natural Language Processing (EMNLP 2014), vol. 12, pp. 1532-1543, 2014. find
  53. P. Bolettieri et al., "CoPhIR: a test collection for content-based image retrieval," arXiv preprint arXiv:0905.4627, 2009. — [arXiv:0905.4627](https://arxiv.org/abs/0905.4627) find
  54. Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, "Gradient-based learning applied to document recognition," Proceedings of the IEEE, vol. 86, no. 11, pp. 2278-2324, 1998. find
  55. E. Chávez, M. Graff, G. Navarro, and E. Téllez, "Near neighbor searching with K nearest references," Information Systems, vol. 51, pp. 43-61, 2015. find
  56. E. C. Gonzalez, K. Figueroa, and G. Navarro, "Effective proximity retrieval by ordering permutations," Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 30, no. 9, pp. 1647-1658, 2008. find
  57. E. S. Tellez, E. Chávez, and G. Navarro, "Succinct nearest neighbor search," Information Systems, vol. 38, no. 7, pp. 1019-1030, 2013. find
  58. P. Sojka, "Software framework for topic modelling with large corpora," in In Proceedings of the LREC 2010 Workshop on New Challenges for NLP Frameworks, 2010: Citeseer. find
  59. C. Beecks, "Distance-based similarity models for content-based multimedia retrieval," Hochschulbibliothek der Rheinisch-Westfälischen Technischen Hochschule Aachen, 2013. Yury A. Malkov received a Master’s degree in physics from Nizhny Novgorod State University in 2009, and a PhD degree in laser phy… find