High Dimensional Similarity Search With Satellite System Graph: Efficiency, Scalability, And Unindexed Query Compatibility

Abstract

Approximate Nearest Neighbor Search (ANNS) in high dimensional space is essential in database and information retrieval. Recently, there has been a surge of interest in exploring efficient graph-based indices for the ANNS problem. Among them, Navigating Spreading-out Graph (NSG) provides fine theoretical analysis and achieves state-of-the-art performance. However, we find there are several limitations with NSG: 1) NSG has no theoretical guarantee on nearest neighbor search when the query is not indexed in the database; 2) NSG is too sparse which harms the search performance. In addition, NSG suffers from high indexing complexity. To address the above problems, we propose the Satellite System Graphs (SSG) and a practical variant NSSG. Specifically, we propose a novel pruning strategy to produce SSGs from the complete graph. SSGs define a new family of MSNETs in which the out-edges of each node are distributed evenly in all directions. Each node in the graph builds effective connections

Stats

• citations55
• S2 citations—
• github stars123
• HF likes0
• heat score17.30
• arxiv keyfu2019high

Related papers

• Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph (2017)18.20
• Sparse Neighborhood Graph-based Approximate Nearest Neighbor Search Revisited: Theoretical Analysis And Optimization (2025)0.00
• A Comprehensive Survey And Experimental Comparison Of Graph-based Approximate Nearest Neighbor Search (2021)17.35
• Scalable Overload-aware Graph-based Index Construction For 10-billion-scale Vector Similarity Search (2025)4.52
• Frequency-aware Graph Construction And Search For Dynamic Vector Databases (2025)0.00
• Fast-convergent Proximity Graphs For Approximate Nearest Neighbor Search (2025)0.00
• Efficient And Effective Retrieval Of Dense-sparse Hybrid Vectors Using Graph-based Approximate Nearest Neighbor Search (2024)0.00
• Subspace Collision: An Efficient And Accurate Framework For High-dimensional Approximate Nearest Neighbor Search (2024)7.16