Categorical Diversity-Aware Inner Product Search

The problem of maximum inner product search (MIPS) is one of the most important components in machine learning systems. However, this problem does not care about diversity, although result diversification can improve user satisfaction. This paper hence considers a new problem, namely the categorical diversity-aware IPS problem, in which users can select preferable categories. Exactly solving this problem needs O(n) time, where n is the number of vectors, and is not efficient for large n. We hence propose an approximation algorithm that has a probabilistic success guarantee and runs in sub-linear time to n. We conduct extensive experiments on real datasets, and the results demonstrate the superior performance of our algorithm to that of a baseline using an existing MIPS technique.

Automated summary

The problem of maximum inner product search (MIPS) is essential in machine learning systems. However, it lacks consideration for diversity despite its ability to improve user satisfaction. This study introduces a new problem, the categorical diversity-aware IPS problem, where users can select preferred categories. We propose an approximation algorithm that has a probabilistic success guarantee and commendable efficiency for large-scale data, outperforming a baseline MIPS technique according to extensive experiments on real datasets.