Diversity-Aware k-Maximum Inner Product Search Revisited
CoRR(2024)
摘要
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
Greedy and DualGreedy, two linear scan-based algorithms
tailored for DkMIPS. They both achieve data-dependent approximations and,
when aiming to minimize the average pairwise similarity, DualGreedy
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.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要