QSRP: Efficient Reverse $k-\text{Ranks}$ Query Processing on High-Dimensional Embeddings

Zheng Bian1,2; Xiao Yan2; Jiahao Zhang3; Man Lung Yiu1; Bo Tang2

10.1109/ICDE60146.2024.00351

2024-05-16

1063-6382

979-8-3503-1716-9

2024 IEEE 40th International Conference on Data Engineering (ICDE)

13-16 May 2024

Utrecht, Netherlands

Embedding models represent users and products as high-dimensional embedding vectors and are widely used for recommendation. In this paper, we study the reverse $k-\mathbf{ranks}$ query, which finds the users that are the most interested in a product and has many applications including product promotion, targeted advertising, and market analysis. As reverse $k-\mathbf{ranks}$ solutions for low dimensionality (e.g., trees) fail for the high-dimensional embeddings generated by embedding models, we propose the QSRP framework. QSRP precomputes the score table between all user and product embeddings to facilitate pruning and refinement at query time. As the score table is usually large, QSRP samples some of its columns as the index to fit in memory. To tackle the problem that naive uniform sampling results in poor pruning effect, we propose query-aware sampling, which conducts sampling by explicitly maximizing the pruning effect for a set of sample queries. Moreover, we introduce regression-based pruning, which fits cheap linear functions to predict the bounds used for pruning. We also design techniques to build the index with limited memory, reduce index building time, and handle updates. We evaluate QSRP under various configurations and compare with state-of-the-art baselines. The results show that QSRP achieves shorter query time than the baselines in all cases, and the speedup is usually over 100x.

其他

EI

1.Department of Computing, The Hong Kong Polytechnic University
2.Department of Computer Science and Engineering, Southern University of Science and Technology
3.Huawei Technologies Co., Ltd.

Zheng Bian,Xiao Yan,Jiahao Zhang,et al. QSRP: Efficient Reverse $k-\text{Ranks}$ Query Processing on High-Dimensional Embeddings[C],2024.