Multiattribute approximate nearest neighbor search based on navigable small world graph

摘要

Approximate nearest neighbor search (ANNS) is widely employed to find the most similar data efficiently from a large-scale dataset. The key of ANNS is to construct an effective index to prune the search space and retrieve the approximate data rather than the exact one in a very short time. Most of the existing ANNS methods only adopt the distance metric to build an index, which cannot support multiattribute ANNS. In this article, we present a novel approach for multiattribute ANNS based on navigable small world (NSW) graph, called MA-NSW. Given a dataset, MA-NSW (i) builds a proximity subgraph overlay for each multiattribute combination, and integrates all overlays to a hierarchical index, (ii) adopts a navigation tree to access related subgraph overlay and prune unrelated overlays, and (iii) gets nearest neighbor results from the related overlays by greedy search. MA-NSW guarantees efficiency and it is defined in terms of arbitrary metric spaces (eg, Euclidean distance and cosine similarity). Performance evaluation has demonstrated that the proposed approach shows superior performance in multiattribute ANNS.