The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
본 논문에서는 근사 최근접 탐색을 위한 새로운 알고리즘을 설명합니다. 특히 고차원 공간에서 이 문제를 해결하기 위해 가장 잘 알려진 알고리즘 중 하나는 LSH(Locity-Sensitive Hashing)입니다. 본 논문에서는 데이터세트가 패턴 인식에서 자주 발생하는 단위 길이로 정규화된 벡터로 구성될 때 이전에 제안된 방법보다 성능이 뛰어난 LSH 알고리즘의 변형을 제시합니다. LSH 체계는 포인트의 위치를 유지하는 해시 함수 계열을 기반으로 합니다. 이 논문은 특별한 경우의 문제에 대해 초구체의 한 점을 무작위로 회전하는 정다포체의 가장 가까운 꼭지점에 매핑하는 효율적인 해시 함수를 설계할 수 있음을 지적합니다. 전산분석을 통해 제안한 방법이 LSH 알고리즘 성능의 주요 지표인 지수 ρ를 향상시킬 수 있음을 확인하였다. 실제 실험은 또한 시간과 공간 모두에서 우리 알고리즘의 효율성을 지원했습니다.
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.
부
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
부
@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},}
부
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 -