Publications
JOURNAL (INTERNATIONAL) Categorical Diversity-Aware Inner Product Search
KOHEI HIRATA (Osaka univ.), DAICHI AMAGATA (Osaka univ.), SUMIO FUJITA, TAKAHIRO HARA (Osaka univ.)
IEEE Access (IEEE Access)
January 04, 2023
In modern machine learning systems, objects, such as users and items, are represented by dense high-dimensional vectors in an inner product space by using embedding techniques. Then, the problem of maximum inner product search is one of the most important components in these systems, because it retrieves (or infers) relevant vectors to a given query vector. Existing works dedicated to this problem to support large-scale systems. Unfortunately, this problem considers only inner products and does not care about diversity, although result diversification can improve user satisfaction. This paper considers categorical diversification and formulates a new problem, namely the categorical diversity-aware IPS problem. Solving this problem exactly needs O(n) time, where n is the number of vectors, and is not efficient for large n. We hence devise 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 efficiency and accuracy of our algorithm.
Paper :
Categorical Diversity-Aware Inner Product Search
(external link)