Proceedings

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

Stephan S. Lorenzen, Ninh Pham

Download BibTeX Cite

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

Keywords

  • Data Mining: Recommender Systems
  • Data Mining: Information Retrieval

Abstract

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.

Stephan S. Lorenzen, and Ninh Pham. 2021. Revisiting Wedge Sampling for Budgeted Maximum Inner Product Search (Extended Abstract). In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 4789–4793. https://doi.org/10.24963/ijcai.2021/652
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards