{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:18:53Z","timestamp":1779175133317,"version":"3.51.4"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T00:00:00Z","timestamp":1686614400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,6,13]]},"abstract":"<jats:p>There is an increasing adoption of machine learning for encoding data into vectors to serve online recommendation and search use cases. As a result, recent data management systems propose augmenting query processing with online vector similarity search. In this work, we explore vector similarity search in the context of Knowledge Graphs (KGs). Motivated by the tasks of finding related KG queries and entities for past KG query workloads, we focus on hybrid vector similarity search (hybrid queries for short) where part of the query corresponds to vector similarity search and part of the query corresponds to predicates over relational attributes associated with the underlying data vectors. For example, given past KG queries for a song entity, we want to construct new queries for new song entities whose vector representations are close to the vector representation of the entity in the past KG query. But entities in a KG also have non-vector attributes such as a song associated with an artist, a genre, and a release date. Therefore, suggested entities must also satisfy query predicates over non-vector attributes beyond a vector-based similarity predicate. While these tasks are central to KGs, our contributions are generally applicable to hybrid queries. In contrast to prior works that optimize online queries, we focus on enabling efficient batch processing of past hybrid query workloads. We present our system, HQI, for high-throughput batch processing of hybrid queries. We introduce a workload-aware vector data partitioning scheme to tailor the vector index layout to the given workload and describe a multi-query optimization technique to reduce the overhead of vector similarity computations. We evaluate our methods on industrial workloads and demonstrate that HQI yields a 31\u00d7 improvement in throughput for finding related KG queries compared to existing hybrid query processing approaches.<\/jats:p>","DOI":"10.1145\/3589777","type":"journal-article","created":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:26:45Z","timestamp":1687292805000},"page":"1-25","source":"Crossref","is-referenced-by-count":41,"title":["High-Throughput Vector Similarity Search in Knowledge Graphs"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5497-0481","authenticated-orcid":false,"given":"Jason","family":"Mohoney","sequence":"first","affiliation":[{"name":"University of Wisconsin-Madison, Madison, WI, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4994-8014","authenticated-orcid":false,"given":"Anil","family":"Pacaci","sequence":"additional","affiliation":[{"name":"Apple, Seattle, WA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6232-2027","authenticated-orcid":false,"given":"Shihabur Rahman","family":"Chowdhury","sequence":"additional","affiliation":[{"name":"Apple, Seattle, WA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1160-5975","authenticated-orcid":false,"given":"Ali","family":"Mousavi","sequence":"additional","affiliation":[{"name":"Apple, Seattle, WA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9052-9714","authenticated-orcid":false,"given":"Ihab F.","family":"Ilyas","sequence":"additional","affiliation":[{"name":"Apple, Seattle, WA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-6520-3794","authenticated-orcid":false,"given":"Umar Farooq","family":"Minhas","sequence":"additional","affiliation":[{"name":"Apple, Seattle, WA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6281-6345","authenticated-orcid":false,"given":"Jeffrey","family":"Pound","sequence":"additional","affiliation":[{"name":"Apple, Seattle, WA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6148-1854","authenticated-orcid":false,"given":"Theodoros","family":"Rekatsinas","sequence":"additional","affiliation":[{"name":"Apple, Seattle, WA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,6,20]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"LLM Powered Search - Vectara. https:\/\/vectara.com Accessed on","year":"2023","unstructured":"2023. LLM Powered Search - Vectara. https:\/\/vectara.com Accessed on February 28, 2023."},{"key":"e_1_2_2_2_1","volume-title":"Vector Database for Vector Search | Pinecone. https:\/\/www.pinecone.io Accessed on","year":"2023","unstructured":"2023. Vector Database for Vector Search | Pinecone. https:\/\/www.pinecone.io Accessed on February 28, 2023."},{"key":"e_1_2_2_3_1","volume-title":"Vespa - the big data serving engine. https:\/\/vespa.ai Accessed on","year":"2023","unstructured":"2023. Vespa - the big data serving engine. https:\/\/vespa.ai Accessed on February 28, 2023."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/3358701.3358707"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2807452"},{"key":"e_1_2_2_6_1","first-page":"1","article-title":"Machine Learning on Graphs: A Model and Comprehensive Taxonomy","volume":"23","author":"Chami Ines","year":"2022","unstructured":"Ines Chami, Sami Abu-El-Haija, Bryan Perozzi, Christopher R\u00c3\u00a9, and Kevin Murphy. 2022. Machine Learning on Graphs: A Model and Comprehensive Taxonomy. Journal of Machine Learning Research 23, 89 (2022), 1--64. http:\/\/jmlr.org\/papers\/v23\/20--852.html","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457270"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/355744.355745"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-46466-4_15"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3219885"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939754"},{"key":"e_1_2_2_12_1","volume-title":"et al","author":"Guo Rentong","year":"2022","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_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330658"},{"key":"e_1_2_2_14_1","volume-title":"Inductive representation learning on large graphs. Advances in neural information processing systems 30","author":"Hamilton Will","year":"2017","unstructured":"Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. Advances in neural information processing systems 30 (2017)."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467188"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2806416.2806502"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389704"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3295748"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526049"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_2_21_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_2_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.2011.5946540"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","unstructured":"Jeff Johnson Matthijs Douze and Herv\u00e9 J\u00e9gou. 2017. Billion-scale similarity search with GPUs. https:\/\/doi.org\/10.48550\/ARXIV.1702.08734","DOI":"10.48550\/ARXIV.1702.08734"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476311.3476392"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3284028.3284030"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3041021.3054202"},{"key":"e_1_2_2_27_1","volume-title":"Monolith: Real Time Recommendation System With Collisionless Embedding Table. In 5th Workshop on Online Recommender Systems and User Modeling (ORSUM2022)","author":"Liu Zhuoran","year":"2022","unstructured":"Zhuoran Liu, Leqi Zou, Xuan Zou, Caihua Wang, Biao Zhang, Da Tang, Bolin Zhu, Yijie Zhu, Peng Wu, Ke Wang, and Youlong Cheng. 2022. Monolith: Real Time Recommendation System With Collisionless Embedding Table. In 5th Workshop on Online Recommender Systems and User Modeling (ORSUM2022), in conjunction with the 16th ACM Conference on Recommender Systems."},{"key":"e_1_2_2_28_1","volume-title":"Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs","author":"Malkov Yu A","year":"2018","unstructured":"Yu A Malkov and Dmitry A Yashunin. 2018. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence 42, 4 (2018), 824--836."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3439726"},{"key":"e_1_2_2_30_1","volume-title":"Marius: Learning massive graph embeddings on a single machine. In 15th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 21). 533--549.","author":"Mohoney Jason","year":"2021","unstructured":"Jason Mohoney, Roger Waleffe, Henry Xu, Theodoros Rekatsinas, and Shivaram Venkataraman. 2021. Marius: Learning massive graph embeddings on a single machine. In 15th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 21). 533--549."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098108"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939751"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403280"},{"key":"e_1_2_2_34_1","volume-title":"Locality sensitive hashing: A comparison of hash function types and querying mechanisms. Pattern recognition letters 31, 11","author":"Paulev\u00e9 Lo\u00efc","year":"2010","unstructured":"Lo\u00efc Paulev\u00e9, Herv\u00e9 J\u00e9gou, and Laurent Amsaleg. 2010. Locality sensitive hashing: A comparison of hash function types and querying mechanisms. Pattern recognition letters 31, 11 (2010), 1348--1358."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623732"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476311.3476371"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/582095.582099"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610515"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741093"},{"key":"e_1_2_2_40_1","volume-title":"MariusGNN: Resource- Efficient Out-of-Core Training of Graph Neural Networks. In ACM SIGOPS European Conference on Computer Systems (EuroSys).","author":"Waleffe Roger","year":"2023","unstructured":"Roger Waleffe, Jason Mohoney, Theodoros Rekatsinas, and Shivaram Venkataraman. 2023. MariusGNN: Resource- Efficient Out-of-Core Training of Graph Neural Networks. In ACM SIGOPS European Conference on Computer Systems (EuroSys)."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3219869"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457550"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2754499"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3415478.3415541"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3386131"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389770"},{"key":"e_1_2_2_47_1","first-page":"5165","article-title":"Link prediction based on graph neural networks","volume":"31","author":"Zhang Muhan","year":"2018","unstructured":"Muhan Zhang and Yixin Chen. 2018. Link prediction based on graph neural networks. Advances in Neural Information Processing Systems 31 (2018), 5165--5175.","journal-title":"Advances in Neural Information Processing Systems"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589777","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3589777","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:22Z","timestamp":1750182562000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589777"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,13]]},"references-count":47,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,13]]}},"alternative-id":["10.1145\/3589777"],"URL":"https:\/\/doi.org\/10.1145\/3589777","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,13]]}}}