Title: Hierarchical navigable small world URL Source: https://en.wikipedia.org/wiki/Hierarchical_Navigable_Small_World_graphs Published Time: 2024-02-22T19:54:41Z Markdown Content: Jump to content Main menu Search Donate Create account Log in Personal tools Toggle the table of contents Hierarchical navigable small world 1 language Article Talk Read Edit View history Tools From Wikipedia, the free encyclopedia (Redirected from Hierarchical Navigable Small World graphs) This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details. (February 2024) (Learn how and when to remove this message) Part of a series on Network science Theory GraphComplex networkContagionSmall-worldScale-freeCommunity structurePercolationEvolutionControllabilityGraph drawingSocial capitalLink analysisOptimizationReciprocityClosureHomophilyTransitivityPreferential attachmentBalance theoryNetwork effectSocial influence Network types Informational (computing)TelecommunicationTransportSocialScientific collaborationBiologicalArtificial neuralInterdependentSemanticSpatialDependencyFlowon-Chip Graphs Features CliqueComponentCutCycleData structureEdgeLoopNeighborhoodPathVertexAdjacency list / matrixIncidence list / matrix Types BipartiteCompleteDirectedHyperLabeledMultiRandomWeighted MetricsAlgorithms CentralityDegreeMotifClusteringDegree distributionAssortativityDistanceModularityEfficiency Models Topology Random graphErdős–RényiBarabási–AlbertBianconi–BarabásiFitness modelWatts–StrogatzExponential random (ERGM)Random geometric (RGG)Hyperbolic (HGN)HierarchicalStochastic blockBlockmodelingMaximum entropySoft configurationLFR Benchmark Dynamics Boolean networkagent basedEpidemic/SIR ListsCategories TopicsSoftwareNetwork scientists Category:Network theoryCategory:Graph theory vte The Hierarchical navigable small world (HNSW) algorithm is a graph-based approximate nearest neighbor search technique used in many vector databases.[1][2] Nearest neighbor search without an index involves computing the distance from the query to each point in the database, which for large datasets is computationally prohibitive. For high-dimensional data, tree-based exact vector search techniques such as the k-d tree and R-tree do not perform well enough because of the curse of dimensionality. To remedy this, approximate k-nearest neighbor searches have been proposed, such as locality-sensitive hashing (LSH) and product quantization (PQ) that trade performance for accuracy.[2] The HNSW graph offers an approximate k-nearest neighbor search which scales logarithmically even in high-dimensional data. It is an extension of the earlier work on navigable small world graphs presented at the Similarity Search and Applications (SISAP) conference in 2012 with an additional hierarchical navigation to find entry points to the main graph faster.[3] HNSW-based libraries are among the best performers in the approximate nearest neighbors benchmark.[4][5][6] Use in vector databases[edit] HNSW is a key method for approximate nearest neighbor search in high-dimensional vector databases, for example in the context of embeddings from neural networks in large language models. Databases that use HNSW as search index include: Apache Lucene Vector Search Chroma Qdrant Vespa Vearch Gamma Weaviate pgvector MariaDB[7] MongoDB Atlas[8] Milvus[9] Several of these use either the hnswlib library[10] provided by the original authors, or the FAISS library. References[edit] ^ Malkov, Yu A.; Yashunin, D. A. (2016). "Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs". arXiv:1603.09320 [cs.DS]. ^ a b Malkov, Yury A; Yashunin, Dmitry A (1 April 2020). "Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs". IEEE Transactions on Pattern Analysis and Machine Intelligence. 42 (4): 824–836. arXiv:1603.09320. doi:10.1109/TPAMI.2018.2889473. PMID 30602420. ^ Malkov, Yury; Ponomarenko, Alexander; Logvinov, Andrey; Krylov, Vladimir (2012). "Scalable Distributed Algorithm for Approximate Nearest Neighbor Search Problem in High Dimensional General Metric Spaces". In Navarro, Gonzalo; Pestov, Vladimir (eds.). Similarity Search and Applications. Lecture Notes in Computer Science. Vol. 7404. Berlin, Heidelberg: Springer. pp. 132–147. doi:10.1007/978-3-642-32153-5_10. ISBN 978-3-642-32153-5. ^ Aumüller, Martin; Bernhardsson, Erik; Faithfull, Alexander (2017). "ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms". In Beecks, Christian; Borutta, Felix; Kröger, Peer; Seidl, Thomas (eds.). Similarity Search and Applications. Lecture Notes in Computer Science. Vol. 10609. Cham: Springer International Publishing. pp. 34–49. arXiv:1807.05614. doi:10.1007/978-3-319-68474-1_3. ISBN 978-3-319-68474-1. ^ Aumüller, Martin; Bernhardsson, Erik; Faithfull, Alexander (2020). "ANN-Benchmarks: A benchmarking tool for approximate nearest neighbor algorithms". Information Systems. 87: 101374. arXiv:1807.05614. doi:10.1016/j.is.2019.02.006. ^ "ANN-Benchmarks". ann-benchmarks.com. Retrieved 2024-03-19. ^ "MariaDB Vector". MariaDB.org. Retrieved 2024-07-30. ^ "MongoDB Atlas Vector Search". mongodb.com. Retrieved 2024-09-17. ^ "How to Pick a Vector Index in Your Milvus Instance: A Visual Guide". zilliz.com. Retrieved 2024-10-10. ^ nmslib/hnswlib, nmslib, 2024-03-18, retrieved 2024-03-19 This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it. This computing article is a stub. You can help Wikipedia by expanding it. Categories: GraphsNetwork scienceSearch algorithmsDatabase index techniquesData miningMachine learningAlgorithms and data structures stubsComputing stubs This page was last edited on 1 December 2024, at 18:44 (UTC). Text is available under the Creative Commons Attribution-ShareAlike 4.0 License; additional terms may apply. By using this site, you agree to the Terms of Use and Privacy Policy. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a non-profit organization. Privacy policy About Wikipedia Disclaimers Contact Wikipedia Code of Conduct Developers Statistics Cookie statement Mobile view