आंशिक कैस्केडिंग: Difference between revisions

From Vigyanwiki
No edit summary
Line 59: Line 59:


== अनुप्रयोग ==
== अनुप्रयोग ==
[[File:Convex layers halfspace.svg|thumb|200px|पॉइंट सेट की उत्तल परतें, हाफ-प्लेन रेंज रिपोर्टिंग के लिए एक कुशल आंशिक रूप से कैस्केड डेटा संरचना का हिस्सा।]]आंशिक कैस्केडिंग के विशिष्ट अनुप्रयोगों में [[कम्प्यूटेशनल ज्यामिति]] में [[रेंज खोज]] डेटा स्ट्रक्चर सम्मिलित हैं। उदाहरण के लिए, [[आधा विमान]] [[रेंज रिपोर्टिंग]] की समस्या पर विचार करें: यानी, आधे-प्लेन क्वेरी के साथ एन बिंदुओं के एक निश्चित सेट को इंटरसेक्ट करना और इंटरसेक्शन में सभी बिंदुओं को सूचीबद्ध करना। समस्या इस तरह से बिंदुओं की संरचना करना है कि चौराहे के आकार एच के संदर्भ में इस प्रकार की एक क्वेरी का कुशलतापूर्वक उत्तर दिया जा सके। इस प्रयोजन के लिए उपयोग की जा सकने वाली एक संरचना इनपुट बिंदु सेट की [[उत्तल परतें]] हैं, नेस्टेड [[उत्तल बहुभुज]]ों का एक परिवार जिसमें बिंदु सेट का उत्तल पतवार और शेष बिंदुओं की पुनरावर्ती-निर्मित उत्तल परतें सम्मिलित हैं। एक एकल परत के भीतर, उत्तल बहुभुज किनारे ढलानों के क्रमबद्ध अनुक्रम के बीच अर्ध-समतल सीमा रेखा के ढलान के लिए एक द्विआधारी खोज करके क्वेरी हाफ-प्लेन के अंदर के बिंदुओं को पाया जा सकता है, जो कि पॉलीगॉन वर्टेक्स की ओर जाता है जो क्वेरी हाफ के अंदर है। -प्लेन और इसकी सीमा से सबसे दूर, और फिर बहुभुज किनारों के साथ अनु[[क्रमिक खोज]] क्वेरी हाफ-प्लेन के अंदर अन्य सभी कोने खोजने के लिए। पूरी हाफ-प्लेन रेंज रिपोर्टिंग समस्या को इस खोज प्रक्रिया को सबसे बाहरी परत से प्रारंभ करके और अंदर की ओर तब तक जारी रखते हुए हल किया जा सकता है जब तक कि क्वेरी आधे स्थान से अलग न हो जाए। आंशिक कैस्केडिंग प्रत्येक परत में बहुभुज किनारे ढलानों के अनुक्रमों के बीच लगातार बाइनरी खोजों को गति देता है, जिससे अंतरिक्ष ओ(एन) और क्वेरी समय ओ(log एन + h) के साथ इस समस्या के लिए एक डेटा संरचना बनती है। डेटा संरचना का निर्माण समय ओ(एन log एन) के एल्गोरिदम द्वारा किया जा सकता है {{harvtxt|Chazelle|1985}}. जैसा कि हमारे उदाहरण में, इस एप्लिकेशन में सूचियों के रैखिक अनुक्रम (उत्तल परतों का नेस्टेड अनुक्रम) में बाइनरी खोज सम्मिलित है, इसलिए सूची ग्राफ़ केवल एक पथ है।
[[File:Convex layers halfspace.svg|thumb|200px|पॉइंट सेट की उत्तल परतें, हाफ-प्लेन रेंज रिपोर्टिंग के लिए एक कुशल आंशिक रूप से कैस्केड डेटा संरचना का हिस्सा।]]आंशिक कैस्केडिंग के विशिष्ट अनुप्रयोगों में [[कम्प्यूटेशनल ज्यामिति]] में [[रेंज खोज]] डेटा संरचना सम्मिलित हैं। उदाहरण के लिए, [[आधा विमान]] [[रेंज रिपोर्टिंग]] की समस्या पर विचार करें: यानी, आधे-प्लेन क्वेरी के साथ एन बिंदुओं के एक निश्चित सेट को इंटरसेक्ट करना और चौराहे में सभी बिंदुओं को सूचीबद्ध करना। समस्या इस तरह से बिंदुओं की संरचना करना है कि चौराहे के आकार एच के संदर्भ में इस प्रकार की एक क्वेरी का कुशलतापूर्वक उत्तर दिया जा सके। इस प्रयोजन के लिए उपयोग की जा सकने वाली एक संरचना इनपुट बिंदु सेट की [[उत्तल परतें]] हैं, नेस्टेड [[उत्तल बहुभुज]]ों का एक परिवार जिसमें बिंदु सेट का उत्तल पतवार और शेष बिंदुओं की पुनरावर्ती-निर्मित उत्तल परतें सम्मिलित हैं। एक एकल परत के भीतर, उत्तल बहुभुज किनारे ढलानों के क्रमबद्ध अनुक्रम के बीच अर्ध-समतल सीमा रेखा के ढलान के लिए एक द्विआधारी खोज करके क्वेरी हाफ-प्लेन के अंदर के बिंदुओं को पाया जा सकता है, जो कि पॉलीगॉन वर्टेक्स की ओर जाता है जो क्वेरी हाफ के अंदर है। -प्लेन और इसकी सीमा से सबसे दूर, और फिर बहुभुज किनारों के साथ अनु[[क्रमिक खोज]] क्वेरी हाफ-प्लेन के अंदर अन्य सभी कोने खोजने के लिए। पूरी हाफ-प्लेन रेंज रिपोर्टिंग समस्या को इस खोज प्रक्रिया को सबसे बाहरी परत से प्रारंभ करके और अंदर की ओर तब तक जारी रखते हुए हल किया जा सकता है जब तक कि क्वेरी आधे स्थान से अलग न हो जाए। आंशिक कैस्केडिंग प्रत्येक परत में बहुभुज किनारे ढलानों के अनुक्रमों के बीच निरंतर बाइनरी खोजों को गति देता है, जिससे अंतरिक्ष ओ(एन) और क्वेरी समय ओ(लाग एन + एच) के साथ इस समस्या के लिए एक डेटा संरचना बनती है। डेटा संरचना का निर्माण समय ओ(एन लाग एन) के एल्गोरिदम द्वारा किया जा सकता है {{harvtxt|चेज़ेल
|1985}}. जैसा कि हमारे उदाहरण में, इस एप्लिकेशन में सूचियों के रैखिक अनुक्रम (उत्तल परतों का नेस्टेड अनुक्रम) में बाइनरी खोज सम्मिलित है, इसलिए सूची ग्राफ़ केवल एक पथ है।


