검색 기능은 준비 중입니다.
검색 기능은 준비 중입니다.

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

Approximate Nearest Neighbor Search for a Dataset of Normalized Vectors 정규화된 벡터의 데이터세트에 대한 대략적인 최근접 이웃 검색

Kengo TERASAWA, Yuzuru TANAKA

  • 조회수

    0

  • 이것을 인용

요약 :

본 논문에서는 근사 최근접 탐색을 위한 새로운 알고리즘을 설명합니다. 특히 고차원 공간에서 이 문제를 해결하기 위해 가장 잘 알려진 알고리즘 중 하나는 LSH(Locity-Sensitive Hashing)입니다. 본 논문에서는 데이터세트가 패턴 인식에서 자주 발생하는 단위 길이로 정규화된 벡터로 구성될 때 이전에 제안된 방법보다 성능이 뛰어난 LSH 알고리즘의 변형을 제시합니다. LSH 체계는 포인트의 위치를 ​​유지하는 해시 함수 계열을 기반으로 합니다. 이 논문은 특별한 경우의 문제에 대해 초구체의 한 점을 무작위로 회전하는 정다포체의 가장 가까운 꼭지점에 매핑하는 효율적인 해시 함수를 설계할 수 있음을 지적합니다. 전산분석을 통해 제안한 방법이 LSH 알고리즘 성능의 주요 지표인 지수 ρ를 향상시킬 수 있음을 확인하였다. 실제 실험은 또한 시간과 공간 모두에서 우리 알고리즘의 효율성을 지원했습니다.

발행
IEICE TRANSACTIONS on Information Vol.E92-D No.9 pp.1609-1619
발행일
2009/09/01
공개일
온라인 ISSN
1745-1361
DOI
10.1587/transinf.E92.D.1609
원고의 종류
PAPER
범주
알고리즘 이론

작성자

키워드