नॉन-वर्दीली आकार के हाइपरफेयर के बीच निकटतम पड़ोसी खोज के लिए तेज़ स्थानिक डेटा संरचना

Question

एक अप्रत्याशित रूप से चलती/बढ़ती/सिकुड़ने वाली हाइपरफेयर से भरे एक के-आयामी निरंतर (यूक्लिडियन) स्थान को देखते हुए मुझे बार-बार हाइपरफेयर ढूंढने की आवश्यकता होती है जिसकी सतह निकटतम होती है निर्देशांक दिया गया। अगर कुछ हाइपरफेयर मेरे समन्वय के लिए एक ही दूरी के हैं, तो सबसे बड़ा हाइपरस्फेयर जीतता है। (Hyperspheres की कुल संख्या समय के साथ ही रहने की गारंटी है।)

मेरी पहली सोचा एक KDTree का इस्तेमाल किया गया, लेकिन यह ध्यान में hyperspheres 'असमान मात्रा में नहीं ले जाएगा। तो मैंने आगे देखा और बीवीएच (बाउंडिंग वॉल्यूम पदानुक्रम) और बीआईएच (बाउंडिंग अंतराल पदानुक्रम), जो चाल चल रहा है। कम से कम 2-/3-आयामी अंतरिक्ष में। हालांकि बीवीएच पर काफी जानकारी और विज़ुअलाइज़ेशन ढूंढते समय मुझे शायद ही कभी बीआईएच पर कुछ भी मिल सके।

मेरे बुनियादी आवश्यकता एक कश्मीर आयामी स्थानिक डेटा संरचना है कि खाता में मात्रा लेता है और या तो सुपर (बंद लाइन) का निर्माण करने के लिए तेजी से या बमुश्किल कोई unbalancing साथ गतिशील है।

उपर्युक्त मेरी आवश्यकताओं को देखते हुए, आप किस डेटा संरचना के साथ जाएंगे? किसी और ने मुझे भी उल्लेख नहीं किया?

---

संपादित करें 1: उल्लेख करने के लिए भूल गए: हाइपरशेयर की अनुमति है (वास्तव में अत्यधिक अपेक्षित) ओवरलैप करने के लिए!

संपादित करें 2: "दूरी" (और विशेष रूप से "नकारात्मक दूरी" के बजाय) जैसा दिखता है, मेरे वर्णित मीट्रिक power of a point से बेहतर है।

Answer 1

मैं उम्मीद करता हूं कि केए की आपकी आयामीता के लिए क्वाड्री/ऑक्ट्री/सामान्यीकृत 2^के-पेड़ की चाल होगी; ये पुनरावर्ती विभाजन स्थान, और संभवतः आप तब रोक सकते हैं जब एक के-सबक्यूब (या के-आयताकार ईंट अगर विभाजन भी नहीं होते हैं) में एक हाइपरफेयर नहीं होता है, या इसमें एक या अधिक हाइपरफ़ेरेस होते हैं जैसे कि विभाजन किसी को अलग नहीं करता है, या वैकल्पिक रूप से केवल एक ही हाइपरफेयर का केंद्र होता है (शायद आसान)।

ऐसे पेड़ों में इकाइयों को सम्मिलित करना और हटाना तेज़ है, इसलिए एक हाइपरस्फेयर बदलते आकार में ऑपरेशन की डिलीट/डालने वाली जोड़ी होती है। (मुझे संदेह है कि यदि आप गोलाकार हो जाते हैं, या स्थानीय के-ब्लॉक विलय होने पर स्थानीय क्षेत्र के रिकर्सिव विभाजन द्वारा आपके क्षेत्र का आकार बदलता है तो आप इसे अनुकूलित कर सकते हैं)।

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

लेकिन किसी भी मामले में मैंने सोचा कि 2^के पेड़ और/या बीएसपी/केडीटीआर के लिए सम्मिलन/हटाना एल्गोरिदम अच्छी तरह से समझा और तेज़ था। तो हाइपरस्फेयर आकार में परिवर्तन हटाना/सम्मिलन संचालन का कारण बनता है लेकिन वे तेज़ होते हैं। तो मैं केडी-पेड़ों को आपत्ति नहीं समझता।

मुझे लगता है कि इन सभी का प्रदर्शन असम्बद्ध रूप से वही है।

Answer 2

मैं SQLite के लिए आर * वृक्ष एक्सटेंशन का उपयोग करूंगा। एक तालिका में आमतौर पर 1 या 2 आयामी डेटा होगा। एसक्यूएल प्रश्न उच्च आयामों में खोजने के लिए कई तालिकाओं को जोड़ सकते हैं।

नकारात्मक दूरी के साथ फॉर्मूलेशन थोड़ा अजीब है।ज्यामिति में दूरी सकारात्मक है, इसलिए उपयोग करने के लिए बहुत उपयोगी सिद्धांत नहीं हो सकता है।

एक अलग फॉर्मूलेशन जो केवल सकारात्मक दूरी का उपयोग करता है सहायक हो सकता है। हाइपरबॉलिक रिक्त स्थान के बारे में पढ़ें। यह दूरी का वर्णन करने के अन्य तरीकों के लिए विचार प्रदान करने में मदद कर सकता है।