STING গ্রিড-ভিত্তিক ক্লাস্টারিং
গ্রিড-ভিত্তিক ক্লাস্টারিং পদ্ধতিগুলো একটি মাল্টি-রেজোলিউশন গ্রিড ডেটা স্ট্রাকচার ব্যবহার করে। এটি অবজেক্ট এলাকাকে সellige সংখ্যক সেলে কোয়ান্টাইজ করে যা একটি গ্রিড কাঠামো তৈরি করে যার ওপর ক্লাস্টারিং-এর সকল অপারেশন বাস্তবায়ন করা হয়। এই পদ্ধতির সুবিধা হল এর দ্রুত প্রসেসিং টাইম, যা সাধারণত ডেটা অবজেক্টের সংখ্যার ওপর নির্ভরশীল নয়, বরং কোয়ান্টাইজড স্পেসে প্রতিটি ডায়মেনশনে সেলের সংখ্যার ওপর নির্ভরশীল।
গ্রিড-ভিত্তিক ক্লাস্টারিং একটি মাল্টি-রেজোলিউশন গ্রিড ডেটা স্ট্রাকচার ব্যবহার করে এবং ঘন গ্রিড সেল ব্যবহার করে ক্লাস্টার তৈরি করে। বেশ কিছু আকর্ষণীয় পদ্ধতি রয়েছে: STING, ওয়েভ ক্লাস্টার (wave cluster), এবং CLIQUE।
STING (Statistical Information Grid approach)
স্থানিক এলাকাকে আয়তাকার সেলে ভাগ করা হয়। রেজোলিউশনের বিভিন্ন পদ্ধতির সাথে সম্পর্কিত সেলের বিভিন্ন লেভেল রয়েছে। হাই লেভেলের প্রতিটি সেল পরবর্তী নিম্ন লেভেলে একাধিক ছোট সেলে ভাগ করা হয়। প্রতিটি সেলের সাংখ্যিক তথ্য আগে থেকে গণনা ও সংরক্ষণ করা থাকে এবং কোয়ারি উত্তর দেওয়া যায়। হাই-লেভেল সেলের স্পেসিফিকেশন নিম্ন-লেভেল সেলের স্পেসিফিকেশন থেকে সহজে গণনা করা যায়:
- কাউন্ট (count), গড় (mean), s, মিন (min), ম্যাক্স (max)
- বন্টনের ধরন - নরমাল, ইউনিফর্ম, ইত্যাদি।
সাংখ্যিক ইনফরমেশন গ্রিড-ভিত্তিক পদ্ধতি (STING) একটি হায়ারার্কিক্যাল পদ্ধতি অনুসরণ করে স্থানিক এলাকাকে আয়তাকার সেলে ভাগ করতে কোয়ার্টট্রি (quadtree) সদৃশ। স্পেশিয়াল ডেটাবেস একবার স্ক্যান করা হয়, এবং প্রতিটি সেলের জন্য সাংখ্যিক প্যারামিটার নির্ধারিত হয়। STING কৌশলকে একটি হায়ারার্কিক্যাল পদ্ধতির ধরন হিসেবে দেখা যেতে পারে। প্রথম ধাপ হল একটি হায়ারার্কিক্যাল বর্ণনা তৈরি করা। তৈরি ট্রি আলাদা করে এলাকাকে কোয়ার্টারে ভাগ করে।
স্পেসের প্রতিটি সেল ট্রিতে একটি নোডের সাথে সম্পর্কিত এবং উভয় অ্যাট্রিবিউট-স্বতন্ত্র (কাউন্ট) ডেটা এবং অ্যাট্রিবিউট-নির্ভর (গড়, স্ট্যান্ডার্ড ডেভিয়েশন, ন্যূনতম, সর্বোচ্চ, বন্টন) ডেটা দিয়ে বর্ণিত। যেহেতু ট্রিতে নোডের সংখ্যা ডেটাবেসে আইটেমের সংখ্যা থেকে কম, STING BUILD-এর কমপ্লেক্সিটি O(n)।
অ্যালগরিদম
ইনপুট (Input)
D // হায়ারার্কিক্যাল স্ট্রাকচারে রাখার ডেটা k // নিম্নতম লেভেলে ইচ্ছিত সেলের সংখ্যা
আউটপুট (Output)
T // ট্রি STING BUILD অ্যালগরিদম // টপ-ডাউন থেকে একটি খালি ট্রি তৈরি T = রুট নোড ডেটা ভ্যালু ইনিশিয়ালাইজড; // প্রাথমিকভাবে শুধু রুট নোড i = 1; রিপিট লেভেল i-এ প্রতিটি নোডের জন্য ৪টি চাইল্ড নোড তৈরি ইনিশিয়াল ভ্যালুসহ; i = i + 1; যতক্ষণ না 4i = k; // বটম-আপ থেকে ট্রি পপুলেট করুন D-এ প্রতিটি আইটেমের জন্য D-এর পজিশন সম্পর্কিত লিফ নোড j নির্ধারণ করুন; আইটেমের অ্যাট্রিবিউট ভ্যালুতে ভিত্তি করে j-এর ভ্যালু আপডেট করুন; i := log4(k); রিপিট i := i - 1; লেভেল i-এ প্রতিটি নোড j-এর জন্য তার ৪টি চাইল্ডের অ্যাট্রিবিউট ভ্যালুতে ভিত্তি করে j-এর ভ্যালু আপডেট করুন; যতক্ষণ না i = 1;
