Revisiting Wedge Sampling for Budgeted Maximum Inner Product Search (Extended Abstract)
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.
Cite
Text
Lorenzen and Pham. "Revisiting Wedge Sampling for Budgeted Maximum Inner Product Search (Extended Abstract)." International Joint Conference on Artificial Intelligence, 2021. doi:10.24963/IJCAI.2021/652Markdown
[Lorenzen and Pham. "Revisiting Wedge Sampling for Budgeted Maximum Inner Product Search (Extended Abstract)." International Joint Conference on Artificial Intelligence, 2021.](https://mlanthology.org/ijcai/2021/lorenzen2021ijcai-revisiting/) doi:10.24963/IJCAI.2021/652BibTeX
@inproceedings{lorenzen2021ijcai-revisiting,
title = {{Revisiting Wedge Sampling for Budgeted Maximum Inner Product Search (Extended Abstract)}},
author = {Lorenzen, Stephan Sloth and Pham, Ninh},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2021},
pages = {4789-4793},
doi = {10.24963/IJCAI.2021/652},
url = {https://mlanthology.org/ijcai/2021/lorenzen2021ijcai-revisiting/}
}