تقرير
Faster Maximum Inner Product Search in High Dimensions
| العنوان: | Faster Maximum Inner Product Search in High Dimensions |
|---|---|
| المؤلفون: | Tiwari, Mo, Kang, Ryan, Lee, Je-Yong, Lee, Donghyun, Piech, Chris, Thrun, Sebastian, Shomorony, Ilan, Zhang, Martin Jinye |
| سنة النشر: | 2022 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Machine Learning, Computer Science - Artificial Intelligence |
| الوصف: | Maximum Inner Product Search (MIPS) is a ubiquitous task in machine learning applications such as recommendation systems. Given a query vector and $n$ atom vectors in $d$-dimensional space, the goal of MIPS is to find the atom that has the highest inner product with the query vector. Existing MIPS algorithms scale at least as $O(\sqrt{d})$, which becomes computationally prohibitive in high-dimensional settings. In this work, we present BanditMIPS, a novel randomized MIPS algorithm whose complexity is independent of $d$. BanditMIPS estimates the inner product for each atom by subsampling coordinates and adaptively evaluates more coordinates for more promising atoms. The specific adaptive sampling strategy is motivated by multi-armed bandits. We provide theoretical guarantees that BanditMIPS returns the correct answer with high probability, while improving the complexity in $d$ from $O(\sqrt{d})$ to $O(1)$. We also perform experiments on four synthetic and real-world datasets and demonstrate that BanditMIPS outperforms prior state-of-the-art algorithms. For example, in the Movie Lens dataset ($n$=4,000, $d$=6,000), BanditMIPS is 20$\times$ faster than the next best algorithm while returning the same answer. BanditMIPS requires no preprocessing of the data and includes a hyperparameter that practitioners may use to trade off accuracy and runtime. We also propose a variant of our algorithm, named BanditMIPS-$\alpha$, which achieves further speedups by employing non-uniform sampling across coordinates. Finally, we demonstrate how known preprocessing techniques can be used to further accelerate BanditMIPS, and discuss applications to Matching Pursuit and Fourier analysis. Comment: 24 pages |
| نوع الوثيقة: | Working Paper |
| الوصول الحر: | http://arxiv.org/abs/2212.07551Test |
| رقم الانضمام: | edsarx.2212.07551 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |