{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T22:38:41Z","timestamp":1778279921730,"version":"3.51.4"},"reference-count":79,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,9,22]]},"abstract":"<jats:p>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\u00d7 throughput on average in four nodes and 58% performance improvement over traditional distribution for skewed workloads.<\/jats:p>","DOI":"10.1145\/3749167","type":"journal-article","created":{"date-parts":[[2025,9,23]],"date-time":"2025-09-23T17:17:03Z","timestamp":1758647823000},"page":"1-28","source":"Crossref","is-referenced-by-count":4,"title":["HARMONY: A Scalable Distributed Vector Database for High-Throughput Approximate Nearest Neighbor Search"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-3276-3262","authenticated-orcid":false,"given":"Qian","family":"Xu","sequence":"first","affiliation":[{"name":"Renmin University of China, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1983-7321","authenticated-orcid":false,"given":"Feng","family":"Zhang","sequence":"additional","affiliation":[{"name":"Renmin University of China, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-8493-6238","authenticated-orcid":false,"given":"Chengxi","family":"Li","sequence":"additional","affiliation":[{"name":"Renmin University of China, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9909-8607","authenticated-orcid":false,"given":"Lei","family":"Cao","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, American Samoa"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-8342-9504","authenticated-orcid":false,"given":"Zheng","family":"Chen","sequence":"additional","affiliation":[{"name":"Renmin University of China, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7656-6428","authenticated-orcid":false,"given":"Jidong","family":"Zhai","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5757-9135","authenticated-orcid":false,"given":"Xiaoyong","family":"Du","sequence":"additional","affiliation":[{"name":"Renmin University of China, Beijing, China"}]}],"member":"320","published-online":{"date-parts":[[2025,9,23]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2017. JanusGraph. https:\/\/janusgraph.org\/. Accessed: 2025-01-08."},{"key":"e_1_2_1_2_1","unstructured":"2024. UCI Machine Learning Repository. https:\/\/archive.ics.uci.edu\/."},{"key":"e_1_2_1_3_1","unstructured":"2024. YouTube. https:\/\/www.youtube.com\/. https:\/\/www.youtube.com"},{"key":"e_1_2_1_4_1","unstructured":"2025. Apache Drill. https:\/\/drill.apache.org\/."},{"key":"e_1_2_1_5_1","unstructured":"2025. CockroachDB. https:\/\/www.cockroachlabs.com\/product\/cockroachdb\/."},{"key":"e_1_2_1_6_1","unstructured":"2025. Integrating Presto with Spark SQL. https:\/\/prestodb.io\/docs\/current\/connector\/spark.html."},{"key":"e_1_2_1_7_1","unstructured":"2025. Neo4j. https:\/\/neo4j.com\/."},{"key":"e_1_2_1_8_1","unstructured":"2025. Pinecone. http:\/\/pinecone.io. http:\/\/pinecone.io"},{"key":"e_1_2_1_9_1","unstructured":"2025. Presto: Distributed SQL Query Engine for Big Data. https:\/\/prestodb.io\/."},{"key":"e_1_2_1_10_1","unstructured":"2025. Qdrant. http:\/\/qdrant.tech. http:\/\/qdrant.tech"},{"key":"e_1_2_1_11_1","unstructured":"2025. TigerGraph. https:\/\/www.tigergraph.com\/."},{"key":"e_1_2_1_12_1","unstructured":"2025. Vald. http:\/\/vald.vdaas.org. http:\/\/vald.vdaas.org"},{"key":"e_1_2_1_13_1","unstructured":"2025. Vespa. https:\/\/vespa.ai\/. https:\/\/vespa.ai"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Artem Babenko Victor Lempitsky B.Hari Babu N.Subhash Chandra and T.V. Gopal. 2014. The inverted multi-index. IEEE transactions on pattern analysis and machine intelligence 37 6 (2014) 1247--1260.","DOI":"10.1109\/TPAMI.2014.2361319"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-01258-8_13"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_2_1_17_1","volume-title":"Spann: Highly-efficient billion-scale approximate nearest neighborhood search. In Advances in Neural Information Processing Systems","author":"Chen Qi","year":"2021","unstructured":"Qi Chen, Bing Zhao, Haidong Wang, Mingqin Li, Chuanjie Liu, Zengzhong Li, Mao Yang, and Jingdong Wang. 2021. Spann: Highly-efficient billion-scale approximate nearest neighborhood search. In Advances in Neural Information Processing Systems, M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J.Wortman Vaughan (Eds.). Vol. 34. Curran Associates, Inc, 5199--5212."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/177424.177609"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI). 251--264","author":"Corbett James C.","unstructured":"James C. Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes, Christopher Frost, J. J. Furman, Sanjay Ghemawat, Andrey Gubarev, Christian Heiser, Peter Hochschild, and et al. 2012. Spanner: Google's Globally-Distributed Database. In Proceedings of the 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI). 251--264."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the Twentieth Annual Symposium on Computational Geometry, SCG '04","author":"Datar Mayur","unstructured":"Mayur Datar, Nicole Immorlica, Piotr Indyk, and Va-hab S. Mirrokni. 2004. Locality-sensitive hashing scheme based on p-stable distributions. In Proceedings of the Twentieth Annual Symposium on Computational Geometry, SCG '04. 253--262,."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2408776.2408794"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_2_1_23_1","first-page":"793","article-title":"Sur la sph\u00e8re vide","volume":"6","author":"Delaunay B.N.","year":"1934","unstructured":"B.N. Delaunay. 1934. Sur la sph\u00e8re vide. Bull. Acad. Sci. URSS 6 (1934), 793--800.","journal-title":"Bull. Acad. Sci. URSS"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963487"},{"key":"e_1_2_1_25_1","unstructured":"Facebook. 2020. Faiss. https:\/\/github.com\/facebookresearch\/faiss. Accessed: 2024--10--15."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3303753.3303754"},{"key":"e_1_2_1_27_1","volume-title":"Sokal","author":"Ruben Gabriel K.","year":"1969","unstructured":"K.Ruben Gabriel and Robert R. Sokal. 1969. A new statistical approach to geographic variation analysis. Systematic zoology 18, 3 (1969), 259--278."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3725413"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589282"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654970"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1037\/1076-898X.6.4.322"},{"key":"e_1_2_1_32_1","unstructured":"Rentong Guo Xiaofan Luan Long Xiang Xiao Yan Xiaomeng Yi Jigao Luo Qianya Cheng Weizhi Xu Jiarui Luo Frank Liu et al. 2022. Manu: a cloud native vector database management system. arXiv preprint arXiv:2206.13843 (2022)."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5591\/978--1--57735--516--8\/IJCAI11--222"},{"key":"e_1_2_1_34_1","volume-title":"2008 IEEE Conference on Computer Vision and Pattern Recognition. 1--8,.","author":"Jain P.","unstructured":"P. Jain, B. Kulis, and K. Grauman. 2008-06. Fast image search for learned metrics. In 2008 IEEE Conference on Computer Vision and Pattern Recognition. 1--8,."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2534169.2486028"},{"key":"e_1_2_1_36_1","volume-title":"Ravishankar Krishnawamy, and Rohan Kadekodi.","author":"Subramanya Suhas Jayaram","year":"2019","unstructured":"Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. 2019. DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. In Advances in Neural Information Processing Systems, H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alch\u00e9-Buc, E. Fox, and R. Garnett (Eds.), Vol. 32. Curran Associates, Inc. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2019\/file\/09853c7fb1d3f8ee67a61b6bf4a7f8e6- Paper.pdf"},{"key":"e_1_2_1_37_1","volume-title":"Product quantization for nearest neighbor search","author":"Jegou Herve","year":"2010","unstructured":"Herve Jegou, Matthijs Douze, and Cordelia Schmid. 2010. Product quantization for nearest neighbor search. IEEE transactions on pattern analysis and machine intelligence 33, 1 (2010), 117--128."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.2011.5946540"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2014.298"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2396831"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3725333"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2009.5459466"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064009"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3284028.328403"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.26599\/TST.2024.9010016"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467101"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380151"},{"key":"e_1_2_1_48_1","volume-title":"NIPS","author":"Liu Ting","year":"2004","unstructured":"Ting Liu, Andrew W. Moore, Alexander Gray, and Ke Yang. December 13--18, 2004. An investigation of practical approximate nearest neighbor algorithms. In Advances in Neural Information Processing Systems 17 [Neural Information Processing Systems, NIPS 2004. Vancouver, British Columbia, Canada, 825--832,."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11704-025--50058-z"},{"key":"e_1_2_1_50_1","unstructured":"Fangzhou Alec Lu. 2024. Towards software-defined FPGA acceleration for big data analytics. (2024)."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI"},{"key":"e_1_2_1_52_1","unstructured":"Tomas Mikolov Kai Chen Greg Corrado and Jeffrey Dean. 2013. Efficient Estimation of Word Representations in Vector Space. arXiv:1301.3781 [cs.CL."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2014.2321376"},{"key":"e_1_2_1_54_1","volume-title":"10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13","author":"Nishtala Rajesh","year":"2013","unstructured":"Rajesh Nishtala, Hans Fugal, Steven Grimm, Marc Kwiatkowski, Herman Lee, Harry C. Li, Ryan McElroy, Mike Paleczny, Daniel Peek, and Paul Saab. 2013. Scaling memcache at facebook. In 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13. 385--398,."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3572848"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.3115\/v1\/D14--1162"},{"key":"e_1_2_1_57_1","volume-title":"Proceedings ofthe 34th International Conference on Neural Information Processing Systems 895","author":"Ren Jie","year":"2020","unstructured":"Jie Ren, Minjia Zhang, and Dong Li. 2020. HM-ANN: Efficient BillionPoint Nearest Neighbor Search on Heterogeneous Memory. Proceedings ofthe 34th International Conference on Neural Information Processing Systems 895 (2020), 20."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536222.2536232"},{"key":"e_1_2_1_59_1","volume-title":"The relative neighbourhood graph of a finite planar set. Pattern recognition 12, 4","author":"Toussaint Godfried T.","year":"1980","unstructured":"Godfried T. Toussaint. 1980. The relative neighbourhood graph of a finite planar set. Pattern recognition 12, 4 (1980), 261--268."},{"key":"e_1_2_1_60_1","volume-title":"Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on. IEEE, IEEE Computer Society, USA.","author":"Zeng Gang","year":"2012","unstructured":"JingWang, JingdongWang, Gang Zeng, Zhuowen Tu, Rui Gan, and Shipeng Li. 2012. Scalable k-nn graph construction for visual descriptors. In Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on. IEEE, IEEE Computer Society, USA."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2013.125"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457550"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2017.2699960"},{"key":"e_1_2_1_64_1","unstructured":"Yair Weiss Antonio Torralba and Rob Fergus. 2009. Spectral hashing. In Advances in neural information processing systems. 1753--1760 ."},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.26599\/TST.2024.9010160"},{"key":"e_1_2_1_66_1","volume-title":"Hadoop: The Definitive Guide","author":"White Tom","year":"2012","unstructured":"Tom White. 2012. Hadoop: The Definitive Guide (3rd ed.). O'Reilly Media, Inc.","edition":"3"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.26599\/TST"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/3485447.3511957"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.14778\/3665844.3665852"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/3709743"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/3600006.3613166"},{"key":"e_1_2_1_72_1","volume-title":"Proceedings of the 2nd USENIX conference on Hot topics in cloud computing (HotCloud)","volume":"10","author":"Zaharia Matei","year":"2010","unstructured":"Matei Zaharia, Mosharaf Chowdhury, Michael J Franklin, Scott Shenker, and Ion Stoica. 2010. Spark: Cluster computing with working sets. In Proceedings of the 2nd USENIX conference on Hot topics in cloud computing (HotCloud), Vol. 10. 10--10."},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/3613424.3614292"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2021.3093234"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00636-3"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCC.2025.3559346"},{"key":"e_1_2_1_77_1","volume-title":"17th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2023","author":"Zhang Qianxi","year":"2023","unstructured":"Qianxi Zhang, Shuotao Xu, Qi Chen, Guoxin Sui, Jiadong Xie, Zhizhen Cai, Yaoqi Chen, Yinxuan He, Yuqing Yang, Fan Yang, Mao Yang, and Lidong Zhou. 2023. VBASE: Unifying Online Vector Similarity Search and Relational Queries via Relaxed Monotonicity. In 17th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2023, Boston, MA, USA, July 10--12, 2023, Roxana Geambasu and Ed Nightingale (Eds.). USENIX Association, 377--395. https:\/\/www.usenix.org\/conference\/osdi23\/presentation\/zhang-qianxi"},{"key":"e_1_2_1_78_1","volume-title":"Proceedings ofthe 31th International Conference on Machine Learning (ICML","volume":"32","author":"Zhang Ting","year":"2014","unstructured":"Ting Zhang, Chao Du, and Jingdong Wang. 2014. Composite quantization for approximate nearest neighbor search. In Proceedings ofthe 31th International Conference on Machine Learning (ICML, Vol. 32. 838--846,."},{"key":"e_1_2_1_79_1","volume-title":"Approximate Vector Queries on Very Large Unstructured Datasets. In 20th USENIX Symposium on Networked Systems Design and Implementation (NSDI 23)","author":"Zhang Zili","year":"2023","unstructured":"Zili Zhang, Chao Jin, Linpeng Tang, Xuanzhe Liu, and Xin Jin. 2023. Fast, Approximate Vector Queries on Very Large Unstructured Datasets. In 20th USENIX Symposium on Networked Systems Design and Implementation (NSDI 23). USENIX Association, Boston, MA, 995--1011. https:\/\/www.usenix.org\/conference\/nsdi23\/presentation\/zhang-zili"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3749167","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,26]],"date-time":"2025-09-26T16:23:31Z","timestamp":1758903811000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3749167"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,22]]},"references-count":79,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,9,22]]}},"alternative-id":["10.1145\/3749167"],"URL":"https:\/\/doi.org\/10.1145\/3749167","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,22]]}}}