ज्यामितीय डेटा संरचनाओं में भिन्नात्मक कैस्केडिंग का एक अन्य अनुप्रयोग एक मोनोटोन उपखंड में [[बिंदु स्थान]] से संबंधित है, अर्थात, बहुभुज में विमान का एक विभाजन जैसे कि कोई भी ऊर्ध्वाधर रेखा किसी भी बहुभुज को अधिकतम दो बिंदुओं पर काटती है। जैसा {{harvtxt|Edelsbrunner|Guibas|Stolfi|1986}} दिखाया गया है, इस समस्या को बहुभुज पथों के अनुक्रम को ढूंढकर हल किया जा सकता है जो उपखंड में बाएं से दाएं तक फैला हुआ है, और बाइनरी इन पथों में से सबसे कम खोजता है जो क्वेरी बिंदु से ऊपर है। यह परीक्षण करना कि क्या क्वेरी बिंदु पथों में से किसी एक के ऊपर या नीचे है, को बाइनरी खोज समस्या के रूप में हल किया जा सकता है, पथ के कोने के एक्स निर्देशांक के बीच बिंदुओं के एक्स निर्देशांक की खोज करके यह निर्धारित किया जा सकता है कि कौन सा पथ किनारा ऊपर या नीचे हो सकता है प्रश्न बिंदु। इस प्रकार, प्रत्येक बिंदु स्थान क्वेरी को पथों के बीच बाइनरी खोज की बाहरी परत के रूप में हल किया जा सकता है, जिनमें से प्रत्येक चरण स्वयं एक्स निर्देशांक के बीच एक बाइनरी खोज करता है। आंशिक कैस्केडिंग का उपयोग आंतरिक बाइनरी खोजों के लिए समय को गति देने के लिए किया जा सकता है, ओ(एन) स्थान के साथ डेटा संरचना का उपयोग करके प्रति क्वेरी कुल समय को घटाकर ओ(log एन) कर दिया जाता है। इस एप्लिकेशन में सूची ग्राफ़ बाहरी बाइनरी खोज के संभावित खोज अनुक्रमों का प्रतिनिधित्व करने वाला एक पेड़ है।
ज्यामितीय डेटा संरचनाओं में भिन्नात्मक कैस्केडिंग का एक अन्य अनुप्रयोग एक मोनोटोन उपखंड में [[बिंदु स्थान]] से संबंधित है, अर्थात, बहुभुज में विमान का एक विभाजन जैसे कि कोई भी ऊर्ध्वाधर रेखा किसी भी बहुभुज को अधिकतम दो बिंदुओं पर काटती है। जैसा {{harvtxt|एडल्सब्रूनर|गुइबास|स्टोल्फी|1986}} दिखाया गया है, इस समस्या को बहुभुज पथों के अनुक्रम को ढूंढकर हल किया जा सकता है जो उपखंड में बाएं से दाएं तक फैला हुआ है, और बाइनरी इन पथों में से सबसे कम खोजता है जो क्वेरी बिंदु से ऊपर है। यह परीक्षण करना कि क्या क्वेरी बिंदु पथों में से किसी एक के ऊपर या नीचे है, को बाइनरी खोज समस्या के रूप में हल किया जा सकता है, पथ के कोने के एक्स निर्देशांक के बीच बिंदुओं के एक्स निर्देशांक की खोज करके यह निर्धारित किया जा सकता है कि कौन सा पथ किनारा ऊपर या नीचे हो सकता है प्रश्न बिंदु। इस प्रकार, प्रत्येक बिंदु स्थान क्वेरी को पथों के बीच बाइनरी खोज की बाहरी परत के रूप में हल किया जा सकता है, जिनमें से प्रत्येक चरण स्वयं एक्स निर्देशांक के बीच एक बाइनरी खोज करता है। आंशिक कैस्केडिंग का उपयोग आंतरिक बाइनरी खोजों के लिए समय को गति देने के लिए किया जा सकता है, ओ(एन) स्थान के साथ डेटा संरचना का उपयोग करके प्रति क्वेरी कुल समय को घटाकर ओ(लाग एन) कर दिया जाता है। इस एप्लिकेशन में सूची ग्राफ़ बाहरी बाइनरी खोज के संभावित खोज अनुक्रमों का प्रतिनिधित्व करने वाला एक पेड़ है।


