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
Makalah ini menerangkan algoritma baru untuk anggaran carian jiran terdekat. Untuk menyelesaikan masalah ini terutamanya dalam ruang dimensi tinggi, salah satu algoritma yang paling terkenal ialah Locality-Sensitive Hashing (LSH). Makalah ini membentangkan varian algoritma LSH yang mengatasi kaedah yang dicadangkan sebelum ini apabila set data terdiri daripada vektor yang dinormalkan kepada panjang unit, yang selalunya berlaku dalam pengecaman corak. Skim LSH adalah berdasarkan keluarga fungsi cincang yang mengekalkan lokaliti mata. Makalah ini menunjukkan bahawa untuk masalah kes khas kami, kami boleh mereka bentuk fungsi cincang yang cekap yang memetakan titik pada hipersfera ke puncak terdekat politop biasa yang diputar secara rawak. Analisis pengiraan mengesahkan bahawa kaedah yang dicadangkan boleh meningkatkan eksponen ρ, penunjuk utama prestasi algoritma LSH. Eksperimen praktikal juga menyokong kecekapan algoritma kami dalam masa dan dalam ruang.
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.
Salinan
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
Salinan
@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},}
Salinan
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 -