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

Revision as of 21:34, 12 July 2023

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

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

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

अनुप्रयोग

निकटतम पड़ोसी खोज समस्या अनुप्रयोग के कई क्षेत्रों में उत्पन्न होती है, जिनमें शामिल हैं:

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

तरीके

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

सटीक तरीके

रैखिक खोज

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

अंतरिक्ष विभाजन

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

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

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

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

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

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

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

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

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

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

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

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

वृक्ष को ढकें में सैद्धांतिक सीमा होती है जो डेटासेट के दोहरीकरण स्थिरांक पर आधारित होती है। खोज समय की सीमा O(c) है¹²लॉग एन) जहां सी डेटासेट की विस्तारशीलता स्थिरांक है।

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

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

वेक्टर सन्निकटन फ़ाइलें

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

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

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

वेरिएंट

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

k-निकटतम पड़ोसी

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

अनुमानित निकटतम पड़ोसी

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

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

निकटतम पड़ोसी दूरी अनुपात

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

पड़ोसियों के पास निश्चित-त्रिज्या

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

सभी निकटतम पड़ोसी

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

एक निश्चित आयाम को देखते हुए, अर्ध-निश्चित सकारात्मक मानदंड (जिससे प्रत्येक एलपी स्पेस|एल शामिल है^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}}
-निकटतम पड़ोसी खोज (एनएनएस), निकटता खोज के एक रूप के रूप में, किसी दिए गए सेट में उस बिंदु को खोजने की [[अनुकूलन समस्या]] है जो किसी दिए गए बिंदु के सबसे करीब (या सबसे समान) है। निकटता को आम तौर पर एक असमानता फ़ंक्शन के संदर्भ में व्यक्त किया जाता है: जितनी कम समानता वस्तुओं को मापती है, फ़ंक्शन मान उतना ही बड़ा होता है।
+निकटतम पड़ोसी खोज (एनएनएस), निकटता खोज के रूप के रूप में, किसी दिए गए सेट में उस बिंदु को खोजने की [[अनुकूलन समस्या]] है जो किसी दिए गए बिंदु के सबसे करीब (या सबसे समान) है। निकटता को आम तौर पर असमानता फ़ंक्शन के संदर्भ में व्यक्त किया जाता है: जितनी कम समानता वस्तुओं को मापती है, फ़ंक्शन मान उतना ही बड़ा होता है।
-औपचारिक रूप से, निकटतम-पड़ोसी (एनएन) खोज समस्या को इस प्रकार परिभाषित किया गया है: एक स्थान ''एम'' में बिंदुओं का एक सेट ''एस'' और एक क्वेरी बिंदु ''क्यू'' ∈ ''एम'' दिया गया है, ''S'' से ''q'' में निकटतम बिंदु खोजें। वॉल्यूम में [[डोनाल्ड नुथ]]। ''[[कंप्यूटर प्रोग्रामिंग की कला]]'' (1973) के 3 में इसे डाकघर की समस्या कहा गया है, जिसमें निकटतम डाकघर के लिए निवास आवंटित करने के एक आवेदन का जिक्र है। इस समस्या का प्रत्यक्ष सामान्यीकरण ''k''-NN खोज है, जहां हमें ''k'' निकटतम बिंदु खोजने की आवश्यकता होती है।
+औपचारिक रूप से, निकटतम-पड़ोसी (एनएन) खोज समस्या को इस प्रकार परिभाषित किया गया है: स्थान ''एम'' में बिंदुओं का सेट ''एस'' और क्वेरी बिंदु ''क्यू'' ∈ ''एम'' दिया गया है, ''S'' से ''q'' में निकटतम बिंदु खोजें। वॉल्यूम में [[डोनाल्ड नुथ]]। ''[[कंप्यूटर प्रोग्रामिंग की कला]]'' (1973) के 3 में इसे डाकघर की समस्या कहा गया है, जिसमें निकटतम डाकघर के लिए निवास आवंटित करने के आवेदन का जिक्र है। इस समस्या का प्रत्यक्ष सामान्यीकरण ''k''-NN खोज है, जहां हमें ''k'' निकटतम बिंदु खोजने की आवश्यकता होती है।
-आमतौर पर ''एम'' एक [[मीट्रिक स्थान]] है और असमानता को [[दूरी मीट्रिक]] के रूप में व्यक्त किया जाता है, जो सममित है और त्रिकोण असमानता को संतुष्ट करता है। इससे भी अधिक सामान्य, ''एम'' को ''डी''-आयामी [[सदिश स्थल]] के रूप में लिया जाता है जहां असमानता को [[यूक्लिडियन दूरी]], [[टैक्सीकैब ज्यामिति]] या अन्य [[सांख्यिकीय दूरी]] का उपयोग करके मापा जाता है। हालाँकि, असमानता फ़ंक्शन मनमाना हो सकता है। एक उदाहरण असममित [[ब्रेगमैन विचलन]] है, जिसके लिए त्रिभुज असमानता लागू नहीं होती है।<ref name=Cayton2008>{{Cite book
+आमतौर पर ''एम'' [[मीट्रिक स्थान]] है और असमानता को [[दूरी मीट्रिक]] के रूप में व्यक्त किया जाता है, जो सममित है और त्रिकोण असमानता को संतुष्ट करता है। इससे भी अधिक सामान्य, ''एम'' को ''डी''-आयामी [[सदिश स्थल]] के रूप में लिया जाता है जहां असमानता को [[यूक्लिडियन दूरी]], [[टैक्सीकैब ज्यामिति]] या अन्य [[सांख्यिकीय दूरी]] का उपयोग करके मापा जाता है। हालाँकि, असमानता फ़ंक्शन मनमाना हो सकता है। उदाहरण असममित [[ब्रेगमैन विचलन]] है, जिसके लिए त्रिभुज असमानता लागू नहीं होती है।<ref name=Cayton2008>{{Cite book
   | last1 = Cayton | first1 = Lawerence
   | year = 2008
@@ Line 29: / Line 29: @@
 * [[रोबोटिक]] सेंसिंग<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>
 * [[अनुशंसा प्रणाली]], उदा. सहयोगात्मक फ़िल्टरिंग देखें
-* [[ इंटरनेट विपणन ]] - [[प्रासंगिक विज्ञापन]] और [[व्यवहारिक लक्ष्यीकरण]] देखें
+* [[ इंटरनेट विपणन | इंटरनेट विपणन]] - [[प्रासंगिक विज्ञापन]] और [[व्यवहारिक लक्ष्यीकरण]] देखें
 * [[डीएनए श्रृंखला बनाना]]
 * वर्तनी जाँच - सही वर्तनी का सुझाव देना
 * [[साहित्यिक चोरी का पता लगाना]]
 * पेशेवर एथलीटों के करियर पथ की भविष्यवाणी के लिए [[समानता स्कोर]]।
-* [[क्लस्टर विश्लेषण]] - अवलोकनों के एक सेट को उपसमूहों (जिन्हें क्लस्टर कहा जाता है) में असाइन करना ताकि एक ही क्लस्टर में अवलोकन कुछ अर्थों में समान हों, आमतौर पर यूक्लिडियन दूरी पर आधारित होते हैं
+* [[क्लस्टर विश्लेषण]] - अवलोकनों के सेट को उपसमूहों (जिन्हें क्लस्टर कहा जाता है) में असाइन करना ताकि ही क्लस्टर में अवलोकन कुछ अर्थों में समान हों, आमतौर पर यूक्लिडियन दूरी पर आधारित होते हैं
 *[[रासायनिक समानता]]
 * मोशन प्लानिंग#सैंपलिंग-आधारित एल्गोरिदम|सैंपलिंग-आधारित मोशन प्लानिंग
@@ Line 45: / Line 45: @@
 ====रैखिक खोज====
-एनएनएस समस्या का सबसे सरल समाधान अब तक के सर्वश्रेष्ठ का ट्रैक रखते हुए, डेटाबेस में क्वेरी बिंदु से हर दूसरे बिंदु तक की दूरी की गणना करना है। यह एल्गोरिदम, जिसे कभी-कभी अनुभवहीन दृष्टिकोण के रूप में जाना जाता है, का चलने का समय 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
+के दशक से, शाखा और बाध्य पद्धति को समस्या पर लागू किया गया है। यूक्लिडियन अंतरिक्ष के मामले में, यह दृष्टिकोण [[स्थानिक सूचकांक]] या स्थानिक पहुंच विधियों को शामिल करता है। एनएनएस समस्या को हल करने के लिए कई अंतरिक्ष विभाजन|अंतरिक्ष-विभाजन विधियां विकसित की गई हैं। शायद सबसे सरल [[ के-डी पेड़ |के-डी पेड़]] है, जो खोज स्थान को मूल क्षेत्र के आधे बिंदुओं वाले दो क्षेत्रों में पुनरावृत्त रूप से विभाजित करता है। प्रत्येक विभाजन पर क्वेरी बिंदु का मूल्यांकन करके क्वेरी को जड़ से पत्ती तक पेड़ के ट्रैवर्सल के माध्यम से निष्पादित किया जाता है। क्वेरी में निर्दिष्ट दूरी के आधार पर, पड़ोसी शाखाओं जिनमें हिट हो सकती हैं, का भी मूल्यांकन करने की आवश्यकता हो सकती है। निरंतर आयाम क्वेरी समय के लिए, औसत जटिलता 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
   | last1 = Lee | first1 = D. T. | author1-link = Der-Tsai Lee
   | last2 = Wong | first2 = C. K.
@@ Line 59: / Line 58: @@
   | pages = 23–29
   | doi = 10.1007/BF00263763
-  | s2cid = 36580055 }}</ref>
+  | 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> आर-पेड़ न केवल यूक्लिडियन दूरी के लिए निकटतम पड़ोसी प्रदान कर सकते हैं, बल्कि अन्य दूरियों के साथ भी इसका उपयोग किया जा सकता है।
-वैकल्पिक रूप से [[ आर-वृक्ष ]] डेटा संरचना को गतिशील संदर्भ में निकटतम पड़ोसी खोज का समर्थन करने के लिए डिज़ाइन किया गया था, क्योंकि इसमें [[ आर* पेड़ ]] जैसे सम्मिलन और विलोपन के लिए कुशल एल्गोरिदम हैं।<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> आर-पेड़ न केवल यूक्लिडियन दूरी के लिए निकटतम पड़ोसी प्रदान कर सकते हैं, बल्कि अन्य दूरियों के साथ भी इसका उपयोग किया जा सकता है।
-सामान्य मीट्रिक स्थान के मामले में, शाखा-और-बाउंड दृष्टिकोण को [[मीट्रिक पेड़]] दृष्टिकोण के रूप में जाना जाता है। विशेष उदाहरणों में [[ वीपी-वृक्ष ]] और [[ बीके-वृक्ष ]] विधियां शामिल हैं।
+सामान्य मीट्रिक स्थान के मामले में, शाखा-और-बाउंड दृष्टिकोण को [[मीट्रिक पेड़]] दृष्टिकोण के रूप में जाना जाता है। विशेष उदाहरणों में [[ वीपी-वृक्ष |वीपी-वृक्ष]] और [[ बीके-वृक्ष |बीके-वृक्ष]] विधियां शामिल हैं।
--आयामी स्थान से लिए गए बिंदुओं के एक सेट का उपयोग करके और [[बाइनरी स्पेस विभाजन]] में डालकर, और उसी स्थान से लिया गया एक क्वेरी बिंदु दिया गया, क्वेरी बिंदु के निकटतम बिंदु-क्लाउड बिंदु को खोजने की समस्या का एक संभावित समाधान है एक एल्गोरिदम के निम्नलिखित विवरण में दिया गया है। {{Confusing|date=November 2021}} (सख्ती से कहें तो, ऐसा कोई बिंदु मौजूद नहीं हो सकता है, क्योंकि यह अद्वितीय नहीं हो सकता है। लेकिन व्यवहार में, आमतौर पर हम केवल सभी बिंदु-क्लाउड बिंदुओं के सबसेट में से किसी एक को खोजने की परवाह करते हैं जो किसी दिए गए क्वेरी बिंदु से सबसे कम दूरी पर मौजूद होते हैं .) विचार यह है कि, पेड़ की प्रत्येक शाखा के लिए, अनुमान लगाएं कि बादल में निकटतम बिंदु क्वेरी बिंदु वाले आधे स्थान में रहता है। यह मामला नहीं हो सकता है, लेकिन यह एक अच्छा अनुमान है। अनुमानित अर्ध-स्थान के लिए समस्या को हल करने की सभी परेशानियों से गुजरने के बाद, अब इस परिणाम द्वारा लौटाई गई दूरी की तुलना क्वेरी बिंदु से विभाजन तल तक की सबसे छोटी दूरी से करें। यह बाद वाली दूरी क्वेरी बिंदु और निकटतम संभावित बिंदु के बीच की दूरी है जो खोजे न गए आधे स्थान में मौजूद हो सकती है। यदि यह दूरी पिछले परिणाम में दी गई दूरी से अधिक है, तो स्पष्ट रूप से अन्य आधे स्थान की खोज करने की कोई आवश्यकता नहीं है। यदि ऐसी कोई आवश्यकता है, तो आपको अन्य आधे स्थान के लिए समस्या को हल करने की परेशानी से गुजरना होगा, और फिर उसके परिणाम की तुलना पिछले परिणाम से करनी होगी, और फिर उचित परिणाम लौटाना होगा। इस एल्गोरिदम का प्रदर्शन रैखिक समय की तुलना में लॉगरिदमिक समय के करीब होता है जब क्वेरी बिंदु क्लाउड के नजदीक होता है, क्योंकि क्वेरी बिंदु और निकटतम बिंदु-क्लाउड बिंदु के बीच की दूरी शून्य के करीब होती है, एल्गोरिदम को केवल लुक-अप का उपयोग करने की आवश्यकता होती है सही परिणाम प्राप्त करने के लिए क्वेरी बिंदु को कुंजी के रूप में उपयोग करें।
+-आयामी स्थान से लिए गए बिंदुओं के सेट का उपयोग करके और [[बाइनरी स्पेस विभाजन]] में डालकर, और उसी स्थान से लिया गया क्वेरी बिंदु दिया गया, क्वेरी बिंदु के निकटतम बिंदु-क्लाउड बिंदु को खोजने की समस्या का संभावित समाधान है एल्गोरिदम के निम्नलिखित विवरण में दिया गया है।
+(सख्ती से कहें तो, ऐसा कोई बिंदु मौजूद नहीं हो सकता है, क्योंकि यह अद्वितीय नहीं हो सकता है। लेकिन व्यवहार में, आमतौर पर हम केवल सभी बिंदु-क्लाउड बिंदुओं के सबसेट में से किसी को खोजने की परवाह करते हैं जो किसी दिए गए क्वेरी बिंदु से सबसे कम दूरी पर मौजूद होते हैं .) विचार यह है कि, पेड़ की प्रत्येक शाखा के लिए, अनुमान लगाएं कि बादल में निकटतम बिंदु क्वेरी बिंदु वाले आधे स्थान में रहता है। यह मामला नहीं हो सकता है, लेकिन यह अच्छा अनुमान है। अनुमानित अर्ध-स्थान के लिए समस्या को हल करने की सभी परेशानियों से गुजरने के बाद, अब इस परिणाम द्वारा लौटाई गई दूरी की तुलना क्वेरी बिंदु से विभाजन तल तक की सबसे छोटी दूरी से करें। यह बाद वाली दूरी क्वेरी बिंदु और निकटतम संभावित बिंदु के बीच की दूरी है जो खोजे न गए आधे स्थान में मौजूद हो सकती है। यदि यह दूरी पिछले परिणाम में दी गई दूरी से अधिक है, तो स्पष्ट रूप से अन्य आधे स्थान की खोज करने की कोई आवश्यकता नहीं है। यदि ऐसी कोई आवश्यकता है, तो आपको अन्य आधे स्थान के लिए समस्या को हल करने की परेशानी से गुजरना होगा, और फिर उसके परिणाम की तुलना पिछले परिणाम से करनी होगी, और फिर उचित परिणाम लौटाना होगा। इस एल्गोरिदम का प्रदर्शन रैखिक समय की तुलना में लॉगरिदमिक समय के करीब होता है जब क्वेरी बिंदु क्लाउड के नजदीक होता है, क्योंकि क्वेरी बिंदु और निकटतम बिंदु-क्लाउड बिंदु के बीच की दूरी शून्य के करीब होती है, एल्गोरिदम को केवल लुक-अप का उपयोग करने की आवश्यकता होती है सही परिणाम प्राप्त करने के लिए क्वेरी बिंदु को कुंजी के रूप में उपयोग करें।
 === सन्निकटन विधियाँ ===
-एक अनुमानित निकटतम पड़ोसी खोज एल्गोरिदम को उन बिंदुओं को वापस करने की अनुमति है जिनकी क्वेरी से दूरी अधिकतम है <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> क्वेरी से उसके निकटतम बिंदुओं की दूरी का गुना। इस दृष्टिकोण की अपील यह है कि, कई मामलों में, अनुमानित निकटतम पड़ोसी लगभग उतना ही अच्छा होता है जितना कि सटीक पड़ोसी। विशेष रूप से, यदि दूरी माप उपयोगकर्ता की गुणवत्ता की धारणा को सटीक रूप से पकड़ लेता है, तो दूरी में छोटे अंतर से कोई फर्क नहीं पड़ना चाहिए।<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>. सेट S में क्वेरी q के निकटतम पड़ोसियों की खोज ग्राफ़ में शीर्ष की खोज का रूप लेती है <math>G(V,E)</math>.
-विधियाँ निकटता पड़ोस ग्राफ़ में लालची ट्रैवर्सिंग पर आधारित हैं <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>, और फिर न्यूनतम दूरी मान वाला शीर्ष ढूँढता है। यदि क्वेरी और चयनित शीर्ष के बीच की दूरी का मान क्वेरी और वर्तमान तत्व के बीच की दूरी से छोटा है, तो एल्गोरिदम चयनित शीर्ष पर चला जाता है, और यह नया प्रवेश-बिंदु बन जाता है। एल्गोरिदम तब रुक जाता है जब यह स्थानीय न्यूनतम तक पहुंच जाता है: शीर्ष जिसके पड़ोस में शीर्ष नहीं होता है जो शीर्ष की तुलना में क्वेरी के करीब होता है।
-मूल एल्गोरिदम - लालची खोज - निम्नानुसार काम करती है: खोज एक प्रवेश-बिंदु शीर्ष से शुरू होती है <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>
+निकटता पड़ोस ग्राफ़ के विचार का कई प्रकाशनों में उपयोग किया गया, जिसमें आर्य और माउंट का मौलिक पेपर भी शामिल है,<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>
 ====स्थानीय संवेदनशील हैशिंग====
-[[स्थानीयता संवेदनशील हैशिंग]] (एलएसएच) बिंदुओं पर संचालित कुछ दूरी मीट्रिक के आधार पर अंतरिक्ष में बिंदुओं को 'बाल्टी' में समूहीकृत करने की एक तकनीक है। चुने गए मीट्रिक के तहत एक-दूसरे के करीब आने वाले बिंदुओं को उच्च संभावना के साथ एक ही बकेट में मैप किया जाता है।<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>लॉग एन) जहां सी डेटासेट की [[विस्तारशीलता स्थिरांक]] है।
+[[ वृक्ष को ढकें | वृक्ष को ढकें]] में सैद्धांतिक सीमा होती है जो डेटासेट के [[दोहरीकरण स्थिरांक]] पर आधारित होती है। खोज समय की सीमा O(c) है<sup>12</sup>लॉग एन) जहां सी डेटासेट की [[विस्तारशीलता स्थिरांक]] है।
 ====प्रक्षेपित रेडियल खोज====
