EUVIMEDEUVIMED entdecken
Crossref

Enhancing Graph-based Approximate Maximum Inner Product Search via Norm-Adaptive Partitioning

Xi Zhao, Zhoujin Tian, Kai Huang, Yao Tian, Xiaokui Xiao, Bolong Zheng, Xiaofang Zhou

Proceedings of the ACM on Management of Data · 18.05.2026 · 4 (3) · 1-26

DOI: 10.1145/3802051 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 18.05.2026. Verfasst von Xi Zhao und 6 weiteren Autor:innen. Die Arbeit nennt 48 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The rapid development of vector databases and large language models has significantly increased the importance of the Approximate Maximum Inner Product Search (AMIPS) 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 norm domination 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 ead , B ody , and T ail based on vector norms. The H ead contains a small number of large-norm vectors for exhaustive search; the T ail includes small-norm vectors that can be safely pruned under accuracy bounds; and the B ody , 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 ail , H ead , and B ody . 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.

Zitieren

APA

Zhao, X., Tian, Z., Huang, K., Tian, Y., Xiao, X., Zheng, B., & Zhou, X. (2026). Enhancing Graph-based Approximate Maximum Inner Product Search via Norm-Adaptive Partitioning. Proceedings of the ACM on Management of Data, 4(3), 1-26. https://doi.org/10.1145/3802051

Vancouver

Zhao X, Tian Z, Huang K, Tian Y, Xiao X, Zheng B, et al. Enhancing Graph-based Approximate Maximum Inner Product Search via Norm-Adaptive Partitioning. Proceedings of the ACM on Management of Data. 2026;4(3):1-26. doi:10.1145/3802051

BibTeX
@article{Zhao2026,
  author = {Zhao, Xi and Tian, Zhoujin and Huang, Kai and Tian, Yao and Xiao, Xiaokui and Zheng, Bolong and Zhou, Xiaofang},
  title = {Enhancing Graph-based Approximate Maximum Inner Product Search via Norm-Adaptive Partitioning},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2026},
  volume = {4},
  number = {3},
  pages = {1--26},
  doi = {10.1145/3802051}
}
Kostenlos starten →