आर-ट्री कार्यान्वयन जावा

Question

मैं असीमित आयामों के समर्थन के साथ आर-ट्री के स्थिर कार्यान्वयन के लिए पिछले कुछ दिनों की खोज कर रहा था (20 या तो पर्याप्त होगा)। मुझे केवल यह http://sourceforge.net/projects/jsi/ मिला लेकिन वे केवल 2 आयामों का समर्थन करते हैं।

एक और विकल्प अंतराल-पेड़ का एक बहुआयामी कार्यान्वयन होगा।

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

समस्या को हल करने की समस्या मुझे किसी प्रकार की निकटतम पड़ोसी खोज है। मेरे पास एंटेना और कमरे का एक सेट है और प्रत्येक एंटीना के लिए इंटीग्रियों का अंतराल है। जैसे एंटीना 1, न्यूनतम -92, अधिकतम -85। वास्तव में इसे कमरे के रूप में प्रदर्शित किया जा सकता है -> एंटेना का सेट -> एंटीना के लिए अंतराल। विचार यह था कि प्रत्येक कमरा एंटीना के आयाम और अंतराल के प्रत्येक आयाम पर आर-ट्री में एक बॉक्स को फैलाता है।

यदि मुझे एन एंटेना और प्रत्येक एंटीना के लिए मूल्यों के साथ कोई प्रश्न मिलता है तो मैं कमरे में एक प्रश्न बिंदु के रूप में जानकारी का प्रतिनिधित्व कर सकता हूं और कमरे को "निकटतम" बिंदुओं को पुनर्प्राप्त कर सकता हूं।

आशा है कि आपको समस्या का विचार और मेरा विचार मिलेगा।

Answer 1

मैं आपकी सटीक समस्या के बारे में पूरी तरह से स्पष्ट नहीं हूं, लेकिन आर-ट्री या अंतराल का पेड़ 20 आयामों में अच्छी तरह से काम नहीं करेगा। यह आयामों की एक बड़ी संख्या नहीं है, लेकिन यह आयाम के अभिशाप को शुरू करने के लिए काफी बड़ा है।

मेरा मतलब यह देखने के लिए, बस बॉक्स के सभी पड़ोसियों को देखने की कोशिश करें, जिनमें कोनों और किनारों से बाहर भी शामिल है। 20 आयामों के साथ, आपके पास 3 - 1 या 3,486,784,400 पड़ोसी बक्से होंगे। (आपको यह समझकर मिलता है कि प्रत्येक अक्ष के साथ एक पड़ोसी -1 यूनिट, 0 यूनिट, या +1 यूनिट हो सकता है, लेकिन (0,0,0) पड़ोसी नहीं है क्योंकि यह मूल बॉक्स का प्रतिनिधित्व करता है।)

मुझे खेद है, लेकिन आपको या तो ब्रूट फोर्स की खोज स्वीकार करने की आवश्यकता है, या फिर अपनी समस्या का बेहतर विश्लेषण करें और एक चतुर समाधान के साथ आएं।

Answer 2

ध्यान रखें कि जब आपके पास असतत डेटा होता है तो आर-पेड़ बुरी तरह खराब हो सकता है। पहली चीज़ जो आपको वास्तव में खोजने की ज़रूरत है वह उचित डेटा प्रस्तुति है, फिर जांच करें कि क्या आपके प्रश्न डेटा के सबसेट पर काम करते हैं।

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

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

Answer 3

मुझे जावा में यह आर * -ट्री कार्यान्वयन मिला है जो लगता है कई सुविधाओं की पेशकश करने के लिए:

https://github.com/davidmoten/rtree

आप इसे बाहर की जाँच करने के लिए चाहते हो सकता है!

Answer 4

जावा में एक और अच्छा कार्यान्वयन ELKI: https://elki-project.github.io/ है।