Approximate nearest neighbor search (ANNS) in high-dimensional spaces is a pivotal challenge in the field of machine learning. In recent years graph-based methods have emerged as the superior approach to ANNS, establishing a new state of the art. Although various optimizations for graph-based ANNS have been introduced, they predominantly rely on heuristic methods that lack formal theoretical backing. This paper aims to enhance routing within graph-based ANNS by introducing a method that offers a probabilistic guarantee when exploring a node’s neighbors in the graph. We formulate the problem as probabilistic routing and develop two baseline strategies by incorporating locality-sensitive techniques. Subsequently, we introduce PEOs, a novel approach that efficiently identifies which neighbors in the graph should be considered for exact distance computation, thus significantly improving efficiency in practice. Our experiments demonstrate that equipping PEOs can increase throughput on a commonly utilized graph index (HNSW) by a factor of 1.6 to 2.5, and its efficiency consistently outperforms the leading-edge routing technique by 1.1 to 1.4 times. The code and datasets used for our evaluations are publicly accessible at https//github.com/ICML2024-code/PEOs .

Point-to-hyperplane nearest neighbor search (P2HNNS) is a fundamental problem which has many applications in data mining and machine learning. In this paper, we propose a provable Locality-Sensitive-Hashing (LSH) scheme based on multi-level quantization errors to solve this problem. In the indexing phase, for each data point, we compute the hash values of its residual vectors generated by a stepwise quantization process. In the query phase, for each processed point, we first determine its suitable level for hashing and then determine the size of hash bucket based on its quantization error in that level. We theoretically show that this treatment not only yields a probability guarantee on query results, but also makes the generated hash functions much more efficient to prune those false points. Experimental results on five real datasets show that the proposed approach generally runs 2X-10X faster than the state-of-the-art LSH-based approaches.

Approximate nearest neighbor search (ANNS) is a fundamental problem that has a wide range of applications in information retrieval and data mining. Among state-of-the-art in-memory ANNS methods, graph-based methods have attracted particular interest owing to their superior efficiency and query accuracy. Most of these methods focus on the selection of edges to shorten the search path, but do not pay much attention to the computational cost at each hop. To reduce the cost, we propose a novel graph structure called HVS. HVS has a hierarchical structure of multiple layers that corresponds to a series of subspace divisions in a coarse-to-fine manner. In addition, we utilize a virtual Voronoi diagram in each layer to accelerate the search. By traversing Voronoi cells, HVS can reach the nearest neighbors of a given query efficiently, resulting in a reduction in the total search cost. Experiments confirm that HVS is superior to other state-of-the-art graph-based methods.

Locality sensitive hashing (LSH) is a widely practiced c-approximate nearest neighbor (c-ANN) search algorithm because of its appealing theoretical guarantee and empirical performance. However, available LSH-based solutions do not achieve a good balance between cost and quality because of certain limitations in their index structures. In this paper, we propose a novel and easy-to-implement disk- based method named R2LSH to answer ANN queries in high-dimensional spaces. In the indexing phase, R2LSH maps data objects into multiple two-dimensional projected spaces. In each space, a group of B+-trees is constructed to characterize the corresponding data distribution. In the query phase, by setting a query-centric ball in each projected space and using a dynamic counting technique, R2LSH efficiently determines candidates and returns query results with the required quality. Rigorous theoretical analysis reveals that the proposed algorithm supports c-ANN search for arbitrarily small c ≥ 1 with probability guarantee. Extensive experiments on real datasets verify the superiority of R2LSH over state-of-the-art methods.

Locality sensitive hashing (LSH) is a widely practiced c -approximate nearest neighbor( c -ANN) search algorithm in high dimensional spaces. The state-of-the-art LSH based algorithm searches an unbounded and irregular space to identify candidates, which jeopardizes the efficiency. To address this issue, we introduce the concept of virtual hypersphere partitioning. The core idea is to impose a virtual hypersphere, centered at the query, in the original feature space and only examine points inside the hypersphere. The search space of a hypersphere is isotropic and bounded, and thus more efficient than the existing one. In practice, we use multiple physical hyperspheres with different radii in corresponding projection subspaces to emulate the single virtual hypersphere. We also developed a principled method to compute the hypersphere radii for given success probability. Based on virtual hypersphere partitioning, we propose a novel disk-based indexing and searching scheme VHP to answer c -ANN queries. In the indexing phase, VHP stores LSH projections with independent B + -trees. To process a query, VHP keeps increasing the radii of physical hyperspheres co-ordinately, which in effect amounts to enlarging the virtual hypersphere, to accommodate more candidates until the success probability is met. Rigorous theoretical analysis shows that the proposed algorithm supports c -ANN search for arbitrarily small c ≥ 1 with probability guarantee. Extensive experiments on a variety of datasets, including the billion-scale ones, demonstrate that VHP could achieve different tradeoffs between efficiency and accuracy, and achieves up to 2x speedup in running time over the state-of-the-art methods.