-विशेष मामले में जहां डेटा ज्यामितीय बिंदुओं का एक सघन 3डी मानचित्र है, सेंसिंग तकनीक की प्रक्षेपण ज्यामिति का उपयोग खोज समस्या को नाटकीय रूप से सरल बनाने के लिए किया जा सकता है।
+विशेष मामले में जहां डेटा ज्यामितीय बिंदुओं का सघन 3डी मानचित्र है, सेंसिंग तकनीक की प्रक्षेपण ज्यामिति का उपयोग खोज समस्या को नाटकीय रूप से सरल बनाने के लिए किया जा सकता है। इस दृष्टिकोण के लिए आवश्यक है कि 3डी डेटा को दो-आयामी ग्रिड के प्रक्षेपण द्वारा व्यवस्थित किया जाए और यह माना जाए कि डेटा ऑब्जेक्ट सीमाओं के अपवाद के साथ पड़ोसी ग्रिड कोशिकाओं में स्थानिक रूप से सुचारू है। सर्वेक्षण, रोबोटिक्स और स्टीरियो विज़न जैसे अनुप्रयोगों में 3डी सेंसर डेटा से निपटने के दौरान ये धारणाएँ मान्य हैं, लेकिन सामान्य तौर पर असंगठित डेटा के लिए ये मान्य नहीं हो सकती हैं। व्यवहार में इस तकनीक को वास्तविक विश्व स्टीरियो विज़न डेटा पर लागू करने पर k-निकटतम पड़ोसी समस्या के लिए औसत खोज समय O(1) या O(K) होता है।<ref name=panSearch/>
-इस दृष्टिकोण के लिए आवश्यक है कि 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> क्लस्टरिंग और एलएसएच के बीच समानताएं भी नोट करें।
 ==वेरिएंट==
