사용자:Sungyup Kim/연습장

근사 근접 이웃(Approximate nearest neighbor)[편집]

몇몇 어플리케이션들에서는 최근접 이웃을 통해 "좋은 추론"을 하는 것이 용인된다. 이런 경우들에 있어서, 우리는 모든 경우에 있어서 속도의 향상과 메모리의 절약을 위해 실제의 최근접 이웃의 반환을 보장해주지 않는 알고리즘을 사용할 수 있다. 대개 이런 알고리즘은 대부분의 경우에 있어서 최근접 이웃을 찾아주지만, 이것은 질의된 데이터셋에 매우 강하게 의존한다.

근사 근접 이웃 탐색(approximate nearest neighbor search)을 지원하는 알고리즘들은 지역 민감 해싱, best bin first, balanced box-decomposition tree에 기반을 둔 검색을 포함한다.^[1]

최근접 이웃 거리 비율(Nearest neighbor distance ratio)[편집]

최인접 거리 비율은 원래 노드로부터 challenger neighbor까지의 direct distance를 사용하지 않지만 그것의 비율은 예전의 이웃과의 거리의 비율에 의지한다. 이것은 극소 특징점(local features)들의 유사성을 이용하여 예시 질의(query by example)를 통해 사진들을 추출하기 위한 CBIR에 사용된다. 더 일반적으로, 이것은 여러 형식 일치 문제에 적용된다.

Fixed-radius 근접 이웃(Fixed-radius near neighbors)[편집]

Fixed-radius near neighbors은 특정한 점으로부터 주어진 거리 이내의 유클리드 공간에 주어진 모든 점들을 효율적으로 찾는 문제이다. 이 데이터구조는 고정된 거리에 작용해야하지만, 점의 질의(query point)는 임의여도 된다.

모든 최근접 이웃(All nearest neighbors)[편집]

어떤 어플리케이션들에서는(예 : entropy estimation) 우리는 N 개의 데이터 점들을 가지고, 어떤 모든 N개의 점들중 한 점이 근접 이웃인지 알고 싶을 수 있다. 이것은 물론 모든 점에 있어서 최근접 이웃 탐색을 실행하는 것으로 수행될 수 있지만, 더 효율적인 탐색을 이뤄내기 위해 이 N개의 쿼리의 불필요한 중복된 정보들을 이용(exploit)한 알고리즘이 개선된 전략(strategy)이 될 수 있다. 하나의 간단한 예로, X점에서 Y점으로의 거리를 알려고 할때, Y'점에서 X점으로의 거리를 역시 알수 있으며, 그렇기 때문에 어떤 하나의 계산은 두개의 다른 쿼리들에 다시 활용될 수 있다.

고정된(fixed) 차원(dimension)과, 반 확정적인(semi-definite) positive norm (그래서 모든 L^p norm를 포함한다), 그리고 이 공간 내의 n개의 점들이 주어졌을때, 모든 점들에 있어서 최근접 이웃은 O(n log n)시간 내에서 찾을 수 있고, 모든 점의 m 개의 최근접 이웃들은 O(mn log n) 시간 내에 찾을 수 있다.^[2]^[3]

Notes[편집]

↑ S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman and A. Wu, An optimal algorithm for approximate nearest neighbor searching, Journal of the ACM, 45(6):891-923, 1998. [1]
↑ Clarkson, Kenneth L. (1983), 〈Fast algorithms for the all nearest neighbors problem〉, 《24th IEEE Symp. Foundations of Computer Science, (FOCS '83)》, 226–232쪽, doi:10.1109/SFCS.1983.16, ISBN 0-8186-0508-1 .
↑ Vaidya, P. M. (1989). “An O(n log n) Algorithm for the All-Nearest-Neighbors Problem”. 《Discrete and Computational Geometry》 4 (1): 101–115. doi:10.1007/BF02187718.

References[편집]

Andrews, L.. A template for the nearest neighbor problem. C/C++ Users Journal, vol. 19, no 11 (November 2001), 40 - 49, 2001, ISSN:1075-2838, www.ddj.com/architect/184401449
Arya, S., D. M. Mount, N. S. Netanyahu, R. Silverman, and A. Y. Wu. An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions. Journal of the ACM, vol. 45, no. 6, pp. 891–923
Beyer, K., Goldstein, J., Ramakrishnan, R., and Shaft, U. 1999. When is nearest neighbor meaningful? In Proceedings of the 7th ICDT, Jerusalem, Israel.
Chung-Min Chen and Yibei Ling - A Sampling-Based Estimator for Top-k Query. ICDE 2002: 617-627
Samet, H. 2006. Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann. ISBN 0-12-369446-9
Zezula, P., Amato, G., Dohnal, V., and Batko, M. Similarity Search - The Metric Space Approach. Springer, 2006. ISBN 0-387-29146-6

External links[편집]

Nearest Neighbors and Similarity Search – a website dedicated to educational materials, software, literature, researchers, open problems and events related to NN searching. Maintained by Yury Lifshits
Similarity Search Wiki – a collection of links, people, ideas, keywords, papers, slides, code and data sets on nearest neighbours
KGraph – a C++ library for fast approximate nearest neighbor search with user-provided distance metric by Wei Dong.
FLANN – a library for performing fast approximate nearest neighbor searches in high dimensional spaces by Marius Muja and David G. Low
Metric Spaces Library – An open-source C-based library for metric space indexing by Karina Figueroa, Gonzalo Navarro, Edgar Chávez
Non-Metric Space Library – An open-source C++ library for exact and approximate searching in non-metric and metric spaces
ANN – A library for Approximate Nearest Neighbor searching by David M. Mount and Sunil Arya
Product Quantization – Matlab implementation of approximate nearest neighbor search in the compressed domain by Herve Jegou
MESSIF – Metric Similarity Search Implementation Framework by Michal Batko and David Novak
OBSearch – Similarity Search engine for Java (GPL); implementation by Arnoldo Muller, developed during Google Summer of Code 2007
KNNLSB – K Nearest Neighbors Linear Scan Baseline (distributed, LGPL); implementation by Georges Quénot (LIG-CNRS)
NearTree – An API for finding nearest neighbors among points in spaces of arbitrary dimensions by Lawrence C. Andrews and Herbert J. Bernstein
NearPy – Python framework for fast approximated nearest neighbor search by Ole Krause-Sparmann
dD Spatial Searching in CGAL – the Computational Geometry Algorithms Library
Panns – A Python library for searching approximate nearest neighbors, optimized for large dataset with high dimensional features, developed by Liang Wang

[1] S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman and A. Wu, An optimal algorithm for approximate nearest neighbor searching, Journal of the ACM, 45(6):891-923, 1998. [1]

[2] Clarkson, Kenneth L. (1983), 〈Fast algorithms for the all nearest neighbors problem〉, 《24th IEEE Symp. Foundations of Computer Science, (FOCS '83)》, 226–232쪽, doi:10.1109/SFCS.1983.16, ISBN 0-8186-0508-1 .

[Vaidya-3] Vaidya, P. M. (1989). “An O(n log n) Algorithm for the All-Nearest-Neighbors Problem”. 《Discrete and Computational Geometry》 4 (1): 101–115. doi:10.1007/BF02187718.

[1]

[2]

[3]