IEICE TRANSACTIONS on Information
AdaLSH: Adaptive LSH for Solving c-Approximate Maximum Inner Product Search Problem
Summary :
Maximum inner product search (MIPS) problem has gained much attention in a wide range of applications. In order to overcome the curse of dimensionality in high-dimensional spaces, most of existing methods first transform the MIPS problem into another approximate nearest neighbor search (ANNS) problem and then solve it by Locality Sensitive Hashing (LSH). However, due to the error incurred by the transmission and incomprehensive search strategies, these methods suffer from low precision and have loose probability guarantees. In this paper, we propose a novel search method named Adaptive-LSH (AdaLSH) to solve MIPS problem more efficiently and more precisely. AdaLSH examines objects in the descending order of both norms and (the probably correctly estimated) cosine angles with a query object in support of LSH with extendable windows. Such extendable windows bring not only efficiency in searching but also the probability guarantee of finding exact or approximate MIP objects. AdaLSH gives a better probability guarantee of success than those in conventional algorithms, bringing less running times on various datasets compared with them. In addition, AdaLSH can even support exact MIPS with probability guarantee.
- Publication
- IEICE TRANSACTIONS on Information Vol.E104-D No.1 pp.138-145
- Publication Date
- 2021/01/01
- Publicized
- 2020/10/13
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2020EDP7132
- Type of Manuscript
- PAPER
- Category
- Data Engineering, Web Information Systems
Authors
Kejing LU
Graduate School of Information Science and Technology, Hokkaido University
Mineichi KUDO
Graduate School of Information Science and Technology, Hokkaido University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Kejing LU, Mineichi KUDO, "AdaLSH: Adaptive LSH for Solving c-Approximate Maximum Inner Product Search Problem" in IEICE TRANSACTIONS on Information,
vol. E104-D, no. 1, pp. 138-145, January 2021, doi: 10.1587/transinf.2020EDP7132.
Abstract: Maximum inner product search (MIPS) problem has gained much attention in a wide range of applications. In order to overcome the curse of dimensionality in high-dimensional spaces, most of existing methods first transform the MIPS problem into another approximate nearest neighbor search (ANNS) problem and then solve it by Locality Sensitive Hashing (LSH). However, due to the error incurred by the transmission and incomprehensive search strategies, these methods suffer from low precision and have loose probability guarantees. In this paper, we propose a novel search method named Adaptive-LSH (AdaLSH) to solve MIPS problem more efficiently and more precisely. AdaLSH examines objects in the descending order of both norms and (the probably correctly estimated) cosine angles with a query object in support of LSH with extendable windows. Such extendable windows bring not only efficiency in searching but also the probability guarantee of finding exact or approximate MIP objects. AdaLSH gives a better probability guarantee of success than those in conventional algorithms, bringing less running times on various datasets compared with them. In addition, AdaLSH can even support exact MIPS with probability guarantee.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2020EDP7132/_p
Copy
@ARTICLE{e104-d_1_138,
author={Kejing LU, Mineichi KUDO, },
journal={IEICE TRANSACTIONS on Information},
title={AdaLSH: Adaptive LSH for Solving c-Approximate Maximum Inner Product Search Problem},
year={2021},
volume={E104-D},
number={1},
pages={138-145},
abstract={Maximum inner product search (MIPS) problem has gained much attention in a wide range of applications. In order to overcome the curse of dimensionality in high-dimensional spaces, most of existing methods first transform the MIPS problem into another approximate nearest neighbor search (ANNS) problem and then solve it by Locality Sensitive Hashing (LSH). However, due to the error incurred by the transmission and incomprehensive search strategies, these methods suffer from low precision and have loose probability guarantees. In this paper, we propose a novel search method named Adaptive-LSH (AdaLSH) to solve MIPS problem more efficiently and more precisely. AdaLSH examines objects in the descending order of both norms and (the probably correctly estimated) cosine angles with a query object in support of LSH with extendable windows. Such extendable windows bring not only efficiency in searching but also the probability guarantee of finding exact or approximate MIP objects. AdaLSH gives a better probability guarantee of success than those in conventional algorithms, bringing less running times on various datasets compared with them. In addition, AdaLSH can even support exact MIPS with probability guarantee.},
keywords={},
doi={10.1587/transinf.2020EDP7132},
ISSN={1745-1361},
month={January},}
Copy
TY - JOUR
TI - AdaLSH: Adaptive LSH for Solving c-Approximate Maximum Inner Product Search Problem
T2 - IEICE TRANSACTIONS on Information
SP - 138
EP - 145
AU - Kejing LU
AU - Mineichi KUDO
PY - 2021
DO - 10.1587/transinf.2020EDP7132
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E104-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 2021
AB - Maximum inner product search (MIPS) problem has gained much attention in a wide range of applications. In order to overcome the curse of dimensionality in high-dimensional spaces, most of existing methods first transform the MIPS problem into another approximate nearest neighbor search (ANNS) problem and then solve it by Locality Sensitive Hashing (LSH). However, due to the error incurred by the transmission and incomprehensive search strategies, these methods suffer from low precision and have loose probability guarantees. In this paper, we propose a novel search method named Adaptive-LSH (AdaLSH) to solve MIPS problem more efficiently and more precisely. AdaLSH examines objects in the descending order of both norms and (the probably correctly estimated) cosine angles with a query object in support of LSH with extendable windows. Such extendable windows bring not only efficiency in searching but also the probability guarantee of finding exact or approximate MIP objects. AdaLSH gives a better probability guarantee of success than those in conventional algorithms, bringing less running times on various datasets compared with them. In addition, AdaLSH can even support exact MIPS with probability guarantee.
ER -
English
