হিলবার্ট আর-ট্রি, একটি আর-ট্রি বৈকল্পিক, বহুমাত্রিক বস্তু যেমন লাইন, অঞ্চল, 3-ডি বস্তু বা উচ্চ-মাত্রিক বৈশিষ্ট্য-ভিত্তিক প্যারামেট্রিক বস্তুর জন্য একটি সূচক হিসাবে সংজ্ঞায়িত করা হয়। এটিকে বহুমাত্রিক বস্তুর জন্য B+-ট্রির এক্সটেনশন হিসেবে কল্পনা করা যেতে পারে।
R-trees-এর কর্মক্ষমতা নির্ভর করে অ্যালগরিদমের মানের উপর যা একটি নোডে ডেটা আয়তক্ষেত্রগুলিকে ক্লাস্টার করে। হিলবার্ট আর-ট্রি স্পেস-ফিলিং কার্ভ এবং বিশেষ করে হিলবার্ট বক্ররেখা প্রয়োগ করে, ডেটা আয়তক্ষেত্রে রৈখিক ক্রম আরোপ করার জন্য।
হিলবার্ট আর-ট্রি দুটি ধরনের:একটি স্ট্যাটিক ডাটাবেসের জন্য এবং একটি গতিশীল ডাটাবেসের জন্য। উভয় ক্ষেত্রেই হিলবার্ট স্পেস-ফিলিং কার্ভগুলি নোডে বহুমাত্রিক বস্তুর আরও ভাল ক্রম অর্জনের জন্য প্রয়োগ করা হয়। এই ক্রমটিকে 'ভাল' হিসাবে বিবেচনা করা উচিত, সেই অর্থে এটিকে 'সদৃশ' ডেটা আয়তক্ষেত্রগুলিকে একত্রে গোষ্ঠীভুক্ত করা উচিত, ফলে ন্যূনতম আবদ্ধ আয়তক্ষেত্রগুলির (MBRs) ক্ষেত্রফল এবং পরিধি কমাতে। প্যাকড হিলবার্ট আর-ট্রিগুলি স্ট্যাটিক ডাটাবেসের জন্য দরকারী যেখানে আপডেটগুলি খুব বিরল বা যেখানে কোনও আপডেট নেই৷
মূল ধারণা
যদিও নিম্নলিখিত উদাহরণটি একটি স্থির পরিবেশের জন্য বোঝানো হয়েছে, এটি ভাল আর-ট্রি ডিজাইনের জন্য স্বজ্ঞাত নীতিগুলি নিয়ে আলোচনা করে। এই নীতিগুলি স্ট্যাটিক এবং ডাইনামিক উভয় ডেটাবেসের জন্যই বৈধ৷
৷Roussopoulos এবং Leifker একটি প্যাকড আর-ট্রি নির্মাণের জন্য একটি কৌশল প্রস্তাব করেছেন যা প্রায় 100% স্থান ব্যবহার করে।
আয়তক্ষেত্রগুলির একটি কোণে x বা y স্থানাঙ্কের ডেটা সাজানোর জন্য ধারণাটি তৈরি করা হয়েছে। চারটি স্থানাঙ্কের যেকোনো একটিতে সাজানো একই ফলাফল দেয়। এই আলোচনায় হয় বিন্দু বা আয়তক্ষেত্রগুলি আয়তক্ষেত্রের নীচের বাম কোণের x স্থানাঙ্কে সাজানো হয়, যাকে "lowx প্যাকড R-tree" হিসাবে চিহ্নিত করা হয়। আয়তক্ষেত্রের সাজানো তালিকা স্ক্যান করা হয়; ক্রমাগত আয়তক্ষেত্রগুলি অনুরূপ আর-ট্রি লিফ নোডে বরাদ্দ করা হয় যতক্ষণ না সেই নোডটি পূর্ণ হয়; তারপরে একটি নতুন লিফ নোড তৈরি করা হয় এবং সাজানো তালিকার স্ক্যানিং চলতে থাকে। এইভাবে, R-tree-এর নোড সম্পূর্ণরূপে প্যাক করা হবে, প্রতিটি স্তরে শেষ নোডের সম্ভাব্য ব্যতিক্রম সহ। এই ঘটনা বাড়ে যাতে স্থান ব্যবহার ≈100%. গাছের উচ্চ স্তর একইভাবে নির্মিত হয়।
অ্যালগরিদম হিলবার্ট-প্যাক
(একটি আর-ট্রিতে আয়তক্ষেত্র প্যাকিং)
ধাপ 1. প্রতিটি ডেটা আয়তক্ষেত্রের জন্য হিলবার্ট মান গণনা করা হয়।
ধাপ 2. আরোহী হিলবার্ট মানের ডেটা আয়তক্ষেত্রগুলি সাজানো হয়েছে৷
ধাপ 3। /* লিফ নোড তৈরি করা (লেভেল l=0) */
- যখন (আরও আয়তক্ষেত্র আছে)
- একটি নতুন আর-ট্রি নোড তৈরি করা হয়েছে
- এই নোডের পরবর্তী C আয়তক্ষেত্রগুলি বরাদ্দ করা হয়েছে
ধাপ 4. /* উচ্চ স্তরে নোড তৈরি করা (l + 1) */
- যখন (l স্তরে> 1টি নোড আছে)
- আরোহী সৃষ্টির সময় l ≥ 0 স্তরে নোডগুলি সাজানো হয়
- ধাপ 3 পুনরাবৃত্তি হয়
এখানে অনুমান হল যে হয় ডেটা স্ট্যাটিক বা পরিবর্তনের ফ্রিকোয়েন্সি কম। ~100% স্পেস ইউটিলাইজেশন সহ একটি আর-ট্রি তৈরির জন্য এটি একটি সহজ হিউরিস্টিক যা একই সময়ে একটি ভাল প্রতিক্রিয়া সময় পাবে৷
