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

Summary: Analyzes AMIPS norm bias as norm domination and introduces Norm-Adaptive Partitioning (NAP): exhaustive Head, graph-indexed Body, and safely pruned Tail. A hybrid index cuts graph size by >50% and delivers >2× speedup at equal recall. (summarized by gpt-5.6-luna on Jul 26 2026)

Paper ID: 7424
Venue: SIGMOD
Year: 2026
Pagerank: 5.093636e-05
Overall Rank: 10,233 | 29.80%
DOI: 10.1145/3802051

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Xi Zhao (Hong Kong University of Science and Technology)
2. Zhoujin Tian (Hong Kong University of Science and Technology)
3. Kai Huang (East China Normal University)
4. Yao Tian (Hong Kong University of Science and Technology)
5. Xiaokui Xiao (National University of Singapore)
6. Bolong Zheng (Wuhan University)
7. Xiaofang Zhou (Hong Kong University of Science and Technology)

BibTeX Citation

@inproceedings{zhao_sigmod26,
        title = {{Enhancing Graph-based Approximate Maximum Inner Product Search via Norm-Adaptive Partitioning}},
        author = {Zhao, Xi and Tian, Zhoujin and Huang, Kai and Tian, Yao and Xiao, Xiaokui and Zheng, Bolong and Zhou, Xiaofang},
        series = {{SIGMOD} '26},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3802051},
        url = {https://dl.acm.org/doi/10.1145/3802051},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
21	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00056760516
93	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00034701237
286	Milvus: A Purpose-Built Vector Data Management System	2021	SIGMOD	0.00022357911
287	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search	2007	VLDB	0.00022323585
369	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.00019945234
398	A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search	2021	VLDB	0.00019194947
1,934	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB	9.4561907e-05
2,938	FEXIPRO: Fast and Exact Inner Product Retrieval in Recommender Systems	2017	SIGMOD	7.942728e-05
3,806	On the Complexity of Inner Product Similarity Join	2016	PODS	7.108802e-05
5,223	FARGO: Fast Maximum Inner Product Search via Global Multi-Probing	2023	VLDB	6.3102417e-05
6,851	Maximum Inner Product is Query-Scaled Nearest Neighbor	2025	VLDB	5.7546877e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,052	Fast Approximate Similarity Join in Vector Databases	2025	SIGMOD
2	93	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB
3	398	A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search	2021	VLDB
4	5,965	Answering Top-k Representative Queries on Graph Databases	2014	SIGMOD
5	10,364	Efficient Approximate Nearest Neighbor Search via Hemi-Sphere Centroids Graph	2026	SIGMOD
6	9,892	Accelerating Approximate Nearest Neighbor Search in Hierarchical Graphs: Efficient Level Navigation with Shortcuts	2025	VLDB
7	1,244	Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases	2023	SIGMOD
8	10,227	Efficient Index Layout and Search Strategy for Large-scale High-dimensional Vector Similarity Search	2026	SIGMOD
9	1,934	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB
10	6,851	Maximum Inner Product is Query-Scaled Nearest Neighbor	2025	VLDB