Title: HARMONY: A Scalable Distributed Vector Database for High-Throughput Approximate Nearest Neighbor Search Show Chinese title

Title: HARMONY：一种可扩展的分布式向量数据库，用于高吞吐量近似最近邻搜索

Abstract: Approximate Nearest Neighbor Search (ANNS) is essential for various data-intensive applications, including recommendation systems, image retrieval, and machine learning. Scaling ANNS to handle billions of high-dimensional vectors on a single machine presents significant challenges in memory capacity and processing efficiency. To address these challenges, distributed vector databases leverage multiple nodes for the parallel storage and processing of vectors. However, existing solutions often suffer from load imbalance and high communication overhead, primarily due to traditional partition strategies that fail to effectively distribute the workload. In this paper, we introduce Harmony, a distributed ANNS system that employs a novel multi-granularity partition strategy, combining dimension-based and vector-based partition. This strategy ensures a balanced distribution of computational load across all nodes while effectively minimizing communication costs. Furthermore, Harmony incorporates an early-stop pruning mechanism that leverages the monotonicity of distance computations in dimension-based partition, resulting in significant reductions in both computational and communication overhead. We conducted extensive experiments on diverse real-world datasets, demonstrating that Harmony outperforms leading distributed vector databases, achieving 4.63 times throughput on average in four nodes and 58% performance improvement over traditional distribution for skewed workloads. Show Chinese abstract

Abstract: 近似最近邻搜索（ANNS）对于推荐系统、图像检索和机器学习等各种数据密集型应用至关重要。在单台机器上扩展ANNS以处理数十亿个高维向量，在内存容量和处理效率方面带来了重大挑战。 为了解决这些挑战，分布式向量数据库利用多个节点进行向量的并行存储和处理。然而，现有的解决方案通常会遇到负载不平衡和高通信开销的问题，这主要是由于传统的分区策略无法有效分配工作负载。 本文介绍了一种名为Harmony的分布式ANNS系统，该系统采用了一种新颖的多粒度分区策略，结合了基于维度和基于向量的分区方法。此策略确保了所有节点之间的计算负载均衡，并有效减少了通信成本。 此外，Harmony还引入了一种早期停止剪枝机制，利用基于维度分区的距离计算单调性，显著降低了计算和通信开销。我们在各种真实世界的数据集上进行了广泛的实验，结果表明Harmony优于领先的分布式向量数据库，在四节点情况下平均吞吐量提高了4.63倍，并且在偏斜工作负载下比传统分布方式性能提升了58%。