2 डी

Question

में फास्ट के-निकटतम पड़ोसी खोज के लिए डेटा संरचना और एल्गोरिदम का उपयुक्त विकल्प मेरे पास 2 डी स्पेस में अंक का प्रतिनिधित्व करने वाले लगभग 100,000 (एक्स, वाई) जोड़े का डेटासेट है। प्रत्येक बिंदु के लिए, मैं अपने के-निकटतम पड़ोसियों को ढूंढना चाहता हूं।

तो, मेरे सवाल है - क्या डेटा संरचना/एल्गोरिथ्म एक उपयुक्त विकल्प होगा, यह मानते हुए मैं बिल्कुल समग्र समय चल रहा है कम करने के लिए करना चाहते हैं?

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

मुझे लगता है कि डेटा संरचना बनाने का सबसे अच्छा तरीका है, फिर कुछ चलाएं प्रत्येक बिंदु के लिए के-निकटतम पड़ोसी खोज की तरह। हालांकि, चूंकि (ए) मैं पहले से ही अंक जानता हूं, और (बी) मुझे पता है कि मुझे हर बार एक बिंदु के लिए खोज चलाना चाहिए, शायद एक बेहतर दृष्टिकोण है?

कुछ अतिरिक्त विवरण:

• जब से मैं पूरे प्रसारण समय कम करना चाहते हैं, मुझे परवाह नहीं करता है, तो समय के बहुमत खोज बनाम संरचना पर खर्च किया जाता है है।
• (एक्स, वाई) जोड़े काफी अच्छी तरह फैल गए हैं, इसलिए हम लगभग समान वितरण मान सकते हैं।

Answer 1

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

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

यदि आपके पास अभी तक के अंक नहीं हैं, या आपके पास के अंक हैं लेकिन ग्रिड तत्व की एक या अधिक दीवारें के बिंदुओं के सबसे दूर की तुलना में आपकी रुचि के बिंदु के करीब हैं, तो प्रासंगिक आसन्न ग्रिड तत्वों को जोड़ें खोज।

यह आपको एक अपेक्षाकृत कम निरंतर कारक के साथ, O(N*k^2) की तरह कुछ के प्रदर्शन देना चाहिए। यदि के बड़ा है, तो यह रणनीति बहुत सरल है और आपको एल्गोरिदम चुनना चाहिए जो कि रैखिक या लॉग-रैखिक है, जैसे कि केडी-पेड़ हो सकते हैं।