निकटतम नेबर सर्च (एनएनएस): Difference between revisions

Latest revision as of 10:07, 18 July 2023

निकटतम नेबर सर्च (एनएनएस), निकटतम खोज के रूप किसी दिए गए समुच्चय में उस बिंदु को खोजने की अनुकूलन समस्या है जो किसी दिए गए बिंदु के सबसे समीप (या सबसे समान) है। निकटतम को सामान्यतः असमानता फलन के संदर्भ में व्यक्त किया जाता है: जितनी कम समानता वस्तुओं को मापती है, फलन मान उतना ही बड़ा होता है।

औपचारिक रूप से निकटतम-नेबर (एनएन) खोज समस्या को निम्नलिखित इस प्रकार परिभाषित किया गया है: किसी स्थान M में बिंदुओं का समुच्चय S और क्वेरी बिंदु q ∈ M दिया गया है S में q में निकटतम बिंदु q खोजें और वॉल्यूम में डोनाल्ड नुथ या कंप्यूटर प्रोग्रामिंग की कला (1973) के 3 में इसे निकटतम डाकघर को निवास आवंटित करने के आवेदन का जिक्र करते हुए इसे डाकघर की समस्या कहा गया है। इस समस्या का प्रत्यक्ष सामान्यीकरण k-NN खोज है, जहां हमें k निकटतम बिंदु खोजने की आवश्यकता होती है।

सामान्यतः M मीट्रिक स्थान है और असमानता को दूरी मीट्रिक के रूप में व्यक्त किया जाता है जो सममित है और त्रिकोण असमानता को संतुष्ट करता है। इससे भी अधिक सामान्य M को d-आयामी सदिश स्थल के रूप में लिया जाता है जहां असमानता को यूक्लिडियन दूरी, टैक्सीकैब ज्यामिति या अन्य सांख्यिकीय दूरी का उपयोग करके मापा जाता है। चूँकि असमानता फलन इच्छानुसार हो सकता है। उदाप्रत्येकण असममित ब्रेगमैन विचलन है जिसके लिए त्रिभुज असमानता प्रयुक्त नहीं होती है।^[1]

अनुप्रयोग

निकटतम नेबर सर्च समस्या अनुप्रयोग के अनेक क्षेत्रों में उत्पन्न होती है जिनमें सम्मिलित हैं:

क्रम पहचान - विशेष रूप से ऑप्टिकल कैरेक्टर पहचान के लिए
सांख्यिकीय वर्गीकरण - के-निकटतम नेबर एल्गोरिदम देखें
कंप्यूटर दृष्टि - पॉइंट क्लाउड पंजीकरण के लिए^[2]
कम्प्यूटेशनल ज्यामिति - बिंदुओं की निकटतम जोड़ी समस्या देखें
डेटाबेस - उदा. सामग्री-आधारित छवि पुनर्प्राप्ति
कोडिंग सिद्धांत - अधिकतम संभावना डिकोडिंग विधियां देखें
सिमेंटिक खोज
डेटा संपीड़न - एमपईजी-2 मानक देखें
रोबोटिक सेंसिंग^[3]
अनुशंसा प्रणाली उदा. सहयोगात्मक फ़िल्टरिंग देखें
इंटरनेट विपणन - प्रासंगिक विज्ञापन और व्यवहारिक लक्ष्यीकरण देखें
डीएनए श्रृंखला बनाना
वर्तनी जाँच - सही वर्तनी का सुझाव देना
प्लागिअरिस्म डिटेक्शन
प्रोफेशनल एथलीटों के करियर पथ की पूर्वानुमान के लिए समानता स्कोर।
क्लस्टर विश्लेषण - अवलोकनों के समुच्चय को उपसमूहों (जिन्हें क्लस्टर कहा जाता है) में असाइन करना जिससे ही क्लस्टर में अवलोकन कुछ अर्थों में समान हों, सामान्यतः यह यूक्लिडियन दूरी पर आधारित होते हैं
रासायनिक समानता
मोशन प्लानिंग या सैंपलिंग-आधारित एल्गोरिदम
नमूना-आधारित गति योजना

विधियाँ

एनएनएस समस्या के विभिन्न समाधान प्रस्तावित किए गए हैं। इस प्रकार एल्गोरिदम की गुणवत्ता और उपयोगिता प्रश्नों की समय जटिलता के साथ-साथ किसी भी खोज डेटा संरचना की स्थान जटिलता द्वारा निर्धारित की जाती है जिसे बनाए रखा जाना चाहिए। अनौपचारिक अवलोकन जिसे सामान्यतः आयामी स्थिति के अभिशाप के रूप में जाना जाता है, यह बताता है कि बहुपद प्रीप्रोसेसिंग और पॉलीलॉगरिदमिक खोज समय का उपयोग करके उच्च-आयामी यूक्लिडियन सम्मिस्ट में एनएनएस के लिए कोई सामान्य-उद्देश्य स्पष्ट समाधान नहीं है।

स्पष्ट विधियाँ

रैखिक खोज

एनएनएस समस्या का सबसे सरल समाधान अब तक के सर्वश्रेष्ठ का ट्रैक रखते हुए डेटाबेस में क्वेरी बिंदु से प्रत्येक दूसरे बिंदु तक की दूरी की गणना करना है। यह एल्गोरिदम, जिसे कभी-कभी अनुभवहीन दृष्टिकोण के रूप में जाना जाता है इसका चलने का समय O(dN)) है जहां N, S की प्रमुखता है और d, S की आयामीता है। इसको बनाए रखने के लिए कोई खोज डेटा संरचनाएं नहीं हैं, इसलिए रैखिक खोज में डेटाबेस के संचयन से परे कोई स्थान जटिलता नहीं हैं। सामान्य खोज औसतन उच्च आयामी स्थानों पर सम्मिस्ट विभाजन दृष्टिकोण से उत्तम प्रदर्शन कर सकती है।^[4]

दूरी की तुलना के लिए पूर्ण दूरी की आवश्यकता नहीं है, इसमें अतिरिक्त सापेक्ष दूरी की आवश्यकता होती है। और ज्यामितीय समन्वय प्रणालियों में दो निर्देशांकों के मध्य की दूरी की गणना से वर्गमूल गणना को हटाकर दूरी की गणना में अधिक तेजी लाई जा सकती है। और दूरी की तुलना अभी भी समान परिणाम देती हैं।

सम्मिस्ट विभाजन

1970 के दशक से, शाखा और बाध्य पद्धति को समस्या पर प्रयुक्त किया गया है। यूक्लिडियन सम्मिस्ट के स्तिथियों में, यह दृष्टिकोण स्थानिक सूचकांक या स्थानिक पहुंच विधियों को सम्मिलित करता है। एनएनएस समस्या को हल करने के लिए अनेक सम्मिस्ट विभाजन सम्मिस्ट-विभाजन विधियां विकसित की गई हैं। संभवतः सबसे सरल k-d ट्री है, जो मूल क्षेत्र के आधे बिंदुओं वाले खोज स्थान को दो क्षेत्रों में पुनरावृत्त रूप से विभाजित करता है। और प्रत्येक विभाजन पर क्वेरी बिंदु का मूल्यांकन करके क्वेरी को रूट से लीव्स तक ट्री के ट्रैवर्सल के माध्यम से निष्पादित किया जाता है। इस प्रकार क्वेरी में निर्दिष्ट दूरी के आधार पर, निकटतम शाखाओं जिनमें हिट हो सकती हैं, इसलिए इनका भी मूल्यांकन करने की आवश्यकता हो सकती है। और निरंतर आयाम क्वेरी समय के लिए, औसत जटिलता O(log N) होता है| ^[5] उत्तम ढंग से वितरित बिंदुओं के स्तिथियों में, सबसे व्यर्थ स्थिति जटिलता O(kN^(1-1/k))है| ^[6] वैकल्पिक रूप से R-ट्री डेटा संरचना को गतिशील संदर्भ में निकटतम नेबर सर्च का समर्थन करने के लिए डिज़ाइन किया गया था, क्योंकि इसमें आर* ट्री जैसे सम्मिलन और विलोपन के लिए कुशल एल्गोरिदम हैं।^[7] R-ट्री न अतिरिक्त यूक्लिडियन दूरी के लिए निकटतम नेबर प्रदान कर सकते हैं, किंतु अन्य दूरियों के साथ भी इसका उपयोग किया जा सकता है।

सामान्य मीट्रिक स्थान के स्तिथियों में, शाखा-और-बाउंड दृष्टिकोण को मीट्रिक ट्री दृष्टिकोण के रूप में जाना जाता है। विशेष उदाहरणों में वीपी-ट्री और बीके-ट्री विधियां सम्मिलित हैं।

3-आयामी स्थान से लिए दिए गए बिंदुओं के समुच्चय का उपयोग करके और बाइनरी स्पेस विभाजन में डालकर और उसी स्थान से लिया गया क्वेरी बिंदु दिया गया हैं क्वेरी बिंदु के निकटतम बिंदु-क्लाउड बिंदु को खोजने की समस्या का संभावित समाधान है और यह एल्गोरिदम के निम्नलिखित विवरण में दिया गया है।

(सख्ती से कहें तब, ऐसा कोई बिंदु उपस्थित नहीं हो सकता है, क्योंकि यह अद्वितीय नहीं हो सकता है। किन्तु वास्तव में, सामान्यतः हम अतिरिक्त सभी बिंदु-क्लाउड बिंदुओं के सब समुच्चय में से किसी को खोजने की परवाह करते हैं और जो किसी दिए गए क्वेरी बिंदु से सबसे कम दूरी पर उपस्थित होते हैं) इस प्रकार विचार यह है कि, ट्री की प्रत्येक शाखा के लिए, अनुमान लगाएं कि पश्चात्ल में निकटतम बिंदु क्वेरी बिंदु वाले आधे स्थान में रहता है। यह स्थितिया नहीं हो सकती है, किन्तु यह श्रेष्ठ अनुमान है। कि अनुमानित अर्ध-स्थान के लिए समस्या को हल करने की सभी परेशानियों से गुजरने के पश्चात्ब अब इस परिणाम द्वारा लौटाई गई दूरी की तुलना क्वेरी बिंदु से विभाजन तल तक की सबसे छोटी दूरी से तय करें।और यह पश्चात् वाली दूरी क्वेरी बिंदु और निकटतम संभावित बिंदु के मध्य की दूरी है जो बिना खोजे गए आधे स्थान में उपस्थित हो सकती है। इस प्रकार यदि यह दूरी पिछले परिणाम में दी गई दूरी से अधिक होती है तब स्पष्ट रूप से अन्य आधे स्थान की खोज करने की कोई आवश्यकता नहीं होती है। यदि ऐसी कोई आवश्यकता है, तब आपको अन्य आधे स्थान के लिए समस्या को हल करने की परेशानी से निकलना होगा, और फिर उसके परिणाम की तुलना पिछले परिणाम से करनी होगी, और फिर उसे उचित परिणाम लौटाना होगा। इस एल्गोरिदम का प्रदर्शन रैखिक समय की तुलना में लॉगरिदमिक समय के समीप होता है और जब क्वेरी बिंदु क्लाउड के समीप होता है, क्योंकि क्वेरी बिंदु और निकटतम बिंदु-क्लाउड बिंदु के मध्य की दूरी शून्य के समीप होती है, एल्गोरिदम को अतिरिक्त लुक-अप का उपयोग करने की आवश्यकता होती है और सही परिणाम प्राप्त करने के लिए क्वेरी बिंदु को कुंजी के रूप में उपयोग करना होता हैं।

सन्निकटन विधियाँ

एक अनुमानित निकटतम नेबर सर्च एल्गोरिदम को उन बिंदुओं को वापस करने की अनुमति होती है जिनकी क्वेरी से दूरी अधिकतम हैं $c$ क्वेरी से उसके निकटतम बिंदुओं की दूरी $c$ का गुना हैं। इस दृष्टिकोण की अपील यह है कि अनेक स्थितियों में अनुमानित निकटतम नेबर लगभग उतना ही श्रेष्ठ होता है जितना कि स्पष्ट निकटतम होता हैं। विशेष रूप से यदि दूरी माप उपयोगकर्ता की गुणवत्ता की धारणा को स्पष्ट रूप से पकड़ लेता है, तब दूरी में छोटे अंतर से कोई अंतर नहीं पड़ना चाहिए।^[8]

निकटता निकटतम ग्राफ़ में ग्रीडी खोज

निकटता ग्राफ़ विधियाँ (जैसे एचएनएसडब्ल्यू^[9]) को निकटतम नेबर की खोज के लिए वर्तमान अत्याधुनिक माना जाता है।^[9]^[10]^[11]

