ARKGraph: All-Range Approximate K-Nearest-Neighbor Graph
ARKGraph: All-Range Approximate K-Nearest-Neighbor Graph
复制标题
DOI：
10.14778/3603581.3603601
复制
发表时间：
2023-06
期刊：
影响因子：
--
通讯作者：
Chaoji Zuo;Dong Deng
中科院分区：
文献类型：
--
作者：
Chaoji Zuo;Dong Deng
给定一个向量集合，近似K-近邻图(简称KGRAP)将每个向量连接到其近似K-近邻(简称KNN)。KGraph在高维数据可视化、语义搜索、流形学习、机器学习等领域发挥着重要作用。向量通常是真实世界对象(例如，图像和文档)的向量表示，其通常带有一些结构化属性，例如时间夯实和位置。本文研究了全范围近似K近邻图(ARKGraph)问题。具体地说，给定一个向量集合，每个向量与一个数字搜索关键字(例如，时间戳)相关联，我们的目标是建立一个将搜索关键字范围作为查询并返回其搜索关键字在该查询范围内的向量的K图的索引。ARKGraph可以促进交互式高维数据可视化、数据挖掘等。这个问题的一个关键挑战是巨大的索引规模。这是因为，给定n个向量，暴力索引为每个搜索关键字范围存储一个K图，这导致O(K N 3)个索引大小，因为有O(N 2)个搜索关键字范围，并且每个K图占用O(K N)个空间。我们观察到，一个向量在附近范围内的kNN通常是相同的，可以将它们组合在一起以节省空间。基于这一观察结果，我们提出了一系列新的技术，在平均情况下将索引大小显著降低到仅为O(Knlogn)。此外，我们还提出了一种高效的索引算法，该算法不需要穷举地计算每对向量之间的距离，而直接构造优化的ARKGRAPH索引。为了处理一个查询，对于查询范围内的每个向量，我们只需要O(loglogn+KlogK)来从优化的ARKGraph索引中恢复它在查询范围内的kNN。我们在真实世界的数据集上进行了广泛的实验。实验结果表明，优化后的ARKGraph索引具有较小的索引大小、较低的查询延迟和良好的可扩展性。具体地说，我们的方法比为查询范围中的所有向量动态构建KGraph的基线方法快1000倍。
Given a collection of vectors, the approximate K-nearest-neighbor graph (KGraph for short) connects every vector to its approximate K-nearest-neighbors (KNN for short). KGraph plays an important role in high dimensional data visualization, semantic search, manifold learning, and machine learning. The vectors are typically vector representations of real-world objects (e.g., images and documents), which often come with a few structured attributes, such as times-tamps and locations. In this paper, we study the all-range approximate K-nearest-neighbor graph (ARKGraph) problem. Specifically, given a collection of vectors, each associated with a numerical search key (e.g., a timestamp), we aim to build an index that takes a search key range as the query and returns the KGraph of vectors whose search keys are within the query range. ARKGraph can facilitate interactive high dimensional data visualization, data mining, etc. A key challenge of this problem is the huge index size. This is because, given n vectors, a brute-force index stores a KGraph for every search key range, which results in O (K n 3 ) index size as there are O ( n 2 ) search key ranges and each KGraph takes O (K n ) space. We observe that the KNN of a vector in nearby ranges are often the same, which can be grouped together to save space. Based on this observation, we propose a series of novel techniques that reduce the index size significantly to just O (K n log n ) in the average case. Furthermore, we develop an efficient indexing algorithm that constructs the optimized ARKGraph index directly without exhaustively calculating the distance between every pair of vectors. To process a query, for each vector in the query range, we only need O (log log n + K log K) to restore its KNN in the query range from the optimized ARKGraph index. We conducted extensive experiments on real-world datasets. Experimental results show that our optimized ARKGraph index achieved a small index size, low query latency, and good scalability. Specifically, our approach was 1000x faster than the baseline method that builds a KGraph for all the vectors in the query range on-the-fly.