https://github.com/swapneel/hnsw-rust Skip to content Toggle navigation Sign in * Product + Actions Automate any workflow + Packages Host and manage packages + Security Find and fix vulnerabilities + Codespaces Instant dev environments + Copilot Write better code with AI + Code review Manage code changes + Issues Plan and track work + Discussions Collaborate outside of code Explore + All features + Documentation + GitHub Skills + Blog * Solutions For + Enterprise + Teams + Startups + Education By Solution + CI/CD & Automation + DevOps + DevSecOps Resources + Learning Pathways + White papers, Ebooks, Webinars + Customer Stories + Partners * Open Source + GitHub Sponsors Fund open source developers + The ReadME Project GitHub community articles Repositories + Topics + Trending + Collections * Pricing Search or jump to... Search code, repositories, users, issues, pull requests... Search [ ] Clear Search syntax tips Provide feedback We read every piece of feedback, and take your input very seriously. [ ] [ ] Include my email address so I can be contacted Cancel Submit feedback Saved searches Use saved searches to filter your results more quickly Name [ ] Query [ ] To see all available qualifiers, see our documentation. Cancel Create saved search Sign in Sign up You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session. Dismiss alert {{ message }} swapneel / hnsw-rust Public * Notifications * Fork 2 * Star 93 * HNSW implementation in Rust. Reference: https://arxiv.org/ftp/arxiv/ papers/1603/1603.09320.pdf 93 stars 2 forks Branches Tags Activity Star Notifications * Code * Issues 0 * Pull requests 0 * Actions * Projects 0 * Security * Insights Additional navigation options * Code * Issues * Pull requests * Actions * Projects * Security * Insights swapneel/hnsw-rust This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository. main BranchesTags Go to file Code Folders and files Name Name Last commit message Last commit date Latest commit History 7 Commits src src .gitignore .gitignore Cargo.lock Cargo.lock Cargo.toml Cargo.toml README.md README.md View all files Repository files navigation * README hnsw-rust - a fast HNSW implementation in Rust Technical Details hnsw-rust is a Rust implementation of The Hierarchical Navigable Small World (HNSW) algorithm. HNSW is a notable advancement in Approximate Nearest Neighbor (ANN) search in high-dimensional spaces, fundamentally altering our approach to these problems. The algorithm constructs a layered graph structure, where higher layers (less dense) are used for rapid global navigation, while lower layers (more dense) facilitate fine-grained local search. This structure mirrors the 'small world' phenomenon observed in social networks, where short path lengths exist between any two nodes (Watts and Strogatz, 1998). HNSW's search efficiency arises from its unique use of a greedy heuristic. It commences from a high layer and iteratively moves to the node closest to the target, transitioning down to denser layers until the nearest neighbors are refined. This method of layer traversal for nearest neighbor search finds its roots in earlier works like Kleinberg's small-world model, which also highlights efficient navigation in sparse, high-dimensional spaces (Kleinberg, 2000). image New nodes are inserted starting from the lowest layer, with their inclusion in each subsequent higher layer governed by a probabilistic threshold. This strategy is influenced by earlier research in dynamic random graphs and scale-free networks, which also deal with node connections based on probabilistic models (Barabasi and Albert, 1999). The probability of ascending to higher layers decreases exponentially, a method validated by research emphasizing the balance between exploration and exploitation in search algorithms (Arya et al., 1998). References: Malkov, Yu. A., & Yashunin, D. A. (2016). Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs. arXiv preprint arXiv:1603.09320. Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of 'small-world' networks. Nature, 393(6684), 440-442. Kleinberg, J. M. (2000). The small-world phenomenon: An algorithmic perspective. Proceedings of the 32nd annual ACM symposium on Theory of computing. Barabasi, A. L., & Albert, R. (1999). Emergence of scaling in random networks. Science, 286(5439), 509-512. Arya, S., Mount, D. M., Netanyahu, N. S., Silverman, R., & Wu, A. Y. (1998). An optimal algorithm for approximate nearest neighbor searching fixed dimensions. Journal of the ACM (JACM), 45(6), 891-923. Aumuller, M., Bernhardsson, E., & Faithfull, A. (2017). ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms. Information Systems, arXiv:1807.05614. About HNSW implementation in Rust. Reference: https://arxiv.org/ftp/arxiv/ papers/1603/1603.09320.pdf Resources Readme Activity Stars 93 stars Watchers 1 watching Forks 2 forks Report repository Releases No releases published Packages 0 No packages published Languages * Rust 100.0% Footer (c) 2024 GitHub, Inc. Footer navigation * Terms * Privacy * Security * Status * Docs * Contact * Manage cookies * Do not share my personal information You can't perform that action at this time.