মৌলিক ধারণা
ডেটা প্রসেসিংয়ের ক্ষেত্রে, R*-trees-কে R-trees-এর একটি রূপ হিসাবে সংজ্ঞায়িত করা হয় যা স্থানিক তথ্যের সূচীকরণের জন্য প্রয়োগ করা হয়।
R*-গাছের নির্মাণ খরচ স্ট্যান্ডার্ড R-ট্রির তুলনায় একটু বেশি, কারণ ডেটা পুনরায় ঢোকানোর প্রয়োজন হতে পারে; কিন্তু ফলস্বরূপ গাছের সাধারণত একটি ভাল ক্যোয়ারী কর্মক্ষমতা থাকবে। স্ট্যান্ডার্ড আর-ট্রির মতোই, এটি পয়েন্ট এবং স্থানিক ডেটা উভয়ই সঞ্চয় করতে পারে। 1990 সালে নরবার্ট বেকম্যান, হ্যান্স-পিটার ক্রিগেল, রাল্ফ স্নাইডার এবং বার্নহার্ড সিগার দ্বারা R*-ট্রির ধারণাটি প্রস্তাব করা হয়েছিল।
R*-trees এবং R-trees এর মধ্যে পার্থক্য
R*-বৃক্ষ বারবার সন্নিবেশ দ্বারা নির্মিত হয়। এই গাছে সামান্য (অর্থাৎ প্রায় নেই) ওভারল্যাপ আছে, যার ফলে ভাল ক্যোয়ারী পারফরম্যান্স হয়। কভারেজ এবং ওভারল্যাপ উভয়েরই ন্যূনতমকরণ R-trees-এর কর্মক্ষমতার জন্য খুবই গুরুত্বপূর্ণ। ওভারল্যাপের অর্থ, ডেটা সন্নিবেশ বা অনুসন্ধানে, গাছের একাধিক শাখা প্রসারিত করা প্রয়োজন (যেভাবে ডেটা ওভারল্যাপ হতে পারে এমন অঞ্চলে ভাগ করা হচ্ছে)। একটি ন্যূনতম কভারেজ ছাঁটাই কার্যকারিতা বাড়ায়, বিশেষ করে নেতিবাচক পরিসরের প্রশ্নের জন্য ঘন ঘন অনুসন্ধান থেকে পুরো পৃষ্ঠাগুলি বাদ দেওয়ার অনুমতি দেয়। R*-ট্রি একটি সংশোধিত নোড স্প্লিট অ্যালগরিদমের সংগ্রহ এবং নোড ওভারফ্লোতে জোরপূর্বক পুনঃপ্রবেশের ধারণা বাস্তবায়ন করে উভয়কেই কমানোর চেষ্টা করে। এই ধারণাটি এই পর্যবেক্ষণের উপর ভিত্তি করে তৈরি করা হয়েছে যে আর-ট্রি স্ট্রাকচারগুলি যে ক্রমে তাদের এন্ট্রিগুলি ঢোকানো হয় তার জন্য অত্যন্ত সংবেদনশীল, তাই একটি সন্নিবেশ-নির্মিত (বাল্ক-লোডের পরিবর্তে) কাঠামো উপ-অনুকূল হতে পারে। এন্ট্রিগুলি মুছে ফেলা এবং পুনঃপ্রবেশ করা তাদের গাছের মধ্যে একটি জায়গা "খুঁজে" করার অনুমতি দেয় যা তাদের প্রকৃত অবস্থানের চেয়ে বেশি উপযুক্ত হতে পারে৷
অ্যালগরিদম এবং জটিলতা
- R*-tree ক্যোয়ারী এবং ডিলিট অপারেশনের জন্য নিয়মিত R-tree-এর মতো অনুরূপ অ্যালগরিদম প্রয়োগ করে।
- সন্নিবেশ করার সময়, R*-tree একটি সম্মিলিত কৌশল প্রয়োগ করে। লিফ নোডের জন্য, ওভারল্যাপ মিনিমাইজ করা হয়, যখন ভিতরের নোডের জন্য, বড় করা এবং ক্ষেত্রফল ছোট করা হয়।
- বিভক্ত হওয়ার সময়, R*-ট্রি একটি টপোলজিকাল স্প্লিট প্রয়োগ করে যা পরিধির উপর ভিত্তি করে একটি বিভক্ত অক্ষ নির্বাচন করে, তারপর ওভারল্যাপকে ছোট করে।
- একটি বর্ধিত বিভক্ত কৌশল ছাড়াও, R*-tree একটি B-tree ভারসাম্য রাখার ধারণা দ্বারা অনুপ্রাণিত হয়ে গাছের মধ্যে বস্তু এবং উপবৃক্ষগুলিকে পুনরায় সন্নিবেশিত করে বিভাজন এড়ানোর চেষ্টা করে।
সবচেয়ে খারাপ কেস কোয়েরি এবং মুছে ফেলার জটিলতা এইভাবে আর-ট্রির মতো। R*-ট্রিতে সন্নিবেশ করার কৌশলটি O(M log M) এর সাথে R-ট্রির রৈখিক বিভক্ত কৌশল (O(M)) এর চেয়ে জটিল, তবে দ্বিঘাত বিভক্ত কৌশল (O(M
