بحث النقطة الأقرب
مسألة بحث النقطة الأقرب Nearest neighbor search هي مسألة رياضية لإيجاد أقرب النقاط من مجموعة نقاط لنقطة معينة في الفضاء المتري.
صياغة المسألة
مجموعة نقاط S في الفضاء المتري M ونقطة استعلام q ∈ M، والمطلوب إيجاد أقرب النقاط من S إلى q. في الكثير من الحالات،قد يكون الفضاء M هوالفضاء الإقليدي وتكون المسافة مقاسة بالمسافة الإقليدية أومسافة مانهاتن.
تطبيقات المسألة
تستخدم هذه المسألة في الكثير من التطبيقات منها:
- تمييز الأنماط
- تعهد ضوئي على المحارف
- تصنيف إحصائي
- رؤية حاسوبية
- قاعدة بيانات
- ضغط بيانات
- الترويج عبر الإنترنت
انظر أيضاً
- Ball tree
- Closest pair of points problem
- Cluster analysis
- Content-based image retrieval
- Curse of dimensionality
- Digital signal processing
- Dimension reduction
- Fixed-radius near neighbors
- Fourier analysis
- Instance-based learning
- -nearest neighbor algorithm
- Linear least squares
- Locality sensitive hashing
- MinHash
- Multidimensional analysis
- Nearest-neighbor interpolation
- Neighbor joining
- Principal component analysis
- Range search
- Set cover problem
- Similarity learning
- Singular value decomposition
- Sparse distributed memory
- Statistical distance
- Time series
- Voronoi diagram
- Wavelet
مراجع
- 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
- Zezula, P., Amato, G., Dohnal, V., and Batko, M. Similarity Search - The Metric Space Approach. Springer, 2006. ISBN: 0-387-29146-6
