आंशिक कैस्केडिंग

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

उदाहरण

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

एल₁ = 24, 64, 65, 80, 93

एल₂ = 23, 25, 26

एल₃ = 13, 44, 62, 66

एल₄ = 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] = 64, एल₂[3] (एक ध्वज मान दर्शाता है कि क्यू एल के अंत से पहले है₂), एल₃[2] = 62, और एल₄[3] = 79। चुकीं, यह समाधान अंतरिक्ष जटिलता में एक उच्च जुर्माना देता है: यह अंतरिक्ष ओ (केएन) का उपयोग करता है क्योंकि एल में प्रत्येक एन आइटम को के खोज परिणामों की एक सूची संग्रहित करनी चाहिए।

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

भिन्नात्मक कैस्केडिंग समाधान ऍम सूचियों के एक नए अनुक्रम को संग्रहीत करना है_i. इसी क्रम में अंतिम सूची, एम_के, एल के बराबर है_के; प्रत्येक पूर्व सूची एम_iएल को मिलाकर बनता है_iएम से हर दूसरे सामान के साथ_i+1. इस सम्मिलित की गई सूची में प्रत्येक आइटम एक्स के साथ, हम दो संख्याएँ संग्रहीत करते हैं: एल_i में एक्स की खोज से उत्पन्न होने वाली स्थिति_iऔर ऍम_i+1 में एक्स की खोज से उत्पन्न स्थिति_i+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]

एम₂ = 23[0, 1], 25[1, 1], 26[2, 1], 35[3, 1], 62[3, 3], 79[3, 5]

एम₃ = 13[0, 1], 35[1, 1], 44[1, 2], 62[2, 3], 66[3, 3], 79[4, 3]

एम₄ = 11[0, 0], 35[1, 0], 46[2, 0], 79[3, 0], 81[4, 0]

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

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

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

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

$|L_{i}|+{\frac {1}{2}}|L_{i+1}|+{\frac {1}{4}}|L_{i+2}|+\cdots +{\frac {1}{2^{j}}}|L_{i+j}|+\cdots ,$

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

$\sum |M_{i}|=\sum |L_{i}|\left(1+{\frac {1}{2}}+{\frac {1}{4}}+\cdots \right)\leq 2n=O(n),$

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

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

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

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

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

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

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

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

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

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

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

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

अनुप्रयोग

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

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

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

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

संदर्भ

• Atallah, Mikhail J.; Blanton, Marina; Goodrich, Michael T.; Polu, Stanislas (2007), "Discrepancy-sensitive dynamic fractional cascading, dominated maxima searching, and 2-d nearest neighbors in any Minkowski metric" (PDF), Algorithms and Data Structures, 10th International Workshop, WADS 2007, Lecture Notes in Computer Science, vol. 4619, Springer-Verlag, pp. 114–126, arXiv:0904.4670, doi:10.1007/978-3-540-73951-7_11, ISBN 978-3-540-73948-7, S2CID 2590335.
• Buddhikot, Milind M.; Suri, Subhash; Waldvogel, Marcel (1999), "Space Decomposition Techniques for Fast Layer-4 Switching" (PDF), Proceedings of the IFIP TC6 WG6.1 & WG6.4 / IEEE ComSoc TC on Gigabit Networking Sixth International Workshop on Protocols for High Speed Networks VI, pp. 25–42, archived from the original (PDF) on 2004-10-20.
• Chazelle, Bernard (1983), "Filtering search: A new approach to query-answering" (PDF), Proc. 24 IEEE FOCS.
• Chazelle, Bernard (1985), "On the convex layers of a point set" (PDF), IEEE Transactions on Information Theory, 31 (4): 509–517, CiteSeerX 10.1.1.113.8709, doi:10.1109/TIT.1985.1057060.
• Chazelle, Bernard; Guibas, Leonidas J. (1986), "Fractional cascading: I. A data structuring technique" (PDF), Algorithmica, 1 (1–4): 133–162, doi:10.1007/BF01840440, S2CID 12745042.
• Chazelle, Bernard; Guibas, Leonidas J. (1986), "Fractional cascading: II. Applications" (PDF), Algorithmica, 1 (1–4): 163–191, doi:10.1007/BF01840441, S2CID 11232235.
• Chazelle, Bernard; Liu, Ding (2004), "Lower bounds for intersection searching and fractional cascading in higher dimension" (PDF), Journal of Computer and System Sciences, 68 (2): 269–284, CiteSeerX 10.1.1.298.7772, doi:10.1016/j.jcss.2003.07.003.
• Dietz, F. Paul (1982), "Maintaining order in a linked list", 14th ACM Symp. Theory of Computing, pp. 122–127, doi:10.1145/800070.802184, ISBN 978-0-89791-070-5, S2CID 24008786.
• Edelsbrunner, H.; Guibas, L. J.; Stolfi, J. (1986), "Optimal point location in a monotone subdivision" (PDF), SIAM Journal on Computing, 15 (1): 317–340, doi:10.1137/0215023.
• Gao, J.; Guibas, L. J.; Hershberger, J.; Zhang, L. (2004), "Fractionally cascaded information in a sensor network" (PDF), Proc. of the 3rd International Symposium on Information Processing in Sensor Networks (IPSN'04), pp. 311–319, doi:10.1145/984622.984668, ISBN 978-1-58113-846-7, S2CID 1033287.
• JaJa, Joseph F.; Shi, Qingmin (2003), Fast fractional cascading and its applications (PDF), Univ. of Maryland, Tech. Report UMIACS-TR-2003-71.
• Lakshman, T. V.; Stiliadis, D. (1998), "High-speed policy-based packet forwarding using efficient multi-dimensional range matching", Proceedings of the ACM SIGCOMM '98 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, pp. 203–214, CiteSeerX 10.1.1.39.697, doi:10.1145/285237.285283, ISBN 978-1-58113-003-4, S2CID 15363397.
• Lueker, George S. (1978), "A data structure for orthogonal range queries", Proc. 19th Symp. Foundations of Computer Science, IEEE, pp. 28–34, doi:10.1109/SFCS.1978.1, S2CID 14970942.
• Mehlhorn, Kurt; Näher, Stefan (1990), "Dynamic fractional cascading", Algorithmica, 5 (1): 215–241, doi:10.1007/BF01840386, S2CID 7721690.
• Sen, S. D. (1995), "Fractional cascading revisited", Journal of Algorithms, 19 (2): 161–172, doi:10.1006/jagm.1995.1032.
• Willard, D. E. (1978), Predicate-oriented database search algorithms, Ph.D. thesis, Harvard University.
• Yap, Chee; Zhu, Yunyue (2001), "Yet another look at fractional cascading: B-graphs with application to point location", Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pp. 173–176.