@@ Line 112: / Line 108: @@
 ===अनुमानित निकटतम पड़ोसी===
-कुछ अनुप्रयोगों में निकटतम पड़ोसी का अच्छा अनुमान प्राप्त करना स्वीकार्य हो सकता है। उन मामलों में, हम एक एल्गोरिदम का उपयोग कर सकते हैं जो बेहतर गति या मेमोरी बचत के बदले में हर मामले में वास्तविक निकटतम पड़ोसी को वापस करने की गारंटी नहीं देता है। अक्सर ऐसा एल्गोरिदम अधिकांश मामलों में निकटतम पड़ोसी ढूंढ लेगा, लेकिन यह पूछताछ किए जा रहे डेटासेट पर दृढ़ता से निर्भर करता है।
+कुछ अनुप्रयोगों में निकटतम पड़ोसी का अच्छा अनुमान प्राप्त करना स्वीकार्य हो सकता है। उन मामलों में, हम एल्गोरिदम का उपयोग कर सकते हैं जो बेहतर गति या मेमोरी बचत के बदले में हर मामले में वास्तविक निकटतम पड़ोसी को वापस करने की गारंटी नहीं देता है। अक्सर ऐसा एल्गोरिदम अधिकांश मामलों में निकटतम पड़ोसी ढूंढ लेगा, लेकिन यह पूछताछ किए जा रहे डेटासेट पर दृढ़ता से निर्भर करता है।
 अनुमानित निकटतम पड़ोसी खोज का समर्थन करने वाले एल्गोरिदम में निकटतम पड़ोसी खोज के लिए स्थानीयता-संवेदनशील हैशिंग#एलएसएच एल्गोरिदम शामिल है|स्थानीयता-संवेदनशील हैशिंग, सर्वोत्तम बिन प्रथम और संतुलित बॉक्स-अपघटन वृक्ष आधारित खोज।<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>