कम्प्यूटेशनल ज्यामिति से परे, {{harvtxt|Lakshman|Stiliadis|1998}} और {{harvtxt|Buddhikot|Suri|Waldvogel|1999}} [[इंटरनेट राउटर]]्स में तेज़ [[पैकेट फिल्टर]] के लिए डेटा संरचनाओं के डिज़ाइन में भिन्नात्मक कैस्केडिंग लागू करें। {{harvtxt|Gao|Guibas|Hershberger|Zhang|2004}} [[सेंसर नेटवर्क]] में डेटा वितरण और पुनर्प्राप्ति के लिए एक मॉडल के रूप में भिन्नात्मक कैस्केडिंग का उपयोग करें।
कम्प्यूटेशनल ज्यामिति से परे, {{harvtxt|लक्ष्मण|स्टिलियाडिस|1998}} और {{harvtxt|बुद्धिकोट|सूरी|वाल्डवोगेल|1999}} [[इंटरनेट राउटर]]्स में तेज़ [[पैकेट फिल्टर]] के लिए डेटा संरचनाओं के डिज़ाइन में भिन्नात्मक कैस्केडिंग प्रयुक्त करें। {{harvtxt|गाओ|गुइबास|हर्शबर्गर|Zhang|2004}} [[सेंसर नेटवर्क]] में डेटा वितरण और पुनर्प्राप्ति के लिए एक मॉडल के रूप में भिन्नात्मक कैस्केडिंग का उपयोग करें।


==संदर्भ==
==संदर्भ==

Revision as of 17:42, 2 March 2023

कंप्यूटर विज्ञान में, भिन्नात्मक कैस्केडिंग संबंधित डेटा संरचनाओं के अनुक्रम में समान मान के लिए बाइनरी खोजों के अनुक्रम को गति देने की एक तकनीक है। अनुक्रम में पहली बाइनरी खोज में लॉगरिदमिक समय लगता है, जैसा कि बाइनरी खोजों के लिए मानक है, लेकिन अनुक्रम में क्रमिक खोजें तेज़ होती हैं। आंशिक कैस्केडिंग का मूल संस्करण, 1986 में बर्नार्ड चाज़ेल और लियोनिदास जे. गुइबास द्वारा दो पत्रों में प्रस्तुत किया गया (चेज़ेल, गुइबास & 1986ए; चेज़ेल, गुइबास & 1986बी), की डेटा संरचनाओं की श्रेणी खोज में उत्पन्न, कैस्केडिंग के विचार को संयुक्त किया ल्यूकर (1978) और विलार्ड (1978), आंशिक नमूनाकरण के विचार के साथ, जिसकी उत्पत्ति हुई थी चेज़ेल (1983). बाद के लेखकों ने आंशिक कैस्केडिंग के अधिक जटिल रूपों को प्रस्तुत किया जो असतत सम्मिलन और विलोपन घटनाओं के अनुक्रम द्वारा डेटा परिवर्तन के रूप में डेटा संरचना को बनाए रखने की अनुमति देता है।

उदाहरण

भिन्नात्मक कैस्केडिंग के सरल उदाहरण के रूप में, निम्न समस्या पर विचार करें। हमें इनपुट के रूप में के आदेशित सूचियों एलi का संग्रह दिया गया है i संख्याओं की, जैसे कि कुल लंबाई Σ|एलi| सभी सूचियों की संख्या एन है, और उन्हें संसाधित करना चाहिए ताकि हम प्रत्येक के सूचियों में क्वेरी मान क्यू के लिए बाइनरी खोज कर सकें। उदाहरण के लिए, के = 4 और एन = 17 के साथ,

