NeurIPS 2019poster68 citations
Möbius Transformation for Fast Inner Product Search on Graph
Zhixin Zhou, Shulong Tan, Zhaozhuo Xu, Ping Li
Abstract
We present a fast search on graph algorithm for Maximum Inner Product Search (MIPS). This optimization problem is challenging since traditional Approximate Nearest Neighbor (ANN) search methods may not perform efficiently in the non-metric similarity measure. Our proposed method is based on the property that Möbius transformation introduces an isomorphism between a subgraph of l^2-Delaunay graph and Delaunay graph for inner product. Under this observation, we propose a simple but novel graph indexing and searching algorithm to find the optimal solution with the largest inner product with the query. Experiments show our approach leads to significant improvements compared to existing methods.
BibTeX
@inproceedings{NEURIPS2019_0fd7e4f4,
author = {Zhou, Zhixin and Tan, Shulong and Xu, Zhaozhuo and Li, Ping},
booktitle = {Advances in Neural Information Processing Systems},
editor = {H. Wallach and H. Larochelle and A. Beygelzimer and F. d\textquotesingle Alch\'{e}-Buc and E. Fox and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {M\"{o}bius Transformation for Fast Inner Product Search on Graph},
url = {https://proceedings.neurips.cc/paper_files/paper/2019/file/0fd7e4f42a8b4b4ef33394d35212b13e-Paper.pdf},
volume = {32},
year = {2019}
}