{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T04:22:55Z","timestamp":1785558175693,"version":"3.56.0"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2024,12,18]],"date-time":"2024-12-18T00:00:00Z","timestamp":1734480000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Key Projects of the National Natural Science Foundation of China","award":["U23A20496"],"award-info":[{"award-number":["U23A20496"]}]},{"name":"Shanghai Science and Technology Innovation Action Plan","award":["21511100401"],"award-info":[{"award-number":["21511100401"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,12,18]]},"abstract":"<jats:p>\n                    Given a query vector, approximate nearest neighbor search (ANNS) aims to retrieve similar vectors from a set of high-dimensional base vectors. However, many real-world applications jointly query both vector data and structured data, imposing label constraints such as attributes and keywords on the search, known as filtered ANNS. Effectively incorporating filtering conditions with vector similarity presents significant challenges, including index for dynamically filtered search space, agnostic query labels, computational overhead for label-irrelevant vectors, and potential inadequacy in returning results. To tackle these challenges, we introduce a novel approach called the\n                    <jats:italic toggle=\"yes\">Label Navigating Graph,<\/jats:italic>\n                    which encodes the containment relationships of label sets for all vectors. Built upon graph-based ANNS methods, we develop a general framework termed\n                    <jats:italic toggle=\"yes\">Unified Navigating Graph (UNG)<\/jats:italic>\n                    to bridge the gap between label set containment and vector proximity relations. UNG offers several advantages, including\n                    <jats:italic toggle=\"yes\">versatility<\/jats:italic>\n                    in supporting any query label size and specificity,\n                    <jats:italic toggle=\"yes\">fidelity<\/jats:italic>\n                    in exclusively searching filtered vectors,\n                    <jats:italic toggle=\"yes\">completeness<\/jats:italic>\n                    in providing sufficient answers, and\n                    <jats:italic toggle=\"yes\">adaptability<\/jats:italic>\n                    in integration with most graph-based ANNS algorithms. Extensive experiments on real datasets demonstrate that the proposed framework outperforms all baselines, achieving 10x speedups at the same accuracy.\n                  <\/jats:p>","DOI":"10.1145\/3698822","type":"journal-article","created":{"date-parts":[[2024,12,20]],"date-time":"2024-12-20T16:40:35Z","timestamp":1734712835000},"page":"1-27","source":"Crossref","is-referenced-by-count":26,"title":["Navigating Labels and Vectors: A Unified Approach to Filtered Approximate Nearest Neighbor Search"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-7096-5328","authenticated-orcid":false,"given":"Yuzheng","family":"Cai","sequence":"first","affiliation":[{"name":"Fudan University, Shanghai, CN"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-6459-4180","authenticated-orcid":false,"given":"Jiayang","family":"Shi","sequence":"additional","affiliation":[{"name":"Fudan University, Shanghai, CN"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-4931-1259","authenticated-orcid":false,"given":"Yizhuo","family":"Chen","sequence":"additional","affiliation":[{"name":"Fudan University, Shanghai, CN"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1200-7368","authenticated-orcid":false,"given":"Weiguo","family":"Zheng","sequence":"additional","affiliation":[{"name":"Fudan University, Shanghai, CN"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,12,20]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/focs.2006.49"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2019.02.006"},{"key":"e_1_2_1_3_1","volume-title":"The inverted multi-index","author":"Babenko Artem","year":"2014","unstructured":"Artem Babenko and Victor Lempitsky. 2014. The inverted multi-index. IEEE transactions on pattern analysis and machine intelligence, Vol. 37, 6 (2014), 1247--1260."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390156.1390171"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR52729.2023.00276"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963487"},{"key":"e_1_2_1_7_1","unstructured":"Matthijs Douze Alexandr Guzhva Chengqi Deng Jeff Johnson Gergely Szilvasy Pierre-Emmanuel Mazar\u00e9 Maria Lomeli Lucas Hosseini and Herv\u00e9 J\u00e9gou. 2024. The Faiss library. (2024). arxiv: 2401.08281 [cs.LG]"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476311.3476407"},{"key":"e_1_2_1_9_1","unstructured":"Efarrall. 2024. Word Embeddings. https:\/\/huggingface.co\/datasets\/efarrall\/word_embeddings."},{"key":"e_1_2_1_10_1","volume-title":"Fast approximate nearest neighbor search with the navigating spreading-out graph. arXiv preprint arXiv:1707.00143","author":"Fu Cong","year":"2017","unstructured":"Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2017. Fast approximate nearest neighbor search with the navigating spreading-out graph. arXiv preprint arXiv:1707.00143 (2017)."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213898"},{"key":"e_1_2_1_12_1","volume-title":"Retrieval-augmented generation for large language models: A survey. arXiv preprint arXiv:2312.10997","author":"Gao Yunfan","year":"2023","unstructured":"Yunfan Gao, Yun Xiong, Xinyu Gao, Kangxiang Jia, Jinliu Pan, Yuxi Bi, Yi Dai, Jiawei Sun, and Haofen Wang. 2023. Retrieval-augmented generation for large language models: A survey. arXiv preprint arXiv:2312.10997 (2023)."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/tpami.2013.240"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3543507.3583552"},{"key":"e_1_2_1_15_1","volume-title":"CAPS: A Practical Partition Index for Filtered Similarity Search. arXiv preprint arXiv:2308.15014","author":"Gupta Gaurav","year":"2023","unstructured":"Gaurav Gupta, Jonah Yi, Benjamin Coleman, Chen Luo, Vihan Lakshman, and Anshumali Shrivastava. 2023. CAPS: A Practical Partition Index for Filtered Similarity Search. arXiv preprint arXiv:2308.15014 (2023)."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505665"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850469.2850470"},{"key":"e_1_2_1_19_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, Vol. 33, 1 (2010), 117--128."},{"key":"e_1_2_1_20_1","unstructured":"Vihan Lakshman ChoonHui Teo Xiaowen Chu Priyanka Nigam Abhinandan Patni Pooja Maknikar and SVN Vishwanathan. [n. d.]. Embracing Structure in Data for Billion-Scale Semantic Product Search. ( [n. d.])."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3284028.3284030"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467101"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2909204"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467149"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2013.10.006"},{"key":"e_1_2_1_26_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, Vol. 42, 4 (2018), 824--836."},{"key":"e_1_2_1_27_1","unstructured":"Malteos. 2022. Aspect Paper Embeddings. https:\/\/huggingface.co\/datasets\/malteos\/aspect-paper-embeddings."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2019.106970"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330759"},{"key":"e_1_2_1_30_1","unstructured":"OpenAI. 2024. New embedding models and API updates. https:\/\/openai.com\/blog\/new-embedding-models-and-api-updates."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3529372.3530912"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","unstructured":"Rodrigo Paredes and Edgar Ch\u00e1vez. 2005. Using the k-Nearest Neighbor Graph for Proximity Searching in Metric Spaces. 127--138. https:\/\/doi.org\/10.1007\/11575832_14","DOI":"10.1007\/11575832_14"},{"key":"e_1_2_1_33_1","unstructured":"Liana Patel. 2024. ACORN. https:\/\/github.com\/stanford-futuredata\/ACORN."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654923"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588908"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816815"},{"key":"e_1_2_1_37_1","unstructured":"Pinecone. 2019. The vector database to build knowledgeable AI. https:\/\/www.pinecone.io\/."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3404835.3463242"},{"key":"e_1_2_1_39_1","volume-title":"LAION-400M: Open Dataset of Clip-filtered 400 Million Image-text Pairs. arXiv preprint arXiv:2111.02114","author":"Schuhmann Christoph","year":"2021","unstructured":"Christoph Schuhmann, Richard Vencu, Romain Beaumont, Robert Kaczmarczyk, Clayton Mullis, Aarush Katta, Theo Coombes, Jenia Jitsev, and Aran Komatsuzaki. 2021. LAION-400M: Open Dataset of Clip-filtered 400 Million Image-text Pairs. arXiv preprint arXiv:2111.02114 (2021)."},{"key":"e_1_2_1_40_1","volume-title":"Scryfall Magic: The Gathering Card Search. https:\/\/scryfall.com\/.","year":"2024","unstructured":"Scryfall. 2024. Scryfall Magic: The Gathering Card Search. https:\/\/scryfall.com\/."},{"key":"e_1_2_1_41_1","volume-title":"DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. Neural Information Processing Systems,Neural Information Processing Systems (Nov","author":"Subramanya SuhasJayaram","year":"2019","unstructured":"SuhasJayaram Subramanya, Fnu Devvrit, HarshaVardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. 2019. DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. Neural Information Processing Systems,Neural Information Processing Systems (Nov 2019)."},{"key":"e_1_2_1_42_1","unstructured":"TrevorJS. 2024. Mtg Scryfall Cropped Art Embeddings. https:\/\/huggingface.co\/datasets\/TrevorJS\/mtg-scryfall-cropped-art-embeddings-open-clip-ViT-SO400M-14-SigLIP-384."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457550"},{"key":"e_1_2_1_44_1","volume-title":"Advances in Neural Information Processing Systems","volume":"36","author":"Wang Mengzhao","year":"2024","unstructured":"Mengzhao Wang, Lingwei Lv, Xiaoliang Xu, Yuxiang Wang, Qiang Yue, and Jiongkang Ni. 2024. An efficient and robust framework for approximate nearest neighbor search with attribute constraint. Advances in Neural Information Processing Systems, Vol. 36 (2024)."},{"key":"e_1_2_1_45_1","volume-title":"A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search. arXiv preprint arXiv:2101.12631","author":"Wang Mengzhao","year":"2021","unstructured":"Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. 2021. A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search. arXiv preprint arXiv:2101.12631 (2021)."},{"key":"e_1_2_1_46_1","volume-title":"Steiner-Hardness: A Query Hardness Measure for Graph-Based ANN Indexes. arXiv preprint arXiv:2408.13899","author":"Wang Zeyu","year":"2024","unstructured":"Zeyu Wang, Qitong Wang, Xiaoxing Cheng, Peng Wang, Themis Palpanas, and Wei Wang. 2024. Steiner-Hardness: A Query Hardness Measure for Graph-Based ANN Indexes. arXiv preprint arXiv:2408.13899 (2024)."},{"key":"e_1_2_1_47_1","unstructured":"Weaviate. 2022. Weaviate -- Vector Database. https:\/\/weaviate.io\/."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/3415478.3415541"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3511808.3557610"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.5970"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3386131"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.5555\/313559.313789"},{"key":"e_1_2_1_53_1","volume-title":"Retrieval-Augmented Generation for AI-Generated Content: A Survey. arXiv preprint arXiv:2402.19473","author":"Zhao Penghao","year":"2024","unstructured":"Penghao Zhao, Hailin Zhang, Qinhan Yu, Zhengren Wang, Yunteng Geng, Fangcheng Fu, Ling Yang, Wentao Zhang, and Bin Cui. 2024. Retrieval-Augmented Generation for AI-Generated Content: A Survey. arXiv preprint arXiv:2402.19473 (2024)."},{"key":"e_1_2_1_54_1","volume-title":"Constrained Approximate Similarity Search on Proximity Graph. (Oct","author":"Zhao Weijie","year":"2022","unstructured":"Weijie Zhao, Shulong Tan, and Ping Li. 2022. Constrained Approximate Similarity Search on Proximity Graph. (Oct 2022)."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.14778\/3594512.3594527"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639324"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3698822","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3698822","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T17:46:07Z","timestamp":1774979167000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3698822"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,18]]},"references-count":56,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,12,18]]}},"alternative-id":["10.1145\/3698822"],"URL":"https:\/\/doi.org\/10.1145\/3698822","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,18]]}}}