एल1 = 24, 64, 65, 80, 93
एल2 = 23, 25, 26
एल3 = 13, 44, 62, 66
एल4 = 11, 35, 46, 79, 81

इस खोज समस्या का सबसे सरल समाधान केवल प्रत्येक सूची को अलग-अलग संग्रहीत करना है। यदि हम ऐसा करते हैं, तो स्थान की आवश्यकता ओ(एन) है, लेकिन क्वेरी करने का समय ओ(के लाग(एन/के)) है, क्योंकि हमें प्रत्येक के सूचियों में एक अलग बाइनरी खोज करनी होगी। इस संरचना को क्वेरी करने का सबसे खराब स्थिति तब होता है जब प्रत्येक के सूची का आकार एन/के के बराबर होता है, इसलिए क्वेरी में सम्मिलित प्रत्येक के बाइनरी खोज में ओ(लाग(एन/के)) समय लगता है।

एक दूसरा समाधान अधिक स्थान की कीमत पर तेजी से पूछताछ की अनुमति देता है: हम सभी के सूचियों को एक बड़ी सूची एल में सम्मिलित कर सकते हैं, और एल के प्रत्येक आइटम एक्स के साथ प्रत्येक छोटी सूची में एक्स की खोज के परिणामों की एक सूची संबद्ध कर सकते हैं। एलi. यदि हम इस सम्मिलित की गई सूची के एक तत्व का वर्णन एक्स [ए बी सी डी] के रूप में करते हैं, जहां एक्स संख्यात्मक मान है और ए बी सी, और डी अगले तत्व की स्थिति है (पहली संख्या की स्थिति 0 है) प्रत्येक मूल इनपुट सूची में कम से कम एक्स जितना बड़ा (या सूची के अंत के बाद की स्थिति यदि ऐसा कोई तत्व उपस्थित नहीं है), तो हमारे पास होगा

एल = '11' [0,0,0,0], '13' [0,0,0,1], '23' [0,0,1,1], '24' [0,1, 1,1], '25' [1,1,1,1], '26' [1,2,1,1],
'35'[1,3,1,1], '44'[1,3,1,2], '46'[1,3,2,2], '62'[1,3,2 ,3], '64'[1,3,3,3], '65'[2,3,3,3],
'66'[3,3,3,3], '79'[3,3,4,3], '80'[3,3,4,4], '81'[4,3,4 ,4], '93'[4,3,4,5]

यह विलय किया गया समाधान ओ(लाग एन+के) समय में एक क्वेरी की अनुमति देता है: बस एल में क्यू की खोज करें और फिर इस खोज द्वारा प्राप्त आइटम एक्स पर संग्रहीत परिणामों की विवरण करें। उदाहरण के लिए, यदि क्यू = 50, एल में क्यू की खोज करने पर आइटम 62 [1,3,2,3] मिलता है, जिससे हम परिणाम एल लौटाते हैं1 [1] = 64, एल2[3] (एक ध्वज मान दर्शाता है कि क्यू एल के अंत से पहले है2), एल3[2] = 62, और एल4[3] = 79। चुकीं, यह समाधान अंतरिक्ष जटिलता में एक उच्च जुर्माना देता है: यह अंतरिक्ष ओ (केएन) का उपयोग करता है क्योंकि एल में प्रत्येक एन आइटम को के खोज परिणामों की एक सूची संग्रहित करनी चाहिए।

आंशिक कैस्केडिंग इसी खोज समस्या को समय और स्थान की सीमाओं के साथ हल करने की अनुमति देता है जो दोनों दुनिया के सर्वश्रेष्ठ को पूरा करता है: क्वेरी समय ओ(लाग एन+के), और स्थान ओ(एन)।

भिन्नात्मक कैस्केडिंग समाधान ऍम सूचियों के एक नए अनुक्रम को संग्रहीत करना हैi. इसी क्रम में अंतिम सूची, एमके, एल के बराबर हैके; प्रत्येक पूर्व सूची एमiएल को मिलाकर बनता हैiएम से हर दूसरे सामान के साथi+1. इस सम्मिलित की गई सूची में प्रत्येक आइटम एक्स के साथ, हम दो संख्याएँ संग्रहीत करते हैं: एलi में एक्स की खोज से उत्पन्न होने वाली स्थितिiऔर ऍमi+1 में एक्स की खोज से उत्पन्न स्थितिi+1. उपरोक्त डेटा के लिए, यह हमें निम्नलिखित सूचियाँ देगा:

