The search functionality is under construction.

The search functionality is under construction.

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

Kejing LU

Graduate School of Information Science and Technology, Hokkaido University

Mineichi KUDO

Graduate School of Information Science and Technology, Hokkaido University

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.

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 -