{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T19:06:24Z","timestamp":1779131184279,"version":"3.51.4"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,5,18]]},"abstract":"<jats:p>\n                    The rapid development of vector databases and large language models has significantly increased the importance of the\n                    <jats:italic toggle=\"yes\">Approximate Maximum Inner Product Search (AMIPS)<\/jats:italic>\n                    problem. Over the past decade, various approaches have been proposed to efficiently address AMIPS problems. Compared to other methods, such as those based on Locality Sensitive Hashing (LSH), proximity graph-based methods have shown superior query performance on AMIPS. However, the performance of graph-based methods for AMIPS is still not fully optimized due to the norm bias issue, while graph-based methods have demonstrated strong effectiveness for ANNS. In this paper, we theoretically analyze norm bias in MIPS and identify a\n                    <jats:italic toggle=\"yes\">norm domination<\/jats:italic>\n                    phenomenon: results are consistently dominated by a handful of large-norm vectors, with negligible contributions from small-norm ones. Building on this observation, we propose the Norm-Adaptive Partitioning (NAP) scheme, which splits the vectors in a dataset into H\n                    <jats:sc>ead<\/jats:sc>\n                    , B\n                    <jats:sc>ody<\/jats:sc>\n                    , and T\n                    <jats:sc>ail<\/jats:sc>\n                    based on vector norms. The H\n                    <jats:sc>ead<\/jats:sc>\n                    contains a small number of large-norm vectors for exhaustive search; the T\n                    <jats:sc>ail<\/jats:sc>\n                    includes small-norm vectors that can be safely pruned under accuracy bounds; and the B\n                    <jats:sc>ody<\/jats:sc>\n                    , characterized by concentrated norms, is well-suited for conventional proximity graphs. The main challenge of the NAP strategy is balancing query accuracy and the extra cost introduced by NAP by efficiently determining the sizes of\n                    <jats:sc>ail<\/jats:sc>\n                    , H\n                    <jats:sc>ead<\/jats:sc>\n                    , and B\n                    <jats:sc>ody<\/jats:sc>\n                    . To address this, we further design a practical NAP algorithm that minimizes search cost while ensuring bounded accuracy. To demonstrate NAP, we introduce a hybrid index combining a lightweight structure (for example, a hash table) for the head and a proximity graph for the body. Experimental results show that NAP reduces the index size of existing proximity graphs by over 50%, and the NAP-based hybrid index enables more than 2x speedup over state-of-the-art graph-based AMIPS methods at the same recall level.\n                  <\/jats:p>","DOI":"10.1145\/3802051","type":"journal-article","created":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T18:19:16Z","timestamp":1779128356000},"page":"1-26","source":"Crossref","is-referenced-by-count":0,"title":["Enhancing Graph-based Approximate Maximum Inner Product Search via Norm-Adaptive Partitioning"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3240-8225","authenticated-orcid":false,"given":"Xi","family":"Zhao","sequence":"first","affiliation":[{"name":"The Hong Kong University of Science and Technology, Hong Kong, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-7673-7311","authenticated-orcid":false,"given":"Zhoujin","family":"Tian","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology, Hong Kong, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3385-6417","authenticated-orcid":false,"given":"Kai","family":"Huang","sequence":"additional","affiliation":[{"name":"East China Normal University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6876-5059","authenticated-orcid":false,"given":"Yao","family":"Tian","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology, Hong Kong, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0914-4580","authenticated-orcid":false,"given":"Xiaokui","family":"Xiao","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8639-4570","authenticated-orcid":false,"given":"Bolong","family":"Zheng","sequence":"additional","affiliation":[{"name":"Wuhan University of Technology, Wuhan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5878-3683","authenticated-orcid":false,"given":"Xiaofang","family":"Zhou","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology, Hong Kong, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,5,18]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"1250","article-title":"To Index or Not to Index","author":"Abuzaid Firas","year":"2019","unstructured":"Firas Abuzaid, Geet Sethi, Peter Bailis, and Matei Zaharia. 2019. To Index or Not to Index: Optimizing Exact Maximum Inner Product Search. In ICDE. IEEE, 1250-1261.","journal-title":"Optimizing Exact Maximum Inner Product Search. In ICDE. IEEE"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902285"},{"key":"e_1_2_1_3_1","first-page":"273","article-title":"Reverse Maximum Inner Product Search: How to efficiently find users who would like to buy my item?","author":"Amagata Daichi","year":"2021","unstructured":"Daichi Amagata and Takahiro Hara. 2021. Reverse Maximum Inner Product Search: How to efficiently find users who would like to buy my item?. In RecSys. ACM, 273-281.","journal-title":"RecSys. ACM"},{"key":"e_1_2_1_4_1","unstructured":"Alexandr Andoni and Piotr Indyk. 2016. LSH Algorithm and Implementation (E2LSH). https:\/\/www.mit.edu\/ andoni\/LSH"},{"key":"e_1_2_1_5_1","first-page":"4772","article-title":"Reward Optimizing Recommendation using Deep Learning and Fast Maximum Inner Product Search","author":"Aouali Imad","year":"2022","unstructured":"Imad Aouali, Amine Benhalloum, Martin Bompaire, Achraf Ait Sidi Hammou, Sergey Ivanov, Benjamin Heymann, David Rohde, Otmane Sakhi, Flavian Vasile, and Maxime Vono. 2022. Reward Optimizing Recommendation using Deep Learning and Fast Maximum Inner Product Search. In KDD. ACM, 4772-4773.","journal-title":"KDD. ACM"},{"key":"e_1_2_1_6_1","first-page":"257","article-title":"Speeding up the Xbox recommender system using a Euclidean transformation for inner-product spaces","author":"Bachrach Yoram","year":"2014","unstructured":"Yoram Bachrach, Yehuda Finkelstein, Ran Gilad-Bachrach, Liran Katzir, Noam Koenigstein, Nir Nice, and Ulrich Paquet. 2014. Speeding up the Xbox recommender system using a Euclidean transformation for inner-product spaces. In RecSys. 257-264.","journal-title":"RecSys."},{"key":"e_1_2_1_7_1","volume-title":"Simple and Efficient ways to Improve REALM. CoRR","author":"Balachandran Vidhisha","year":"2021","unstructured":"Vidhisha Balachandran, Ashish Vaswani, Yulia Tsvetkov, and Niki Parmar. 2021. Simple and Efficient ways to Improve REALM. CoRR, Vol. abs\/2104.08710 (2021)."},{"key":"e_1_2_1_8_1","article-title":"EBK-means: A clustering technique based on elbow method and k-means in WSN","volume":"105","author":"Bholowalia Purnima","year":"2014","unstructured":"Purnima Bholowalia and Arvind Kumar. 2014. EBK-means: A clustering technique based on elbow method and k-means in WSN. International Journal of Computer Applications, Vol. 105, 9 (2014).","journal-title":"International Journal of Computer Applications"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509965"},{"key":"e_1_2_1_10_1","first-page":"26","article-title":"On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product","volume":"25","author":"Chen Lijie","year":"2018","unstructured":"Lijie Chen. 2018. On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product. Electronic Colloquium on Computational Complexity (ECCC), Vol. 25 (2018), 26.","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3725688.3725705"},{"key":"e_1_2_1_12_1","first-page":"5","article-title":"Introduction to the k-means clustering algorithm based on the elbow method","volume":"1","author":"Mengyao Cui","year":"2020","unstructured":"Mengyao Cui et al., 2020. Introduction to the k-means clustering algorithm based on the elbow method. Accounting, Auditing and Finance, Vol. 1, 1 (2020), 5-8.","journal-title":"Accounting, Auditing and Finance"},{"key":"e_1_2_1_13_1","volume-title":"Jiu Liu, and James Cheng.","author":"Dai Xinyan","year":"2020","unstructured":"Xinyan Dai, Xiao Yan, Kelvin Kai Wing Ng, Jiu Liu, and James Cheng. 2020. Norm-Explicit Quantization: Improving Vector Quantization for Maximum Inner Product Search. In AAAI. 51-58."},{"key":"e_1_2_1_14_1","first-page":"6491","article-title":"A Survey on RAG Meeting LLMs","author":"Fan Wenqi","year":"2024","unstructured":"Wenqi Fan, Yujuan Ding, Liangbo Ning, Shijie Wang, Hengyun Li, Dawei Yin, Tat-Seng Chua, and Qing Li. 2024. A Survey on RAG Meeting LLMs: Towards Retrieval-Augmented Large Language Models. In KDD. ACM, 6491-6501.","journal-title":"Towards Retrieval-Augmented Large Language Models. In KDD. ACM"},{"key":"e_1_2_1_15_1","first-page":"1554","article-title":"Indexable Probabilistic Matrix Factorization for Maximum Inner Product Search","author":"Fraccaro Marco","year":"2016","unstructured":"Marco Fraccaro, Ulrich Paquet, and Ole Winther. 2016. Indexable Probabilistic Matrix Factorization for Maximum Inner Product Search. In AAAI. 1554-1560.","journal-title":"AAAI."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/3303753.3303754"},{"key":"e_1_2_1_17_1","first-page":"541","article-title":"Locality-sensitive hashing scheme based on dynamic collision counting","author":"Gan Junhao","year":"2012","unstructured":"Junhao Gan, Jianlin Feng, Qiong Fang, and Wilfred Ng. 2012. Locality-sensitive hashing scheme based on dynamic collision counting. In SIGMOD. 541-552.","journal-title":"SIGMOD."},{"key":"e_1_2_1_18_1","first-page":"518","article-title":"Similarity Search in High Dimensions via Hashing","author":"Gionis Aristides","year":"1999","unstructured":"Aristides Gionis, Piotr Indyk, and Rajeev Motwani. 1999. Similarity Search in High Dimensions via Hashing. In VLDB. 518-529.","journal-title":"VLDB."},{"key":"e_1_2_1_19_1","volume-title":"An Intermediate Course in Probability","author":"Gut Allan","unstructured":"Allan Gut. 2009. The multivariate normal distribution. In An Intermediate Course in Probability. Springer, 117-145."},{"key":"e_1_2_1_20_1","volume-title":"ICML (Proceedings of Machine Learning Research","volume":"3938","author":"Guu Kelvin","year":"2020","unstructured":"Kelvin Guu, Kenton Lee, Zora Tung, Panupong Pasupat, and Ming-Wei Chang. 2020. Retrieval Augmented Language Model Pre-Training. In ICML (Proceedings of Machine Learning Research, Vol. 119). PMLR, 3929-3938."},{"key":"e_1_2_1_21_1","volume-title":"Challenge. CoRR","author":"Han Yikun","year":"2023","unstructured":"Yikun Han, Chunjiang Liu, and Pengfei Wang. 2023. A Comprehensive Survey on Vector Database: Storage and Retrieval Technique, Challenge. CoRR, Vol. abs\/2310.11703 (2023)."},{"key":"e_1_2_1_22_1","first-page":"5713","article-title":"FANNG: Fast Approximate Nearest Neighbour Graphs","author":"Harwood Ben","year":"2016","unstructured":"Ben Harwood and Tom Drummond. 2016. FANNG: Fast Approximate Nearest Neighbour Graphs. In CVPR. IEEE Computer Society, 5713-5722.","journal-title":"CVPR. IEEE Computer Society"},{"key":"e_1_2_1_23_1","first-page":"1561","article-title":"Accurate and Fast Asymmetric Locality-Sensitive Hashing Scheme for Maximum Inner Product Search","author":"Huang Qiang","year":"2018","unstructured":"Qiang Huang, Guihong Ma, Jianlin Feng, Qiong Fang, and Anthony K. H. Tung. 2018. Accurate and Fast Asymmetric Locality-Sensitive Hashing Scheme for Maximum Inner Product Search. In KDD. 1561-1570.","journal-title":"KDD."},{"key":"e_1_2_1_24_1","first-page":"604","article-title":"Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality","author":"Indyk Piotr","year":"1998","unstructured":"Piotr Indyk and Rajeev Motwani. 1998. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. In STOC. 604-613.","journal-title":"STOC."},{"key":"e_1_2_1_25_1","first-page":"873","article-title":"Random maximum margin hashing","author":"Joly Alexis","year":"2011","unstructured":"Alexis Joly and Olivier Buisson. 2011. Random maximum margin hashing. In CVPR. IEEE Computer Society, 873-880.","journal-title":"CVPR. IEEE Computer Society"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064009"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i01.5344"},{"key":"e_1_2_1_28_1","first-page":"950","article-title":"Multi-Probe LSH","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 VLDB. 950-961.","journal-title":"Efficient Indexing for High-Dimensional Similarity Search. In VLDB."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2018.2889473"},{"key":"e_1_2_1_30_1","first-page":"4726","article-title":"Non-metric Similarity Graphs for Maximum Inner Product Search","author":"Morozov Stanislav","year":"2018","unstructured":"Stanislav Morozov and Artem Babenko. 2018. Non-metric Similarity Graphs for Maximum Inner Product Search. In NeurIPS. 4726-4735.","journal-title":"NeurIPS."},{"key":"e_1_2_1_31_1","first-page":"1926","article-title":"On Symmetric and Asymmetric LSHs for Inner Product Search","volume":"37","author":"Neyshabur Behnam","year":"2015","unstructured":"Behnam Neyshabur and Nathan Srebro. 2015. On Symmetric and Asymmetric LSHs for Inner Product Search. In ICML, Vol. 37. 1926-1934.","journal-title":"ICML"},{"key":"e_1_2_1_32_1","unstructured":"Hossein Pishro-Nik. 2014. Introduction to probability statistics and random processes. Kappa Research LLC Blue Bell PA USA."},{"key":"e_1_2_1_33_1","first-page":"4148","article-title":"Learning Binary Codes for Maximum Inner Product Search","author":"Shen Fumin","year":"2015","unstructured":"Fumin Shen, Wei Liu, Shaoting Zhang, Yang Yang, and Heng Tao Shen. 2015. Learning Binary Codes for Maximum Inner Product Search. In ICCV. 4148-4156.","journal-title":"ICCV."},{"key":"e_1_2_1_34_1","volume-title":"Improved Asymmetric Locality Sensitive Hashing (ALSH) for Maximum Inner Product Search (MIPS)","author":"Shrivastava Anshumali","unstructured":"Anshumali Shrivastava. 2015. Improved Asymmetric Locality Sensitive Hashing (ALSH) for Maximum Inner Product Search (MIPS). In UAI. AUAI Press, 812-821."},{"key":"e_1_2_1_35_1","first-page":"2321","article-title":"Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)","author":"Shrivastava Anshumali","year":"2014","unstructured":"Anshumali Shrivastava and Ping Li. 2014. Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS). In NIPS. 2321-2329.","journal-title":"NIPS."},{"key":"e_1_2_1_36_1","first-page":"13748","article-title":"DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node","author":"Subramanya Suhas Jayaram","year":"2019","unstructured":"Suhas Jayaram Subramanya, Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnaswamy, and Rohan Kadekodi. 2019. DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. In NeurIPS. 13748-13758.","journal-title":"NeurIPS."},{"key":"e_1_2_1_37_1","first-page":"1552","article-title":"Norm Adjusted Proximity Graph for Fast Inner Product Retrieval","author":"Tan Shulong","year":"2021","unstructured":"Shulong Tan, Zhaozhuo Xu, Weijie Zhao, Hongliang Fei, Zhixin Zhou, and Ping Li. 2021. Norm Adjusted Proximity Graph for Fast Inner Product Retrieval. In KDD. ACM, 1552-1560.","journal-title":"KDD. ACM"},{"key":"e_1_2_1_38_1","first-page":"5235","article-title":"On Efficient Retrieval of Top Similarity Vectors. In EMNLP\/IJCNLP (1)","author":"Tan Shulong","year":"2019","unstructured":"Shulong Tan, Zhixin Zhou, Zhaozhuo Xu, and Ping Li. 2019. On Efficient Retrieval of Top Similarity Vectors. In EMNLP\/IJCNLP (1). Association for Computational Linguistics, 5235-5245.","journal-title":"Association for Computational Linguistics"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2996452"},{"key":"e_1_2_1_40_1","first-page":"2250","article-title":"DB-LSH","author":"Tian Yao","year":"2022","unstructured":"Yao Tian, Xi Zhao, and Xiaofang Zhou. 2022. DB-LSH: Locality-Sensitive Hashing with Query-based Dynamic Bucketing. In ICDE. 2250-2262.","journal-title":"Locality-Sensitive Hashing with Query-based Dynamic Bucketing. In ICDE."},{"key":"e_1_2_1_41_1","unstructured":"Mo Tiwari Ryan Kang Jaeyong Lee Donghyun Lee Christopher Piech Sebastian Thrun Ilan Shomorony and Martin Jinye Zhang. 2024. Faster Maximum Inner Product Search in High Dimensions. In ICML. OpenReview.net."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781108231596"},{"key":"e_1_2_1_43_1","first-page":"2614","article-title":"Milvus","author":"Wang Jianguo","year":"2021","unstructured":"Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xiangyu Wang, Xiangzhou Guo, Chengming Li, Xiaohai Xu, Kun Yu, Yuxing Yuan, Yinghao Zou, Jiquan Long, Yudong Cai, Zhenxiang Li, Zhifeng Zhang, Yihua Mo, Jun Gu, Ruiyi Jiang, Yi Wei, and Charles Xie. 2021b. Milvus: A Purpose-Built Vector Data Management System. In SIGMOD. ACM, 2614-2627.","journal-title":"A Purpose-Built Vector Data Management System. In SIGMOD. ACM"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476255"},{"key":"e_1_2_1_45_1","first-page":"2956","article-title":"Norm-Ranging LSH for Maximum Inner Product Search","author":"Yan Xiao","year":"2018","unstructured":"Xiao Yan, Jinfeng Li, Xinyan Dai, Hongzhi Chen, and James Cheng. 2018. Norm-Ranging LSH for Maximum Inner Product Search. In NeurIPS. 2956-2965.","journal-title":"NeurIPS."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/3594512.3594527"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/3579075.3579084"},{"key":"e_1_2_1_48_1","first-page":"8216","article-title":"M\u00f6bius Transformation for Fast Inner Product Search on Graph","author":"Zhou Zhixin","year":"2019","unstructured":"Zhixin Zhou, Shulong Tan, Zhaozhuo Xu, and Ping Li. 2019. M\u00f6bius Transformation for Fast Inner Product Search on Graph. In NeurIPS. 8216-8227.","journal-title":"NeurIPS."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3802051","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T18:22:58Z","timestamp":1779128578000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3802051"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,18]]},"references-count":48,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,5,18]]}},"alternative-id":["10.1145\/3802051"],"URL":"https:\/\/doi.org\/10.1145\/3802051","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,18]]}}}