بحث النقطة الأقرب

مسألة بحث النقطة الأقرب 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
• k-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