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

Revision as of 11:19, 13 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(लॉग N ) होता है| ^[5] उत्तम ढंग से वितरित बिंदुओं के स्तिथियों में, सबसे खराब स्थिति जटिलता O(kN^(1-1/k))है| ^[6] वैकल्पिक रूप से R-ट्री डेटा संरचना को गतिशील संदर्भ में निकटतम नेबर सर्च का समर्थन करने के लिए डिज़ाइन किया गया था, क्योंकि इसमें आर* ट्री जैसे सम्मिलन और विलोपन के लिए कुशल एल्गोरिदम हैं।^[7] R-ट्री न अतिरिक्त यूक्लिडियन दूरी के लिए निकटतम नेबर प्रदान कर सकते हैं, किंतु अन्य दूरियों के साथ भी इसका उपयोग किया जा सकता है।

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

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

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

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

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

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

निकटता ग्राफ़ विधियाँ (जैसे HNSW^[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] और मेट्रिज़्ड स्मॉल वर्ल्ड ^[15] और एचएनएसडब्ल्यू^[9]में दूरी फलन वाले रिक्त स्थान के सामान्य स्तिथियों के लिए एल्गोरिदम। इन कार्यों से पहले टूसेंट का अग्रणी पेपर प्रकाशित हुआ था, जिसमें उन्होंने सापेक्ष निकटतम ग्राफ की अवधारणा प्रस्तुत की थी।^[16]

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

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

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

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

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

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

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

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

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

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

प्रकार

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

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

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

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

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

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

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

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

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

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

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

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

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

यह भी देखें

बॉल ट्री
अंकों की निकटतम जोड़ी की समस्या
क्लस्टर विश्लेषण
सामग्री-आधारित छवि पुनर्प्राप्ति
परिमाणिकता का अभिशाप
अंकीय संकेत प्रक्रिया
आयाम में कमी
नेबर के पास निश्चित-त्रिज्या
फूरियर विश्लेषण
उदाहरण-आधारित शिक्षा
k-निकटतम नेबर एल्गोरिथम|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)
↑ Malkov, Yury; Ponomarenko, Alexander; Krylov, Vladimir; Logvinov, Andrey (2014). "नौगम्य छोटे विश्व ग्राफ़ पर आधारित अनुमानित निकटतम पड़ोसी एल्गोरिदम". Information Systems. 45: 61–68. doi:10.1016/j.is.2013.10.006. S2CID 9896397.
↑ 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)

[msw2014-15] Malkov, Yury; Ponomarenko, Alexander; Krylov, Vladimir; Logvinov, Andrey (2014). "नौगम्य छोटे विश्व ग्राफ़ पर आधारित अनुमानित निकटतम पड़ोसी एल्गोरिदम". Information Systems. 45: 61–68. doi:10.1016/j.is.2013.10.006. S2CID 9896397.

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

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

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

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

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

[21] 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.

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

[23]

@@ Line 1: / Line 1: @@
 {{Short description|Optimization problem in computer science}}