विधियाँ निकटता निकटता ग्राफ़ में $G(V,E)$ ग्रीडी ट्रैवर्सिंग पर आधारित होता हैं जिसमें प्रत्येक बिंदु $x_{i}\in S$ में शीर्ष $v_{i}\in V$ के साथ विशिष्ट रूप से जुड़ा हुआ है | समुच्चय में क्वेरी q के निकटतम नेबर S ग्राफ़ $G(V,E)$ शीर्ष की खोज का रूप लेती है| मूल एल्गोरिदम - ग्रीडी खोज - निम्नानुसार काम करती है: खोज क्वेरी q से उसके निकटतम $\{v_{j}:(v_{i},v_{j})\in E\}$ के प्रत्येक शीर्ष तक की दूरी की गणना करके वी में प्रवेश-बिंदु शीर्ष $v_{i}\in V$ से प्रारंभ होती है और फिर न्यूनतम दूरी मान वाला शीर्ष खोजता है। यदि क्वेरी और चयनित शीर्ष के मध्य की दूरी का मान क्वेरी और वर्तमान तत्व के मध्य की दूरी से छोटा है, तब एल्गोरिदम चयनित शीर्ष पर चला जाता है, और यह नया प्रवेश-बिंदु बन जाता है। एल्गोरिदम तब रुक जाता है जब यह स्थानीय न्यूनतम तक पहुंच जाता है वह शीर्ष जिसके निकटतम में शीर्ष नहीं होता है जो शीर्ष की तुलना में क्वेरी के समीप होता है।

निकटतम नेबर ग्राफ़ के विचार का उपयोग कई प्रकाशनों में किया गया था, जिसमें विमान के लिए वोरोनेट प्रणाली में आर्य और माउंट का मौलिक पेपर $\mathbb {E} ^{n}$ के लिए रेनेट प्रणाली में सम्मिलित था।,^[12] ^[13] ,^[14] और मेट्रिज़्ड स्मॉल वर्ल्ड और एचएनएसडब्ल्यू ^[9] एल्गोरिदम में दूरी फलन वाले स्थानों के सामान्य स्थिति के लिए इन कार्यों से पहले टूसेंट का एक अग्रणी पेपर प्रकाशित हुआ था, जिसमें उन्होंने सापेक्ष पड़ोस ग्राफ की अवधारणा प्रस्तुत की थी ^[15]

स्थानीय संवेदनशील हैशिंग

स्थानीयता संवेदनशील हैशिंग (एलएसएच) बिंदुओं पर संचालित कुछ दूरी मीट्रिक के आधार पर सम्मिस्ट में बिंदुओं को 'बकेट्स' में समूहीकृत करने की विधि है। जिसमे चुने गए मीट्रिक के अनुसार एक-दूसरे के समीप आने वाले बिंदुओं को उच्च संभावना के साथ ही बकेट में मानचित्र किया जाता है।^[16]

छोटे आंतरिक आयाम वाले स्थानों में निकटतम नेबर की खोज

ट्री की आवरण में सैद्धांतिक सीमा होती है जो डेटा समुच्चय के दोहरीकरण स्थिरांक पर आधारित होती है। और खोज समय की सीमा O(c¹² log n) हैं जहां c डेटा समुच्चय की विस्तारशीलता स्थिरांक होता है।

प्रक्षेपित रेडियल खोज

विशेष स्तिथियों में जहां डेटा ज्यामितीय बिंदुओं का सघन 3डी मानचित्र होता है, तब सेंसिंग विधि की प्रक्षेपण ज्यामिति का उपयोग खोज समस्या को नाटकीय रूप से सरल बनाने के लिए किया जा सकता है। इस दृष्टिकोण के लिए आवश्यक है कि 3डी डेटा को दो-आयामी ग्रिड के प्रक्षेपण द्वारा व्यवस्थित किया जाए और यह माना जाए कि डेटा ऑब्जेक्ट सीमाओं के अपवाद के साथ निकटतम ग्रिड कोशिकाओं में स्थानिक रूप से सुचारू है। सर्वेक्षण रोबोटिक्स और स्टीरियो विज़न जैसे अनुप्रयोगों में 3डी सेंसर डेटा से निपटने के समय ये धारणाएँ मान्य हैं, किन्तु सामान्यतः असंगठित डेटा के लिए ये मान्य नहीं हो सकती हैं। और वास्तव में इस विधि को वास्तविक विश्व स्टीरियो विज़न डेटा पर प्रयुक्त करने पर k-निकटतम नेबर समस्या के लिए औसत खोज समय O(1) या O(K) होता है।^[3]

सदिश सन्निकटन फ़ाइलें

उच्च-आयामी स्थानों में, ट्री अनुक्रमण संरचनाएं व्यर्थ हो जाती हैं क्योंकि नोड्स के बढ़ते प्रतिशत की वैसे भी जांच करने की आवश्यकता होती है। रैखिक खोज को तेज़ करने के लिए रैम में संग्रहीत विशेषता सदिश के संपीड़ित संस्करण का उपयोग पहली बार में डेटासमुच्चय को प्रीफ़िल्टर करने के लिए किया जाता है। दूरी की गणना के लिए डिस्क से असम्पीडित डेटा का उपयोग करके दूसरे चरण में अंतिम उम्मीदवारों का निर्धारण किया जाता है।^[17]

संपीड़न/क्लस्टरिंग आधारित खोज

वीए-फ़ाइल दृष्टिकोण संपीड़न आधारित खोज का विशेष स्थितिया है, जहां प्रत्येक फलन घटक समान रूप से और स्वतंत्र रूप से संपीड़ित होता है। बहुआयामी स्थानों में इष्टतम संपीड़न विधि सदिश परिमाणीकरण (वीक्यू) है, जिसे क्लस्टरिंग के माध्यम से कार्यान्वित किया जाता है। और डेटाबेस को क्लस्टर किया गया है और सबसे आशा जनक क्लस्टर पुनर्प्राप्त किए गए हैं। इस प्रकार वीए-फ़ाइल, ट्री-आधारित इंडेक्स और अनुक्रमिक स्कैन पर भारी लाभ देखा गया है।^[18]^[19] क्लस्टरिंग और एलएसएच के मध्य समानताएं भी ध्यान करना हैं।

प्रकार

एनएनएस समस्या के कई प्रकार हैं और दो सबसे प्रसिद्ध हैं के-निकटतम नेबर खोज और ε-अनुमानित निकटतम नेबर खोज हैं।

k-निकटतम नेबर

K-निकटतम नेबर एल्गोरिथ्म k-निकटतम नेबर सर्च क्वेरी के शीर्ष k निकटतम नेबर की पहचान करती है। इस विधि का उपयोग सामान्यतः अपने निकटतम की सहमति के आधार पर किसी बिंदु का अनुमान लगाने या वर्गीकृत करने के लिए पूर्वानुमानित विश्लेषण में किया जाता है। k-निकटतम नेबर ग्राफ़ वे ग्राफ़ होते हैं जिनमें प्रत्येक बिंदु अपने k निकटतम नेबर से जुड़ा होता है।

अनुमानित निकटतम नेबर

कुछ अनुप्रयोगों में निकटतम नेबर का श्रेष्ठ अनुमान प्राप्त करना स्वीकार्य हो सकता है। उन स्थितियों में, हम एल्गोरिदम का उपयोग कर सकते हैं जो उत्तम गति या मेमोरी बचत के बदले में प्रत्येक स्तिथियों में वास्तविक निकटतम नेबर को वापस करने की आश्वासन नहीं देता है। अधिकांशतः ऐसा एल्गोरिदम अधिकांश स्थितियों में निकटतम नेबर खोज लेगा, किन्तु यह पूछताछ किए जा रहे डेटासमुच्चय पर दृढ़ता से निर्भर करता है।

अनुमानित निकटतम नेबर सर्च का समर्थन करने वाले एल्गोरिदम में निकटतम नेबर सर्च के लिए स्थानीयता-संवेदनशील हैशिंगयाएलएसएच एल्गोरिदम सम्मिलित है|स्थानीयता-संवेदनशील हैशिंग, सर्वोत्तम बिन प्रथम और संतुलित बॉक्स-अपघटन ट्री आधारित खोज हैं|^[20]

निकटतम नेबर दूरी अनुपात

निकटतम नेबर दूरी अनुपात मूल बिंदु से चुनौती देने वाले निकट तक की सीधी दूरी पर सीमा प्रयुक्त नहीं करता है, किंतु पिछले निकटतम से दूरी के आधार पर इसके अनुपात पर प्रयुक्त होता है। इसकी उपयोग सामग्री-आधारित छवि पुनर्प्राप्ति में स्थानीय सुविधाओं के मध्य समानता का उपयोग करके उदाहरण के माध्यम से चित्रों को पुनः प्राप्त करने के लिए किया जाता है। इस प्रकार सामान्यतः यह अनेक क्रम मिलान समस्याओं में सम्मिलित होता है।

निकटतम के पास निश्चित-त्रिज्या

निकटतम के पास निश्चित-त्रिज्या वह समस्या है जहां कोई निर्दिष्ट बिंदु से निश्चित दूरी के अंदर यूक्लिडियन सम्मिस्ट में दिए गए सभी बिंदुओं को कुशलतापूर्वक खोज नही चाहता है। और इसमें दूरी निश्चित मानी जाती है, किन्तु प्रश्न बिंदु इच्छानुसार होते है।

सभी निकटतम नेबर

कुछ अनुप्रयोगों (जैसे एन्ट्रापी अनुमान) के लिए, हमारे पास एन डेटा-पॉइंट हो सकते हैं और हम जानना चाहते हैं कि उन एन पॉइंट्स में से प्रत्येक के लिए निकटतम नेबर कौन सा होता है। यह, निश्चित रूप से, प्रत्येक बिंदु के लिए अनेक बार निकटतम-नेबर खोज चलाकर प्राप्त किया जा सकता है, किन्तु उत्तम रणनीति एल्गोरिदम होती हैं जो अधिक कुशल खोज उत्पन्न करने के लिए इन एन प्रश्नों के मध्य सूचना अतिरेक का लाभ उठाती है। सरल उदाहरण के रूप में: जब हम बिंदु X से बिंदु Y तक की दूरी पाते हैं, तब वह हमें बिंदु Y से बिंदु से प्राप्त होती हैं

एक निश्चित आयाम को देखते हुए, अर्ध-निश्चित सकारात्मक मानदंड (जिससे प्रत्येक L^p मानदंड सम्मिलित है)| और इस स्थान में n बिंदु, दिए गए हैं प्रत्येक बिंदु का निकटतम नेबर O(n log n) समय में पाया जा सकता है और प्रत्येक के m निकटतम नेबर बिंदु O(mn log n) समय में पाया जा सकता है। ^[21]^[22]

यह भी देखें

बॉल ट्री
अंकों की निकटतम जोड़ी की समस्या
क्लस्टर विश्लेषण
सामग्री-आधारित छवि पुनर्प्राप्ति
परिमाणिकता का अभिशाप
अंकीय संकेत प्रक्रिया
आयाम में कमी
नेबर के पास निश्चित-त्रिज्या
फूरियर विश्लेषण
उदाहरण-आधारित शिक्षा
k-निकटतम नेबर एल्गोरिथम|
रैखिक न्यूनतम वर्ग (गणित)
स्थानीयता संवेदनशील हैशिंग
अधिकतम आंतरिक-उत्पाद खोज
मिनहैश
बहुआयामी विश्लेषण
निकटतम-नेबर प्रक्षेप
नेबर का जुड़ना
प्रमुख कंपोनेंट विश्लेषण
रेंज खोज
समानता सीखना
विलक्षण मान अपघटन
विरल वितरित स्मृति
सांख्यिकीय दूरी
समय श्रृंखला
वोरोनोई आरेख
तरंगिका

संदर्भ

उद्धरण

