मूल अवधारणा (Basic Concept)
काइनेटिक डेटा स्ट्रक्चर को एक ऐसे डेटा स्ट्रक्चर के रूप में परिभाषित किया जाता है जिसे लगातार गतिमान ज्यामितीय प्रणाली (Geometric System) के एक गुण को ट्रैक करने के लिए लागू किया जाता है। उदाहरण के लिए, एक काइनेटिक कन्वेक्स हल (Kinetic Convex Hull) डेटा स्ट्रक्चर n गतिमान बिंदुओं के समूह के कन्वेक्स हल को ट्रैक करता है।
काइनेटिक डेटा स्ट्रक्चर्स का विकास कम्प्यूटेशनल ज्योमेट्री (Computational Geometry) समस्याओं से प्रेरित था जिनमें निरंतर गति में भौतिक वस्तुएं शामिल होती हैं, उदाहरण के लिए रोबोटिक्स, एनिमेशन या कंप्यूटर ग्राफिक्स में टकराव (Collision) या दृश्यता पहचान (Visibility Detection)।
अवलोकन (Overview)
काइनेटिक डेटा स्ट्रक्चर्स उन प्रणालियों पर लागू होते हैं जहां मानों का एक समूह समय के फलन के रूप में बदल रहा होता है, एक ज्ञात फैशन (Known Fashion) में। इसलिए प्रणाली के कुछ मान हैं, और प्रत्येक प्रणाली मान v के लिए, यह दर्शाता है कि v = f(t)। काइनेटिक डेटा स्ट्रक्चर्स वर्तमान वर्चुअल समय t पर प्रणाली पर क्वेरी की अनुमति देते हैं, और दो अतिरिक्त ऑपरेशन्स:
- advance(t): प्रणाली को समय t तक आगे बढ़ाया जाता है।
- change(v, f(t)): वर्तमान समय के अनुसार मान v के प्रक्षेपवक्र (Trajectory) को f(t) में बदला जाता है।
अतिरिक्त ऑपरेशन्स समर्थित हो सकते हैं। उदाहरण के लिए, काइनेटिक डेटा स्ट्रक्चर्स अक्सर बिंदुओं के एक समूह के साथ लागू होते हैं। इस मामले में, संरचना आमतौर पर बिंदुओं को सम्मिलित (Insert) और हटाने (Delete) की अनुमति देती है।
पारंपरिक डेटा स्ट्रक्चर्स के साथ विपरीत (Contrast with Traditional Data Structures)
एक काइनेटिक डेटा स्ट्रक्चर इसमें संग्रहीत मानों को समय के साथ लगातार बदलने की अनुमति देता है। सिद्धांत रूप में, इसे बिंदुओं की स्थिति को समय के निश्चित अंतराल पर नमूना लेकर, और प्रत्येक बिंदु को एक "स्थैतिक" (पारंपरिक) डेटा स्ट्रक्चर में हटाकर और पुनः सम्मिलित करके अनुमानित किया जा सकता है। हालांकि, ऐसा दृष्टिकोण ओवरसैंपलिंग या अंडरसैंपलिंग के लिए अतिसंवेदनशील होता है, यह इस बात पर निर्भर करता है कि किस समय अंतराल को लागू किया जाता है, और कम्प्यूटेशनल संसाधनों की बर्बादी भी हो सकती है।
सर्टिफिकेट दृष्टिकोण (Certificates Approach)
काइनेटिक डेटा स्ट्रक्चर्स बनाने के लिए निम्न सामान्य दृष्टिकोण लागू किया जा सकता है:
- वर्तमान समय t पर प्रणाली पर एक डेटा स्ट्रक्चर संग्रहीत किया जाता है। यह डेटा स्ट्रक्चर वर्तमान वर्चुअल समय पर प्रणाली पर क्वेरी की अनुमति देता है।
- डेटा स्ट्रक्चर को सर्टिफिकेट्स (Certificates) के साथ संवर्धित (Augmented) किया जाता है। सर्टिफिकेट्स को उन शर्तों के रूप में माना जाता है जिनके तहत डेटा स्ट्रक्चर सटीक होता है। सर्टिफिकेट्स अभी सभी सत्य हैं, और डेटा स्ट्रक्चर केवल तभी सटीक होना बंद होगा जब सर्टिफिकेट्स में से कोई एक सत्य नहीं रहेगा।
- प्रत्येक सर्टिफिकेट का विफलता समय (Failure Time) 계산 किया जाता है, वह समय जब यह सत्य नहीं रहेगा।
- सर्टिफिकेट्स को उनकी विफलता समय के अनुसार की-ड (Keyed) करके प्रायोरिटी क्यू (Priority Queue) में संग्रहीत किया जाता है।
- समय t तक आगे बढ़ने के लिए, प्रायोरिटी क्यू से न्यूनतम विफलता समय वाले सर्टिफिकेट को देखें। यदि सर्टिफिकेट समय t से पहले विफल होता है, तो इसे क्यू से हटाएं या पॉप करें और डेटा स्ट्रक्चर को ठीक करें ताकि यह विफलता के समय सटीक हो, और सर्टिफिकेट्स को अपडेट करें। इसे तब तक दोहराएं जब तक कि प्रायोरिटी क्यू में सबसे कम विफलता समय वाला सर्टिफिकेट समय t के बाद विफल न हो। यदि प्रायोरिटी क्यू में न्यूनतम विफलता समय वाला सर्टिफिकेट समय t के बाद विफल होता है, तो सभी सर्टिफिकेट्स को समय t पर सत्य घोषित किया जाता है ताकि डेटा स्ट्रक्चर समय t पर क्वेरी का सही उत्तर दे सके।
घटनाओं के प्रकार (Types of Events)
सर्टिफिकेट विफलताओं को "इवेंट्स" (Events) कहा जाता है। एक इवेंट को आंतरिक (Internal) घोषित किया जाता है यदि काइनेटिक डेटा स्ट्रक्चर द्वारा बनाए रखा गया गुण इवेंट के घटित होने के समय नहीं बदलता। एक इवेंट को बाह्य (External) घोषित किया जाता है यदि डेटा स्ट्रक्चर द्वारा बनाए रखा गया गुण इवेंट के घटित होने के समय बदलता है।
प्रदर्शन (Performance)
सर्टिफिकेट दृष्टिकोण लागू करते समय, प्रदर्शन के चार माप होते हैं। हम एक मात्रा को छोटा कहते हैं यदि यह n का पॉलीलॉगरिदमिक फंक्शन (Polylogarithmic Function) है, या यादृच्छिक रूप से छोटे ε के लिए O(n^ε) है, जहां n को वस्तुओं की संख्या माना जाता है।
