HVS: Hierarchical Graph Structure Based on Voronoi Diagrams for Solving Approximate Nearest Neighbor Search
HVS: Hierarchical Graph Structure Based on Voronoi Diagrams for Solving Approximate Nearest Neighbor Search
复制标题
DOI：
10.14778/3489496.3489506
复制
发表时间：
2021-10
期刊：
影响因子：
--
通讯作者：
Kejing Lu;Mineichi Kudo;Chuan Xiao;Y. Ishikawa
中科院分区：
文献类型：
--
作者：
Kejing Lu;Mineichi Kudo;Chuan Xiao;Y. Ishikawa
近似最近邻搜索（ANNS）是信息检索和数据挖掘中广泛应用的一个基本问题。在最先进的内存ANNS方法中，基于图的方法由于其优越的效率和查询精度而引起了人们的特别关注。这些方法大多侧重于边的选择以缩短搜索路径，而不太关注每跳的计算代价。为了降低成本，我们提出了一种新的图结构HVS。HVS具有多层的层次结构，对应于一系列从粗到细的子空间划分。此外，我们在每层中使用虚拟Voronoi图来加速搜索。通过遍历Voronoi单元，HVS可以有效地到达给定查询的最近邻居，从而降低总搜索成本。实验证实，HVS优于其他最先进的基于图形的方法。
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.