Approximate Nearest Neighbor Search for a Dataset of Normalized Vectors

Kengo TERASAWA; Yuzuru TANAKA

doi:10.1587/transinf.E92.D.1609

Approximate Nearest Neighbor Search for a Dataset of Normalized Vectors

Kengo TERASAWA, Yuzuru TANAKA

Full Text Views

0

Cite this

Summary :

This paper describes a novel algorithm for approximate nearest neighbor searching. For solving this problem especially in high dimensional spaces, one of the best-known algorithm is Locality-Sensitive Hashing (LSH). This paper presents a variant of the LSH algorithm that outperforms previously proposed methods when the dataset consists of vectors normalized to unit length, which is often the case in pattern recognition. The LSH scheme is based on a family of hash functions that preserves the locality of points. This paper points out that for our special case problem we can design efficient hash functions that map a point on the hypersphere into the closest vertex of the randomly rotated regular polytope. The computational analysis confirmed that the proposed method could improve the exponent ρ, the main indicator of the performance of the LSH algorithm. The practical experiments also supported the efficiency of our algorithm both in time and in space.

Publication: IEICE TRANSACTIONS on Information Vol.E92-D No.9 pp.1609-1619

Publication Date: 2009/09/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1587/transinf.E92.D.1609

Type of Manuscript: PAPER

Category: Algorithm Theory

Cite this

Copy

Kengo TERASAWA, Yuzuru TANAKA, "Approximate Nearest Neighbor Search for a Dataset of Normalized Vectors" in IEICE TRANSACTIONS on Information, vol. E92-D, no. 9, pp. 1609-1619, September 2009, doi: 10.1587/transinf.E92.D.1609.
Abstract: This paper describes a novel algorithm for approximate nearest neighbor searching. For solving this problem especially in high dimensional spaces, one of the best-known algorithm is Locality-Sensitive Hashing (LSH). This paper presents a variant of the LSH algorithm that outperforms previously proposed methods when the dataset consists of vectors normalized to unit length, which is often the case in pattern recognition. The LSH scheme is based on a family of hash functions that preserves the locality of points. This paper points out that for our special case problem we can design efficient hash functions that map a point on the hypersphere into the closest vertex of the randomly rotated regular polytope. The computational analysis confirmed that the proposed method could improve the exponent ρ, the main indicator of the performance of the LSH algorithm. The practical experiments also supported the efficiency of our algorithm both in time and in space.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E92.D.1609/_p

Copy

@ARTICLE{e92-d_9_1609,
author={Kengo TERASAWA, Yuzuru TANAKA, },
journal={IEICE TRANSACTIONS on Information},
title={Approximate Nearest Neighbor Search for a Dataset of Normalized Vectors},
year={2009},
volume={E92-D},
number={9},
pages={1609-1619},
abstract={This paper describes a novel algorithm for approximate nearest neighbor searching. For solving this problem especially in high dimensional spaces, one of the best-known algorithm is Locality-Sensitive Hashing (LSH). This paper presents a variant of the LSH algorithm that outperforms previously proposed methods when the dataset consists of vectors normalized to unit length, which is often the case in pattern recognition. The LSH scheme is based on a family of hash functions that preserves the locality of points. This paper points out that for our special case problem we can design efficient hash functions that map a point on the hypersphere into the closest vertex of the randomly rotated regular polytope. The computational analysis confirmed that the proposed method could improve the exponent ρ, the main indicator of the performance of the LSH algorithm. The practical experiments also supported the efficiency of our algorithm both in time and in space.},
keywords={},
doi={10.1587/transinf.E92.D.1609},
ISSN={1745-1361},
month={September},}

Copy

TY - JOUR
TI - Approximate Nearest Neighbor Search for a Dataset of Normalized Vectors
T2 - IEICE TRANSACTIONS on Information
SP - 1609
EP - 1619
AU - Kengo TERASAWA
AU - Yuzuru TANAKA
PY - 2009
DO - 10.1587/transinf.E92.D.1609
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E92-D
IS - 9
JA - IEICE TRANSACTIONS on Information
Y1 - September 2009
AB - This paper describes a novel algorithm for approximate nearest neighbor searching. For solving this problem especially in high dimensional spaces, one of the best-known algorithm is Locality-Sensitive Hashing (LSH). This paper presents a variant of the LSH algorithm that outperforms previously proposed methods when the dataset consists of vectors normalized to unit length, which is often the case in pattern recognition. The LSH scheme is based on a family of hash functions that preserves the locality of points. This paper points out that for our special case problem we can design efficient hash functions that map a point on the hypersphere into the closest vertex of the randomly rotated regular polytope. The computational analysis confirmed that the proposed method could improve the exponent ρ, the main indicator of the performance of the LSH algorithm. The practical experiments also supported the efficiency of our algorithm both in time and in space.
ER -