# Diversity-Aware k-Maximum Inner Product Search Revisited

arXiv: https://arxiv.org/abs/2402.13858 · HTML: https://mlsanity.com/paper/2402.13858/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Feb 2024.

## Built on by (most cited first, 7 of 7)

- [Position: Text Embeddings Should Capture Implicit Semantics, Not Just Surface Meaning](https://mlsanity.com/paper/2506.08354/) (2025)
- [PRISM: A Framework for Producing Interpretable Political Bias Embeddings with Political-Aware Cross-Encoder](https://mlsanity.com/paper/2505.24646/) (2025)
- [Uncovering the Bigger Picture: Comprehensive Event Understanding Via Diverse News Retrieval](https://mlsanity.com/paper/2508.19758/) (2025)
- [Measuring Social Bias in Vision-Language Models with Face-Only Counterfactuals from Real Photos](https://mlsanity.com/paper/2601.06931/) (2026)
- [Very Efficient Listwise Multimodal Reranking for Long Documents](https://mlsanity.com/paper/2605.11864/) (2026)
- [Isometry pursuit](https://mlsanity.com/paper/2411.18502/) (2024)
- [Approximate Diverse k-nearest Neighbor Search in Vector Database](https://mlsanity.com/paper/2510.27243/) (2025)

## Abstract (arXiv)

The k-Maximum Inner Product Search (kMIPS) serves as a foundational component in recommender systems and various data mining tasks. However, while most existing kMIPS approaches prioritize the efficient retrieval of highly relevant items for users, they often neglect an equally pivotal facet of search results: diversity. To bridge this gap, we revisit and refine the diversity-aware kMIPS (DkMIPS) problem by incorporating two well-known diversity objectives -- minimizing the average and maximum pairwise item similarities within the results -- into the original relevance objective. This enhancement, inspired by Maximal Marginal Relevance (MMR), offers users a controllable trade-off between relevance and diversity. We introduce textscGreedy and textscDualGreedy, two linear scan-based algorithms tailored for DkMIPS. They both achieve data-dependent approximations and, when aiming to minimize the average pairwise similarity, textscDualGreedy attains an approximation ratio of 1/4 with an additive term for regularization. To further improve query efficiency, we integrate a lightweight Ball-Cone Tree (BC-Tree) index with the two algorithms. Finally, comprehensive experiments on ten real-world data sets demonstrate the efficacy of our proposed methods, showcasing their capability to efficiently deliver diverse and relevant search results to users.