Two-stage routing with optimized guided search and greedy algorithm on proximity graph

As interest surges in large-scale retrieval tasks, proximity graphs are now the leading paradigm. Most existing proximity graphs share the simple greedy algorithm as their routing strategy for approximate nearest neighbor search (ANNS), but this leads to two issues: low routing efficiency and local optimum; this because they ignore the special requirements of different routing stages. Generally, the routing can be divided into two stages: the stage far from the query (S1) and the stage closer to the query (S2). S1 aims to quickly route to the vicinity of the query, and the efficiency is dominant. While S2 focuses on finding the results accurately, so the accuracy is staple. We carefully design tailored routing algorithm for each stage, then combine them together to form a Two-stage routing with Optimized Guided search and Greedy algorithm (TOGG). For S1, we propose optimized guided search to quickly locate the query's neighborhood by the guidance of the query direction. While for S2, we propose optimized greedy algorithm to comprehensively visit the vertices near the query by agilely detecting explicit and implicit convergence paths. Finally, using theoretical and experimental analysis, we demonstrate the proposed method can achieve better performance of efficiency and effectiveness than state-of-the-art work. (C) 2021 Elsevier B.V. All rights reserved.