Revisiting Wedge Sampling for Budgeted Maximum Inner Product Search (Extended Abstract)

Revisiting Wedge Sampling for Budgeted Maximum Inner Product Search (Extended Abstract)

Stephan S. Lorenzen, Ninh Pham

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence
Sister Conferences Best Papers. Pages 4789-4793. https://doi.org/10.24963/ijcai.2021/652

Top-k maximum inner product search (MIPS) is a central task in many machine learning applications. This work extends top-k MIPS with a budgeted setting, that asks for the best approximate top-k MIPS given a limited budget of computational operations. We study recent advanced sampling methods, including wedge and diamond sampling, to solve budgeted top-k MIPS. First, we theoretically show that diamond sampling is essentially a combination of wedge sampling and basic sampling for top-k MIPS. Second, we propose dWedge, a simple deterministic variant of wedge sampling for budgeted top-k MIPS. Empirically, dWedge provides significantly higher accuracy than other budgeted top-k MIPS solvers while maintaining a similar speedup.
Keywords:
Data Mining: Information Retrieval
Data Mining: Recommender Systems