-निकटतम '''निकटतम''' खोज (एनएनएस), निकटता खोज के रूप के रूप में, किसी दिए गए समुच्चय में उस बिंदु को खोजने की [[अनुकूलन समस्या]] है जो किसी दिए गए बिंदु के सबसे करीब (या सबसे समान) है। निकटता को सामान्यतः असमानता फलन के संदर्भ में व्यक्त किया जाता है: जितनी कम समानता वस्तुओं को मापती है, फलन मान उतना ही बड़ा होता है।
+'''निकटतम नेबर सर्च (एनएनएस),''' निकटता खोज के रूप , किसी दिए गए समुच्चय में उस बिंदु को खोजने की [[अनुकूलन समस्या]] है जो किसी दिए गए बिंदु के सबसे समीप (या सबसे समान) है। निकटता को सामान्यतः असमानता फलन के संदर्भ में व्यक्त किया जाता है: जितनी कम समानता वस्तुओं को मापती है, फलन मान उतना ही बड़ा होता है।
-औपचारिक रूप से, निकटतम-निकटतम (एनएन) खोज समस्या को  निम्नलिखित  इस प्रकार परिभाषित किया गया है:  किसी स्थान ''M''   में बिंदुओं का समुच्चय ''S''  और क्वेरी बिंदु ''q'' ∈ ''M'' दिया गया है, ''S''  में '''से''' ''q'' में निकटतम बिंदु ''q'' खोजें। और वॉल्यूम में [[डोनाल्ड नुथ]]। ''[[कंप्यूटर प्रोग्रामिंग की कला]]'' (1973) के 3 में इसे निकटतम '''डाकघर'''  को निवास आवंटित करने के आवेदन का जिक्र करते हुए इसे  '''डाकघर''' की समस्या कहा गया है। इस समस्या का प्रत्यक्ष सामान्यीकरण ''k''-NN खोज है, जहां हमें ''k'' निकटतम बिंदु खोजने की आवश्यकता होती है।
+औपचारिक रूप से, निकटतम-नेबर (एनएन) खोज समस्या को निम्नलिखित इस प्रकार परिभाषित किया गया है: किसी स्थान ''M'' में बिंदुओं का समुच्चय ''S'' और क्वेरी बिंदु ''q'' ∈ ''M'' दिया गया है, ''S'' में ''q'' में निकटतम बिंदु ''q'' खोजें। और वॉल्यूम में [[डोनाल्ड नुथ]]। ''[[कंप्यूटर प्रोग्रामिंग की कला]]'' (1973) के 3 में इसे निकटतम डाकघर को निवास आवंटित करने के आवेदन का जिक्र करते हुए इसे डाकघर की समस्या कहा गया है। इस समस्या का प्रत्यक्ष सामान्यीकरण ''k''-NN खोज है, जहां हमें ''k'' निकटतम बिंदु खोजने की आवश्यकता होती है।
-सामान्यतः  ''M''  [[मीट्रिक स्थान]] है और असमानता को [[दूरी मीट्रिक]] के रूप में व्यक्त किया जाता है, जो सममित है और त्रिकोण असमानता को संतुष्ट करता है। इससे भी अधिक सामान्य,  ''M'' को ''d''-आयामी [[सदिश स्थल]] के रूप में लिया जाता है जहां असमानता को [[यूक्लिडियन दूरी]], [[टैक्सीकैब ज्यामिति]] या अन्य [[सांख्यिकीय दूरी]] का उपयोग करके मापा जाता है। चूँकि, असमानता फलन इच्छानुसार हो सकता है। उदाप्रत्येकण असममित [[ब्रेगमैन विचलन]] है, जिसके लिए त्रिभुज असमानता प्रयुक्त नहीं होती है।<ref name="Cayton2008">{{Cite book
+सामान्यतः ''M'' [[मीट्रिक स्थान]] है और असमानता को [[दूरी मीट्रिक]] के रूप में व्यक्त किया जाता है, जो सममित है और त्रिकोण असमानता को संतुष्ट करता है। इससे भी अधिक सामान्य, ''M'' को ''d''-आयामी [[सदिश स्थल]] के रूप में लिया जाता है जहां असमानता को [[यूक्लिडियन दूरी]], [[टैक्सीकैब ज्यामिति]] या अन्य [[सांख्यिकीय दूरी]] का उपयोग करके मापा जाता है। चूँकि, असमानता फलन इच्छानुसार हो सकता है। उदाप्रत्येकण असममित [[ब्रेगमैन विचलन]] है, जिसके लिए त्रिभुज असमानता प्रयुक्त नहीं होती है।<ref name="Cayton2008">{{Cite book
   | last1 = Cayton | first1 = Lawerence
   | year = 2008
@@ Line 21: / Line 21: @@
 ==अनुप्रयोग==
-निकटतम निकटतम खोज समस्या अनुप्रयोग के अनेक क्षेत्रों में उत्पन्न होती है, जिनमें सम्मिलित हैं:
+निकटतम नेबर सर्च समस्या अनुप्रयोग के अनेक क्षेत्रों में उत्पन्न होती है, जिनमें सम्मिलित हैं:
-* पैटर्न पहचान - विशेष रूप से ऑप्टिकल कैरेक्टर पहचान के लिए
+* क्रम पहचान - विशेष रूप से ऑप्टिकल कैरेक्टर पहचान के लिए
-* [[सांख्यिकीय वर्गीकरण]] - के-निकटतम निकटतम एल्गोरिदम देखें
+* [[सांख्यिकीय वर्गीकरण]] - के-निकटतम नेबर एल्गोरिदम देखें
 * [[कंप्यूटर दृष्टि]] - पॉइंट क्लाउड पंजीकरण के लिए<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>
 * [[कम्प्यूटेशनल ज्यामिति]] - बिंदुओं की निकटतम जोड़ी समस्या देखें
@@ Line 35: / Line 35: @@
 * [[डीएनए श्रृंखला बनाना]]
 * वर्तनी जाँच - सही वर्तनी का सुझाव देना
-* [[साहित्यिक चोरी का पता लगाना|'''साहित्यिक चोरी का पता लगाना''']]
+* [[साहित्यिक चोरी का पता लगाना|प्लागिअरिस्म डिटेक्शन]]
 * प्रोफेशनल एथलीटों के करियर पथ की पूर्वानुमान के लिए [[समानता स्कोर]]।
 * [[क्लस्टर विश्लेषण]] - अवलोकनों के समुच्चय को उपसमूहों (जिन्हें क्लस्टर कहा जाता है) में असाइन करना जिससे ही क्लस्टर में अवलोकन कुछ अर्थों में समान हों, सामान्यतः यह यूक्लिडियन दूरी पर आधारित होते हैं
 *[[रासायनिक समानता]]
 * मोशन प्लानिंग या सैंपलिंग-आधारित एल्गोरिदम|सैंपलिंग-आधारित मोशन प्लानिंग
-*'''नमूना-आधारित गति योजना'''
+*नमूना-आधारित गति योजना
-==तरीके==
+==विधियाँ==
-एनएनएस समस्या के विभिन्न समाधान प्रस्तावित किए गए हैं। एल्गोरिदम की गुणवत्ता और उपयोगिता प्रश्नों की समय जटिलता के साथ-साथ किसी भी खोज डेटा संरचना की स्थान जटिलता द्वारा निर्धारित की जाती है जिसे बनाए रखा जाना चाहिए। अनौपचारिक अवलोकन जिसे सामान्यतः '''आयामीता''' के अभिशाप के रूप में जाना जाता है, यह बताता है कि बहुपद प्रीप्रोसेसिंग और पॉलीलॉगरिदमिक खोज समय का उपयोग करके उच्च-आयामी यूक्लिडियन '''सम्मिस्ट''' में एनएनएस के लिए कोई सामान्य-उद्देश्य स्पष्ट समाधान नहीं है।
+एनएनएस समस्या के विभिन्न समाधान प्रस्तावित किए गए हैं। इस प्रकार एल्गोरिदम की गुणवत्ता और उपयोगिता प्रश्नों की समय जटिलता के साथ-साथ किसी भी खोज डेटा संरचना की स्थान जटिलता द्वारा निर्धारित की जाती है जिसे बनाए रखा जाना चाहिए। अनौपचारिक अवलोकन जिसे सामान्यतः आयामी स्थिति के अभिशाप के रूप में जाना जाता है, यह बताता है कि बहुपद प्रीप्रोसेसिंग और पॉलीलॉगरिदमिक खोज समय का उपयोग करके उच्च-आयामी यूक्लिडियन सम्मिस्ट में एनएनएस के लिए कोई सामान्य-उद्देश्य स्पष्ट समाधान नहीं है।
-=== स्पष्ट तरीके ===
+=== स्पष्ट विधियाँ ===
 ====रैखिक खोज====
 एनएनएस समस्या का सबसे सरल समाधान अब तक के सर्वश्रेष्ठ का ट्रैक रखते हुए, डेटाबेस में क्वेरी बिंदु से प्रत्येक दूसरे बिंदु तक की दूरी की गणना करना है। यह एल्गोरिदम, जिसे कभी-कभी अनुभवहीन दृष्टिकोण के रूप में जाना जाता है, इसका चलने का समय ''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>
-दूरी की तुलना के लिए पूर्ण दूरी की आवश्यकता नहीं है,  इसमें केवल सापेक्ष दूरी की आवश्यकता  होती है। और ज्यामितीय समन्वय प्रणालियों में दो निर्देशांकों के मध्य की दूरी की गणना से वर्गमूल गणना को हटाकर दूरी की गणना में अधिक तेजी लाई जा सकती है। दूरी की तुलना अभी भी समान परिणाम देती हैं।
+दूरी की तुलना के लिए पूर्ण दूरी की आवश्यकता नहीं है, इसमें अतिरिक्त सापेक्ष दूरी की आवश्यकता होती है। और ज्यामितीय समन्वय प्रणालियों में दो निर्देशांकों के मध्य की दूरी की गणना से वर्गमूल गणना को हटाकर दूरी की गणना में अधिक तेजी लाई जा सकती है।और दूरी की तुलना अभी भी समान परिणाम देती हैं।
 ====[[अंतरिक्ष विभाजन|सम्मिस्ट विभाजन]]====
-के दशक से, शाखा और बाध्य पद्धति को समस्या पर प्रयुक्त किया गया है। यूक्लिडियन सम्मिस्ट के स्तिथियों में, यह दृष्टिकोण [[स्थानिक सूचकांक]] या स्थानिक पहुंच विधियों को सम्मिलित करता है। एनएनएस समस्या को हल करने के लिए अनेक सम्मिस्ट विभाजन'''|सम्मिस्ट-विभाजन''' विधियां विकसित की गई हैं। संभवतः सबसे सरल [[ के-डी पेड़ |k-d पेड़]] है, जो मूल क्षेत्र के आधे बिंदुओं वाले खोज स्थान को दो क्षेत्रों में पुनरावृत्त रूप से विभाजित करता है। और प्रत्येक विभाजन पर क्वेरी बिंदु का मूल्यांकन करके क्वेरी को जड़ से पत्ती तक पेड़ के ट्रैवर्सल के माध्यम से निष्पादित किया जाता है। इस प्रकार क्वेरी में निर्दिष्ट दूरी के आधार पर, निकटतम शाखाओं जिनमें हिट हो सकती हैं, इसलिए इनका भी मूल्यांकन करने की आवश्यकता हो सकती है। और निरंतर आयाम क्वेरी समय के लिए, औसत जटिलता O(लॉग ''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
+के दशक से, शाखा और बाध्य पद्धति को समस्या पर प्रयुक्त किया गया है। यूक्लिडियन सम्मिस्ट के स्तिथियों में, यह दृष्टिकोण [[स्थानिक सूचकांक]] या स्थानिक पहुंच विधियों को सम्मिलित करता है। एनएनएस समस्या को हल करने के लिए अनेक सम्मिस्ट विभाजन| सम्मिस्ट-विभाजन विधियां विकसित की गई हैं। संभवतः सबसे सरल [[ के-डी पेड़ |k-d ट्री]] है, जो मूल क्षेत्र के आधे बिंदुओं वाले खोज स्थान को दो क्षेत्रों में पुनरावृत्त रूप से विभाजित करता है। और प्रत्येक विभाजन पर क्वेरी बिंदु का मूल्यांकन करके क्वेरी को रूट से लीव्स तक ट्री के ट्रैवर्सल के माध्यम से निष्पादित किया जाता है। इस प्रकार क्वेरी में निर्दिष्ट दूरी के आधार पर, निकटतम शाखाओं जिनमें हिट हो सकती हैं, इसलिए इनका भी मूल्यांकन करने की आवश्यकता हो सकती है। और निरंतर आयाम क्वेरी समय के लिए, औसत जटिलता O(लॉग ''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 64: / Line 64: @@
   | pages = 23–29
   | doi = 10.1007/BF00263763
-  | 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-पेड़ न केवल यूक्लिडियन दूरी के लिए निकटतम निकटतम प्रदान कर सकते हैं, किंतु अन्य दूरियों के साथ भी इसका उपयोग किया जा सकता है।
+  | 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> क्वेरी से उसके निकटतम बिंदुओं की दूरी <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>
-====निकटता निकटतम ग्राफ़ में लालची खोज====
+====निकटता निकटतम ग्राफ़ में ग्रीडी खोज====
-निकटता ग्राफ़ विधियाँ (जैसे 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>
+निकटता ग्राफ़ विधियाँ (जैसे 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> के साथ विशिष्ट रूप से जुड़ा हुआ है | समुच्चय में क्वेरी 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>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="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>
@@ Line 84: / Line 84: @@
 ====स्थानीय संवेदनशील हैशिंग====
-[[स्थानीयता संवेदनशील हैशिंग]] (एलएसएच) बिंदुओं पर संचालित कुछ दूरी मीट्रिक के आधार पर सम्मिस्ट में बिंदुओं को '''<nowiki/>'बाल्टी'''' में समूहीकृत करने की विधि है। जिसमे  चुने गए मीट्रिक के अनुसार एक-दूसरे के करीब आने वाले बिंदुओं को उच्च संभावना के साथ ही बकेट में मानचित्र किया जाता है।<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>
-====छोटे आंतरिक आयाम वाले स्थानों में निकटतम निकटतम की खोज====
+====छोटे आंतरिक आयाम वाले स्थानों में निकटतम नेबर की खोज====
-[[ वृक्ष को ढकें | वृक्ष को ढकें]] में सैद्धांतिक सीमा होती है जो डेटा समुच्चय के [[दोहरीकरण स्थिरांक]] पर आधारित होती है। और खोज समय की सीमा ''O''(''c''<sup>12</sup> log ''n'') हैं जहां ''c''  डेटा समुच्चय की [[विस्तारशीलता स्थिरांक]] होता है।
+[[Index.php?title=वृक्ष की ढकें|ट्री की आवरण]] में सैद्धांतिक सीमा होती है जो डेटा समुच्चय के [[दोहरीकरण स्थिरांक]] पर आधारित होती है। और खोज समय की सीमा ''O''(''c''<sup>12</sup> log ''n'') हैं जहां ''c'' डेटा समुच्चय की [[विस्तारशीलता स्थिरांक]] होता है।
 ====प्रक्षेपित रेडियल खोज====
-विशेष स्तिथियों में जहां डेटा ज्यामितीय बिंदुओं का सघन 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> क्लस्टरिंग और एलएसएच के मध्य समानताएं भी नोट करना हैं।
-==वेरिएंट==
+==प्रकार ==
-एनएनएस समस्या के कई प्रकार हैं और दो सबसे प्रसिद्ध हैं के-निकटतम पड़ोसी खोज और ε-अनुमानित निकटतम पड़ोसी खोज।
+एनएनएस समस्या के कई प्रकार हैं और दो सबसे प्रसिद्ध हैं के-निकटतम नेबर खोज और ε-अनुमानित निकटतम नेबर खोज हैं।
-===<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 से बिंदु से प्राप्त होती हैं
+कुछ अनुप्रयोगों (जैसे [[एन्ट्रापी अनुमान]]) के लिए, हमारे पास एन डेटा-पॉइंट हो सकते हैं और हम जानना चाहते हैं कि उन एन पॉइंट्स में से प्रत्येक के लिए निकटतम नेबर कौन सा होता है। यह, निश्चित रूप से, प्रत्येक बिंदु के लिए अनेक बार निकटतम-नेबर खोज चलाकर प्राप्त किया जा सकता है, किन्तु उत्तम रणनीति एल्गोरिदम होती हैं जो अधिक कुशल खोज उत्पन्न करने के लिए इन एन प्रश्नों के मध्य सूचना अतिरेक का लाभ उठाती है। सरल उदाहरण के रूप में: जब हम बिंदु X से बिंदु Y तक की दूरी पाते हैं, तब वह हमें बिंदु Y से बिंदु से प्राप्त होती हैं
-एक निश्चित आयाम को देखते हुए, अर्ध-निश्चित सकारात्मक मानदंड (जिससे प्रत्येक  L<sup>p</sup> मानदंड  सम्मिलित है)| और इस स्थान में n बिंदु, दिए गए हैं प्रत्येक बिंदु का निकटतम निकटतम ''O''(''n'' log ''n'') समय में पाया जा सकता है और प्रत्येक के ''m''  निकटतम निकटतम बिंदु ''O''(''mn'' log ''n'') समय में पाया जा सकता है। <ref>{{citation
+एक निश्चित आयाम को देखते हुए, अर्ध-निश्चित सकारात्मक मानदंड (जिससे प्रत्येक L<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 144: @@
 ==यह भी देखें==
 {{div col|colwidth=20em}}
-* [[गेंद का पेड़]]
+* [[बॉल ट्री ]]
 * अंकों की निकटतम जोड़ी की समस्या
 * क्लस्टर विश्लेषण
@@ Line 153: / Line 151: @@
 * [[अंकीय संकेत प्रक्रिया]]
 * [[आयाम में कमी]]
-* पड़ोसियों के पास निश्चित-त्रिज्या
+* नेबर के पास निश्चित-त्रिज्या
 * [[फूरियर विश्लेषण]]
 * [[उदाहरण-आधारित शिक्षा]]
-* k-निकटतम पड़ोसी एल्गोरिथम|k-निकटतम पड़ोसी एल्गोरिथम
+* k-निकटतम नेबर एल्गोरिथम|k-निकटतम नेबर एल्गोरिथम
 * [[रैखिक न्यूनतम वर्ग (गणित)]]
 * स्थानीयता संवेदनशील हैशिंग
@@ Line 162: / Line 160: @@
 * [[मिनहैश]]
 * [[बहुआयामी विश्लेषण]]
-* [[निकटतम-पड़ोसी प्रक्षेप]]
+* [[निकटतम-नेबर प्रक्षेप]]
-*पड़ोसी का जुड़ना
+* नेबर का जुड़ना
 * [[प्रमुख कंपोनेंट विश्लेषण]]
 * [[रेंज खोज]]

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 11:19, 13 July 2023

Contents

अनुप्रयोग