एम1 = 24 [0, 1], 25 [1, 1], 35 [1, 3], 64 [1, 5], 65 [2, 5], 79 [3, 5], 80 [3, 6], 93 [4, 6]
एम2 = 23[0, 1], 25[1, 1], 26[2, 1], 35[3, 1], 62[3, 3], 79[3, 5]
एम3 = 13[0, 1], 35[1, 1], 44[1, 2], 62[2, 3], 66[3, 3], 79[4, 3]
एम4 = 11[0, 0], 35[1, 0], 46[2, 0], 79[3, 0], 81[4, 0]

मान लीजिए कि हम इस संरचना में क्यू = 50 के लिए एक क्वेरी करना चाहते हैं। हम पहले एम में क्यू के लिए एक मानक बाइनरी खोज करते हैं।1, मान 64 [1,5] ढूँढना। 64[1,5] में 1, हमें बताता है कि एल1 में क्यू की खोज1 एल1[1] = 64 वापस करना चाहिए1[1] = 64। 64 में 5 [1,5] हमें बताता है कि एम2 में क्यू की अनुमानित स्थिति2 स्थिति 5 है। अधिक सही रूप से, एम2 में क्यू के लिए द्विआधारी खोज2 स्थिति 5 पर या तो मान 79[3,5] लौटाएगा, या मान 62[3,3] एक स्थान पहले लौटाएगा। क्यू की तुलना 62 से करके, और यह देखते हुए कि यह छोटा है, हम यह निर्धारित करते हैं कि एम2 में सही खोज परिणाम है2 62 [3,3] है। 62[3,3] में पहला 3 हमें बताता है कि एल2 में क्यू की खोज2 एल2[3] वापस करना चाहिए2[3], एक ध्वज मान जिसका अर्थ है कि क्यू सूची एल2 के अंत से पहले है2. 62 [3,3] में दूसरा 3 हमें बताता है कि एम3 में क्यू का अनुमानित स्थान3 स्थिति 3 है। अधिक सटीक रूप से, एम3 में क्यू के लिए द्विआधारी खोज3 स्थिति 3 पर या तो मान 62[2,3] लौटाएगा, या मान 44[1,2] एक स्थान पहले लौटाएगा। छोटे मान 44 के साथ क्यू की तुलना से हमें पता चलता है कि एम3 में सही खोज परिणाम3 62 [2,3] है। 62 में 2[2,3] हमें बताता है कि एल3 में क्यू की खोज3 एल3[2]= 62 वापस करना चाहिए3[2] = 62, और 3 में 62 [2,3] हमें बताता है कि एम4 में क्यू की खोज का परिणाम4 या तो एम4[3] = 79 [3,0] है4[3] = 79 [3,0] या एम4[2] = 46 [2,0]; क्यू की तुलना 46 से करने पर पता चलता है कि सही परिणाम 79[3,0] है और एल4 में क्यू की खोज का परिणाम है4 एल4[3] है4[3] = 79। इस प्रकार, हमने अपनी चार सूचियों में से प्रत्येक में क्यू पाया है, एकल सूची एम1 में एक द्विआधारी खोज करके बाद की प्रत्येक सूची में एक ही तुलना के बाद होते है।

अधिक सामान्यतः, इस प्रकार की किसी भी डेटा संरचना के लिए, हम एम1 में क्यू के लिए बाइनरी खोज करके एक क्वेरी करते हैं1, और परिणामी मूल्य से एल में क्यू1 की स्थिति का निर्धारण1. फिर, प्रत्येक i> 1 के लिए, हम एमi+1 में क्यू की ज्ञात स्थिति का उपयोग करते हैंiएमi+1. में अपनी स्थिति खोजने के लिएi+1. एम में क्यू की स्थिति से जुड़ा मानi एमi+1 में एक स्थिति की ओर इशारा करता हैi+1 यह एमi+1 में क्यू के लिए द्विआधारी खोज का सही परिणाम हैi+1 या उस सही परिणाम से एक कदम दूर है, इसलिए i से i + 1 तक जाने के लिए केवल एक ही तुलना की आवश्यकता है। इस प्रकार, एक क्वेरी के लिए कुल समय ओ(लाग एन + के) है।

हमारे उदाहरण में, आंशिक रूप से कैस्केड सूचियों में कुल 25 तत्व हैं, जो मूल इनपुट के दोगुने से भी कम है।

सामान्यतः, एम का आकारiइस डेटा संरचना में अधिकतम है

जैसा कि प्रेरण द्वारा आसानी से सिद्ध किया जा सकता है। इसलिए, डेटा संरचना का कुल आकार अधिकतम है

जैसा कि समान इनपुट सूची एल से आने वाले कुल आकार में योगदानों को पुनर्समूहित करके देखा जा सकता हैiएक दूसरे के साथ।

सामान्य समस्या

