ডেটা স্ট্রাকচারে হিলবার্ট ট্রি

হিলবার্ট R-ট্রি, একটি R-ট্রি ভ্যারিয়েন্ট, হলো মাল্টিডাইমেনশনাল অবজেক্টের জন্য একটি ইনডেক্স যেমন লাইন, রিজন, 3-D অবজেক্ট, বা হাই-ডাইমেনশনাল ফিচার-বেসড প্যারামেট্রিক অবজেক্ট। এটি কল্পনা করা যায় B+-ট্রির এক্সটেনশন হিসেবে মাল্টিডাইমেনশনাল অবজেক্টের জন্য।

R-ট্রির পারফরমেন্স নির্ভর করে ডেটা রেক্ট্যাঙ্গেল ক্লাস্টার করার অ্যালগরিদমের গুণগত ওপর যা একটি নোডে থাকে। হিলবার্ট R-ট্রি স্পেস-ফিলিং কার্ভ, এবং বিশেষভাবে হিলবার্ট কার্ভ, বাস্তবায়ন করে ডেটা রেক্ট্যাঙ্গেলের ওপর একটি লিনিয়ার অর্ডারিং আরোপ করতে।

হিলবার্ট R-ট্রি দুটি প্রকারের: একটি স্ট্যাটিক ডেটাবেসের জন্য, এবং একটি ডাইনামিক ডেটাবেসের জন্য। দুটি কেসেই হিলবার্ট স্পেস-ফিলিং কার্ভ বাস্তবায়ন করা হয় মাল্টিডাইমেনশনাল অবজেক্টের নোডে बेटার অর্ডারিং অর্জন করতে। এই অর্ডারিংকে 'ভালো' মনে করা হয় সেই মানে যে এতে 'সাদৃশ্য' ডেটা রেক্ট্যাঙ্গেল একসাথে গ্রুপ করা উচিত, যাতে ফলাফলস্বরূপ মিনিমাম বাউন্ডিং রেক্ট্যাঙ্গেল (MBRs) এর এরিয়া এবং পেরিমিটার কমিয়ে আনা যায়। প্যাকড হিলবার্ট R-ট্রি স্ট্যাটিক ডেটাবেসের জন্য উপযোগী যেখানে আপডেট খুব কম বা কখনোই নেই।

মৌলিক ধারণা

যদিও নিচের উদাহরণটি স্ট্যাটিক এনভায়রনমেন্টের জন্য, এটি ভালো R-ট্রি ডিজাইনের ইন্টুইটিভ প্রিন্সিপল আলোচনা করে। এই প্রিন্সিপলগুলো স্ট্যাটিক এবং ডাইনামিক ডেটাবেস দুটোইর জন্য বৈধ।

Roussopoulos এবং Leifker একটি টেকনিক প্রপোজ করেছেন প্যাকড R-ট্রি কনস্ট্রাক্ট করার জন্য যা প্রায় ১০০% স্পেস ইউটিলাইজেশন অর্জন করে।

আইডিয়া হলো ডেটা সোর্ট করা x বা y কোঅর্ডিনেটের ওপর রেক্ট্যাঙ্গেলের কোর্নারের যেকোনো একটি। চারটি কোঅর্ডিনেটের যেকোনো একটি দিয়ে সোর্ট করলে একই ফলাফল দেয়। এই আলোচনায় হয় পয়েন্ট বা রেক্ট্যাঙ্গেল সর্ট করা হয় রেক্ট্যাঙ্গেলের নিচের বাম কোনার x কোঅর্ডিনেট দিয়ে, যাকে "lowx packed R-tree" বলা হয়। রেক্ট্যাঙ্গেলের সর্টেড লিস্ট স্ক্যান করা হয়; সাকসেসিভ রেক্ট্যাঙ্গেল একই R-ট্রি লিফ নোডে অ্যাসাইন করা হয় যতক্ষণ না সেটি ফুল হয়; একটি নতুন লিফ নোড তৈরি হয়, এবং সর্টেড লিস্ট স্ক্যানিং চালু থাকে। ফলে, ফলাফলস্বরূপ R-ট্রির নোড ফুলি প্যাকড থাকবে, সম্ভবত প্রতিটি লেভেলের শেষ নোড বাদে। এতে ঘটে যাতে স্পেস ইউটিলাইজেশন ≈100%। হায়ার লেভেলগুলো একইভাবে তৈরি হয়।

অ্যালগরিদম Hilbert-Pack

(রেক্ট্যাঙ্গেলকে R-ট্রিতে প্যাক করা)

Step 1. প্রতিটি ডেটা রেক্ট্যাঙ্গেলের জন্য হিলবার্ট ভ্যালু ক্যালকুলেট করা হয়।

Step 2. ডেটা রেক্ট্যাঙ্গেল আরোহী হিলবার্ট ভ্যালু দিয়ে সর্ট করা হয়।

Step 3. /* লিফ নোড তৈরি করা (লেভেল l=0) */

• যখন (আরও রেক্ট্যাঙ্গেল আছে)
• একটি নতুন R-ট্রি নোড জেনারেট করা হয়
• পরবর্তী Cটি রেক্ট্যাঙ্গেল এই নোডে অ্যাসাইন করা হয়

Step 4. /* হায়ার লেভেলে নোড তৈরি (l + 1) */

• যখন (লেভেল l-এ > ১টি নোড আছে)
• লেভেল l ≥ 0-এ নোডগুলো আরোহী ক্রিয়েশন টাইম দিয়ে সর্ট করা হয়
• Step 3 রিপিট করা হয়

এখানে অনুমান করা হয়েছে যে ডেটা বা तो স্ট্যাটিক অথবা মডিফিকেশন ফ্রিকোয়েন্সি কম। এটি একটি সিম্পল হিউরিস্টিক R-ট্রি বিল্ড করার জন্য ~100% স্পেস ইউটিলাইজেশন সহ যা একই সময়ে ভালো রেসপন্স টাইম দেবে।