{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,23]],"date-time":"2026-10-23T20:30:06Z","timestamp":1792787406912,"version":"4.5.0"},"reference-count":60,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,5,26]],"date-time":"2023-05-26T00:00:00Z","timestamp":1685059200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Hong Kong RGC","award":["C2004-21GF, 12202221, 12201518, 12201119"],"award-info":[{"award-number":["C2004-21GF, 12202221, 12201518, 12201119"]}]},{"name":"NSF of Hunan Province","award":["2021JJ40123"],"award-info":[{"award-number":["2021JJ40123"]}]},{"name":"NSF of Guangdong Province","award":["2023A1515030273, 2023A1515011655, 2019B1515130001"],"award-info":[{"award-number":["2023A1515030273, 2023A1515011655, 2019B1515130001"]}]},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["62002108, 62202401, 62072132"],"award-info":[{"award-number":["62002108, 62202401, 62072132"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,5,26]]},"abstract":"<jats:p>Approximate nearest neighbor (ANN) search is a fundamental search in multi-dimensional databases, which has numerous real-world applications, such as image retrieval, recommendation, entity resolution, and sequence matching. Proximity graph (PG) has been the state-of-the-art index for ANN search. However, the search on existing PGs either suffers from a high time complexity or has no performance guarantee on the search result. In this paper, we propose a novel \u03c4-monotonic graph (\u03c4- MG) to address the limitations. The novelty of \u03c4-MG lies in a \u03c4-monotonic property. Based on this property, we prove that if the distance between a query q and its nearest neighbor is less than a constant \u03c4, the search on \u03c4-MG guarantees to find the exact nearest neighbor of q and the time complexity of the search is smaller than all existing PG-based methods. For index construction efficiency, we propose an approximate variant of \u03c4-MG, namely \u03c4-monotonic neighborhood graph (\u03c4- MNG), which only requires the neighborhood of each node to be \u03c4-monotonic. We further propose an optimization to reduce the number of distance computations in search. Our extensive experiments show that our techniques outperform all existing methods on well-known real-world datasets.<\/jats:p>","DOI":"10.1145\/3588908","type":"journal-article","created":{"date-parts":[[2023,5,30]],"date-time":"2023-05-30T13:42:05Z","timestamp":1685454125000},"page":"1-27","source":"Crossref","is-referenced-by-count":85,"title":["Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6358-2333","authenticated-orcid":false,"given":"Yun","family":"Peng","sequence":"first","affiliation":[{"name":"Guangzhou University &amp; Hong Kong Baptist University, Guangzhou &amp; Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8381-336X","authenticated-orcid":false,"given":"Byron","family":"Choi","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5851-7967","authenticated-orcid":false,"given":"Tsz Nam","family":"Chan","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3417-823X","authenticated-orcid":false,"given":"Jianye","family":"Yang","sequence":"additional","affiliation":[{"name":"Guangzhou University, Guangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9404-5848","authenticated-orcid":false,"given":"Jianliang","family":"Xu","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,5,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783405"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-02224-2_5"},{"key":"e_1_2_2_3_1","volume-title":"Datasets for approximate nearest neighbor search. Retrieved","year":"2022","unstructured":"Anon. 2010. Datasets for approximate nearest neighbor search. Retrieved May 2022 from http:\/\/corpus-texmex.irisa.fr\/."},{"key":"e_1_2_2_4_1","volume-title":"Million Song Dataset Benchmarks. Retrieved","year":"2020","unstructured":"Anon. 2011. Million Song Dataset Benchmarks. Retrieved May 2020 from http:\/\/www.ifs.tuwien.ac.at\/mir\/msd\/."},{"key":"e_1_2_2_5_1","volume-title":"unknown. Common Crawl. Retrieved","year":"2020","unstructured":"Anon. unknown. Common Crawl. Retrieved April 2020 from http:\/\/commoncrawl.org\/."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2019.02.006"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/116873.116880"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-01258-8_13"},{"key":"e_1_2_2_9_1","volume-title":"Proceedings of the International Conference on Machine Learning (ICML). 475--484","author":"Baranchuk Dmitry","year":"2019","unstructured":"Dmitry Baranchuk, Dmitry Persiyanov, Anton Sinitsin, and Artem Babenko. 2019. Learning to route in similarity graphs. In Proceedings of the International Conference on Machine Learning (ICML). 475--484."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1038\/nbt.3238"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-49257-7_15"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242610"},{"key":"e_1_2_2_13_1","volume-title":"Proceedings of the Asilomar Conference on Signals, Systems and Computers","volume":"2","author":"Dearholt D.W.","unstructured":"D.W. Dearholt, N. Gonzales, and G. Kurup. 1988. Monotonic Search Networks For Computer Vision Databases. In Proceedings of the Asilomar Conference on Signals, Systems and Computers, Vol. 2. 548--553."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963487"},{"key":"e_1_2_2_15_1","volume-title":"EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN Graph. CoRR","author":"Fu Cong","year":"2016","unstructured":"Cong Fu and Deng Cai. 2016. EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN Graph. CoRR, Vol. abs\/1609.07228 (2016)."},{"key":"e_1_2_2_16_1","volume-title":"High Dimensional Similarity Search with Satellite System Graph: Efficiency, Scalability, and Unindexed Query Compatibility","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. IEEE Transactions on Pattern Analysis and Machine Intelligence (2021), 1--1."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3303753.3303754"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209662"},{"key":"e_1_2_2_19_1","volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). 1312--1317","author":"Hajebi Kiana","year":"2011","unstructured":"Kiana Hajebi, Yasin Abbasi-Yadkori, Hossein Shahbazi, and Hong Zhang. 2011. Fast Approximate Nearest-Neighbor Search with k-Nearest Neighbor Graph. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). 1312--1317."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2016.616"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2396832"},{"key":"e_1_2_2_22_1","volume-title":"Khandker Mushfiqul Islam, and Chidambaram Crushev","author":"Jafari Omid","year":"2021","unstructured":"Omid Jafari, Preeti Maurya, Parth Nagarkar, Khandker Mushfiqul Islam, and Chidambaram Crushev. 2021. A Survey on Locality Sensitive Hashing Algorithms and their Applications. CoRR, Vol. abs\/2102.08942 (2021)."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.163414"},{"key":"e_1_2_2_24_1","volume-title":"GloVe: Global Vectors for Word Representation. Retrieved","author":"Jeffrey Pennington","year":"2022","unstructured":"Pennington Jeffrey, Socher Richard, and D. Manning Christopher. 2015. GloVe: Global Vectors for Word Representation. Retrieved May 2022 from http:\/\/nlp.stanford.edu\/projects\/glove\/."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.57"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCYB.2014.2302018"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335325"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2009.5459466"},{"key":"e_1_2_2_29_1","unstructured":"Govinda D. Kurup. 1992. Database Organized on the Basis of Similarities with Applications in Computer Vision. Ph. D. Dissertation."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2008.130"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380600"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2909204"},{"key":"e_1_2_2_33_1","volume-title":"Advances in Neural Information Processing Systems","volume":"17","author":"Liu Ting","year":"2004","unstructured":"Ting Liu, Andrew Moore, Ke Yang, and Alexander Gray. 2004. An Investigation of Practical Approximate Nearest Neighbor Algorithms. In Advances in Neural Information Processing Systems, Vol. 17."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00635-4"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2013.10.006"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2018.2889473"},{"key":"e_1_2_2_37_1","volume-title":"Proceedings of the Annual ACM Symposium on Principles of Distributed Computing (PODC). ACM, 179--188","author":"Charles","unstructured":"Charles U. Martel and Van Nguyen. 2004. Analyzing Kleinberg's (and other) small-world Models. In Proceedings of the Annual ACM Symposium on Principles of Distributed Computing (PODC). ACM, 179--188."},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.3169\/mta.6.2"},{"key":"e_1_2_2_39_1","first-page":"61","article-title":"The small world problem","volume":"1","author":"Milgram Stanley","year":"1967","unstructured":"Stanley Milgram. 1967. The small world problem. Psychology Today, Vol. 1, 1 (1967), 61--67.","journal-title":"Psychology Today"},{"key":"e_1_2_2_40_1","volume-title":"Advances in Neural Information Processing Systems","volume":"31","author":"Morozov Stanislav","year":"2018","unstructured":"Stanislav Morozov and Artem Babenko. 2018. Non-metric Similarity Graphs for Maximum Inner Product Search. In Advances in Neural Information Processing Systems, Vol. 31."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.20965\/jaciii.2014.p0658"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/SISAP.2008.18"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00233"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2007.383172"},{"key":"e_1_2_2_45_1","volume-title":"Proceedings of the International Conference on Machine Learning (ICML). 7803--7813","author":"Prokhorenkova Liudmila","year":"2020","unstructured":"Liudmila Prokhorenkova and Aleksandr Shekhovtsov. 2020a. Graph-based Nearest Neighbor Search: From Practice to Theory. In Proceedings of the International Conference on Machine Learning (ICML). 7803--7813."},{"key":"e_1_2_2_46_1","volume-title":"Proceedings of the International Conference on Machine Learning (ICML))","volume":"119","author":"Prokhorenkova Liudmila","year":"2020","unstructured":"Liudmila Prokhorenkova and Aleksandr Shekhovtsov. 2020b. Graph-based Nearest Neighbor Search: From Practice to Theory. In Proceedings of the International Conference on Machine Learning (ICML)), Vol. 119. 7803--7813."},{"key":"e_1_2_2_47_1","volume-title":"Proceedings of the International Conference on Database Theory (ICDT). 158--172","author":"Shaft Uri","year":"2005","unstructured":"Uri Shaft and Raghu Ramakrishnan. 2005. When Is Nearest Neighbors Indexable?. In Proceedings of the International Conference on Database Theory (ICDT). 158--172."},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2020.101507"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735461.2735462"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2019.106970"},{"key":"e_1_2_2_51_1","volume-title":"A Note on Graph-Based Nearest Neighbor Search. arxiv","author":"Wang Hongya","year":"2012","unstructured":"Hongya Wang, Zhizheng Wang, Wei Wang, Yingyuan Xiao, Zeng Zhao, and Kaixiang Yang. 2020. A Note on Graph-Based Nearest Neighbor Search. arxiv: 2012.11083 [cs.LG]"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2013.125"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476255"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1038\/30918"},{"key":"e_1_2_2_55_1","volume-title":"Sanjiv Kumar, Daniel N. Holtmann-Rice, David Simcha, and Felix X. Yu.","author":"Wu Xiang","year":"2017","unstructured":"Xiang Wu, Ruiqi Guo, Ananda Theertha Suresh, Sanjiv Kumar, Daniel N. Holtmann-Rice, David Simcha, and Felix X. Yu. 2017. Multiscale Quantization for Fast Similarity Search. In Advances in Neural Information Processing Systems. 5745--5755."},{"key":"e_1_2_2_56_1","volume-title":"Proximity Graph Maintenance for Fast Online Nearest Neighbor Search. arXiv","author":"Xu Zhaozhuo","year":"2022","unstructured":"Zhaozhuo Xu, Weijie Zhao, Shulong Tan, Zhixin Zhou, and Ping Li. 2022. Proximity Graph Maintenance for Fast Online Nearest Neighbor Search. arXiv (2022)."},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2016.226"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00046"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00094"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882930"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588908","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3588908","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T12:47:36Z","timestamp":1750164456000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588908"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,26]]},"references-count":60,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,5,26]]}},"alternative-id":["10.1145\/3588908"],"URL":"https:\/\/doi.org\/10.1145\/3588908","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,26]]}}}