सामान्यतः, भिन्नात्मक कैस्केडिंग एक सूची ग्राफ़ के साथ प्रारंभ होती है, एक निर्देशित ग्राफ़ जिसमें प्रत्येक वर्टेक्स (ग्राफ़ थ्योरी) को एक आदेशित सूची के साथ लेबल किया जाता है। इस डेटा संरचना में एक क्वेरी में ग्राफ़ में एक पथ (ग्राफ़ सिद्धांत) और एक क्वेरी मान क्यू होता है; डेटा संरचना को पथ के शीर्ष से जुड़ी प्रत्येक आदेशित सूची में क्यू की स्थिति निर्धारित करनी चाहिए। उपरोक्त सरल उदाहरण के लिए, सूची ग्राफ़ अपने आप में एक पथ है, जिसमें केवल चार नोड हैं। पथ के पिछले भागों में खोजों द्वारा प्राप्त परिणामों के उत्तर में, किसी क्वेरी के भाग के रूप में गतिशील रूप से निर्धारित किए जाने वाले पथ के बाद के शीर्षों के लिए यह संभव है।

इस प्रकार के प्रश्नों को संभालने के लिए, एक ग्राफ़ के लिए जिसमें प्रत्येक शीर्ष पर कुछ निरंतर डी के लिए अधिकतम डी आवक और अधिकांश डी जावक किनारे हैं, प्रत्येक शीर्ष से जुड़ी सूचियों को प्रत्येक बहिर्गामी पड़ोसी से वस्तु के एक अंश द्वारा संवर्धित किया जाता है। शिखर; अंश को 1/डी से छोटा चुना जाना चाहिए, ताकि कुल राशि जिसके द्वारा सभी सूचियों को बढ़ाया जाता है, इनपुट आकार में रैखिक बनी रहे। प्रत्येक संवर्धित सूची में प्रत्येक आइटम अपने साथ उस आइटम की स्थिति को उसी शीर्ष पर संग्रहीत असंवर्धित सूची में और प्रत्येक आउटगोइंग पड़ोसी सूची में संग्रहीत करता है। उपरोक्त सरल उदाहरण में, डी = 1, और हमने प्रत्येक सूची को पड़ोसी वस्तुओं के 1/2 अंश के साथ बढ़ाया।

इस डेटा संरचना में एक क्वेरी में पथ के प्रत्येक क्रमिक शीर्ष पर सरल खोजों के साथ, क्वेरी पथ के पहले शीर्ष से जुड़ी संवर्धित सूची में एक मानक बाइनरी खोज सम्मिलित है। यदि प्रत्येक पड़ोसी आइटम से सूचियों को बढ़ाने के लिए आइटम का 1/आर अंश उपयोग किया जाता है, तो प्रत्येक क्रमिक क्वेरी परिणाम पिछले पथ शीर्ष से क्वेरी परिणाम में संग्रहीत स्थिति के अधिकांश आर चरणों में पाया जा सकता है, और इसलिए हो सकता है पूर्ण बाइनरी खोज किए बिना निरंतर समय में मिला।

डायनेमिक आंशिक कैस्केडिंग

डायनेमिक आंशिक कैस्केडिंग में, सूची ग्राफ़ के प्रत्येक नोड पर संग्रहीत सूची गतिशील रूप से बदल सकती है, अद्यतनों के एक क्रम से जिसमें सूची वस्तु सम्मिलित और हटाए जाते हैं। यह डेटा संरचना के लिए कई कठिनाइयों का कारण बनता है।

सबसे पहले, जब कोई आइटम सूची ग्राफ़ के नोड में डाला या हटाया जाता है, तो उसे उस नोड से जुड़ी संवर्धित सूची में रखा जाना चाहिए, और सूची ग्राफ़ के अन्य नोड्स में परिवर्तन का कारण हो सकता है। सरणियों में संवर्धित सूचियों को संग्रहीत करने के अतिरिक्त, उन्हें बाइनरी सर्च बी-वृक्ष के रूप में संग्रहीत किया जाना चाहिए, ताकि संवर्धित सूचियों की बाइनरी खोजों की अनुमति देते हुए इन परिवर्तनों को कुशलता से नियंत्रित किया जा सके।

दूसरा, एक सम्मिलन या विलोपन एक नोड से जुड़ी सूची के सबसेट में परिवर्तन का कारण हो सकता है जो कि सूची ग्राफ के पड़ोसी नोड्स को दिया जाता है। यह संभव नहीं है, गतिशील सेटिंग में, इस उपसमुच्चय को सूची के प्रत्येक डीटीएच स्थान पर आइटम के रूप में चुना जाना चाहिए, कुछ डी के लिए, क्योंकि यह उपसमुच्चय हर अद्यतन के बाद बहुत अधिक बदल जाएगा। इसके अतिरिक्त, बी-पेड़ से निकटता से संबंधित एक तकनीक डेटा के एक अंश के चयन की अनुमति देती है जो 1/डी से कम होने की गारंटी है, साथ ही चयनित आइटमों को पूरी सूची में अलग-अलग पदों की निरंतर संख्या के स्थान की गारंटी दी जाती है, और इस तरह कि एक नोड से जुड़ी संवर्धित सूची में एक सम्मिलन या विलोपन 1 / d से कम के संचालन के एक अंश के लिए अन्य नोड्स में प्रचार करने के लिए परिवर्तन का कारण बनता है। इस तरह, नोड्स के बीच डेटा का वितरण क्वेरी एल्गोरिदम के तेज होने के लिए आवश्यक गुणों को संतुष्ट करता है, जबकि यह गारंटी देता है कि प्रति डेटा प्रविष्टि या विलोपन में बाइनरी सर्च ट्री संचालन की औसत संख्या स्थिर है।

