মৌলিক ধারণা
একটি কাইনেটিক ডেটা স্ট্রাকচার হলো একটি ডেটা স্ট্রাকচার যা একটি জ্যামিতিক সিস্টেমের একটি অ্যাট্রিবিউট ট্র্যাক করতে বাস্তবায়িত হয় যা ক্রমাগত চলে। উদাহরণস্বরূপ, একটি কাইনেটিক কনভেক্স হাল ডেটা স্ট্রাকচার nটি চলমান পয়েন্টের কনভেক্স হাল ট্র্যাক করে।
কাইনেটিক ডেটা স্ট্রাকচারের উন্নতি কম্পিউটেশনাল জ্যামিতির সমস্যা থেকে প্রেরণা পায় যাতে ফিজিক্যাল অবজেক্ট ক্রমাগত গতিশীল থাকে, উদাহরণস্বরূপ রোবটিক্স, অ্যানিমেশন বা কম্পিউটার গ্রাফিক্স-এ কলিশন বা ভিজিবিলিটি ডিটেকশন।
ওভারভিউ
কাইনেটিক ডেটা স্ট্রাকচার उन সিস্টেমগুলোর ওপর বাস্তবায়িত হয় যেখানে মানগুলোর একটি সেট সময়ের ফাংশন হিসেবে পরিবর্তিত হয়, একটি ডিক্লেয়ারড ফ্যাশনে। তাই সিস্টেমের কিছু মান আছে, এবং সিস্টেমের প্রতিটি মান v-এর জন্য, এটি ডেনোট করে যে v=f(t)। কাইনেটিক ডেটা স্ট্রাকচার করেন্ট ভার্চুয়াল টাইম t-এ সিস্টেমে কোয়েরি করার অনুমতি দেয়, এবং দুটি অতিরিক্ত অপারেশন:
- advance(t): সিস্টেমকে টাইম t-এ এডভ্যান্স করা হয়।
- change(v,f(t)): করেন্ট টাইম ณ,value v-এর ট্রাজেক্টরি f(t)-এ পরিবর্তন করা হয়।
অতিরিক্ত অপারেশনও সাপোর্ট করা যেতে পারে। উদাহরণস্বরূপ, কাইনেটিক ডেটা স্ট্রাকচার প্রায়ই পয়েন্টের একটি সেটের সাথে বাস্তবায়িত হয়। এই ক্ষেত্রে, স্ট্রাকচারটি সাধারণত পয়েন্ট ইনসার্ট এবং ডিলিট করার অনুমতি দেয়।
পরम्पরাগত ডেটা স্ট্রাকচারের সাথে বিপরীততা
একটি কাইনেটিক ডেটা স্ট্রাকচার এর মধ্যে স্টোর করা মানগুলোর ক্রমাগত পরিবর্তনের অনুমতি দেয় সময়ের সাথে। সিদ্ধান্তে, এটি পয়েন্টের পজিশন স্যাম্পলিং করে ফিক্সড টাইম ইন্টারভালে অনুমান করা যায়, এবং প্রতিটি পয়েন্ট ডিলিট এবং রি-ইনসার্ট করা যায় একটি "স্ট্যাটিক" (পরम्पরাগত) ডেটা স্ট্রাকচারে। যাইহোক, এমন পদ্ধতিটি ওভারস্যাম্পলিং বা আন্ডারস্যাম্পলিং-এ আপদস্থ, টাইম ইন্টারভাল কী ব্যবহার করা হয়েছে তার ওপর নির্ভর করে, এবং কম্পিউটেশনাল রিসোর্সের অপচয়ও হতে পারে।
সার্টিফিকেট পদ্ধতি (Certificates approach)
নিচের সাধারণ পদ্ধতিটি কাইনেটিক ডেটা স্ট্রাকচার বিল্ড করতে বাস্তবায়ন করা যায়:
- করেন্ট টাইম t-এ সিস্টেমের ওপর একটি ডেটা স্ট্রাকচার স্টোর করা হয়। এই ডেটা স্ট্রাকচার করেন্ট ভার্চুয়াল টাইমে সিস্টেমে কোয়েরি করার অনুমতি দেয়।
- ডেটা স্ট্রাকচারকে সার্টিফিকেটসহ অগমেন্ট করা হয়। সার্টিফিকেট হলো শর্তাবলী যারা অধীনে ডেটা স্ট্রাকচারটি আক্যুরেট। সার্টিফিকেটগুলো এখন সব সত্য, এবং ডেটা স্ট্রাকচারটি তখনই আক্যুরেট থাকবере না যখন সার্টিফিকেটের একটা আর সত্য নয়।
- প্রতিটি সার্টিফিকেটের ফেইলার টাইম ক্যালকুলেট করা হয়, সেটি কখন আর সত্য থাকবে না।
- সার্টিফিকেটগুলো একটি প্রায়রিটি কিউতে স্টোর করা হয়, তাদের ফেইলার টাইম দিয়ে কী করা হয়।
- টাইম t-এ এডভ্যান্স করতে, প্রায়রিটি কিউ থেকে মিনিমাম ফেইলার টাইমের সার্টিফিকেটে তাকানো হয়। যদি সার্টিফিকেট টাইম t-এর আগে ফেল করে, তবে কিউ থেকে ডিলিট বা পপ করা হয় এবং ডেটা স্ট্রাকচার ফিক্স করা হয় যাতে সেটি ফেইলার টাইমে আক্যুরেট হয়, এবং সার্টিফিকেট আপডেট করা হয়। এটাকে রিপিট করা হয় যতক্ষণ না প্রায়রিটি কিউতে লোয়েস্ট ফেইলার টাইমের সার্টিফিকেট টাইম t-এর পরে ফেল করে। যদি প্রায়রিটি কিউতে মিনিমাম ফেইলার টাইমের সার্টিফিকেট টাইম t-এর পরে ফেল করে, তবে সকল সার্টিফিকেট টাইম t-এ সত্য ঘোষিত হয় তাই ডেটা স্ট্রাকচার টাইম t-এ সঠিকভাবে কোয়েরি অন্সওয়ার করতে পারে।
ইভেন্টের প্রকার (Types of events)
সার্টিফিকেট ফেইলারকে "ইভেন্ট" বলা হয়। একটি ইভেন্ট ইন্টারনাল বলা হয় যদি কাইনেটিক ডেটা স্ট্রাকচার দ্বারা মেইন্টেইন করা প্রোপার্টি ইভেন্ট ঘটার সময় পরিবর্তন না হয়। একটি ইভেন্ট এক্সটার্নাল বলা হয় যদি ডেটা স্ট্রাকচার দ্বারা মেইন্টেইন করা প্রোপার্টি ইভেন্ট ঘটার সময় পরিবর্তন হয়।
পারফরম্যান্স
সার্টিফিকেট পদ্ধতি বাস্তবায়ন করার সময়, পারফরম্যান্সের চারটি মাপদণ্ড আছে। আমরা একটি কোয়ান্টিটিকে স্মল বলি যদি সেটি n-র পলিলগারিদমিক ফাংশন হয়, অথবা O(n€) যেন র্যান্ডমলি স্মল €, যেখানে n হলো অবজেক্টের সংখ্যা।
