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

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

उदाहरण

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

L₁ = 24, 64, 65, 80, 93

L₂ = 23, 25, 26

L₃ = 13, 44, 62, 66

L₄ = 11, 35, 46, 79, 81

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

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

L = '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]

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

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

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

M₁ = 24 [0, 1], 25 [1, 1], 35 [1, 3], 64 [1, 5], 65 [2, 5], 79 [3, 5], 80 [3, 6], 93 [4, 6]

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

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

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

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

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

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

सामान्यतः, M_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),$

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

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

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

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

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

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

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

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

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

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

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

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

अनुप्रयोग

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

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

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

कम्प्यूटेशनल ज्यामिति से परे, लक्ष्मण & स्टिलियाडिस (1998) और बुद्धिकोट, सूरी & वाल्डवोगेल (1999) इंटरनेट राउटर में तेज़ पैकेट फिल्टर के लिए डेटा संरचनाओं के डिज़ाइन में आंशिक कैस्केडिंग प्रयुक्त करें। गाओ 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.