तीसरा, और सबसे गंभीर रूप से, स्थिर भिन्नात्मक कैस्केडिंग डेटा संरचना, सूची ग्राफ़ के प्रत्येक नोड पर संवर्धित सूची के प्रत्येक तत्व एक्स के लिए, उस नोड से इनपुट आइटम के बीच एक्स की खोज करते समय प्राप्त होने वाले परिणाम का सूचकांक बनाए रखता है। और संवर्धित सूचियों के बीच पड़ोसी नोड्स पर संग्रहीत। चुकीं, गतिशील सेटिंग में बनाए रखने के लिए यह जानकारी बहुत महंगी होगी। एकल मान एक्स डालने या हटाने से अन्य मानों की असीमित संख्या में संग्रहीत अनुक्रमणिकाएँ बदल सकती हैं। इसके अतिरिक्त, आंशिक कैस्केडिंग के गतिशील संस्करण प्रत्येक नोड के लिए कई डेटा संरचनाएं बनाए रखते हैं:

  • छोटे पूर्णांकों के लिए नोड की संवर्धित सूची में वस्तुओं की मैपिंग, जैसे कि संवर्धित सूची में पदों का क्रम पूर्णांकों के तुलनात्मक क्रम के बराबर है, और इन पूर्णांकों से सूची वस्तुओं पर वापस एक रिवर्स मैप . की एक तकनीक डिट्ज़ (1982) इस नंबरिंग को कुशलतापूर्वक बनाए रखने की अनुमति देता है।
  • नोड की इनपुट सूची से जुड़ी संख्याओं के लिए एक पूर्णांक खोज डेटा संरचना जैसे वैन एम्डे बोस कदम इस संरचना के साथ, और आइटम से पूर्णांक तक मैपिंग, कोई भी संवर्धित सूची के प्रत्येक तत्व एक्स के लिए कुशलता से खोज सकता है, वह आइटम जो इनपुट सूची में एक्स की खोज करने पर मिलेगा।
  • सूची ग्राफ में प्रत्येक पड़ोसी नोड के लिए, पड़ोसी नोड से प्रचारित डेटा के सबसेट से जुड़े नंबरों के लिए एक समान पूर्णांक खोज डेटा संरचना। इस संरचना के साथ, और वस्तुओं से पूर्णांक तक मानचित्रण, कोई भी संवर्धित सूची के प्रत्येक तत्व एक्स के लिए कुशलता से खोज सकता है, पड़ोसी नोड से जुड़ी संवर्धित सूची में एक्स के स्थान के निरंतर चरणों के भीतर एक स्थिति।

ये डेटा संरचनाएं डायनेमिक आंशिक कैस्केडिंग को ओ (लॉग एन) प्रति सम्मिलन या विलोपन के समय पर निष्पादित करने की अनुमति देती हैं, और समय ओ (लॉग एन) में किए जाने वाले सूची ग्राफ में लंबाई के पथ के बाद के बाइनरी खोजों का अनुक्रम + के लॉग लॉग एन)।

अनुप्रयोग

पॉइंट सेट की उत्तल परतें, हाफ-प्लेन रेंज रिपोर्टिंग के लिए एक कुशल आंशिक रूप से कैस्केड डेटा संरचना का हिस्सा।

