{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T00:01:56Z","timestamp":1780444916068,"version":"3.54.1"},"reference-count":74,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,7]]},"abstract":"<jats:p>\n            Real-world tasks such as recommending videos tagged\n            <jats:italic toggle=\"yes\">kids<\/jats:italic>\n            can be reduced to finding\n            <jats:italic toggle=\"yes\">similar<\/jats:italic>\n            vectors associated with\n            <jats:italic toggle=\"yes\">hard<\/jats:italic>\n            predicates. This task,\n            <jats:italic toggle=\"yes\">filtered vector search<\/jats:italic>\n            , is challenging as prior state-of-the-art graph-based (unfiltered) similarity search techniques degenerate when hard constraints are considered: effective graph-based filtered similarity search relies on sufficient connectivity for reaching similar items within a few hops. To consider predicates, recent works propose modifying graph traversal to visit only items that satisfy predicates. However, they fail to offer the just-a-few-hops property for a wide range of predicates: they must restrict predicates significantly or lose efficiency if only few items satisfy predicates.\n          <\/jats:p>\n          <jats:p>We propose an opposite approach: instead of constraining traversal, we build many indexes each serving different predicate forms. For effective construction, we devise a three-dimensional analytical model capturing relationships among index size, search time, and recall, with which we follow a workload-aware approach to pack as many useful indexes as possible into a collection. At query time, the analytical model is employed yet again to discern the one that offers the fastest search at a given recall. We show superior performance and support on datasets with varying selectivities and forms: our approach achieves up to 8.06\u00d7 speedup while having as low as 1% build time versus other indexes, with less than 2.15\u00d7 memory of a standard HNSW graph and modest knowledge of past workloads.<\/jats:p>","DOI":"10.14778\/3749646.3749725","type":"journal-article","created":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T17:55:06Z","timestamp":1757008506000},"page":"4723-4736","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["SIEVE: Effective Filtered Vector Search with Collection of Indexes"],"prefix":"10.14778","volume":"18","author":[{"given":"Zhaoheng","family":"Li","sequence":"first","affiliation":[{"name":"UIUC"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Silu","family":"Huang","sequence":"additional","affiliation":[{"name":"Bytedance Inc."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wei","family":"Ding","sequence":"additional","affiliation":[{"name":"Bytedance Inc."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yongjoo","family":"Park","sequence":"additional","affiliation":[{"name":"UIUC"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jianjun","family":"Chen","sequence":"additional","affiliation":[{"name":"Bytedance Inc."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,9,4]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n.d.]. Query Rewrite With A Nested Materialized View. https:\/\/patents.google.com\/patent\/US20090228432A1\/en."},{"key":"e_1_2_1_2_1","first-page":"496","article-title":"Automated selection of materialized views and indexes in SQL databases","volume":"2000","author":"Agrawal Sanjay","year":"2000","unstructured":"Sanjay Agrawal, Surajit Chaudhuri, and Vivek R Narasayya. 2000. Automated selection of materialized views and indexes in SQL databases. In VLDB, Vol. 2000. 496\u2013505.","journal-title":"VLDB"},{"key":"e_1_2_1_3_1","volume-title":"International Conference on Machine Learning. PMLR, 231\u2013242","author":"Amanatidis Georgios","year":"2021","unstructured":"Georgios Amanatidis, Federico Fusco, Philip Lazos, Stefano Leonardi, Alberto Marchetti-Spaccamela, and Rebecca Reiffenh\u00e4user. 2021. Submodular maximization subject to a knapsack constraint: Combinatorial algorithms with near-optimal adaptive complexity. In International Conference on Machine Learning. PMLR, 231\u2013242."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the national academy of sciences 97","author":"Nunes Amaral Lu\u0131s A","year":"2000","unstructured":"Lu\u0131s A Nunes Amaral, Antonio Scala, Marc Barthelemy, and H Eugene Stanley. 2000. Classes of small-world networks. Proceedings of the national academy of sciences 97, 21 (2000), 11149\u201311152."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/11827252_9"},{"key":"e_1_2_1_6_1","unstructured":"Antonio Torralba Aude Oliva. [n.d.]. Modeling the shape of the scene: a holistic representation of the spatial envelope. http:\/\/people.csail.mit.edu\/torralba\/code\/spatialenvelope\/."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3190662"},{"key":"e_1_2_1_8_1","unstructured":"big-ann benchmarks. 2024. YFCC10M - Neurips23 BigANN Challenge Filter Track. https:\/\/github.com\/harsha-simhadri\/big-ann-benchmarks\/blob\/main\/benchmark\/datasets.py."},{"key":"e_1_2_1_9_1","volume-title":"Better bitmap performance with roaring bitmaps. Software: practice and experience 46, 5","author":"Chambi Samy","year":"2016","unstructured":"Samy Chambi, Daniel Lemire, Owen Kaser, and Robert Godin. 2016. Better bitmap performance with roaring bitmaps. Software: practice and experience 46, 5 (2016), 709\u2013719."},{"key":"e_1_2_1_10_1","unstructured":"Chandra Chekuri. [n.d.]. Combinatorial Optimization. https:\/\/courses.grainger.illinois.edu\/cs586\/sp2022\/main.pdf."},{"key":"e_1_2_1_11_1","unstructured":"CloudFlare. [n.d.]. Computing Euclidean distance on 144 dimensions. https:\/\/blog.cloudflare.com\/computing-euclidean-distance-on-144-dimensions\/."},{"key":"e_1_2_1_12_1","unstructured":"cmuparlay. 2024. Benchmarking nearest neighbors."},{"key":"e_1_2_1_13_1","unstructured":"DiskANN. [n.d.]. DiskAnnPy - API. https:\/\/microsoft.github.io\/DiskANN\/docs\/python\/latest\/diskannpy.html."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187801"},{"key":"e_1_2_1_15_1","volume-title":"The faiss library. arXiv preprint arXiv:2401.08281","author":"Douze Matthijs","year":"2024","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. arXiv preprint arXiv:2401.08281 (2024)."},{"key":"e_1_2_1_16_1","volume-title":"Approximate Nearest Neighbor Search with Window Filters. In Forty-first International Conference on Machine Learning.","author":"Engels Joshua","unstructured":"Joshua Engels, Ben Landrum, Shangdi Yu, Laxman Dhulipala, and Julian Shun. [n.d.]. Approximate Nearest Neighbor Search with Window Filters. In Forty-first International Conference on Machine Learning."},{"key":"e_1_2_1_17_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_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589282"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.131"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/376284.375706"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3543507.3583552"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90103-7"},{"key":"e_1_2_1_23_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_24_1","unstructured":"harsha simhadri. 2024. Big ANN Benchmarks. https:\/\/github.com\/harsha-simhadri\/big-ann-benchmarks."},{"key":"e_1_2_1_25_1","first-page":"68","article-title":"Database Cracking","volume":"7","author":"Idreos Stratos","year":"2007","unstructured":"Stratos Idreos, Martin L Kersten, Stefan Manegold, et al. 2007. Database Cracking.. In CIDR, Vol. 7. 68\u201378.","journal-title":"CIDR"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1862919.1862921"},{"key":"e_1_2_1_27_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. Advances in Neural Information Processing Systems 32 (2019)."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3192965.3192971"},{"key":"e_1_2_1_29_1","volume-title":"Link deletion in directed complex networks. Physica A: Statistical Mechanics and its Applications 514","author":"Kashyap G","year":"2019","unstructured":"G Kashyap and G Ambika. 2019. Link deletion in directed complex networks. Physica A: Statistical Mechanics and its Applications 514 (2019), 631\u2013643."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213900"},{"key":"e_1_2_1_31_1","volume-title":"The 1st Workshop on Vector Databases. https:\/\/openreview.net\/forum?id=kXw8E3xT7O","author":"Landrum Ben","year":"2025","unstructured":"Ben Landrum, Magdalen Dobson Manohar, Mazin Karjikar, and Laxman Dhulipala. 2025. IVF2 Index: Fusing Classic and Spatial Inverted Indices for Fast Filtered ANNS. In The 1st Workshop on Vector Databases. https:\/\/openreview.net\/forum?id=kXw8E3xT7O"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00393"},{"key":"e_1_2_1_33_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\u2013836."},{"key":"e_1_2_1_34_1","unstructured":"Information Management and Preservation. 2024. Million Song Dataset Benchmarks. https:\/\/www.ifs.tuwien.ac.at\/mir\/msd\/."},{"key":"e_1_2_1_35_1","unstructured":"Meta. [n.d.]. Llama Models. https:\/\/www.llama.com\/."},{"key":"e_1_2_1_36_1","unstructured":"Microsoft. [n.d.]. Introducing Phi-3: Redefining what's possible with SLMs. https:\/\/azure.microsoft.com\/en-us\/blog\/introducing-phi-3-redefining-whats-possible-with-slms\/."},{"key":"e_1_2_1_37_1","volume-title":"International Conference on Machine Learning. PMLR, 1358\u20131367","author":"Mirzasoleiman Baharan","year":"2016","unstructured":"Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, and Amin Karbasi. 2016. Fast constrained submodular maximization: Personalized data summarization. In International Conference on Machine Learning. PMLR, 1358\u20131367."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375703"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589777"},{"key":"e_1_2_1_40_1","volume-title":"Non-metric space library manual. arXiv preprint arXiv:1508.05470","author":"Naidan Bilegsaikhan","year":"2015","unstructured":"Bilegsaikhan Naidan, Leonid Boytsov, Yury Malkov, and David Novak. 2015. Non-metric space library manual. arXiv preprint arXiv:1508.05470 (2015)."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.84.3201"},{"key":"e_1_2_1_42_1","unstructured":"nmslib. 2024. Hnswlib - fast approximate nearest neighbor search. https:\/\/github.com\/nmslib\/hnswlib."},{"key":"e_1_2_1_43_1","unstructured":"OpenAI. [n.d.]. OpenAI. https:\/\/openai.com\/."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654923"},{"key":"e_1_2_1_45_1","unstructured":"Pinecone. [n.d.]. Hierarchical Navigable Small Worlds (HNSW). https:\/\/www.pinecone.io\/learn\/series\/faiss\/hnsw\/."},{"key":"e_1_2_1_46_1","volume-title":"Set-Valued Attributes in O\/R DBMS: Implementation Options and Performance Implications. R DBMS: Implementation options and performance implications","author":"Ramasamy Karthikeyan","unstructured":"Karthikeyan Ramasamy, Prasad M Deshpande, Jeffrey F Naughton, and David Maier. 1998. Set-Valued Attributes in O\/R DBMS: Implementation Options and Performance Implications. R DBMS: Implementation options and performance implications, Madison: University of Wisconsin (1998)."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/3352063.3352082"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3662010.3663448"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/3007263.3007267"},{"key":"e_1_2_1_50_1","first-page":"488","article-title":"Materialized view selection for multidimensional datasets","volume":"98","author":"Shukla Amit","year":"1998","unstructured":"Amit Shukla, Prasad Deshpande, Jeffrey F Naughton, et al. 1998. Materialized view selection for multidimensional datasets. In VLDB, Vol. 98. 488\u2013499.","journal-title":"VLDB"},{"key":"e_1_2_1_51_1","volume-title":"Dmitry Baranchuk, Edo Liberty, Frank Liu, Ben Landrum, et al.","author":"Simhadri Harsha Vardhan","year":"2024","unstructured":"Harsha Vardhan Simhadri, Martin Aum\u00fcller, Amir Ingber, Matthijs Douze, George Williams, Magdalen Dobson Manohar, Dmitry Baranchuk, Edo Liberty, Frank Liu, Ben Landrum, et al. 2024. Results of the Big ANN: NeurIPS'23 competition. arXiv preprint arXiv:2409.17424 (2024)."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2017.07.006"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610515"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/3025111.3025123"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(03)00062-2"},{"key":"e_1_2_1_56_1","unstructured":"Texmex. 2024. Datasets for approximate nearest neighbor search. http:\/\/corpustexmex.irisa.fr\/."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031763.1031783"},{"key":"e_1_2_1_58_1","volume-title":"Supermodularity and complementarity","author":"Topkis Donald M","unstructured":"Donald M Topkis. 1998. Supermodularity and complementarity. Princeton university press."},{"key":"e_1_2_1_59_1","unstructured":"UQV. 2024. UQV. http:\/\/staff.itee.uq.edu.au\/shenht\/UQVIDEO\/."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457550"},{"key":"e_1_2_1_61_1","volume-title":"Navigable proximity graph-driven native hybrid queries with structured and unstructured constraints. arXiv preprint arXiv:2203.13601","author":"Wang Mengzhao","year":"2022","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 preprint arXiv:2203.13601 (2022)."},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.14778\/3704965.3704974"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.14778\/3415478.3415541"},{"key":"e_1_2_1_64_1","unstructured":"Wikipedia. [n.d.]. Hasse Diagram - Wikipedia. https:\/\/en.wikipedia.org\/wiki\/Hasse_diagram."},{"key":"e_1_2_1_65_1","unstructured":"Wikipedia. 2024. Skip List Data Structure - Wikipedia. https:\/\/en.wikipedia.org\/wiki\/Skip_list."},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/3511808.3557610"},{"key":"e_1_2_1_67_1","volume-title":"Enhancing HNSW Index for Real-Time Updates: Addressing Unreachable Points and Performance Degradation. arXiv preprint arXiv:2407.07871","author":"Xiao Wentao","year":"2024","unstructured":"Wentao Xiao, Yueyang Zhan, Rui Xi, Mengshu Hou, and Jianming Liao. 2024. Enhancing HNSW Index for Real-Time Updates: Addressing Unreachable Points and Performance Degradation. arXiv preprint arXiv:2407.07871 (2024)."},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389770"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1109\/CLOUD.2018.00042"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1109\/5326.971656"},{"key":"e_1_2_1_71_1","unstructured":"Li Zhaoheng Huang Silu Ding Wei Park Yongjoo and Chen Jianjun. [n.d.]. SIEVE Technical Report. https:\/\/arxiv.org\/abs\/2507.11907."},{"key":"e_1_2_1_72_1","unstructured":"Li Zhaoheng Huang Silu Ding Wei Park Yongjoo and Chen Jianjun. 2025. SIEVE - Github. https:\/\/github.com\/BillyZhaohengLi\/SIEVE-vldb25\/."},{"key":"e_1_2_1_73_1","unstructured":"Zilliz. 2024. Faiss vs. HNSWlib: Choosing the Right Vector Search Tool for Your Application."},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639324"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3749646.3749725","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,5]],"date-time":"2025-09-05T03:21:43Z","timestamp":1757042503000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3749646.3749725"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7]]},"references-count":74,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["10.14778\/3749646.3749725"],"URL":"https:\/\/doi.org\/10.14778\/3749646.3749725","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2025,7]]},"assertion":[{"value":"2025-09-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}