iQAN: Fast and Accurate Vector Search with Efficient Intra-Query Parallelism on Multi-Core Architectures
iQAN: Fast and Accurate Vector Search with Efficient Intra-Query Parallelism on Multi-Core Architectures
复制标题
DOI：
10.1145/3572848.3577527
复制
发表时间：
2023-02
期刊：
影响因子：
--
通讯作者：
Zhen Peng;Minjia Zhang;K. Li;R. Jin;Bin Ren
中科院分区：
文献类型：
--
作者：
Zhen Peng;Minjia Zhang;K. Li;R. Jin;Bin Ren
矢量搜索由于其在新的人工智能应用中的应用，在研究界引起了迅速增长的兴趣。最大化其性能对于许多任务至关重要，但仍然是初步理解。在这项工作中，我们调查的可扩展性瓶颈的根本原因，使用查询内并行加速的最先进的基于图形的向量搜索系统的多核架构。我们的深入分析揭示了几个可扩展性的挑战，从系统和算法的角度。基于这些见解，我们提出了iQAN，这是一种并行搜索算法，具有一组优化，可以提高收敛性，避免冗余计算，并减轻同步开销。我们对各种真实数据集的评估结果表明，iQAN在从100万到1亿个数据集的数据集上实现了比最先进的顺序基线低37.7倍和76.6倍的延迟。我们还表明，随着图形大小或准确性目标的增加，iQAN实现了出色的可扩展性，使其在20亿规模的数据集上的性能优于最先进的基线，最高可达16.0倍，最多可达64个核心。
Vector search has drawn a rapid increase of interest in the research community due to its application in novel AI applications. Maximizing its performance is essential for many tasks but remains preliminary understood. In this work, we investigate the root causes of the scalability bottleneck of using intra-query parallelism to speedup the state-of-the-art graph-based vector search systems on multi-core architectures. Our in-depth analysis reveals several scalability challenges from both system and algorithm perspectives. Based on the insights, we propose iQAN, a parallel search algorithm with a set of optimizations that boost convergence, avoid redundant computations, and mitigate synchronization overhead. Our evaluation results on a wide range of real-world datasets show that iQAN achieves up to 37.7× and 76.6× lower latency than state-of-the-art sequential baselines on datasets ranging from a million to a hundred million datasets. We also show that iQAN achieves outstanding scalability as the graph size or the accuracy target increases, allowing it to outperform the state-of-the-art baseline on two billion-scale datasets by up to 16.0× with up to 64 cores.