{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T02:34:31Z","timestamp":1783737271710,"version":"3.55.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T00:00:00Z","timestamp":1710201600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006374","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2152908,2212629"],"award-info":[{"award-number":["2152908,2212629"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006374","name":"Marsden Fund","doi-asserted-by":"publisher","award":["UOA1732"],"award-info":[{"award-number":["UOA1732"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006374","name":"Ministry of Business, Innovation and Employment","doi-asserted-by":"publisher","award":["UOAX2001"],"award-info":[{"award-number":["UOAX2001"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,3,12]]},"abstract":"<jats:p>Effective vector representation models, e.g., word2vec and node2vec, embed real-world objects such as images and documents in high dimensional vector space. In the meanwhile, the objects are often associated with attributes such as timestamps and prices. Many scenarios need to jointly query the vector representations of the objects together with their attributes. These queries can be formalized as range-filtering approximate nearest neighbor search (ANNS) queries. Specifically, given a collection of data vectors, each associated with an attribute value whose domain has a total order. The range-filtering ANNS consists of a query range and a query vector. It finds the approximate nearest neighbors of the query vector among all the data vectors whose attribute values fall in the query range. Existing approaches suffer from a rapidly degrading query performance when the query range width shifts. The query performance can be optimized by a solution that builds an ANNS index for every possible query range; however, the index time and index size become prohibitive -- the number of query ranges is quadratic to the number n of data vectors. To overcome these challenges, for the query range contains all attribute values smaller than a user-provided threshold, we design a structure called the segment graph whose index time and size are the same as a single ANNS index, yet can losslessly compress the n ANNS indexes, reducing the indexing cost by a factor of \u03a9(n). To handle general range queries, we propose a 2D segment graph with average-case index size O(n log n) to compress n segment graphs, breaking the quadratic barrier. Extensive experiments conducted on real-world datasets show that our proposed structures outperformed existing methods significantly; our index also exhibits superior scalability.<\/jats:p>","DOI":"10.1145\/3639324","type":"journal-article","created":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T18:51:32Z","timestamp":1711479092000},"page":"1-26","source":"Crossref","is-referenced-by-count":38,"title":["SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9869-5602","authenticated-orcid":false,"given":"Chaoji","family":"Zuo","sequence":"first","affiliation":[{"name":"Rutgers University, Piscataway, NJ, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8374-140X","authenticated-orcid":false,"given":"Miao","family":"Qiao","sequence":"additional","affiliation":[{"name":"The University of Auckland, Auckland, New Zealand"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-2689-6020","authenticated-orcid":false,"given":"Wenchao","family":"Zhou","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-0770-5775","authenticated-orcid":false,"given":"Feifei","family":"Li","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4596-3850","authenticated-orcid":false,"given":"Dong","family":"Deng","sequence":"additional","affiliation":[{"name":"Rutgers University, Piscataway, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,3,26]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"[n. d.]. Lucene 9.0.0. https:\/\/lucene.apache.org\/core\/corenews.html#apache-lucenetm-900-available."},{"key":"e_1_2_2_2_1","unstructured":"[n. d.]. Pinecone.io. https:\/\/www.pinecone.io\/."},{"key":"e_1_2_2_3_1","unstructured":"[n. d.]. Weaviate.io. https:\/\/weaviate.io\/developers\/weaviate\/concepts\/vector-index."},{"key":"e_1_2_2_4_1","unstructured":"[n. d.]. Zilliz. https:\/\/zilliz.com\/."},{"key":"e_1_2_2_5_1","doi-asserted-by":"crossref","unstructured":"Alexandr Andoni and Piotr Indyk. 2006. Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions. In FOCS. 459--468.","DOI":"10.1109\/FOCS.2006.49"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/2856318.2856324"},{"key":"e_1_2_2_7_1","volume-title":"Mount","author":"Arya Sunil","year":"1993","unstructured":"Sunil Arya and David M. Mount. 1993. Approximate Nearest Neighbor Queries in Fixed Dimensions. In ACM\/SIGACT-SIAM. 271--280."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/116873.116880"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2016.226"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/3--540--47724--1_14"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3303753.3303754"},{"key":"e_1_2_2_12_1","doi-asserted-by":"crossref","unstructured":"Junhao Gan Jianlin Feng Qiong Fang and Wilfred Ng. 2012. Locality-sensitive hashing scheme based on dynamic collision counting. In SIGMOD. 541--552.","DOI":"10.1145\/2213836.2213898"},{"key":"e_1_2_2_13_1","unstructured":"Tiezheng Ge Kaiming He Qifa Ke and Jian Sun. 2013. Optimized Product Quantization for Approximate Nearest Neighbor Search. In CVPR. 2946--2953."},{"key":"e_1_2_2_14_1","doi-asserted-by":"crossref","unstructured":"Siddharth Gollapudi Neel Karia Varun Sivashankar Ravishankar Krishnaswamy Nikit Begwani Swapnil Raz Yiyong Lin Yin Zhang Neelam Mahapatro Premkumar Srinivasan et al. 2023. Filtered-DiskANN: Graph Algorithms for Approximate Nearest Neighbor Search with Filters. In WWW. 3406--3416.","DOI":"10.1145\/3543507.3583552"},{"key":"e_1_2_2_15_1","volume-title":"Face recognition vendor test (FRVT) part 2: identification. US Department of Commerce","author":"Grother Patrick","unstructured":"Patrick Grother, Patrick Grother, Mei Ngan, and Kayee Hanaoka. 2019. Face recognition vendor test (FRVT) part 2: identification. US Department of Commerce, National Institute of Standards and Technology."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","unstructured":"Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable Feature Learning for Networks. In KDD. 855--864. https:\/\/doi.org\/10.1145\/2939672.2939754","DOI":"10.1145\/2939672.2939754"},{"key":"e_1_2_2_17_1","volume-title":"FANNG: Fast Approximate Nearest Neighbour Graphs. In CVPR. 5713--5722.","author":"Harwood Ben","year":"2016","unstructured":"Ben Harwood and Tom Drummond. 2016. FANNG: Fast Approximate Nearest Neighbour Graphs. In CVPR. 5713--5722."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850469.2850470"},{"key":"e_1_2_2_19_1","doi-asserted-by":"crossref","unstructured":"Piotr Indyk and Rajeev Motwani. 1998. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. In STOC. 604--613.","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.163414"},{"key":"e_1_2_2_21_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_2_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.57"},{"key":"e_1_2_2_23_1","doi-asserted-by":"crossref","unstructured":"Yannis Kalantidis and Yannis Avrithis. 2014. Locally Optimized Product Quantization for Approximate Nearest Neighbor Search. In CVPR. 2329--2336.","DOI":"10.1109\/CVPR.2014.298"},{"key":"e_1_2_2_24_1","volume-title":"Navigation in a small world. Nature 406, 6798","author":"Kleinberg Jon M.","year":"2000","unstructured":"Jon M. Kleinberg. 2000. Navigation in a small world. Nature 406, 6798 (2000), 845--845."},{"key":"e_1_2_2_25_1","first-page":"1188","article-title":"Distributed Representations of Sentences and Documents","volume":"32","author":"Le Quoc V.","year":"2014","unstructured":"Quoc V. Le and Tom\u00e1s Mikolov. 2014. Distributed Representations of Sentences and Documents. In ICML, Vol. 32. 1188--1196. http:\/\/proceedings.mlr.press\/v32\/le14.html","journal-title":"ICML"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2909204"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","unstructured":"Xinchen Liu Wu Liu Huadong Ma and Huiyuan Fu. 2016. Large-scale vehicle re-identification in urban surveillance videos. In ICME. 1--6. https:\/\/doi.org\/10.1109\/ICME.2016.7553002","DOI":"10.1109\/ICME.2016.7553002"},{"key":"e_1_2_2_28_1","volume-title":"Zhe Wang, Moses Charikar, and Kai Li.","author":"Lv Qin","year":"2007","unstructured":"Qin Lv, William Josephson, Zhe Wang, Moses Charikar, and Kai Li. 2007. Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search. In PVLDB. 950--961."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2013.10.006"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2018.2889473"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","unstructured":"Yusuke Matsui Ryota Hinami and Shin'ichi Satoh. 2018. Reconfigurable Inverted Index. In MM. 1715--1723. https:\/\/doi.org\/10.1145\/3240508.3240630","DOI":"10.1145\/3240508.3240630"},{"key":"e_1_2_2_32_1","doi-asserted-by":"crossref","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--1948.","DOI":"10.1109\/ICCV.2015.225"},{"key":"e_1_2_2_33_1","unstructured":"Tomas Mikolov Ilya Sutskever Kai Chen Gregory S. Corrado and Jeffrey Dean. 2013. Distributed Representations of Words and Phrases and their Compositionality. In NeurIPS. 3111--3119."},{"key":"e_1_2_2_34_1","first-page":"1","article-title":"High-Throughput Vector Similarity Search in Knowledge Graphs","volume":"1","author":"Mohoney Jason","year":"2023","unstructured":"Jason Mohoney, Anil Pacaci, Shihabur Rahman Chowdhury, Ali Mousavi, Ihab F Ilyas, Umar Farooq Minhas, Jeffrey Pound, and Theodoros Rekatsinas. 2023. High-Throughput Vector Similarity Search in Knowledge Graphs. SIGMOD 1, 2 (2023), 1--25.","journal-title":"SIGMOD"},{"key":"e_1_2_2_35_1","volume-title":"Manning","author":"Pennington Jeffrey","year":"2014","unstructured":"Jeffrey Pennington, Richard Socher, and Christopher D. Manning. 2014. Glove: Global Vectors for Word Representation. In EMNLP. 1532--1543."},{"key":"e_1_2_2_36_1","volume-title":"Russell and Peter Norvig","author":"Stuart","year":"2003","unstructured":"Stuart J. Russell and Peter Norvig. 2003. Artificial intelligence - a modern approach, 2nd Edition. Prentice Hall.","edition":"2"},{"key":"e_1_2_2_37_1","unstructured":"Christoph Schuhmann Romain Beaumont Richard Vencu Cade Gordon Ross Wightman Mehdi Cherti Theo Coombes Aarush Katta Clayton Mullis Mitchell Wortsman Patrick Schramowski Srivatsa Kundurthy Katherine Crowson Ludwig Schmidt Robert Kaczmarczyk and Jenia Jitsev. 2022. LAION-5B: An open large-scale dataset for training next generation image-text models. arXiv:2210.08402 [cs.CV]"},{"key":"e_1_2_2_38_1","unstructured":"Anshumali Shrivastava and Ping Li. 2014. Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS). In NeurIPS. 2321--2329."},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--642--15286--3_16"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457550"},{"key":"e_1_2_2_41_1","unstructured":"Mengzhao Wang Lingwei Lv Xiaoliang Xu Yuxiang Wang Qiang Yue and Jiongkang Ni. 2022. Navigable Proximity Graph-Driven Native Hybrid Queries with Structured and Unstructured Constraints. arXiv:2203.13601 [cs.DB]"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476255"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/3424573.3424580"},{"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\/3511808.3557610"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2210.14958"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","unstructured":"Liang Zheng Liyue Shen Lu Tian Shengjin Wang Jingdong Wang and Qi Tian. 2015. Scalable Person Re-identification: A Benchmark. In CVPR. 1116--1124. https:\/\/doi.org\/10.1109\/ICCV.2015.133","DOI":"10.1109\/ICCV.2015.133"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/3603581.3603601"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639324","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3639324","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T15:16:55Z","timestamp":1755789415000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639324"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,12]]},"references-count":48,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,12]]}},"alternative-id":["10.1145\/3639324"],"URL":"https:\/\/doi.org\/10.1145\/3639324","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,12]]}}}