{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T15:43:06Z","timestamp":1783784586497,"version":"3.55.0"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:p>\n            This paper presents an efficient and scalable framework for Range Filtered Approximate Nearest Neighbors Search (RF-ANNS) over high-dimensional vectors associated with attribute values. Given a query vector\n            <jats:italic>q<\/jats:italic>\n            and a range [\n            <jats:italic>l, h<\/jats:italic>\n            ], RF-ANNS aims to find the approximate\n            <jats:italic>k<\/jats:italic>\n            nearest neighbors of\n            <jats:italic>q<\/jats:italic>\n            among data whose attribute values fall within [\n            <jats:italic>l, h<\/jats:italic>\n            ]. Existing methods including pre-, post-, and hybrid filtering strategies that perform attribute range filtering before, after, or during the ANNS process, all suffer from significant performance degradation when query ranges shift. Though building dedicated indexes for each strategy and selecting the best one based on the query range can address this problem, it leads to index consistency and maintenance issues.\n          <\/jats:p>\n          <jats:p>\n            Our framework, called UNIFY, constructs a unified Proximity Graph-based (PG-based) index that seamlessly supports all three strategies. In UNIFY, we introduce SIG, a novel\n            <jats:bold>S<\/jats:bold>\n            egmented\n            <jats:bold>I<\/jats:bold>\n            nclusive\n            <jats:bold>G<\/jats:bold>\n            raph, which segments the dataset by attribute values. It ensures the PG of objects from any segment combinations is a sub-graph of SIG, thereby enabling efficient hybrid filtering by reconstructing and searching a PG from relevant segments. Moreover, we present\n            <jats:bold>H<\/jats:bold>\n            ierarchical\n            <jats:bold>S<\/jats:bold>\n            egmented\n            <jats:bold>I<\/jats:bold>\n            nclusive\n            <jats:bold>G<\/jats:bold>\n            raph (HSIG), a variant of SIG which incorporates a hierarchical structure inspired by HNSW to achieve logarithmic hybrid filtering complexity. We also implement pre- and post-filtering for HSIG by fusing skip list connections and compressed HNSW edges into the hierarchical graph. Experimental results show that UNIFY delivers state-of-the-art RF-ANNS performance across small, mid, and large query ranges.\n          <\/jats:p>","DOI":"10.14778\/3717755.3717770","type":"journal-article","created":{"date-parts":[[2025,5,20]],"date-time":"2025-05-20T15:51:49Z","timestamp":1747756309000},"page":"1118-1130","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search"],"prefix":"10.14778","volume":"18","author":[{"given":"Anqi","family":"Liang","sequence":"first","affiliation":[{"name":"Shanghai Jiao Tong University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pengcheng","family":"Zhang","sequence":"additional","affiliation":[{"name":"Tencent Inc."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bin","family":"Yao","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhongpu","family":"Chen","sequence":"additional","affiliation":[{"name":"Southwestern University of Finance and Economics"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yitong","family":"Song","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guangxu","family":"Cheng","sequence":"additional","affiliation":[{"name":"Tencent Inc."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,5,20]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Fabien Andr\u00e9 Anne-Marie Kermarrec and Nicolas Le Scouarnec. 2016. Cache locality is not enough: High-performance nearest neighbor search with product quantization fast scan. In VLDB. 288\u2013299.","DOI":"10.14778\/2856318.2856324"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/3204028.3204034"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2019.02.006"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_2_1_5_1","volume-title":"SPTAG: A library for fast approximate nearest neighbor search. https:\/\/github.com\/Microsoft\/SPTAG.","author":"Chen Qi","year":"2018","unstructured":"Qi Chen, Haidong Wang, Mingqin Li, Gang Ren, Scarlett Li, Jeffery Zhu, Jason Li, Chuanjie Liu, Lintao Zhang, and Jingdong Wang. 2018. SPTAG: A library for fast approximate nearest neighbor search. https:\/\/github.com\/Microsoft\/SPTAG."},{"key":"e_1_2_1_6_1","first-page":"4139","article-title":"High dimensional similarity search with satellite system graph: Efficiency, scalability, and unindexed query compatibility","volume":"44","author":"Fu Cong","year":"2021","unstructured":"Cong Fu, Changxu Wang, and Deng Cai. 2021. High dimensional similarity search with satellite system graph: Efficiency, scalability, and unindexed query compatibility. TPAMI 44, 8 (2021), 4139\u20134150.","journal-title":"TPAMI"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Cong Fu Chao Xiang Changxu Wang and Deng Cai. 2019. Fast approximate nearest neighbor search with the navigating spreading-out graph. In VLDB. 461\u2013474.","DOI":"10.14778\/3303753.3303754"},{"key":"e_1_2_1_8_1","volume-title":"Narendra","author":"Fukunaga Keinosuke","year":"1975","unstructured":"Keinosuke Fukunaga and Patrenahalli M. Narendra. 1975. A branch and bound algorithm for computing k-nearest neighbors. IEEE transactions on computers 100, 7 (1975), 750\u2013753."},{"key":"e_1_2_1_9_1","unstructured":"Tiezheng Ge Kaiming He Qifa Ke and Jian Sun. 2013. Optimized product quantization for approximate nearest neighbor search. In CVPR. 2946\u20132953."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3543507.3583552"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Hazar Harmouch and Felix Naumann. 2017. Cardinality estimation: An experimental survey. In VLDB. 499\u2013512.","DOI":"10.1145\/3186728.3164145"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Qiang Huang Jianlin Feng Yikai Zhang Qiong Fang and Wilfred Ng. 2015. Query-aware locality-sensitive hashing for approximate nearest neighbor search. In VLDB. 1\u201312.","DOI":"10.14778\/2850469.2850470"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_1_15_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 NeurIPS, Vol. 32."},{"key":"e_1_2_1_16_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\u2013128."},{"key":"e_1_2_1_17_1","unstructured":"Jingdong. 2020. A distributed system for embedding-based retrieval. https:\/\/github.com\/vearch\/vearch."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TBDATA.2019.2921572"},{"key":"e_1_2_1_19_1","first-page":"9459","article-title":"Retrieval-augmented generation for knowledge-intensive nlp tasks","volume":"33","author":"Lewis Patrick","year":"2020","unstructured":"Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich K\u00fcttler, Mike Lewis, Wen-tau Yih, Tim Rockt\u00e4schel, et al. 2020. Retrieval-augmented generation for knowledge-intensive nlp tasks. Advances in Neural Information Processing Systems 33 (2020), 9459\u20139474.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3284028.3284030"},{"key":"e_1_2_1_21_1","first-page":"1475","article-title":"Approximate nearest neighbor search on high dimensional data\u2014experiments, analyses, and improvement","volume":"32","author":"Li Wen","year":"2019","unstructured":"Wen Li, Ying Zhang, Yifang Sun, Wei Wang, Mingjie Li, Wenjie Zhang, and Xuemin Lin. 2019. Approximate nearest neighbor search on high dimensional data\u2014experiments, analyses, and improvement. TKDE 32, 8 (2019), 1475\u20131488.","journal-title":"TKDE"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Yingfan Liu Hong Cheng and Jiangtao Cui. 2017. PQBF: i\/o-efficient approximate nearest neighbor search by product quantization. In CIKM. 667\u2013676.","DOI":"10.1145\/3132847.3132901"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2018.2889473"},{"key":"e_1_2_1_24_1","volume-title":"Pqtable: Fast exact asymmetric distance neighbor search for product quantization using hash tables. In ICCV. 1940\u20131948.","author":"Matsui Yusuke","year":"2015","unstructured":"Yusuke Matsui, Toshihiko Yamasaki, and Kiyoharu Aizawa. 2015. Pqtable: Fast exact asymmetric distance neighbor search for product quantization using hash tables. In ICCV. 1940\u20131948."},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Yujie Mo Liang Peng Jie Xu Xiaoshuang Shi and Xiaofeng Zhu. 2022. Simple unsupervised graph representation learning. In AAAI. 7797\u20137805.","DOI":"10.1609\/aaai.v36i7.20748"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2014.2321376"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/45.5.494"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/588011.588037"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/11764298_8"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Gregory Piatetsky-Shapiro and Charles Connell. 1984. Accurate estimation of the number of tuples satisfying a condition. In SIGMOD. 256\u2013276.","DOI":"10.1145\/971697.602294"},{"key":"e_1_2_1_31_1","unstructured":"Pinecone. 2021. Pinecone.io. https:\/\/www.pinecone.io\/."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/78973.78977"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Jianbin Qin Wei Wang Chuan Xiao and Ying Zhang. 2020. Similarity query processing for high-dimensional data. In VLDB. 3437\u20133440.","DOI":"10.14778\/3415478.3415564"},{"key":"e_1_2_1_34_1","volume-title":"Hm-ann: Efficient billion-point nearest neighbor search on heterogeneous memory. In NeurIPS. 10672\u201310684.","author":"Ren Jie","year":"2020","unstructured":"Jie Ren, Minjia Zhang, and Dong Li. 2020. Hm-ann: Efficient billion-point nearest neighbor search on heterogeneous memory. In NeurIPS. 10672\u201310684."},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Yitong Song Kai Wang Bin Yao Zhida Chen Jiong Xie and Feifei Li. 2024. Efficient Reverse k Approximate Nearest Neighbor Search Over High-Dimensional Vectors. In ICDE. 4262\u20134274.","DOI":"10.1109\/ICDE60146.2024.00325"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15286-3_16"},{"key":"e_1_2_1_37_1","first-page":"1000","article-title":"DB-LSH 2.0: Locality-Sensitive Hashing With Query-Based Dynamic Bucketing","volume":"36","author":"Tian Yao","year":"2023","unstructured":"Yao Tian, Xi Zhao, and Xiaofang Zhou. 2023. DB-LSH 2.0: Locality-Sensitive Hashing With Query-Based Dynamic Bucketing. TKDE 36, 3 (2023), 1000\u20131015.","journal-title":"TKDE"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2705101"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457550"},{"key":"e_1_2_1_40_1","first-page":"15738","article-title":"An efficient and robust framework for approximate nearest neighbor search with attribute constraint","volume":"36","author":"Wang Mengzhao","year":"2023","unstructured":"Mengzhao Wang, Lingwei Lv, Xiaoliang Xu, Yuxiang Wang, Qiang Yue, and Jiongkang Ni. 2023. An efficient and robust framework for approximate nearest neighbor search with attribute constraint. In NeurIPS, Vol. 36. 15738\u201315751.","journal-title":"NeurIPS"},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Mengzhao Wang Xiaoliang Xu Qiang Yue and Yuxiang Wang. 2021. A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search. In VLDB. 1964\u20131978.","DOI":"10.14778\/3476249.3476255"},{"key":"e_1_2_1_42_1","unstructured":"Weaviate. 2019. Weaviate.io. https:\/\/weaviate.io\/developers\/weaviate\/concepts\/vector-index."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/3415478.3415541"},{"key":"e_1_2_1_44_1","volume-title":"HQANN: Efficient and robust similarity search for hybrid queries with structured and unstructured constraints. In CIKM. 4580\u20134584.","author":"Wu Wei","year":"2022","unstructured":"Wei Wu, Junlin He, Yu Qiao, Guoheng Fu, Li Liu, and Jin Yu. 2022. HQANN: Efficient and robust similarity search for hybrid queries with structured and unstructured constraints. In CIKM. 4580\u20134584."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.5970"},{"key":"e_1_2_1_46_1","unstructured":"Yahoo. 2016. Nearest neighbor search with neighborhood graph and tree for high-dimensional data. https:\/\/github.com\/yahoojapan\/NGT."},{"key":"e_1_2_1_47_1","volume-title":"Pase: Postgresql ultra-high-dimensional approximate nearest neighbor search extension. In SIGMOD. 2241\u20132253.","author":"Yang Wen","year":"2020","unstructured":"Wen Yang, Tao Li, Gai Fang, and Hong Wei. 2020. Pase: Postgresql ultra-high-dimensional approximate nearest neighbor search extension. In SIGMOD. 2241\u20132253."},{"key":"e_1_2_1_48_1","unstructured":"Peter N Yianilos. 1993. Data structures and algorithms for nearest neighbor search in general metric spaces. In SODA. 311\u2013321."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-022-00762-0"},{"key":"e_1_2_1_50_1","volume-title":"Hang Liu, and Christian S Jensen.","author":"Zheng Bolong","year":"2020","unstructured":"Bolong Zheng, Zhao Xi, Lianggui Weng, Nguyen Quoc Viet Hung, Hang Liu, and Christian S Jensen. 2020. PM-LSH: A fast and accurate LSH framework for high-dimensional approximate NN search. In VLDB. 643\u2013655."},{"key":"e_1_2_1_51_1","doi-asserted-by":"crossref","unstructured":"Chaoji Zuo and Dong Deng. 2023. ARKGraph: All-Range Approximate K-Nearest-Neighbor Graph. In VLDB. 2645\u20132658.","DOI":"10.14778\/3603581.3603601"},{"key":"e_1_2_1_52_1","unstructured":"Chaoji Zuo Miao Qiao Wenchao Zhou Feifei Li and Dong Deng. 2024. SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search. In SIGMOD. 1\u201326."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3717755.3717770","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,20]],"date-time":"2025-05-20T16:16:46Z","timestamp":1747757806000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3717755.3717770"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12]]},"references-count":52,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["10.14778\/3717755.3717770"],"URL":"https:\/\/doi.org\/10.14778\/3717755.3717770","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,12]]},"assertion":[{"value":"2025-05-20","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}