↑ Cayton, Lawerence (2008). "Fast nearest neighbor retrieval for bregman divergences". Proceedings of the 25th International Conference on Machine Learning. pp. 112–119. doi:10.1145/1390156.1390171. ISBN 9781605582054. S2CID 12169321.
↑ Qiu, Deyuan, Stefan May, and Andreas Nüchter. "GPU-accelerated nearest neighbor search for 3D registration." International conference on computer vision systems. Springer, Berlin, Heidelberg, 2009.
↑ ^3.0 ^3.1 Bewley, A.; Upcroft, B. (2013). Advantages of Exploiting Projection Structure for Segmenting Dense 3D Point Clouds (PDF). Australian Conference on Robotics and Automation.
↑ Weber, Roger; Schek, Hans-J.; Blott, Stephen (1998). "A quantitative analysis and performance study for similarity search methods in high dimensional spaces" (PDF). VLDB '98 Proceedings of the 24rd International Conference on Very Large Data Bases. pp. 194–205.
↑ Andrew Moore. "केडी पेड़ों पर एक परिचयात्मक ट्यूटोरियल" (PDF). Archived from the original (PDF) on 2016-03-03. Retrieved 2008-10-03.
↑ Lee, D. T.; Wong, C. K. (1977). "Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees". Acta Informatica. 9 (1): 23–29. doi:10.1007/BF00263763. S2CID 36580055.
↑ Roussopoulos, N.; Kelley, S.; Vincent, F. D. R. (1995). "Nearest neighbor queries". Proceedings of the 1995 ACM SIGMOD international conference on Management of data – SIGMOD '95. p. 71. doi:10.1145/223784.223794. ISBN 0897917316.
↑ Andoni, A.; Indyk, P. (2006-10-01). "Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions". 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06). pp. 459–468. CiteSeerX 10.1.1.142.3471. doi:10.1109/FOCS.2006.49. ISBN 978-0-7695-2720-8.
↑ ^9.0 ^9.1 ^9.2 Malkov, Yury; Yashunin, Dmitry (2016). "पदानुक्रमित नौगम्य लघु विश्व ग्राफ़ का उपयोग करके कुशल और मजबूत अनुमानित निकटतम पड़ोसी खोज". arXiv:1603.09320 [cs.DS].
↑ "New approximate nearest neighbor benchmarks".
↑ "Approximate Nearest Neighbours for Recommender Systems".
↑ Arya, Sunil; Mount, David (1993). "निश्चित आयामों में अनुमानित निकटतम पड़ोसी प्रश्न". Proceedings of the Fourth Annual {ACM/SIGACT-SIAM} Symposium on Discrete Algorithms, 25–27 January 1993, Austin, Texas.: 271–280.
↑ Olivier, Beaumont; Kermarrec, Anne-Marie; Marchal, Loris; Rivière, Etienne (2006). "Voro Net: A scalable object network based on Voronoi tessellations" (PDF). 2007 IEEE International Parallel and Distributed Processing Symposium. Vol. RR-5833. pp. 23–29. doi:10.1109/IPDPS.2007.370210. ISBN 1-4244-0909-8. S2CID 8844431.
↑ Olivier, Beaumont; Kermarrec, Anne-Marie; Rivière, Etienne (2007). Peer to Peer Multidimensional Overlays: Approximating Complex Structures. pp. 315–328. CiteSeerX 10.1.1.626.2980. doi:10.1007/978-3-540-77096-1_23. ISBN 978-3-540-77095-4. {{cite book}}: |journal= ignored (help)
↑ Toussaint, Godfried (1980). "एक परिमित तलीय समुच्चय का सापेक्ष पड़ोस ग्राफ़". Pattern Recognition. 12 (4): 261–268. Bibcode:1980PatRe..12..261T. doi:10.1016/0031-3203(80)90066-7.
↑ A. Rajaraman & J. Ullman (2010). "Mining of Massive Datasets, Ch. 3".
↑ Weber, Roger; Blott, Stephen. "समानता खोज के लिए एक अनुमान-आधारित डेटा संरचना" (PDF). S2CID 14613657. Archived from the original (PDF) on 2017-03-04. {{cite journal}}: Cite journal requires |journal= (help)
↑ Ramaswamy, Sharadh; Rose, Kenneth (2007). "छवि डेटाबेस में समानता खोज के लिए अनुकूली क्लस्टर-दूरी बाउंडिंग". ICIP.
↑ Ramaswamy, Sharadh; Rose, Kenneth (2010). "उच्च-आयामी अनुक्रमण के लिए अनुकूली क्लस्टर-दूरी बाउंडिंग". TKDE.
↑ Arya, S.; Mount, D. M.; Netanyahu, N. S.; Silverman, R.; Wu, A. (1998). "अनुमानित निकटतम पड़ोसी खोज के लिए एक इष्टतम एल्गोरिदम" (PDF). Journal of the ACM. 45 (6): 891–923. CiteSeerX 10.1.1.15.3125. doi:10.1145/293347.293348. S2CID 8193729. Archived from the original (PDF) on 2016-03-03. Retrieved 2009-05-29.
↑ Clarkson, Kenneth L. (1983), "Fast algorithms for the all nearest neighbors problem", 24th IEEE Symp. Foundations of Computer Science, (FOCS '83), pp. 226–232, doi:10.1109/SFCS.1983.16, ISBN 978-0-8186-0508-6, S2CID 16665268.
↑ 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.

स्रोत

Andrews, L. (November 2001). "निकटतम पड़ोसी समस्या के लिए एक टेम्पलेट". C/C++ Users Journal. 19 (11): 40–49. ISSN 1075-2838.
Arya, S.; Mount, D.M.; Netanyahu, N. S.; Silverman, R.; Wu, A. Y. (1998). "निश्चित आयामों में अनुमानित निकटतम पड़ोसी की खोज के लिए एक इष्टतम एल्गोरिदम". Journal of the ACM. 45 (6): 891–923. CiteSeerX 10.1.1.15.3125. doi:10.1145/293347.293348. S2CID 8193729.
Beyer, K.; Goldstein, J.; Ramakrishnan, R.; Shaft, U. (1999). "निकटतम पड़ोसी कब सार्थक है?". Proceedings of the 7th ICDT.
Chen, Chung-Min; Ling, Yibei (2002). "टॉप-के क्वेरी के लिए एक नमूना-आधारित अनुमानक". ICDE: 617–627.
Samet, H. (2006). बहुआयामी और मीट्रिक डेटा संरचनाओं की नींव. Morgan Kaufmann. ISBN 978-0-12-369446-1.
Zezula, P.; Amato, G.; Dohnal, V.; Batko, M. (2006). समानता खोज - मीट्रिक अंतरिक्ष दृष्टिकोण. Springer. ISBN 978-0-387-29146-8.

अग्रिम पठन

Shasha, Dennis (2004). High Performance Discovery in Time Series. Berlin: Springer. ISBN 978-0-387-00857-8.

बाहरी संबंध

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

[Cayton2008-1] Cayton, Lawerence (2008). "Fast nearest neighbor retrieval for bregman divergences". Proceedings of the 25th International Conference on Machine Learning. pp. 112–119. doi:10.1145/1390156.1390171. ISBN 9781605582054. S2CID 12169321.

[2] Qiu, Deyuan, Stefan May, and Andreas Nüchter. "GPU-accelerated nearest neighbor search for 3D registration." International conference on computer vision systems. Springer, Berlin, Heidelberg, 2009.

[panSearch-3] 3.0 ^3.1 Bewley, A.; Upcroft, B. (2013). Advantages of Exploiting Projection Structure for Segmenting Dense 3D Point Clouds (PDF). Australian Conference on Robotics and Automation.

[4] Weber, Roger; Schek, Hans-J.; Blott, Stephen (1998). "A quantitative analysis and performance study for similarity search methods in high dimensional spaces" (PDF). VLDB '98 Proceedings of the 24rd International Conference on Very Large Data Bases. pp. 194–205.

[5] Andrew Moore. "केडी पेड़ों पर एक परिचयात्मक ट्यूटोरियल" (PDF). Archived from the original (PDF) on 2016-03-03. Retrieved 2008-10-03.

[Lee1977-6] Lee, D. T.; Wong, C. K. (1977). "Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees". Acta Informatica. 9 (1): 23–29. doi:10.1007/BF00263763. S2CID 36580055.

[7] Roussopoulos, N.; Kelley, S.; Vincent, F. D. R. (1995). "Nearest neighbor queries". Proceedings of the 1995 ACM SIGMOD international conference on Management of data – SIGMOD '95. p. 71. doi:10.1145/223784.223794. ISBN 0897917316.

[8] Andoni, A.; Indyk, P. (2006-10-01). "Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions". 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06). pp. 459–468. CiteSeerX 10.1.1.142.3471. doi:10.1109/FOCS.2006.49. ISBN 978-0-7695-2720-8.

[:0-9] 9.0 ^9.1 ^9.2 Malkov, Yury; Yashunin, Dmitry (2016). "पदानुक्रमित नौगम्य लघु विश्व ग्राफ़ का उपयोग करके कुशल और मजबूत अनुमानित निकटतम पड़ोसी खोज". arXiv:1603.09320 [cs.DS].

[10] "New approximate nearest neighbor benchmarks".

[11] "Approximate Nearest Neighbours for Recommender Systems".

[12] Arya, Sunil; Mount, David (1993). "निश्चित आयामों में अनुमानित निकटतम पड़ोसी प्रश्न". Proceedings of the Fourth Annual {ACM/SIGACT-SIAM} Symposium on Discrete Algorithms, 25–27 January 1993, Austin, Texas.: 271–280.

[voroNet-13] Olivier, Beaumont; Kermarrec, Anne-Marie; Marchal, Loris; Rivière, Etienne (2006). "Voro Net: A scalable object network based on Voronoi tessellations" (PDF). 2007 IEEE International Parallel and Distributed Processing Symposium. Vol. RR-5833. pp. 23–29. doi:10.1109/IPDPS.2007.370210. ISBN 1-4244-0909-8. S2CID 8844431.

[rayNet-14] Olivier, Beaumont; Kermarrec, Anne-Marie; Rivière, Etienne (2007). Peer to Peer Multidimensional Overlays: Approximating Complex Structures. pp. 315–328. CiteSeerX 10.1.1.626.2980. doi:10.1007/978-3-540-77096-1_23. ISBN 978-3-540-77095-4. {{cite book}}: |journal= ignored (help)

[15] Toussaint, Godfried (1980). "एक परिमित तलीय समुच्चय का सापेक्ष पड़ोस ग्राफ़". Pattern Recognition. 12 (4): 261–268. Bibcode:1980PatRe..12..261T. doi:10.1016/0031-3203(80)90066-7.

[16] A. Rajaraman & J. Ullman (2010). "Mining of Massive Datasets, Ch. 3".

[17] Weber, Roger; Blott, Stephen. "समानता खोज के लिए एक अनुमान-आधारित डेटा संरचना" (PDF). S2CID 14613657. Archived from the original (PDF) on 2017-03-04. {{cite journal}}: Cite journal requires |journal= (help)

[18] Ramaswamy, Sharadh; Rose, Kenneth (2007). "छवि डेटाबेस में समानता खोज के लिए अनुकूली क्लस्टर-दूरी बाउंडिंग". ICIP.

[19] Ramaswamy, Sharadh; Rose, Kenneth (2010). "उच्च-आयामी अनुक्रमण के लिए अनुकूली क्लस्टर-दूरी बाउंडिंग". TKDE.

[20] Arya, S.; Mount, D. M.; Netanyahu, N. S.; Silverman, R.; Wu, A. (1998). "अनुमानित निकटतम पड़ोसी खोज के लिए एक इष्टतम एल्गोरिदम" (PDF). Journal of the ACM. 45 (6): 891–923. CiteSeerX 10.1.1.15.3125. doi:10.1145/293347.293348. S2CID 8193729. Archived from the original (PDF) on 2016-03-03. Retrieved 2009-05-29.

[21] Clarkson, Kenneth L. (1983), "Fast algorithms for the all nearest neighbors problem", 24th IEEE Symp. Foundations of Computer Science, (FOCS '83), pp. 226–232, doi:10.1109/SFCS.1983.16, ISBN 978-0-8186-0508-6, S2CID 16665268.

[Vaidya-22] 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]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

@@ Line 1: / Line 1: @@
 {{Short description|Optimization problem in computer science}}
