LAUSR

Approximate Nearest Neighbor Search in high dimensional space is essential in DB and IR. Recently, NSG provides attractive theoretical analysis and achieves state-of-the-art performance. However, we find there are several limitations with NSG. In the theoretical aspect, NSG has no theoretical guarantee on searching for neighbors of not-in-database queries. In application, NSG is too sparse and thus has an inferior search performance. In addition, NSG's indexing complexity is also too high. To address above problems, we propose the Satellite System Graphs (inspired by the message transfer mechanism of the communication satellite system) and its approximation NSSG. Specifically, Satellite System Graphs define a new family of MSNETs in which the out-edges of each node are distributed evenly in all directions, and each node builds effective connections to its neighborhood omnidirectionally, whereupon we derive SSG's excellent theoretical properties for both in-database queries and not-in-database queries. We can adaptively adjust the sparsity of an SSG with a hyper-parameter to optimize the search performance. Further, NSSG is proposed to reduce the indexing complexity of the SSG for large-scale applications. Both theoretical and extensive experimental analysis are provided to demonstrate the strengths of the proposed approach over the state-of-the-art algorithms.