आंशिक कैस्केडिंग के विशिष्ट अनुप्रयोगों में कम्प्यूटेशनल ज्यामिति में रेंज खोज डेटा संरचना सम्मिलित हैं। उदाहरण के लिए, आधा विमान रेंज रिपोर्टिंग की समस्या पर विचार करें: यानी, आधे-प्लेन क्वेरी के साथ एन बिंदुओं के एक निश्चित सेट को इंटरसेक्ट करना और चौराहे में सभी बिंदुओं को सूचीबद्ध करना। समस्या इस तरह से बिंदुओं की संरचना करना है कि चौराहे के आकार एच के संदर्भ में इस प्रकार की एक क्वेरी का कुशलतापूर्वक उत्तर दिया जा सके। इस प्रयोजन के लिए उपयोग की जा सकने वाली एक संरचना इनपुट बिंदु सेट की उत्तल परतें हैं, नेस्टेड उत्तल बहुभुजों का एक परिवार जिसमें बिंदु सेट का उत्तल पतवार और शेष बिंदुओं की पुनरावर्ती-निर्मित उत्तल परतें सम्मिलित हैं। एक एकल परत के भीतर, उत्तल बहुभुज किनारे ढलानों के क्रमबद्ध अनुक्रम के बीच अर्ध-समतल सीमा रेखा के ढलान के लिए एक द्विआधारी खोज करके क्वेरी हाफ-प्लेन के अंदर के बिंदुओं को पाया जा सकता है, जो कि पॉलीगॉन वर्टेक्स की ओर जाता है जो क्वेरी हाफ के अंदर है। -प्लेन और इसकी सीमा से सबसे दूर, और फिर बहुभुज किनारों के साथ अनुक्रमिक खोज क्वेरी हाफ-प्लेन के अंदर अन्य सभी कोने खोजने के लिए। पूरी हाफ-प्लेन रेंज रिपोर्टिंग समस्या को इस खोज प्रक्रिया को सबसे बाहरी परत से प्रारंभ करके और अंदर की ओर तब तक जारी रखते हुए हल किया जा सकता है जब तक कि क्वेरी आधे स्थान से अलग न हो जाए। आंशिक कैस्केडिंग प्रत्येक परत में बहुभुज किनारे ढलानों के अनुक्रमों के बीच निरंतर बाइनरी खोजों को गति देता है, जिससे अंतरिक्ष ओ(एन) और क्वेरी समय ओ(लाग एन + एच) के साथ इस समस्या के लिए एक डेटा संरचना बनती है। डेटा संरचना का निर्माण समय ओ(एन लाग एन) के एल्गोरिदम द्वारा किया जा सकता है चेज़ेल (1985). जैसा कि हमारे उदाहरण में, इस एप्लिकेशन में सूचियों के रैखिक अनुक्रम (उत्तल परतों का नेस्टेड अनुक्रम) में बाइनरी खोज सम्मिलित है, इसलिए सूची ग्राफ़ केवल एक पथ है।

ज्यामितीय डेटा संरचनाओं में भिन्नात्मक कैस्केडिंग का एक अन्य अनुप्रयोग एक मोनोटोन उपखंड में बिंदु स्थान से संबंधित है, अर्थात, बहुभुज में विमान का एक विभाजन जैसे कि कोई भी ऊर्ध्वाधर रेखा किसी भी बहुभुज को अधिकतम दो बिंदुओं पर काटती है। जैसा एडल्सब्रूनर, गुइबास & स्टोल्फी (1986) दिखाया गया है, इस समस्या को बहुभुज पथों के अनुक्रम को ढूंढकर हल किया जा सकता है जो उपखंड में बाएं से दाएं तक फैला हुआ है, और बाइनरी इन पथों में से सबसे कम खोजता है जो क्वेरी बिंदु से ऊपर है। यह परीक्षण करना कि क्या क्वेरी बिंदु पथों में से किसी एक के ऊपर या नीचे है, को बाइनरी खोज समस्या के रूप में हल किया जा सकता है, पथ के कोने के एक्स निर्देशांक के बीच बिंदुओं के एक्स निर्देशांक की खोज करके यह निर्धारित किया जा सकता है कि कौन सा पथ किनारा ऊपर या नीचे हो सकता है प्रश्न बिंदु। इस प्रकार, प्रत्येक बिंदु स्थान क्वेरी को पथों के बीच बाइनरी खोज की बाहरी परत के रूप में हल किया जा सकता है, जिनमें से प्रत्येक चरण स्वयं एक्स निर्देशांक के बीच एक बाइनरी खोज करता है। आंशिक कैस्केडिंग का उपयोग आंतरिक बाइनरी खोजों के लिए समय को गति देने के लिए किया जा सकता है, ओ(एन) स्थान के साथ डेटा संरचना का उपयोग करके प्रति क्वेरी कुल समय को घटाकर ओ(लाग एन) कर दिया जाता है। इस एप्लिकेशन में सूची ग्राफ़ बाहरी बाइनरी खोज के संभावित खोज अनुक्रमों का प्रतिनिधित्व करने वाला एक पेड़ है।

कम्प्यूटेशनल ज्यामिति से परे, लक्ष्मण & स्टिलियाडिस (1998) और बुद्धिकोट, सूरी & वाल्डवोगेल (1999) इंटरनेट राउटर्स में तेज़ पैकेट फिल्टर के लिए डेटा संरचनाओं के डिज़ाइन में भिन्नात्मक कैस्केडिंग प्रयुक्त करें। गाओ et al. (2004) सेंसर नेटवर्क में डेटा वितरण और पुनर्प्राप्ति के लिए एक मॉडल के रूप में भिन्नात्मक कैस्केडिंग का उपयोग करें।

संदर्भ