@@ Line 123: / Line 119: @@
 ===[[पड़ोसियों के पास निश्चित-त्रिज्या]]===
-पड़ोसियों के पास निश्चित-त्रिज्या वह समस्या है जहां कोई एक निर्दिष्ट बिंदु से निश्चित दूरी के भीतर यूक्लिडियन अंतरिक्ष में दिए गए सभी बिंदुओं को कुशलतापूर्वक ढूंढना चाहता है। दूरी निश्चित मानी जाती है, लेकिन प्रश्न बिंदु मनमाना है।
+पड़ोसियों के पास निश्चित-त्रिज्या वह समस्या है जहां कोई निर्दिष्ट बिंदु से निश्चित दूरी के भीतर यूक्लिडियन अंतरिक्ष में दिए गए सभी बिंदुओं को कुशलतापूर्वक ढूंढना चाहता है। दूरी निश्चित मानी जाती है, लेकिन प्रश्न बिंदु मनमाना है।
 ===सभी निकटतम पड़ोसी===
-कुछ अनुप्रयोगों (जैसे [[एन्ट्रापी अनुमान]]) के लिए, हमारे पास एन डेटा-पॉइंट हो सकते हैं और हम जानना चाहते हैं कि उन एन पॉइंट्स में से प्रत्येक के लिए निकटतम पड़ोसी कौन सा है। यह, निश्चित रूप से, प्रत्येक बिंदु के लिए एक बार निकटतम-पड़ोसी खोज चलाकर हासिल किया जा सकता है, लेकिन एक बेहतर रणनीति एक एल्गोरिदम होगी जो अधिक कुशल खोज उत्पन्न करने के लिए इन एन प्रश्नों के बीच सूचना अतिरेक का फायदा उठाती है। एक सरल उदाहरण के रूप में: जब हम बिंदु X से बिंदु Y तक की दूरी पाते हैं, तो वह हमें बिंदु Y से बिंदु
+कुछ अनुप्रयोगों (जैसे [[एन्ट्रापी अनुमान]]) के लिए, हमारे पास एन डेटा-पॉइंट हो सकते हैं और हम जानना चाहते हैं कि उन एन पॉइंट्स में से प्रत्येक के लिए निकटतम पड़ोसी कौन सा है। यह, निश्चित रूप से, प्रत्येक बिंदु के लिए बार निकटतम-पड़ोसी खोज चलाकर हासिल किया जा सकता है, लेकिन बेहतर रणनीति एल्गोरिदम होगी जो अधिक कुशल खोज उत्पन्न करने के लिए इन एन प्रश्नों के बीच सूचना अतिरेक का फायदा उठाती है। सरल उदाहरण के रूप में: जब हम बिंदु X से बिंदु Y तक की दूरी पाते हैं, तो वह हमें बिंदु Y से बिंदु
-एक निश्चित आयाम को देखते हुए, एक अर्ध-निश्चित सकारात्मक मानदंड (जिससे प्रत्येक एलपी स्पेस|एल शामिल है<sup>p</sup> मानदंड), और इस स्थान में n बिंदु, प्रत्येक बिंदु का निकटतम पड़ोसी O(n log n) समय में पाया जा सकता है और प्रत्येक बिंदु का m निकटतम पड़ोसी O(mn log n) समय में पाया जा सकता है। समय।<ref>{{citation
+एक निश्चित आयाम को देखते हुए, अर्ध-निश्चित सकारात्मक मानदंड (जिससे प्रत्येक एलपी स्पेस|एल शामिल है<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

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 21:34, 12 July 2023

Contents

अनुप्रयोग