-निकटतम पड़ोसी खोज (एनएनएस), निकटता खोज के रूप के रूप में, किसी दिए गए सेट में उस बिंदु को खोजने की [[अनुकूलन समस्या]] है जो किसी दिए गए बिंदु के सबसे करीब (या सबसे समान) है। निकटता को आम तौर पर असमानता फ़ंक्शन के संदर्भ में व्यक्त किया जाता है: जितनी कम समानता वस्तुओं को मापती है, फ़ंक्शन मान उतना ही बड़ा होता है।
+'''निकटतम नेबर सर्च (एनएनएस),''' निकटतम खोज के रूप किसी दिए गए समुच्चय में उस बिंदु को खोजने की [[अनुकूलन समस्या]] है जो किसी दिए गए बिंदु के सबसे समीप (या सबसे समान) है। निकटतम को सामान्यतः असमानता फलन के संदर्भ में व्यक्त किया जाता है: जितनी कम समानता वस्तुओं को मापती है, फलन मान उतना ही बड़ा होता है।
-औपचारिक रूप से, निकटतम-पड़ोसी (एनएन) खोज समस्या को इस प्रकार परिभाषित किया गया है: स्थान ''एम'' में बिंदुओं का सेट ''एस'' और क्वेरी बिंदु ''क्यू'' ∈ ''एम'' दिया गया है, ''S'' से ''q'' में निकटतम बिंदु खोजें। वॉल्यूम में [[डोनाल्ड नुथ]]। ''[[कंप्यूटर प्रोग्रामिंग की कला]]'' (1973) के 3 में इसे डाकघर की समस्या कहा गया है, जिसमें निकटतम डाकघर के लिए निवास आवंटित करने के आवेदन का जिक्र है। इस समस्या का प्रत्यक्ष सामान्यीकरण ''k''-NN खोज है, जहां हमें ''k'' निकटतम बिंदु खोजने की आवश्यकता होती है।
+औपचारिक रूप से निकटतम-नेबर (एनएन) खोज समस्या को निम्नलिखित इस प्रकार परिभाषित किया गया है: किसी स्थान ''M'' में बिंदुओं का समुच्चय ''S'' और क्वेरी बिंदु ''q'' ∈ ''M'' दिया गया है ''S'' में ''q'' में निकटतम बिंदु ''q'' खोजें और वॉल्यूम में [[डोनाल्ड नुथ]] या ''[[कंप्यूटर प्रोग्रामिंग की कला]]'' (1973) के 3 में इसे निकटतम डाकघर को निवास आवंटित करने के आवेदन का जिक्र करते हुए इसे डाकघर की समस्या कहा गया है। इस समस्या का प्रत्यक्ष सामान्यीकरण ''k''-NN खोज है, जहां हमें ''k'' निकटतम बिंदु खोजने की आवश्यकता होती है।
-आमतौर पर ''एम'' [[मीट्रिक स्थान]] है और असमानता को [[दूरी मीट्रिक]] के रूप में व्यक्त किया जाता है, जो सममित है और त्रिकोण असमानता को संतुष्ट करता है। इससे भी अधिक सामान्य, ''एम'' को ''डी''-आयामी [[सदिश स्थल]] के रूप में लिया जाता है जहां असमानता को [[यूक्लिडियन दूरी]], [[टैक्सीकैब ज्यामिति]] या अन्य [[सांख्यिकीय दूरी]] का उपयोग करके मापा जाता है। हालाँकि, असमानता फ़ंक्शन मनमाना हो सकता है। उदाहरण असममित [[ब्रेगमैन विचलन]] है, जिसके लिए त्रिभुज असमानता लागू नहीं होती है।<ref name=Cayton2008>{{Cite book
+सामान्यतः ''M'' [[मीट्रिक स्थान]] है और असमानता को [[दूरी मीट्रिक]] के रूप में व्यक्त किया जाता है जो सममित है और त्रिकोण असमानता को संतुष्ट करता है। इससे भी अधिक सामान्य ''M'' को ''d''-आयामी [[सदिश स्थल]] के रूप में लिया जाता है जहां असमानता को [[यूक्लिडियन दूरी]], [[टैक्सीकैब ज्यामिति]] या अन्य [[सांख्यिकीय दूरी]] का उपयोग करके मापा जाता है। चूँकि असमानता फलन इच्छानुसार हो सकता है। उदाप्रत्येकण असममित [[ब्रेगमैन विचलन]] है जिसके लिए त्रिभुज असमानता प्रयुक्त नहीं होती है।<ref name="Cayton2008">{{Cite book
   | last1 = Cayton | first1 = Lawerence
   | year = 2008
@@ Line 15: / Line 15: @@
   | s2cid = 12169321
   }}</ref>
 ==अनुप्रयोग==
-निकटतम पड़ोसी खोज समस्या अनुप्रयोग के कई क्षेत्रों में उत्पन्न होती है, जिनमें शामिल हैं:
+निकटतम नेबर सर्च समस्या अनुप्रयोग के अनेक क्षेत्रों में उत्पन्न होती है जिनमें सम्मिलित हैं:
-* पैटर्न पहचान - विशेष रूप से ऑप्टिकल कैरेक्टर पहचान के लिए
+* क्रम पहचान - विशेष रूप से ऑप्टिकल कैरेक्टर पहचान के लिए
-* [[सांख्यिकीय वर्गीकरण]] - के-निकटतम पड़ोसी एल्गोरिदम देखें
+* [[सांख्यिकीय वर्गीकरण]] - के-निकटतम नेबर एल्गोरिदम देखें
 * [[कंप्यूटर दृष्टि]] - पॉइंट क्लाउड पंजीकरण के लिए<ref>Qiu, Deyuan, Stefan May, and Andreas Nüchter. [https://core.ac.uk/download/pdf/22872975.pdf "GPU-accelerated nearest neighbor search for 3D registration."] International conference on computer vision systems. Springer, Berlin, Heidelberg, 2009.</ref>
 * [[कम्प्यूटेशनल ज्यामिति]] - बिंदुओं की निकटतम जोड़ी समस्या देखें
 * [[डेटाबेस]] - उदा. [[सामग्री-आधारित छवि पुनर्प्राप्ति]]
-* [[कोडिंग सिद्धांत]] - डिकोडिंग विधियां देखें
+* [[कोडिंग सिद्धांत]] - अधिकतम संभावना डिकोडिंग विधियां देखें
 * सिमेंटिक खोज
-* डेटा संपीड़न - [[MPEG-2]] मानक देखें
+* डेटा संपीड़न - [[Index.php?title=एमपईजी-2|एमपईजी-2]] मानक देखें
 * [[रोबोटिक]] सेंसिंग<ref name=panSearch>{{cite conference|last1=Bewley|first1=A.|last2=Upcroft|first2=B.|date=2013|title=Advantages of Exploiting Projection Structure for Segmenting Dense 3D Point Clouds|conference=Australian Conference on Robotics and Automation |url=http://www.araa.asn.au/acra/acra2013/papers/pap148s1-file1.pdf}}</ref>
-* [[अनुशंसा प्रणाली]], उदा. सहयोगात्मक फ़िल्टरिंग देखें
+* [[अनुशंसा प्रणाली]] उदा. सहयोगात्मक फ़िल्टरिंग देखें
 * [[ इंटरनेट विपणन | इंटरनेट विपणन]] - [[प्रासंगिक विज्ञापन]] और [[व्यवहारिक लक्ष्यीकरण]] देखें
 * [[डीएनए श्रृंखला बनाना]]
 * वर्तनी जाँच - सही वर्तनी का सुझाव देना
-* [[साहित्यिक चोरी का पता लगाना]]
+* [[साहित्यिक चोरी का पता लगाना|प्लागिअरिस्म डिटेक्शन]]
-* पेशेवर एथलीटों के करियर पथ की भविष्यवाणी के लिए [[समानता स्कोर]]।
+* प्रोफेशनल एथलीटों के करियर पथ की पूर्वानुमान के लिए [[समानता स्कोर]]।
-* [[क्लस्टर विश्लेषण]] - अवलोकनों के सेट को उपसमूहों (जिन्हें क्लस्टर कहा जाता है) में असाइन करना ताकि ही क्लस्टर में अवलोकन कुछ अर्थों में समान हों, आमतौर पर यूक्लिडियन दूरी पर आधारित होते हैं
+* [[क्लस्टर विश्लेषण]] - अवलोकनों के समुच्चय को उपसमूहों (जिन्हें क्लस्टर कहा जाता है) में असाइन करना जिससे ही क्लस्टर में अवलोकन कुछ अर्थों में समान हों, सामान्यतः यह यूक्लिडियन दूरी पर आधारित होते हैं
 *[[रासायनिक समानता]]
-* मोशन प्लानिंग#सैंपलिंग-आधारित एल्गोरिदम|सैंपलिंग-आधारित मोशन प्लानिंग
+* मोशन प्लानिंग या सैंपलिंग-आधारित एल्गोरिदम
+*नमूना-आधारित गति योजना
-==तरीके==
+==विधियाँ==
-एनएनएस समस्या के विभिन्न समाधान प्रस्तावित किए गए हैं। एल्गोरिदम की गुणवत्ता और उपयोगिता प्रश्नों की समय जटिलता के साथ-साथ किसी भी खोज डेटा संरचना की स्थान जटिलता द्वारा निर्धारित की जाती है जिसे बनाए रखा जाना चाहिए। अनौपचारिक अवलोकन जिसे आमतौर पर आयामीता के अभिशाप के रूप में जाना जाता है, बताता है कि बहुपद प्रीप्रोसेसिंग और पॉलीलॉगरिदमिक खोज समय का उपयोग करके उच्च-आयामी यूक्लिडियन अंतरिक्ष में एनएनएस के लिए कोई सामान्य-उद्देश्य सटीक समाधान नहीं है।
+एनएनएस समस्या के विभिन्न समाधान प्रस्तावित किए गए हैं। इस प्रकार एल्गोरिदम की गुणवत्ता और उपयोगिता प्रश्नों की समय जटिलता के साथ-साथ किसी भी खोज डेटा संरचना की स्थान जटिलता द्वारा निर्धारित की जाती है जिसे बनाए रखा जाना चाहिए। अनौपचारिक अवलोकन जिसे सामान्यतः आयामी स्थिति के अभिशाप के रूप में जाना जाता है, यह बताता है कि बहुपद प्रीप्रोसेसिंग और पॉलीलॉगरिदमिक खोज समय का उपयोग करके उच्च-आयामी यूक्लिडियन सम्मिस्ट में एनएनएस के लिए कोई सामान्य-उद्देश्य स्पष्ट समाधान नहीं है।
-=== सटीक तरीके ===
+=== स्पष्ट विधियाँ ===
 ====रैखिक खोज====
-एनएनएस समस्या का सबसे सरल समाधान अब तक के सर्वश्रेष्ठ का ट्रैक रखते हुए, डेटाबेस में क्वेरी बिंदु से हर दूसरे बिंदु तक की दूरी की गणना करना है। यह एल्गोरिदम, जिसे कभी-कभी अनुभवहीन दृष्टिकोण के रूप में जाना जाता है, का चलने का समय O(dN) है, जहां N, S की [[प्रमुखता]] है और d, S की आयामीता है। बनाए रखने के लिए कोई खोज डेटा संरचनाएं नहीं हैं, इसलिए रैखिक खोज है डेटाबेस के भंडारण से परे कोई स्थान जटिलता नहीं। सामान्य खोज, औसतन, उच्च आयामी स्थानों पर अंतरिक्ष विभाजन दृष्टिकोण से बेहतर प्रदर्शन कर सकती है।<ref>{{cite book|chapter=A quantitative analysis and performance study for similarity search methods in high dimensional spaces|last1=Weber|first1=Roger|last2=Schek|first2=Hans-J.|last3=Blott|first3=Stephen | title=VLDB '98 Proceedings of the 24rd International Conference on Very Large Data Bases | pages=194–205 | year=1998 | chapter-url=http://www.vldb.org/conf/1998/p194.pdf}}</ref> दूरी की तुलना के लिए पूर्ण दूरी की आवश्यकता नहीं है, केवल सापेक्ष दूरी की आवश्यकता है। ज्यामितीय समन्वय प्रणालियों में दो निर्देशांकों के बीच की दूरी की गणना से वर्गमूल गणना को हटाकर दूरी की गणना में काफी तेजी लाई जा सकती है। दूरी की तुलना अभी भी समान परिणाम देगी।
+एनएनएस समस्या का सबसे सरल समाधान अब तक के सर्वश्रेष्ठ का ट्रैक रखते हुए डेटाबेस में क्वेरी बिंदु से प्रत्येक दूसरे बिंदु तक की दूरी की गणना करना है। यह एल्गोरिदम, जिसे कभी-कभी अनुभवहीन दृष्टिकोण के रूप में जाना जाता है इसका चलने का समय ''O''(''dN'')) है जहां N, S की [[प्रमुखता]] है और d, S की आयामीता है। इसको बनाए रखने के लिए कोई खोज डेटा संरचनाएं नहीं हैं, इसलिए रैखिक खोज में डेटाबेस के संचयन से परे कोई स्थान जटिलता नहीं हैं। सामान्य खोज औसतन उच्च आयामी स्थानों पर सम्मिस्ट विभाजन दृष्टिकोण से उत्तम प्रदर्शन कर सकती है।<ref>{{cite book|chapter=A quantitative analysis and performance study for similarity search methods in high dimensional spaces|last1=Weber|first1=Roger|last2=Schek|first2=Hans-J.|last3=Blott|first3=Stephen | title=VLDB '98 Proceedings of the 24rd International Conference on Very Large Data Bases | pages=194–205 | year=1998 | chapter-url=http://www.vldb.org/conf/1998/p194.pdf}}</ref>
+दूरी की तुलना के लिए पूर्ण दूरी की आवश्यकता नहीं है, इसमें अतिरिक्त सापेक्ष दूरी की आवश्यकता होती है। और ज्यामितीय समन्वय प्रणालियों में दो निर्देशांकों के मध्य की दूरी की गणना से वर्गमूल गणना को हटाकर दूरी की गणना में अधिक तेजी लाई जा सकती है। और दूरी की तुलना अभी भी समान परिणाम देती हैं।
-====[[अंतरिक्ष विभाजन]]====
+====[[अंतरिक्ष विभाजन|सम्मिस्ट विभाजन]]====
-के दशक से, शाखा और बाध्य पद्धति को समस्या पर लागू किया गया है। यूक्लिडियन अंतरिक्ष के मामले में, यह दृष्टिकोण [[स्थानिक सूचकांक]] या स्थानिक पहुंच विधियों को शामिल करता है। एनएनएस समस्या को हल करने के लिए कई अंतरिक्ष विभाजन|अंतरिक्ष-विभाजन विधियां विकसित की गई हैं। शायद सबसे सरल [[ के-डी पेड़ |के-डी पेड़]] है, जो खोज स्थान को मूल क्षेत्र के आधे बिंदुओं वाले दो क्षेत्रों में पुनरावृत्त रूप से विभाजित करता है। प्रत्येक विभाजन पर क्वेरी बिंदु का मूल्यांकन करके क्वेरी को जड़ से पत्ती तक पेड़ के ट्रैवर्सल के माध्यम से निष्पादित किया जाता है। क्वेरी में निर्दिष्ट दूरी के आधार पर, पड़ोसी शाखाओं जिनमें हिट हो सकती हैं, का भी मूल्यांकन करने की आवश्यकता हो सकती है। निरंतर आयाम क्वेरी समय के लिए, औसत जटिलता O(लॉग एन) है<ref>{{cite web|title=केडी पेड़ों पर एक परिचयात्मक ट्यूटोरियल|author=Andrew Moore|url=http://www.autonlab.com/autonweb/14665/version/2/part/5/data/moore-tutorial.pdf?branch=main&language=en|access-date=2008-10-03|archive-url=https://web.archive.org/web/20160303203122/http://www.autonlab.com/autonweb/14665/version/2/part/5/data/moore-tutorial.pdf?branch=main&language=en|archive-date=2016-03-03|url-status=dead}}</ref> बेतरतीब ढंग से वितरित बिंदुओं के मामले में, सबसे खराब स्थिति जटिलता O(kN^(1-1/k)) है<ref name=Lee1977>{{Cite journal
+के दशक से, शाखा और बाध्य पद्धति को समस्या पर प्रयुक्त किया गया है। यूक्लिडियन सम्मिस्ट के स्तिथियों में, यह दृष्टिकोण [[स्थानिक सूचकांक]] या स्थानिक पहुंच विधियों को सम्मिलित करता है। एनएनएस समस्या को हल करने के लिए अनेक सम्मिस्ट विभाजन सम्मिस्ट-विभाजन विधियां विकसित की गई हैं। संभवतः सबसे सरल [[ के-डी पेड़ |k-d ट्री]] है, जो मूल क्षेत्र के आधे बिंदुओं वाले खोज स्थान को दो क्षेत्रों में पुनरावृत्त रूप से विभाजित करता है। और प्रत्येक विभाजन पर क्वेरी बिंदु का मूल्यांकन करके क्वेरी को रूट से लीव्स तक ट्री के ट्रैवर्सल के माध्यम से निष्पादित किया जाता है। इस प्रकार क्वेरी में निर्दिष्ट दूरी के आधार पर, निकटतम शाखाओं जिनमें हिट हो सकती हैं, इसलिए इनका भी मूल्यांकन करने की आवश्यकता हो सकती है। और निरंतर आयाम क्वेरी समय के लिए, औसत जटिलता ''O''(log ''N'') होता है| <ref>{{cite web|title=केडी पेड़ों पर एक परिचयात्मक ट्यूटोरियल|author=Andrew Moore|url=http://www.autonlab.com/autonweb/14665/version/2/part/5/data/moore-tutorial.pdf?branch=main&language=en|access-date=2008-10-03|archive-url=https://web.archive.org/web/20160303203122/http://www.autonlab.com/autonweb/14665/version/2/part/5/data/moore-tutorial.pdf?branch=main&language=en|archive-date=2016-03-03|url-status=dead}}</ref> उत्तम ढंग से वितरित बिंदुओं के स्तिथियों में, सबसे व्यर्थ स्थिति जटिलता ''O''(''kN''^(1-1/''k''))है| <ref name="Lee1977">{{Cite journal
   | last1 = Lee | first1 = D. T. | author1-link = Der-Tsai Lee
   | last2 = Wong | first2 = C. K.
@@ Line 58: / Line 59: @@
   | pages = 23–29
   | doi = 10.1007/BF00263763
-  | s2cid = 36580055 }}</ref> वैकल्पिक रूप से [[ आर-वृक्ष |आर-वृक्ष]] डेटा संरचना को गतिशील संदर्भ में निकटतम पड़ोसी खोज का समर्थन करने के लिए डिज़ाइन किया गया था, क्योंकि इसमें [[ आर* पेड़ |आर* पेड़]] जैसे सम्मिलन और विलोपन के लिए कुशल एल्गोरिदम हैं।<ref>{{Cite conference | doi = 10.1145/223784.223794| chapter = Nearest neighbor queries| title = Proceedings of the 1995 ACM SIGMOD international conference on Management of data – SIGMOD '95| pages = 71| year = 1995| last1 = Roussopoulos | first1 = N. | last2 = Kelley | first2 = S. | last3 = Vincent | first3 = F. D. R. | isbn = 0897917316}}</ref> आर-पेड़ न केवल यूक्लिडियन दूरी के लिए निकटतम पड़ोसी प्रदान कर सकते हैं, बल्कि अन्य दूरियों के साथ भी इसका उपयोग किया जा सकता है।
+  | s2cid = 36580055 }}</ref> वैकल्पिक रूप से [[ आर-वृक्ष |R-ट्री]] डेटा संरचना को गतिशील संदर्भ में निकटतम नेबर सर्च का समर्थन करने के लिए डिज़ाइन किया गया था, क्योंकि इसमें [[ आर* पेड़ |आर* ट्री]] जैसे सम्मिलन और विलोपन के लिए कुशल एल्गोरिदम हैं।<ref>{{Cite conference | doi = 10.1145/223784.223794| chapter = Nearest neighbor queries| title = Proceedings of the 1995 ACM SIGMOD international conference on Management of data – SIGMOD '95| pages = 71| year = 1995| last1 = Roussopoulos | first1 = N. | last2 = Kelley | first2 = S. | last3 = Vincent | first3 = F. D. R. | isbn = 0897917316}}</ref> R-ट्री न अतिरिक्त यूक्लिडियन दूरी के लिए निकटतम नेबर प्रदान कर सकते हैं, किंतु अन्य दूरियों के साथ भी इसका उपयोग किया जा सकता है।
-सामान्य मीट्रिक स्थान के मामले में, शाखा-और-बाउंड दृष्टिकोण को [[मीट्रिक पेड़]] दृष्टिकोण के रूप में जाना जाता है। विशेष उदाहरणों में [[ वीपी-वृक्ष |वीपी-वृक्ष]] और [[ बीके-वृक्ष |बीके-वृक्ष]] विधियां शामिल हैं।
+सामान्य मीट्रिक स्थान के स्तिथियों में, शाखा-और-बाउंड दृष्टिकोण को [[मीट्रिक पेड़|मीट्रिक ट्री]] दृष्टिकोण के रूप में जाना जाता है। विशेष उदाहरणों में [[ वीपी-वृक्ष |वीपी-ट्री]] और [[ बीके-वृक्ष |बीके-ट्री]] विधियां सम्मिलित हैं।
--आयामी स्थान से लिए गए बिंदुओं के सेट का उपयोग करके और [[बाइनरी स्पेस विभाजन]] में डालकर, और उसी स्थान से लिया गया क्वेरी बिंदु दिया गया, क्वेरी बिंदु के निकटतम बिंदु-क्लाउड बिंदु को खोजने की समस्या का संभावित समाधान है एल्गोरिदम के निम्नलिखित विवरण में दिया गया है।
+-आयामी स्थान से लिए दिए गए बिंदुओं के समुच्चय का उपयोग करके और [[बाइनरी स्पेस विभाजन]] में डालकर और उसी स्थान से लिया गया क्वेरी बिंदु दिया गया हैं क्वेरी बिंदु के निकटतम बिंदु-क्लाउड बिंदु को खोजने की समस्या का संभावित समाधान है और यह एल्गोरिदम के निम्नलिखित विवरण में दिया गया है।
-(सख्ती से कहें तो, ऐसा कोई बिंदु मौजूद नहीं हो सकता है, क्योंकि यह अद्वितीय नहीं हो सकता है। लेकिन व्यवहार में, आमतौर पर हम केवल सभी बिंदु-क्लाउड बिंदुओं के सबसेट में से किसी को खोजने की परवाह करते हैं जो किसी दिए गए क्वेरी बिंदु से सबसे कम दूरी पर मौजूद होते हैं .) विचार यह है कि, पेड़ की प्रत्येक शाखा के लिए, अनुमान लगाएं कि बादल में निकटतम बिंदु क्वेरी बिंदु वाले आधे स्थान में रहता है। यह मामला नहीं हो सकता है, लेकिन यह अच्छा अनुमान है। अनुमानित अर्ध-स्थान के लिए समस्या को हल करने की सभी परेशानियों से गुजरने के बाद, अब इस परिणाम द्वारा लौटाई गई दूरी की तुलना क्वेरी बिंदु से विभाजन तल तक की सबसे छोटी दूरी से करें। यह बाद वाली दूरी क्वेरी बिंदु और निकटतम संभावित बिंदु के बीच की दूरी है जो खोजे न गए आधे स्थान में मौजूद हो सकती है। यदि यह दूरी पिछले परिणाम में दी गई दूरी से अधिक है, तो स्पष्ट रूप से अन्य आधे स्थान की खोज करने की कोई आवश्यकता नहीं है। यदि ऐसी कोई आवश्यकता है, तो आपको अन्य आधे स्थान के लिए समस्या को हल करने की परेशानी से गुजरना होगा, और फिर उसके परिणाम की तुलना पिछले परिणाम से करनी होगी, और फिर उचित परिणाम लौटाना होगा। इस एल्गोरिदम का प्रदर्शन रैखिक समय की तुलना में लॉगरिदमिक समय के करीब होता है जब क्वेरी बिंदु क्लाउड के नजदीक होता है, क्योंकि क्वेरी बिंदु और निकटतम बिंदु-क्लाउड बिंदु के बीच की दूरी शून्य के करीब होती है, एल्गोरिदम को केवल लुक-अप का उपयोग करने की आवश्यकता होती है सही परिणाम प्राप्त करने के लिए क्वेरी बिंदु को कुंजी के रूप में उपयोग करें।
+(सख्ती से कहें तब, ऐसा कोई बिंदु उपस्थित नहीं हो सकता है, क्योंकि यह अद्वितीय नहीं हो सकता है। किन्तु वास्तव में, सामान्यतः हम अतिरिक्त सभी बिंदु-क्लाउड बिंदुओं के सब समुच्चय में से किसी को खोजने की परवाह करते हैं और जो किसी दिए गए क्वेरी बिंदु से सबसे कम दूरी पर उपस्थित होते हैं) इस प्रकार विचार यह है कि, ट्री की प्रत्येक शाखा के लिए, अनुमान लगाएं कि पश्चात्ल में निकटतम बिंदु क्वेरी बिंदु वाले आधे स्थान में रहता है। यह स्थितिया नहीं हो सकती है, किन्तु यह श्रेष्ठ अनुमान है। कि अनुमानित अर्ध-स्थान के लिए समस्या को हल करने की सभी परेशानियों से गुजरने के पश्चात्ब अब इस परिणाम द्वारा लौटाई गई दूरी की तुलना क्वेरी बिंदु से विभाजन तल तक की सबसे छोटी दूरी से तय करें।और यह पश्चात् वाली दूरी क्वेरी बिंदु और निकटतम संभावित बिंदु के मध्य की दूरी है जो बिना खोजे गए आधे स्थान में उपस्थित हो सकती है। इस प्रकार यदि यह दूरी पिछले परिणाम में दी गई दूरी से अधिक होती है तब स्पष्ट रूप से अन्य आधे स्थान की खोज करने की कोई आवश्यकता नहीं होती है। यदि ऐसी कोई आवश्यकता है, तब आपको अन्य आधे स्थान के लिए समस्या को हल करने की परेशानी से निकलना होगा, और फिर उसके परिणाम की तुलना पिछले परिणाम से करनी होगी, और फिर उसे उचित परिणाम लौटाना होगा। इस एल्गोरिदम का प्रदर्शन रैखिक समय की तुलना में लॉगरिदमिक समय के समीप होता है और जब क्वेरी बिंदु क्लाउड के समीप होता है, क्योंकि क्वेरी बिंदु और निकटतम बिंदु-क्लाउड बिंदु के मध्य की दूरी शून्य के समीप होती है, एल्गोरिदम को अतिरिक्त लुक-अप का उपयोग करने की आवश्यकता होती है और सही परिणाम प्राप्त करने के लिए क्वेरी बिंदु को कुंजी के रूप में उपयोग करना होता हैं।
 === सन्निकटन विधियाँ ===
-एक अनुमानित निकटतम पड़ोसी खोज एल्गोरिदम को उन बिंदुओं को वापस करने की अनुमति है जिनकी क्वेरी से दूरी अधिकतम है <math>c</math> क्वेरी से उसके निकटतम बिंदुओं की दूरी का गुना। इस दृष्टिकोण की अपील यह है कि, कई मामलों में, अनुमानित निकटतम पड़ोसी लगभग उतना ही अच्छा होता है जितना कि सटीक पड़ोसी। विशेष रूप से, यदि दूरी माप उपयोगकर्ता की गुणवत्ता की धारणा को सटीक रूप से पकड़ लेता है, तो दूरी में छोटे अंतर से कोई फर्क नहीं पड़ना चाहिए।<ref>{{Cite book|last1=Andoni|first1=A.|last2=Indyk|first2=P.|date=2006-10-01|chapter=Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions|title= 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06)|pages=459–468|doi=10.1109/FOCS.2006.49|isbn=978-0-7695-2720-8|citeseerx=10.1.1.142.3471}}</ref>
+एक अनुमानित निकटतम नेबर सर्च एल्गोरिदम को उन बिंदुओं को वापस करने की अनुमति होती है जिनकी क्वेरी से दूरी अधिकतम हैं <math>c</math> क्वेरी से उसके निकटतम बिंदुओं की दूरी <math>c</math> का गुना हैं। इस दृष्टिकोण की अपील यह है कि अनेक स्थितियों में अनुमानित निकटतम नेबर लगभग उतना ही श्रेष्ठ होता है जितना कि स्पष्ट निकटतम होता हैं। विशेष रूप से यदि दूरी माप उपयोगकर्ता की गुणवत्ता की धारणा को स्पष्ट रूप से पकड़ लेता है, तब दूरी में छोटे अंतर से कोई अंतर नहीं पड़ना चाहिए।<ref>{{Cite book|last1=Andoni|first1=A.|last2=Indyk|first2=P.|date=2006-10-01|chapter=Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions|title= 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06)|pages=459–468|doi=10.1109/FOCS.2006.49|isbn=978-0-7695-2720-8|citeseerx=10.1.1.142.3471}}</ref>
+====निकटता निकटतम ग्राफ़ में ग्रीडी खोज====
+निकटता ग्राफ़ विधियाँ (जैसे एचएनएसडब्ल्यू<ref name=":0">{{cite arXiv|last1=Malkov|first1=Yury|last2=Yashunin|first2=Dmitry|date=2016|title=पदानुक्रमित नौगम्य लघु विश्व ग्राफ़ का उपयोग करके कुशल और मजबूत अनुमानित निकटतम पड़ोसी खोज|eprint=1603.09320|class=cs.DS}}</ref>) को निकटतम नेबर की खोज के लिए वर्तमान अत्याधुनिक माना जाता है।<ref name=":0" /><ref>{{Cite web|url=https://erikbern.com/2018/06/17/new-approximate-nearest-neighbor-benchmarks.html|title=New approximate nearest neighbor benchmarks}}</ref><ref>{{Cite web|url=https://www.benfrederickson.com/approximate-nearest-neighbours-for-recommender-systems/|title=Approximate Nearest Neighbours for Recommender Systems}}</ref>
-====निकटता पड़ोस ग्राफ़ में लालची खोज====
-निकटता ग्राफ़ विधियाँ (जैसे HNSW<ref name=":0">{{cite arXiv|last1=Malkov|first1=Yury|last2=Yashunin|first2=Dmitry|date=2016|title=पदानुक्रमित नौगम्य लघु विश्व ग्राफ़ का उपयोग करके कुशल और मजबूत अनुमानित निकटतम पड़ोसी खोज|eprint=1603.09320|class=cs.DS}}</ref>) को निकटतम पड़ोसियों की खोज के लिए वर्तमान अत्याधुनिक माना जाता है।<ref name=":0" /><ref>{{Cite web|url=https://erikbern.com/2018/06/17/new-approximate-nearest-neighbor-benchmarks.html|title=New approximate nearest neighbor benchmarks}}</ref><ref>{{Cite web|url=https://www.benfrederickson.com/approximate-nearest-neighbours-for-recommender-systems/|title=Approximate Nearest Neighbours for Recommender Systems}}</ref> विधियाँ निकटता पड़ोस ग्राफ़ में लालची ट्रैवर्सिंग पर आधारित हैं <math>G(V,E)</math> जिसमें हर बिंदु <math>x_i \in S </math> शिखर के साथ विशिष्ट रूप से जुड़ा हुआ है <math>v_i \in V </math>. सेट S में क्वेरी q के निकटतम पड़ोसियों की खोज ग्राफ़ में शीर्ष की खोज का रूप लेती है <math>G(V,E)</math>.
-मूल एल्गोरिदम - लालची खोज - निम्नानुसार काम करती है: खोज प्रवेश-बिंदु शीर्ष से शुरू होती है <math>v_i \in V </math> क्वेरी q से उसके पड़ोस के प्रत्येक शीर्ष तक की दूरी की गणना करके <math>\{v_j:(v_i,v_j) \in E\}</math>, और फिर न्यूनतम दूरी मान वाला शीर्ष ढूँढता है। यदि क्वेरी और चयनित शीर्ष के बीच की दूरी का मान क्वेरी और वर्तमान तत्व के बीच की दूरी से छोटा है, तो एल्गोरिदम चयनित शीर्ष पर चला जाता है, और यह नया प्रवेश-बिंदु बन जाता है। एल्गोरिदम तब रुक जाता है जब यह स्थानीय न्यूनतम तक पहुंच जाता है: शीर्ष जिसके पड़ोस में शीर्ष नहीं होता है जो शीर्ष की तुलना में क्वेरी के करीब होता है।
-निकटता पड़ोस ग्राफ़ के विचार का कई प्रकाशनों में उपयोग किया गया, जिसमें आर्य और माउंट का मौलिक पेपर भी शामिल है,<ref>{{cite journal|last1=Arya|first1=Sunil|last2=Mount|first2=David|date=1993|title=निश्चित आयामों में अनुमानित निकटतम पड़ोसी प्रश्न|journal=Proceedings of the Fourth Annual {ACM/SIGACT-SIAM} Symposium on Discrete Algorithms, 25–27 January 1993, Austin, Texas.|pages=271–280}}</ref> विमान के लिए वोरोनेट प्रणाली में,<ref name="voroNet">{{Cite book|last1=Olivier|first1=Beaumont|last2=Kermarrec|first2=Anne-Marie|last3=Marchal|first3=Loris|last4=Rivière|first4=Etienne|year=2006|chapter=Voro ''Net'': A scalable object network based on Voronoi tessellations|title= 2007 IEEE International Parallel and Distributed Processing Symposium|volume=RR-5833|issue=1|pages=23–29|doi=10.1109/IPDPS.2007.370210|isbn=1-4244-0909-8|s2cid=8844431|chapter-url=https://hal.inria.fr/inria-00071210/PDF/RR-5833.pdf}}</ref> के लिए RayNet प्रणाली में <math>\mathbb{E}^n</math>,<ref name="rayNet">{{Cite book|last1=Olivier|first1=Beaumont|last2=Kermarrec|first2=Anne-Marie|last3=Rivière|first3=Etienne|year=2007|title=Peer to Peer Multidimensional Overlays: Approximating Complex Structures|journal=Principles of Distributed Systems|volume=4878|pages=315–328|doi=10.1007/978-3-540-77096-1_23|isbn=978-3-540-77095-4|citeseerx=10.1.1.626.2980}}</ref> और मेट्रिज़्ड स्मॉल वर्ल्ड में<ref name="msw2014">{{Cite journal|last1=Malkov|first1=Yury|last2=Ponomarenko|first2=Alexander|last3=Krylov|first3=Vladimir|last4=Logvinov|first4=Andrey|year=2014|title=नौगम्य छोटे विश्व ग्राफ़ पर आधारित अनुमानित निकटतम पड़ोसी एल्गोरिदम|journal=Information Systems|volume=45|pages=61–68|doi=10.1016/j.is.2013.10.006|s2cid=9896397 }}</ref> और एचएनएसडब्ल्यू<ref name=":0" />दूरी फ़ंक्शन वाले रिक्त स्थान के सामान्य मामले के लिए एल्गोरिदम। इन कार्यों से पहले टूसेंट का अग्रणी पेपर प्रकाशित हुआ था, जिसमें उन्होंने सापेक्ष पड़ोस ग्राफ की अवधारणा पेश की थी।<ref>{{cite journal|last1=Toussaint|first1=Godfried|date=1980|title=एक परिमित तलीय समुच्चय का सापेक्ष पड़ोस ग्राफ़|journal=Pattern Recognition|volume=12|issue=4|pages=261–268|doi=10.1016/0031-3203(80)90066-7|bibcode=1980PatRe..12..261T}}</ref>
+विधियाँ निकटता निकटता ग्राफ़ में <math>G(V,E)</math> ग्रीडी ट्रैवर्सिंग पर आधारित होता हैं जिसमें प्रत्येक बिंदु <math>x_i \in S </math> में शीर्ष <math>v_i \in V </math> के साथ विशिष्ट रूप से जुड़ा हुआ है | समुच्चय में क्वेरी q के निकटतम नेबर S ग्राफ़ <math>G(V,E)</math> शीर्ष की खोज का रूप लेती है| मूल एल्गोरिदम - ग्रीडी खोज - निम्नानुसार काम करती है: खोज क्वेरी q से उसके निकटतम <math>\{v_j:(v_i,v_j) \in E\}</math> के प्रत्येक शीर्ष तक की दूरी की गणना करके वी में प्रवेश-बिंदु शीर्ष <math>v_i \in V </math> से प्रारंभ होती है और फिर न्यूनतम दूरी मान वाला शीर्ष खोजता है। यदि क्वेरी और चयनित शीर्ष के मध्य की दूरी का मान क्वेरी और वर्तमान तत्व के मध्य की दूरी से छोटा है, तब एल्गोरिदम चयनित शीर्ष पर चला जाता है, और यह नया प्रवेश-बिंदु बन जाता है। एल्गोरिदम तब रुक जाता है जब यह स्थानीय न्यूनतम तक पहुंच जाता है वह शीर्ष जिसके निकटतम में शीर्ष नहीं होता है जो शीर्ष की तुलना में क्वेरी के समीप होता है।
+निकटतम नेबर ग्राफ़ के विचार का उपयोग कई प्रकाशनों में किया गया था, जिसमें विमान के लिए वोरोनेट प्रणाली में आर्य और माउंट का मौलिक पेपर <math>\mathbb{E}^n</math> के लिए रेनेट प्रणाली में सम्मिलित था।,<ref>{{cite journal|last1=Arya|first1=Sunil|last2=Mount|first2=David|date=1993|title=निश्चित आयामों में अनुमानित निकटतम पड़ोसी प्रश्न|journal=Proceedings of the Fourth Annual {ACM/SIGACT-SIAM} Symposium on Discrete Algorithms, 25–27 January 1993, Austin, Texas.|pages=271–280}}</ref> <ref name="voroNet">{{Cite book|last1=Olivier|first1=Beaumont|last2=Kermarrec|first2=Anne-Marie|last3=Marchal|first3=Loris|last4=Rivière|first4=Etienne|year=2006|chapter=Voro ''Net'': A scalable object network based on Voronoi tessellations|title= 2007 IEEE International Parallel and Distributed Processing Symposium|volume=RR-5833|issue=1|pages=23–29|doi=10.1109/IPDPS.2007.370210|isbn=1-4244-0909-8|s2cid=8844431|chapter-url=https://hal.inria.fr/inria-00071210/PDF/RR-5833.pdf}}</ref> ,<ref name="rayNet">{{Cite book|last1=Olivier|first1=Beaumont|last2=Kermarrec|first2=Anne-Marie|last3=Rivière|first3=Etienne|year=2007|title=Peer to Peer Multidimensional Overlays: Approximating Complex Structures|journal=Principles of Distributed Systems|volume=4878|pages=315–328|doi=10.1007/978-3-540-77096-1_23|isbn=978-3-540-77095-4|citeseerx=10.1.1.626.2980}}</ref> और मेट्रिज़्ड स्मॉल वर्ल्ड और एचएनएसडब्ल्यू <ref name=":0" /> एल्गोरिदम में दूरी फलन वाले स्थानों के सामान्य स्थिति के लिए इन कार्यों से पहले टूसेंट का एक अग्रणी पेपर प्रकाशित हुआ था, जिसमें उन्होंने सापेक्ष पड़ोस ग्राफ की अवधारणा प्रस्तुत की थी <ref>{{cite journal|last1=Toussaint|first1=Godfried|date=1980|title=एक परिमित तलीय समुच्चय का सापेक्ष पड़ोस ग्राफ़|journal=Pattern Recognition|volume=12|issue=4|pages=261–268|doi=10.1016/0031-3203(80)90066-7|bibcode=1980PatRe..12..261T}}</ref>
 ====स्थानीय संवेदनशील हैशिंग====
-[[स्थानीयता संवेदनशील हैशिंग]] (एलएसएच) बिंदुओं पर संचालित कुछ दूरी मीट्रिक के आधार पर अंतरिक्ष में बिंदुओं को 'बाल्टी' में समूहीकृत करने की तकनीक है। चुने गए मीट्रिक के तहत एक-दूसरे के करीब आने वाले बिंदुओं को उच्च संभावना के साथ ही बकेट में मैप किया जाता है।<ref>{{cite web|author1=A. Rajaraman  |author2=J. Ullman |name-list-style=amp | url=http://infolab.stanford.edu/~ullman/mmds.html |title=Mining of Massive Datasets, Ch. 3 |year=2010}}</ref>
+[[स्थानीयता संवेदनशील हैशिंग]] (एलएसएच) बिंदुओं पर संचालित कुछ दूरी मीट्रिक के आधार पर सम्मिस्ट में बिंदुओं को 'बकेट्स' में समूहीकृत करने की विधि है। जिसमे चुने गए मीट्रिक के अनुसार एक-दूसरे के समीप आने वाले बिंदुओं को उच्च संभावना के साथ ही बकेट में मानचित्र किया जाता है।<ref>{{cite web|author1=A. Rajaraman  |author2=J. Ullman |name-list-style=amp | url=http://infolab.stanford.edu/~ullman/mmds.html |title=Mining of Massive Datasets, Ch. 3 |year=2010}}</ref>
+====छोटे आंतरिक आयाम वाले स्थानों में निकटतम नेबर की खोज====
-====छोटे आंतरिक आयाम वाले स्थानों में निकटतम पड़ोसी की खोज====
+[[Index.php?title=वृक्ष की ढकें|ट्री की आवरण]] में सैद्धांतिक सीमा होती है जो डेटा समुच्चय के [[दोहरीकरण स्थिरांक]] पर आधारित होती है। और खोज समय की सीमा ''O''(''c''<sup>12</sup> log ''n'') हैं जहां ''c'' डेटा समुच्चय की [[विस्तारशीलता स्थिरांक]] होता है।
-[[ वृक्ष को ढकें | वृक्ष को ढकें]] में सैद्धांतिक सीमा होती है जो डेटासेट के [[दोहरीकरण स्थिरांक]] पर आधारित होती है। खोज समय की सीमा O(c) है<sup>12</sup>लॉग एन) जहां सी डेटासेट की [[विस्तारशीलता स्थिरांक]] है।
 ====प्रक्षेपित रेडियल खोज====
-विशेष मामले में जहां डेटा ज्यामितीय बिंदुओं का सघन 3डी मानचित्र है, सेंसिंग तकनीक की प्रक्षेपण ज्यामिति का उपयोग खोज समस्या को नाटकीय रूप से सरल बनाने के लिए किया जा सकता है। इस दृष्टिकोण के लिए आवश्यक है कि 3डी डेटा को दो-आयामी ग्रिड के प्रक्षेपण द्वारा व्यवस्थित किया जाए और यह माना जाए कि डेटा ऑब्जेक्ट सीमाओं के अपवाद के साथ पड़ोसी ग्रिड कोशिकाओं में स्थानिक रूप से सुचारू है। सर्वेक्षण, रोबोटिक्स और स्टीरियो विज़न जैसे अनुप्रयोगों में 3डी सेंसर डेटा से निपटने के दौरान ये धारणाएँ मान्य हैं, लेकिन सामान्य तौर पर असंगठित डेटा के लिए ये मान्य नहीं हो सकती हैं। व्यवहार में इस तकनीक को वास्तविक विश्व स्टीरियो विज़न डेटा पर लागू करने पर k-निकटतम पड़ोसी समस्या के लिए औसत खोज समय O(1) या O(K) होता है।<ref name=panSearch/>
+विशेष स्तिथियों में जहां डेटा ज्यामितीय बिंदुओं का सघन 3डी मानचित्र होता है, तब सेंसिंग विधि की प्रक्षेपण ज्यामिति का उपयोग खोज समस्या को नाटकीय रूप से सरल बनाने के लिए किया जा सकता है। इस दृष्टिकोण के लिए आवश्यक है कि 3डी डेटा को दो-आयामी ग्रिड के प्रक्षेपण द्वारा व्यवस्थित किया जाए और यह माना जाए कि डेटा ऑब्जेक्ट सीमाओं के अपवाद के साथ निकटतम ग्रिड कोशिकाओं में स्थानिक रूप से सुचारू है। सर्वेक्षण रोबोटिक्स और स्टीरियो विज़न जैसे अनुप्रयोगों में 3डी सेंसर डेटा से निपटने के समय ये धारणाएँ मान्य हैं, किन्तु सामान्यतः असंगठित डेटा के लिए ये मान्य नहीं हो सकती हैं। और वास्तव में इस विधि को वास्तविक विश्व स्टीरियो विज़न डेटा पर प्रयुक्त करने पर k-निकटतम नेबर समस्या के लिए औसत खोज समय ''O''(''1'') या ''O''(''K'') होता है।<ref name=panSearch/>
-====वेक्टर सन्निकटन फ़ाइलें====
-उच्च-आयामी स्थानों में, वृक्ष अनुक्रमण संरचनाएं बेकार हो जाती हैं क्योंकि नोड्स के बढ़ते प्रतिशत की वैसे भी जांच करने की आवश्यकता होती है। रैखिक खोज को तेज़ करने के लिए, रैम में संग्रहीत फ़ीचर वैक्टर के संपीड़ित संस्करण का उपयोग पहली बार में डेटासेट को प्रीफ़िल्टर करने के लिए किया जाता है। दूरी की गणना के लिए डिस्क से असम्पीडित डेटा का उपयोग करके दूसरे चरण में अंतिम उम्मीदवारों का निर्धारण किया जाता है।<ref>{{cite journal|title=समानता खोज के लिए एक अनुमान-आधारित डेटा संरचना|last1=Weber|first1=Roger|last2=Blott|first2=Stephen|s2cid=14613657|url=https://pdfs.semanticscholar.org/83e4/e3281411ffef40654a4b5d29dae48130aefb.pdf|archive-url=https://web.archive.org/web/20170304043243/https://pdfs.semanticscholar.org/83e4/e3281411ffef40654a4b5d29dae48130aefb.pdf|url-status=dead|archive-date=2017-03-04}}</ref>
+====सदिश सन्निकटन फ़ाइलें====
+उच्च-आयामी स्थानों में, ट्री अनुक्रमण संरचनाएं व्यर्थ हो जाती हैं क्योंकि नोड्स के बढ़ते प्रतिशत की वैसे भी जांच करने की आवश्यकता होती है। रैखिक खोज को तेज़ करने के लिए रैम में संग्रहीत विशेषता सदिश के संपीड़ित संस्करण का उपयोग पहली बार में डेटासमुच्चय को प्रीफ़िल्टर करने के लिए किया जाता है। दूरी की गणना के लिए डिस्क से असम्पीडित डेटा का उपयोग करके दूसरे चरण में अंतिम उम्मीदवारों का निर्धारण किया जाता है।<ref>{{cite journal|title=समानता खोज के लिए एक अनुमान-आधारित डेटा संरचना|last1=Weber|first1=Roger|last2=Blott|first2=Stephen|s2cid=14613657|url=https://pdfs.semanticscholar.org/83e4/e3281411ffef40654a4b5d29dae48130aefb.pdf|archive-url=https://web.archive.org/web/20170304043243/https://pdfs.semanticscholar.org/83e4/e3281411ffef40654a4b5d29dae48130aefb.pdf|url-status=dead|archive-date=2017-03-04}}</ref>
 ====संपीड़न/क्लस्टरिंग आधारित खोज====
-वीए-फ़ाइल दृष्टिकोण संपीड़न आधारित खोज का विशेष मामला है, जहां प्रत्येक फीचर घटक समान रूप से और स्वतंत्र रूप से संपीड़ित होता है। बहुआयामी स्थानों में इष्टतम संपीड़न तकनीक [[ वेक्टर परिमाणीकरण |वेक्टर परिमाणीकरण]] (वीक्यू) है, जिसे क्लस्टरिंग के माध्यम से कार्यान्वित किया जाता है। डेटाबेस को क्लस्टर किया गया है और सबसे आशाजनक क्लस्टर पुनर्प्राप्त किए गए हैं। वीए-फ़ाइल, ट्री-आधारित इंडेक्स और अनुक्रमिक स्कैन पर भारी लाभ देखा गया है।<ref>{{cite journal|title=छवि डेटाबेस में समानता खोज के लिए अनुकूली क्लस्टर-दूरी बाउंडिंग|last1=Ramaswamy|first1=Sharadh|last2=Rose|first2=Kenneth|journal=ICIP|date=2007}}</ref><ref>{{cite journal|title=उच्च-आयामी अनुक्रमण के लिए अनुकूली क्लस्टर-दूरी बाउंडिंग|last1=Ramaswamy|first1=Sharadh|last2=Rose|first2=Kenneth|journal=TKDE|date=2010}}</ref> क्लस्टरिंग और एलएसएच के बीच समानताएं भी नोट करें।
+वीए-फ़ाइल दृष्टिकोण संपीड़न आधारित खोज का विशेष स्थितिया है, जहां प्रत्येक फलन घटक समान रूप से और स्वतंत्र रूप से संपीड़ित होता है। बहुआयामी स्थानों में इष्टतम संपीड़न विधि [[ वेक्टर परिमाणीकरण |सदिश परिमाणीकरण]] (वीक्यू) है, जिसे क्लस्टरिंग के माध्यम से कार्यान्वित किया जाता है। और डेटाबेस को क्लस्टर किया गया है और सबसे आशा जनक क्लस्टर पुनर्प्राप्त किए गए हैं। इस प्रकार वीए-फ़ाइल, ट्री-आधारित इंडेक्स और अनुक्रमिक स्कैन पर भारी लाभ देखा गया है।<ref>{{cite journal|title=छवि डेटाबेस में समानता खोज के लिए अनुकूली क्लस्टर-दूरी बाउंडिंग|last1=Ramaswamy|first1=Sharadh|last2=Rose|first2=Kenneth|journal=ICIP|date=2007}}</ref><ref>{{cite journal|title=उच्च-आयामी अनुक्रमण के लिए अनुकूली क्लस्टर-दूरी बाउंडिंग|last1=Ramaswamy|first1=Sharadh|last2=Rose|first2=Kenneth|journal=TKDE|date=2010}}</ref> क्लस्टरिंग और एलएसएच के मध्य समानताएं भी ध्यान करना हैं।
-==वेरिएंट==
+==प्रकार ==
-एनएनएस समस्या के कई प्रकार हैं और दो सबसे प्रसिद्ध हैं के-निकटतम पड़ोसी एल्गोरिदम|के-निकटतम पड़ोसी खोज और ε-अनुमानित निकटतम पड़ोसी खोज।
+एनएनएस समस्या के कई प्रकार हैं और दो सबसे प्रसिद्ध हैं के-निकटतम नेबर खोज और ε-अनुमानित निकटतम नेबर खोज हैं।
-===<span id= K-निकटतम पड़ोसी > k-निकटतम पड़ोसी </span>===
+===<span id= K-निकटतम पड़ोसी > k-निकटतम नेबर </span>===
-K-निकटतम पड़ोसी एल्गोरिथ्म|k-निकटतम पड़ोसी खोज क्वेरी के शीर्ष k निकटतम पड़ोसियों की पहचान करती है। इस तकनीक का उपयोग आमतौर पर अपने पड़ोसियों की सहमति के आधार पर किसी बिंदु का अनुमान लगाने या वर्गीकृत करने के लिए पूर्वानुमानित विश्लेषण में किया जाता है। k-निकटतम पड़ोसी ग्राफ़ वे ग्राफ़ होते हैं जिनमें प्रत्येक बिंदु अपने k निकटतम पड़ोसियों से जुड़ा होता है।
+K-निकटतम नेबर एल्गोरिथ्म k-निकटतम नेबर सर्च क्वेरी के शीर्ष k निकटतम नेबर की पहचान करती है। इस विधि का उपयोग सामान्यतः अपने निकटतम की सहमति के आधार पर किसी बिंदु का अनुमान लगाने या वर्गीकृत करने के लिए पूर्वानुमानित विश्लेषण में किया जाता है। k-निकटतम नेबर ग्राफ़ वे ग्राफ़ होते हैं जिनमें प्रत्येक बिंदु अपने k निकटतम नेबर से जुड़ा होता है।
-===अनुमानित निकटतम पड़ोसी===
+===अनुमानित निकटतम नेबर===
-कुछ अनुप्रयोगों में निकटतम पड़ोसी का अच्छा अनुमान प्राप्त करना स्वीकार्य हो सकता है। उन मामलों में, हम एल्गोरिदम का उपयोग कर सकते हैं जो बेहतर गति या मेमोरी बचत के बदले में हर मामले में वास्तविक निकटतम पड़ोसी को वापस करने की गारंटी नहीं देता है। अक्सर ऐसा एल्गोरिदम अधिकांश मामलों में निकटतम पड़ोसी ढूंढ लेगा, लेकिन यह पूछताछ किए जा रहे डेटासेट पर दृढ़ता से निर्भर करता है।
+कुछ अनुप्रयोगों में निकटतम नेबर का श्रेष्ठ अनुमान प्राप्त करना स्वीकार्य हो सकता है। उन स्थितियों में, हम एल्गोरिदम का उपयोग कर सकते हैं जो उत्तम गति या मेमोरी बचत के बदले में प्रत्येक स्तिथियों में वास्तविक निकटतम नेबर को वापस करने की आश्वासन नहीं देता है। अधिकांशतः ऐसा एल्गोरिदम अधिकांश स्थितियों में निकटतम नेबर खोज लेगा, किन्तु यह पूछताछ किए जा रहे डेटासमुच्चय पर दृढ़ता से निर्भर करता है।
-अनुमानित निकटतम पड़ोसी खोज का समर्थन करने वाले एल्गोरिदम में निकटतम पड़ोसी खोज के लिए स्थानीयता-संवेदनशील हैशिंग#एलएसएच एल्गोरिदम शामिल है|स्थानीयता-संवेदनशील हैशिंग, सर्वोत्तम बिन प्रथम और संतुलित बॉक्स-अपघटन वृक्ष आधारित खोज।<ref>{{cite journal|first1=S.|last1=Arya|author2-link=David Mount|first2=D. M.|last2=Mount|author3-link=Nathan Netanyahu|first3=N. S.|last3=Netanyahu|first4=R.|last4=Silverman|first5=A.|last5=Wu|title=अनुमानित निकटतम पड़ोसी खोज के लिए एक इष्टतम एल्गोरिदम|journal=Journal of the ACM|volume=45|number=6|pages=891–923|date=1998|url=http://www.cse.ust.hk/faculty/arya/pub/JACM.pdf|doi=10.1145/293347.293348|citeseerx=10.1.1.15.3125|s2cid=8193729|access-date=2009-05-29|archive-url=https://web.archive.org/web/20160303232202/http://www.cse.ust.hk/faculty/arya/pub/JACM.pdf|archive-date=2016-03-03|url-status=dead}}</ref>
+अनुमानित निकटतम नेबर सर्च का समर्थन करने वाले एल्गोरिदम में निकटतम नेबर सर्च के लिए स्थानीयता-संवेदनशील हैशिंगयाएलएसएच एल्गोरिदम सम्मिलित है|स्थानीयता-संवेदनशील हैशिंग, सर्वोत्तम बिन प्रथम और संतुलित बॉक्स-अपघटन ट्री आधारित खोज हैं|<ref>{{cite journal|first1=S.|last1=Arya|author2-link=David Mount|first2=D. M.|last2=Mount|author3-link=Nathan Netanyahu|first3=N. S.|last3=Netanyahu|first4=R.|last4=Silverman|first5=A.|last5=Wu|title=अनुमानित निकटतम पड़ोसी खोज के लिए एक इष्टतम एल्गोरिदम|journal=Journal of the ACM|volume=45|number=6|pages=891–923|date=1998|url=http://www.cse.ust.hk/faculty/arya/pub/JACM.pdf|doi=10.1145/293347.293348|citeseerx=10.1.1.15.3125|s2cid=8193729|access-date=2009-05-29|archive-url=https://web.archive.org/web/20160303232202/http://www.cse.ust.hk/faculty/arya/pub/JACM.pdf|archive-date=2016-03-03|url-status=dead}}</ref>
+===[[निकटतम पड़ोसी दूरी अनुपात|निकटतम नेबर दूरी अनुपात]]===
+निकटतम नेबर दूरी अनुपात मूल बिंदु से चुनौती देने वाले निकट तक की सीधी दूरी पर सीमा प्रयुक्त नहीं करता है, किंतु पिछले निकटतम से दूरी के आधार पर इसके अनुपात पर प्रयुक्त होता है। इसकी उपयोग सामग्री-आधारित छवि पुनर्प्राप्ति में स्थानीय सुविधाओं के मध्य समानता का उपयोग करके उदाहरण के माध्यम से चित्रों को पुनः प्राप्त करने के लिए किया जाता है। इस प्रकार सामान्यतः यह अनेक [[पैटर्न मिलान|क्रम मिलान]] समस्याओं में सम्मिलित होता है।
-===[[निकटतम पड़ोसी दूरी अनुपात]]===
+===[[पड़ोसियों के पास निश्चित-त्रिज्या|निकटतम के पास निश्चित-त्रिज्या]]===
-निकटतम पड़ोसी दूरी अनुपात मूल बिंदु से चुनौती देने वाले पड़ोसी तक की सीधी दूरी पर सीमा लागू नहीं करता है, बल्कि पिछले पड़ोसी से दूरी के आधार पर इसके अनुपात पर लागू होता है। इसका उपयोग सामग्री-आधारित छवि पुनर्प्राप्ति में स्थानीय सुविधाओं के बीच समानता का उपयोग करके उदाहरण के माध्यम से चित्रों को पुनः प्राप्त करने के लिए किया जाता है। आम तौर पर यह कई [[पैटर्न मिलान]] समस्याओं में शामिल होता है।
+निकटतम के पास निश्चित-त्रिज्या वह समस्या है जहां कोई निर्दिष्ट बिंदु से निश्चित दूरी के अंदर यूक्लिडियन सम्मिस्ट में दिए गए सभी बिंदुओं को कुशलतापूर्वक खोज नही चाहता है। और इसमें दूरी निश्चित मानी जाती है, किन्तु प्रश्न बिंदु इच्छानुसार होते है।
-===[[पड़ोसियों के पास निश्चित-त्रिज्या]]===
+===सभी निकटतम नेबर===
-पड़ोसियों के पास निश्चित-त्रिज्या वह समस्या है जहां कोई निर्दिष्ट बिंदु से निश्चित दूरी के भीतर यूक्लिडियन अंतरिक्ष में दिए गए सभी बिंदुओं को कुशलतापूर्वक ढूंढना चाहता है। दूरी निश्चित मानी जाती है, लेकिन प्रश्न बिंदु मनमाना है।
+कुछ अनुप्रयोगों (जैसे [[एन्ट्रापी अनुमान]]) के लिए, हमारे पास एन डेटा-पॉइंट हो सकते हैं और हम जानना चाहते हैं कि उन एन पॉइंट्स में से प्रत्येक के लिए निकटतम नेबर कौन सा होता है। यह, निश्चित रूप से, प्रत्येक बिंदु के लिए अनेक बार निकटतम-नेबर खोज चलाकर प्राप्त किया जा सकता है, किन्तु उत्तम रणनीति एल्गोरिदम होती हैं जो अधिक कुशल खोज उत्पन्न करने के लिए इन एन प्रश्नों के मध्य सूचना अतिरेक का लाभ उठाती है। सरल उदाहरण के रूप में: जब हम बिंदु X से बिंदु Y तक की दूरी पाते हैं, तब वह हमें बिंदु Y से बिंदु से प्राप्त होती हैं
-===सभी निकटतम पड़ोसी===
+एक निश्चित आयाम को देखते हुए, अर्ध-निश्चित सकारात्मक मानदंड (जिससे प्रत्येक L<sup>p</sup> मानदंड सम्मिलित है)| और इस स्थान में n बिंदु, दिए गए हैं प्रत्येक बिंदु का निकटतम नेबर ''O''(''n'' log ''n'') समय में पाया जा सकता है और प्रत्येक के ''m'' निकटतम नेबर बिंदु ''O''(''mn'' log ''n'') समय में पाया जा सकता है। <ref>{{citation
-कुछ अनुप्रयोगों (जैसे [[एन्ट्रापी अनुमान]]) के लिए, हमारे पास एन डेटा-पॉइंट हो सकते हैं और हम जानना चाहते हैं कि उन एन पॉइंट्स में से प्रत्येक के लिए निकटतम पड़ोसी कौन सा है। यह, निश्चित रूप से, प्रत्येक बिंदु के लिए बार निकटतम-पड़ोसी खोज चलाकर हासिल किया जा सकता है, लेकिन बेहतर रणनीति एल्गोरिदम होगी जो अधिक कुशल खोज उत्पन्न करने के लिए इन एन प्रश्नों के बीच सूचना अतिरेक का फायदा उठाती है। सरल उदाहरण के रूप में: जब हम बिंदु X से बिंदु Y तक की दूरी पाते हैं, तो वह हमें बिंदु Y से बिंदु
-एक निश्चित आयाम को देखते हुए, अर्ध-निश्चित सकारात्मक मानदंड (जिससे प्रत्येक एलपी स्पेस|एल शामिल है<sup>p</sup> मानदंड), और इस स्थान में n बिंदु, प्रत्येक बिंदु का निकटतम पड़ोसी O(n log n) समय में पाया जा सकता है और प्रत्येक बिंदु का m निकटतम पड़ोसी O(mn log n) समय में पाया जा सकता है। समय।<ref>{{citation
   | last = Clarkson | first = Kenneth L. | author-link = Kenneth L. Clarkson
   | contribution = Fast algorithms for the all nearest neighbors problem
@@ Line 146: / Line 137: @@
 ==यह भी देखें==
 {{div col|colwidth=20em}}
-* [[गेंद का पेड़]]
+* [[बॉल ट्री ]]
 * अंकों की निकटतम जोड़ी की समस्या
 * क्लस्टर विश्लेषण
@@ Line 153: / Line 144: @@
 * [[अंकीय संकेत प्रक्रिया]]
 * [[आयाम में कमी]]
-* पड़ोसियों के पास निश्चित-त्रिज्या
+* नेबर के पास निश्चित-त्रिज्या
 * [[फूरियर विश्लेषण]]
 * [[उदाहरण-आधारित शिक्षा]]
-* k-निकटतम पड़ोसी एल्गोरिथम|k-निकटतम पड़ोसी एल्गोरिथम
+* k-निकटतम नेबर एल्गोरिथम|
 * [[रैखिक न्यूनतम वर्ग (गणित)]]
 * स्थानीयता संवेदनशील हैशिंग
@@ Line 162: / Line 153: @@
 * [[मिनहैश]]
 * [[बहुआयामी विश्लेषण]]
-* [[निकटतम-पड़ोसी प्रक्षेप]]
+* [[निकटतम-नेबर प्रक्षेप]]
-*पड़ोसी का जुड़ना
+* नेबर का जुड़ना
 * [[प्रमुख कंपोनेंट विश्लेषण]]
 * [[रेंज खोज]]
@@ Line 201: / Line 192: @@
 * [https://archive.today/20130222061350/http://sswiki.tierra-aoi.net/ Similarity Search Wiki] – a collection of links, people, ideas, keywords, papers, slides, code and data sets on nearest neighbours
-{{DEFAULTSORT:Nearest Neighbor Search}}[[Category: सन्निकटन एल्गोरिदम]] [[Category: वर्गीकरण एल्गोरिदम]] [[Category: डेटा खनन]] [[Category: असतत ज्यामिति]] [[Category: ज्यामितीय एल्गोरिदम]] [[Category: गणितीय अनुकूलन]] [[Category: एल्गोरिदम खोजें]]
+{{DEFAULTSORT:Nearest Neighbor Search}}
-[[Category: Machine Translated Page]]
+[[Category:CS1]]
-[[Category:Created On 06/07/2023]]
+[[Category:CS1 errors]]
+[[Category:Commons category link is locally defined|Nearest Neighbor Search]]
+[[Category:Created On 06/07/2023|Nearest Neighbor Search]]
+[[Category:Lua-based templates|Nearest Neighbor Search]]
+[[Category:Machine Translated Page|Nearest Neighbor Search]]
+[[Category:Multi-column templates|Nearest Neighbor Search]]
+[[Category:Pages using div col with small parameter|Nearest Neighbor Search]]
+[[Category:Pages with script errors|Nearest Neighbor Search]]
+[[Category:Templates Vigyan Ready|Nearest Neighbor Search]]
+[[Category:Templates that add a tracking category|Nearest Neighbor Search]]
+[[Category:Templates that generate short descriptions|Nearest Neighbor Search]]
+[[Category:Templates using TemplateData|Nearest Neighbor Search]]
+[[Category:Templates using under-protected Lua modules|Nearest Neighbor Search]]
+[[Category:Wikipedia fully protected templates|Div col]]
+[[Category:असतत ज्यामिति|Nearest Neighbor Search]]
+[[Category:एल्गोरिदम खोजें|Nearest Neighbor Search]]
+[[Category:गणितीय अनुकूलन|Nearest Neighbor Search]]
+[[Category:ज्यामितीय एल्गोरिदम|Nearest Neighbor Search]]
+[[Category:डेटा खनन|Nearest Neighbor Search]]
+[[Category:वर्गीकरण एल्गोरिदम|Nearest Neighbor Search]]
+[[Category:सन्निकटन एल्गोरिदम|Nearest Neighbor Search]]

Anonymous

Search

निकटतम नेबर सर्च (एनएनएस): Difference between revisions

Namespaces

More

Page actions

Latest revision as of 10:07, 18 July 2023

Contents

अनुप्रयोग