बी + ट्री होल्डिंग बहुआयामी डेटा

Question

कुशलता से पूछताछ में मेरे पास 64-बिट पूर्णांक के tuples (x,y) का संग्रह है जो मेरा डेटासेट बनाते हैं। मैंने कहा है, इन tuples के ट्रिलियन; पृथ्वी पर किसी भी मशीन पर डेटासेट को स्मृति में रखना संभव नहीं है। हालांकि, उन्हें डिस्क पर स्टोर करना काफी उचित है।

मेरे पास ऑन-डिस्क स्टोर (एक बी + -ट्री) है जो एक ही आयाम में डेटा की त्वरित, और समवर्ती, क्वेरीिंग की अनुमति देता है। हालांकि, मेरे कुछ प्रश्न दोनों आयामों पर भरोसा करते हैं।

क्वेरी उदाहरण:

• टपल जिसका x से अधिक या कुछ दिया मूल्य
• टपल जिसका x खोजें से बराबर है का पता लगाएं संभव s.t. के रूप में के रूप में छोटा है यह y किसी दिए गए मान से अधिक या उसके बराबर है
• उस टुपल को ढूंढें जिसका x जितना संभव हो उतना छोटा है। यह y कुछ दिया मूल्य
• रखरखाव कार्रवाई करने से कम या बराबर है है (कुछ टपल डालने को दूर कुछ टपल)

सबसे अच्छा शर्त मैं पाया है जेड क्रम घटता रहे हैं, लेकिन मैं यह पता लगाने नहीं कर पा रहे मेरे दो आयामी डेटा-सेट दिए गए प्रश्नों का संचालन कैसे करें।

समाधान जो स्वीकार्य नहीं हैं, उनमें डेटा का क्रमिक स्कैन शामिल है, यह बहुत धीमा हो सकता है।

Answer 1

क्या आप कह रहे हैं कि आप नहीं जानते कि z-order घटता कैसे क्वेरी करें? Wikipedia page वर्णन करता है कि आप श्रेणी की खोज कैसे करते हैं।

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

Start with the largest rectangle that might contain your point. 

    Recursively: 

     Create a result set of rectangles  

    For each rectangle in your set   
     If the rectangle is a single point, you are done, it is what you are looking for. 
     Otherwise, divide the rectangle in two (specify one additional bit of the z-curve) 
      If both halves contain a point 
       If one half is better 
        Add that rectangle to your result set of rectangles 
       Otherwise 
        Add both rectangles to your result set of rectangles 
      Otherwise, only one half contains a point 
        Add that rectangle to your result set of rectangles 

    Search your result set of rectangles 

सबसे खराब केस प्रदर्शन खराब है। आप अपने जेड-ऑर्डर इंडेक्स को कैसे बनाते हैं इसे बदलकर इसे समायोजित कर सकते हैं।

Answer 2

मुझे लगता है कि आपकी आवश्यकताओं के लिए सबसे उपयुक्त डेटा संरचना R-tree और इसके रूप (आर * -ट्री, आर + -ट्री, हिल्बर्ट आर-पेड़) हैं। आर-पेड़ बी + -ट्री के समान है, लेकिन बहुआयामी प्रश्नों की भी अनुमति देता है।

अन्य प्रासंगिक डेटा संरचना प्राथमिकता खोज वृक्ष है। यह आपके उदाहरण 1 .. 3 जैसे प्रश्नों के लिए अच्छा है, लेकिन यदि आपको लगातार अपडेट या ऑन-डिस्क स्टोर की आवश्यकता होती है तो बहुत प्रभावी नहीं है। विवरण के लिए this paper या यह पुस्तक देखें: "Handbook of Data Structures and Applications" (अध्याय 18.5)।

Answer 3

मैं वर्तमान में एक डेटा संरचना जो अनिवार्य रूप से एक 'खड़ी' B + ट्री (या एक घ + ट्री जहां घ आयाम की संख्या है) बहुआयामी डेटा के लिए है डिजाइन करने पर काम कर रहा हूँ

। मेरा मानना ​​है कि यह आपके डेटा को पूरी तरह अनुरूप करेगा और विशेष रूप से आपके उपयोग के मामले के लिए डिज़ाइन किया जा रहा है।

मूल विचार यह है:

प्रत्येक आयाम एक B + ट्री है और अगले आयाम के B + ट्री से जुड़ा हुआ है। आम तौर पर पहले आयाम के माध्यम से खोजें, एक बार पत्ती तक पहुंचने के बाद इसमें अगले बी + पेड़ की जड़ में एक सूचक होता है जो अगले आयाम से संबंधित होता है। दूसरे बी + पेड़ में सबकुछ उसी x मूल्य से संबंधित है।

मूल योजना केवल प्रत्येक आयाम के लिए अद्वितीय मानों को ही इसकी गणना के साथ ही संग्रहित करना था। यह एक बहुत ही सरल संपीड़न एल्गोरिदम (यदि आप इसे भी कॉल कर सकते हैं) को नियोजित करते हैं, जबकि अभी भी पूरे डेटा सेट का प्रतिनिधित्व करने की अनुमति है। यह 'लिंक्ड' आयाम योजना बाद में अतिरिक्त आयामों को जोड़ने की अनुमति दे सकती है क्योंकि उन्हें बस बी + पेड़ों के ढेर में जोड़ा जाता है।

log b(card(x)) + log b(card(y)) 

जहां ख प्रत्येक B + ट्री और कार्ड का आधार है (एक्स) प्रमुखता होगा:

कुल डालने/खोज/यह करने के लिए कुछ इसी तरह होगा 2 आयामों के लिए समय को नष्ट x आयाम का।

मुझे उम्मीद है कि यह समझ में आता है। मैं अभी भी एक कार्यान्वयन पर काम कर रहा हूं, हालांकि विचार करने या विचार को बढ़ाने में भी स्वतंत्र महसूस होता हूं।

Answer 4

http://fallabs.com/tokyocabinet/

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

टोक्यो कैबिनेट सी भाषा में लिखा गया है, और सी, पर्ल, रूबी, जावा और लुआ के एपीआई के रूप में प्रदान किया गया है। टोक्यो कैबिनेट प्लेटफॉर्म पर उपलब्ध है जिसमें एपीआई सी 99 और पॉज़िक्स के अनुरूप है। टोक्यो कैबिनेट एक मुफ्त सॉफ्टवेयर है जो जीएनयू लेसर जनरल पब्लिक लाइसेंस के तहत लाइसेंस प्राप्त है।

क्या आपके लिए एम्बेड करना आसान हो सकता है?