---
title: "Revisiting Wedge Sampling for Budgeted Maximum Inner Product Search (Extended Abstract)"
authors:
  - "Stephan S. Lorenzen"
  - "Ninh Pham"
doi: "10.24963/ijcai.2021/652"
url: "https://ijcai.org/proceedings/2021/652"
pdf: "https://ijcai.org/proceedings/2021/0652.pdf"
venue: "Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence"
year: 2021
pages: "4789-4793"
track: "Sister Conferences Best Papers"
keywords:
  - "Data Mining: Recommender Systems"
  - "Data Mining: Information Retrieval"
---

# 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*, pages 4789-4793. DOI: [10.24963/ijcai.2021/652](https://doi.org/10.24963/ijcai.2021/652)

## 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.