A Bandit Approach to Maximum Inner Product Search

2018-12-15 · Rui Liu, Tianyi Wu, Barzan Mozafari

There has been substantial research on sub-linear time approximate algorithms for Maximum Inner Product Search (MIPS). To achieve fast query time, state-of-the-art techniques require significant preprocessing, which can be a burden when the number of subsequent queries is not sufficiently large to amortize the cost. Furthermore, existing methods do not have the ability to directly control the suboptimality of their approximate results with theoretical guarantees. In this paper, we propose the first approximate algorithm for MIPS that does not require any preprocessing, and allows users to control and bound the suboptimality of the results. We cast MIPS as a Best Arm Identification problem, and introduce a new bandit setting that can fully exploit the special structure of MIPS. Our approach outperforms state-of-the-art methods on both synthetic and real-world datasets.

📄 PDF Abstract BibTeX arXiv:1812.06360

Code (0)

등록된 구현이 없습니다.

Faster Maximum Inner Product Search in High Dimensions

2022-12-14 · Mo Tiwari, Ryan Kang, Je-Yong Lee, DongHyun Lee 외

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 th…

Multi-Armed Bandits Recommendation Systems Vocal Bursts Intensity Prediction

Reinforcement Routing on Proximity Graph for Efficient Recommendation

2022-01-23 · Chao Feng, Defu Lian, Xiting Wang, Zheng Liu 외

We focus on Maximum Inner Product Search (MIPS), which is an essential problem in many machine learning communities. Given a query, MIPS finds the most similar items with the maximum inner products. Methods for Nearest N…

Imitation Learning Recommendation Systems

New Loss Functions for Fast Maximum Inner Product Search

2020-01-01 · ICLR 2020 1 · Ruiqi Guo, Quan Geng, David Simcha, Felix Chern 외

Quantization based methods are popular for solving large scale maximum inner product search problems. However, in most traditional quantization works, the objective is to minimize the reconstruction error for datapoints …

Benchmarking Quantization

Learning Binary Codes for Maximum Inner Product Search

2015-12-01 · ICCV 2015 12 · Fumin Shen, Wei Liu, Shaoting Zhang, Yang Yang 외

Binary coding or hashing techniques are recognized to accomplish efficient near neighbor search, and have thus attracted broad interests in the recent vision and learning studies. However, such studies have rarely been d…

SAH: Shifting-aware Asymmetric Hashing for Reverse $k$-Maximum Inner Product Search

2022-11-23 · Qiang Huang, Yanhao Wang, Anthony K. H. Tung

This paper investigates a new yet challenging problem called Reverse $k$-Maximum Inner Product Search (R$k$MIPS). Given a query (item) vector, a set of item vectors, and a set of user vectors, the problem of R$k$MIPS aim…

Blocking