Promips: Efficient High-dimensional C-approximate Maximum Inner Product Search With A Lightweight Index

Abstract

Due to the wide applications in recommendation systems, multi-class label prediction and deep learning, the Maximum Inner Product (MIP) search problem has received extensive attention in recent years. Faced with large-scale datasets containing high-dimensional feature vectors, the state-of-the-art LSH-based methods usually require a large number of hash tables or long hash codes to ensure the searching quality, which takes up lots of index space and causes excessive disk page accesses. In this paper, we relax the guarantee of accuracy for efficiency and propose an efficient method for c-Approximate Maximum Inner Product (c-AMIP) search with a lightweight iDistance index. We project high-dimensional points to low-dimensional ones via 2-stable random projections and derive probability-guaranteed searching conditions, by which the c-AMIP results can be guaranteed in accuracy with arbitrary probabilities. To further improve the efficiency, we propose Quick-Probe for quickly determining the

Stats

• citations12
• S2 citations—
• github stars0
• HF likes0
• heat score8.35
• arxiv keysong2021promips

Related papers

• To Index Or Not To Index: Optimizing Exact Maximum Inner Product Search (2017)8.35
• PM-LSH: A Fast And Accurate In-memory Framework For High-dimensional Approximate NN And Closest Pair Search (2021)8.09
• Bridging Dense And Sparse Maximum Inner Product Search (2023)6.34
• SINDI: An Efficient Index For Approximate Maximum Inner Product Search On Sparse Vectors (2025)0.00
• SAH: Shifting-aware Asymmetric Hashing For Reverse \(k\)-maximum Inner Product Search (2022)6.21
• Optimistic Query Routing In Clustering-based Approximate Maximum Inner Product Search (2024)0.00
• Norm-range Partition: A Universal Catalyst For LSH Based Maximum Inner Product Search (MIPS) (2018)0.00
• Improving Locality Sensitive Hashing By Efficiently Finding Projected Nearest Neighbors (2020)6.77