फ्यूज़न ट्री

कंप्यूटर विज्ञान में, फ़्यूज़न ट्री एक प्रकार की ट्री डेटा संरचना है जो एक सहयोगी सरणी को लागू करती है w-एक परिमित ब्रह्मांड पर बिट पूर्णांक, जहां प्रत्येक इनपुट पूर्णांक का आकार 2 से कम है^wऔर गैर-नकारात्मक है। के संग्रह पर कार्य करते समय n विशेषता-मूल्य युग्म|कुंजी-मूल्य युग्म, यह उपयोग करता है O(n) स्थान और उसमें खोज करता है O(log_w n) समय, जो कि पारंपरिक स्व-संतुलन द्विआधारी खोज वृक्ष की तुलना में तेज है, और बड़े मूल्यों के लिए वैन एम्डे बोस कदम से भी बेहतर है।w. यह कुछ स्थिर-समय के संचालन का उपयोग करके इस गति को प्राप्त करता है जो एक मशीन शब्द पर किया जा सकता है। फ़्यूज़न पेड़ों का आविष्कार 1990 में माइकल फ्रेडमैन और डैन विलार्ड द्वारा किया गया था। फ्रेडमैन और विलार्ड के मूल 1990 पेपर के बाद से कई प्रगति हुई है। 1999 में यह दिखाया गया कि गणना के एक मॉडल के तहत फ़्यूज़न पेड़ों को कैसे कार्यान्वित किया जाए जिसमें एल्गोरिदम के सभी अंतर्निहित संचालन AC0|AC से संबंधित हों⁰, सर्किट जटिलता का एक मॉडल जो जोड़ और बिटवाइज़ बूलियन संचालन की अनुमति देता है लेकिन मूल फ़्यूज़न ट्री एल्गोरिदम में उपयोग किए जाने वाले गुणन संचालन की अनुमति नहीं देता है। हैश तालिकाओं का उपयोग करके फ़्यूज़न पेड़ों का एक गतिशील संस्करण 1996 में प्रस्तावित किया गया था जो मूल संरचना से मेल खाता था O(log_w n) अपेक्षा में रनटाइम। घातीय वृक्ष का उपयोग करने वाला एक और गतिशील संस्करण 2007 में प्रस्तावित किया गया था जो सबसे खराब स्थिति वाले रनटाइम उत्पन्न करता है O(log_w n + log log n) प्रति ऑपरेशन. अंत में, यह दिखाया गया कि गतिशील संलयन पेड़ प्रत्येक ऑपरेशन को निष्पादित कर सकते हैं O(log_w n) समय निश्चित रूप से। यह डेटा संरचना किसी दी गई कुंजी के लिए कुंजी जोड़ने, कुंजी हटाने, खोज कुंजी और पूर्ववर्ती (अगला छोटा मान) और उत्तराधिकारी (अगला बड़ा मान) खोज संचालन लागू करती है। निरंतर समय में सबसे महत्वपूर्ण बिट लोकेटर के आंशिक परिणाम ने भी आगे के शोध में मदद की है। फ़्यूज़न पेड़ कुशल होने के लिए शब्द-स्तरीय समानांतरवाद (कंप्यूटिंग) का उपयोग करते हैं, कुल संचालन की संख्या को कम करने के लिए एक मशीन शब्द में संग्रहीत कई छोटे पूर्णांकों पर एक साथ गणना करते हैं।

यह कैसे काम करता है

एक संलयन वृक्ष मूलतः शाखा कारक वाला एक बी-वृक्ष है w^1/5 (कोई छोटा घातांक भी संभव है क्योंकि इसका पेड़ की ऊंचाई पर बहुत अधिक प्रभाव नहीं पड़ेगा), जो इसे ऊंचाई देता है O(log_w n). अद्यतनों और प्रश्नों के लिए वांछित रनटाइम प्राप्त करने के लिए, फ़्यूज़न ट्री को तक वाले नोड को खोजने में सक्षम होना चाहिए w^1/5 निरंतर समय में कुंजियाँ। यह कुंजियों को संपीड़ित (स्केचिंग) करके किया जाता है ताकि सभी एक मशीन शब्द में फिट हो सकें, जो बदले में समानांतर में तुलना करने की अनुमति देता है। इसलिए, स्केचिंग, समानांतर तुलना और सबसे महत्वपूर्ण बिट इंडेक्स लोकेटर से जुड़ी गणनाओं की एक श्रृंखला आवश्यक समाधान तक पहुंचने में मदद करती है।

स्केचिंग

स्केचिंग वह विधि है जिसके द्वारा प्रत्येक w-बिट कुंजी एक नोड पर युक्त k कुंजियाँ केवल में संपीड़ित होती हैं k − 1 बिट्स. प्रत्येक कुंजी x को ऊंचाई के पूर्ण बाइनरी ट्री में एक पथ के रूप में सोचा जा सकता है w जड़ से शुरू होकर पत्ती पर समाप्त होता है x. इस पथ को यदि ith बिट 0 है तो i के बाएं चाइल्ड को और यदि 1 है तो राइट चाइल्ड को पुनरावर्ती रूप से खोजकर संसाधित किया जा सकता है, आम तौर पर, जब तक कि सभी बिट्स स्कैन नहीं हो जाते। दो पथों को अलग करने के लिए, उनके शाखा बिंदु (पहला बिट जहां कोई भी दो कुंजी भिन्न होती हैं) को देखना पर्याप्त है। चूँकि अधिकतम k कुंजियाँ हैं, इसलिए k-1 से अधिक शाखा बिंदु नहीं होंगे, जिसका अर्थ है कि किसी कुंजी की पहचान करने के लिए k-1 बिट्स से अधिक की आवश्यकता नहीं है। और इसलिए, किसी भी स्केच में k-1 बिट्स से अधिक नहीं होगा।

स्केच फ़ंक्शन का एक महत्वपूर्ण गुण यह है कि यह कुंजियों के क्रम को संरक्षित करता है। वह है, sketch(x) < sketch(y) किन्हीं दो कुंजियों के लिए x < y. तो, चाबियों की पूरी श्रृंखला के लिए, स्केच(x₀)<स्केच(x₁)<...<स्केच(x_k-1) क्योंकि यदि बाइनरी ट्री जैसे पथ का अनुसरण किया जाता है तो नोड्स को इस तरह से ऑर्डर किया जाएगा कि x₀<x₁<...<x_k-1.

स्केच का अनुमान लगाना

यदि स्केच बिट्स के स्थान बी हैं₁ <बी₂ < ··· < बी_r, फिर कुंजी x का स्केच_w-1···एक्स₁x₀ आर-बिट पूर्णांक है $x_{b_{r}}x_{b_{r-1}}\cdots x_{b_{1}}$.

केवल मानक शब्द संचालन, जैसे कि सी प्रोग्रामिंग भाषा, के साथ, निरंतर समय में किसी कुंजी के सही स्केच की सीधे गणना करना मुश्किल है। इसके बजाय, स्केच बिट्स को अधिकतम r आकार की श्रेणी में पैक किया जा सकता है⁴, बिटवाइज़ AND और गुणन का उपयोग करते हुए, अनुमानित स्केच कहा जाता है, जिसमें सभी महत्वपूर्ण बिट्स होते हैं लेकिन कुछ अतिरिक्त बेकार बिट्स भी एक पूर्वानुमानित पैटर्न में फैले होते हैं। बिटवाइज़ AND ऑपरेशन इन सभी गैर-स्केच बिट्स को कुंजी से हटाने के लिए एक मास्क के रूप में कार्य करता है, जबकि गुणन स्केच बिट्स को एक छोटी सीमा में स्थानांतरित करता है। पूर्ण स्केच की तरह, अनुमानित स्केच भी कुंजियों के क्रम को सुरक्षित रखता है और इसका मतलब है कि स्केच(x₀)<स्केच(x₁)<...<स्केच(x_k-1).

सही गुणन स्थिरांक निर्धारित करने के लिए कुछ पूर्वप्रक्रिया की आवश्यकता होती है। स्थान बी में प्रत्येक स्केच बिट_i बी में शिफ्ट हो जायेंगे_i + एम_i m = से गुणा करके $\textstyle \sum _{i=1}^{r}$ 2^{m_i</सुपर>. अनुमानित स्केच को कार्यान्वित करने के लिए, निम्नलिखित तीन गुण होने चाहिए:}

1. बी_i + एम_j सभी जोड़ियों (i, j) के लिए अलग-अलग हैं। इससे यह सुनिश्चित हो जाएगा कि स्केच बिट्स गुणन द्वारा दूषित नहीं हैं।
2. बी_i + एम_i i का सख्ती से बढ़ता हुआ कार्य है। अर्थात्, स्केच बिट्स का क्रम x'.m में भी संरक्षित रहता है।
3. (बी_r + एम_r) - (बी₁ + एम₁) ≤ आर⁴. अर्थात्, स्केच बिट्स को अधिकतम r आकार की श्रेणी में पैक किया जाता है⁴, जहां r ≤ O(w^1/5).

एक आगमनात्मक तर्क दिखाता है कि कैसे एम_i निर्माण किया जा सकता है. मुझे₁ = डब्ल्यू − बी₁. मान लीजिए कि 1 < t ≤ r और वह m₁, एम₂... एम_t-1 पहले ही चुना जा चुका है. फिर सबसे छोटा पूर्णांक m चुनें_t इस प्रकार कि दोनों गुण (1) और (2) संतुष्ट हैं। संपत्ति (1) के लिए आवश्यक है कि एम_t ≠ बी_i − बी_j + एम_l सभी 1 ≤ i, j ≤ r और 1 ≤ l ≤ t-1 के लिए। इस प्रकार, tr से कम हैं² ≤ आर³मूल्य जो म_t बचना चाहिए. चूंकि एम_t न्यूनतम होना चुना गया है, (बी_t + एम_t) ≤ (बी_t-1 + एम_t-1) + आर³. इसका तात्पर्य संपत्ति (3) से है।

इस प्रकार अनुमानित रेखाचित्र की गणना इस प्रकार की जाती है:

1. स्केच बिट्स को छोड़कर बाकी सभी को x और के बीच बिटवाइज़ से मास्क करें $\sum _{i=0}^{r-1}2^{b_{i}}$.
2. ऊपर की गणना के अनुसार कुंजी को पूर्व निर्धारित स्थिरांक m से गुणा करें। इस ऑपरेशन के लिए वास्तव में दो मशीनी शब्दों की आवश्यकता होती है, लेकिन यह अभी भी निरंतर समय में किया जा सकता है।
3. स्थानांतरित स्केच बिट्स को छोड़कर सभी को मास्क करें। ये अब अधिकतम r के सन्निहित ब्लॉक में समाहित हैं⁴ <w^4/5बिट्स.

समानांतर तुलना

स्केचिंग द्वारा प्राप्त संपीड़न का उद्देश्य सभी कुंजियों को एक डब्ल्यू-बिट शब्द में संग्रहीत करने की अनुमति देना है। किसी नोड का नोड स्केच बिट स्ट्रिंग होने दें

1sketch(एक्स₁)1sketch(एक्स₂)...1sketch(एक्स_k)

यहां, सभी स्केच शब्दों को उनमें से प्रत्येक के लिए एक सेट बिट जोड़कर एक स्ट्रिंग में एक साथ जोड़ा गया है। हम मान सकते हैं कि स्केच फ़ंक्शन बिल्कुल b ≤ r का उपयोग करता है⁴बिट्स. फिर प्रत्येक ब्लॉक 1 + b ≤ w का उपयोग करता है^4/5बिट्स, और चूँकि k ≤ w^1/5, नोड स्केच में बिट्स की कुल संख्या अधिकतम w है।

एक संक्षिप्त नोटेशनल एक तरफ: एक बिट स्ट्रिंग एस और गैर-नकारात्मक पूर्णांक एम के लिए, चलो एस^ms के स्वयं के साथ m बार संयोजन को दर्शाता है। यदि t एक बिट स्ट्रिंग st भी है, तो t से s के संयोजन को दर्शाता है।

नोड स्केच किसी भी बी-बिट पूर्णांक y के लिए कुंजी खोजना संभव बनाता है। मान लीजिए z = (0y)^k, जिसकी गणना स्थिर समय में की जा सकती है (y को स्थिरांक (0) से गुणा करें)।^ख1)^k), इसे नोड स्केच जितना लंबा बनाने के लिए, ताकि नोड स्केच में प्रत्येक शब्द की तुलना एक ऑपरेशन में क्वेरी पूर्णांक y के साथ की जा सके, जो शब्द-स्तरीय समानता का प्रदर्शन करता है। यदि y 5 बिट लंबा होता, तो स्केच(y) प्राप्त करने के लिए इसे 000001....000001 से गुणा किया जाता।^क. स्केच(x) के बीच का अंतर_i) और 0y के परिणामस्वरूप प्रत्येक ब्लॉक के लिए अग्रणी बिट 1 होता है, यदि और केवल यदि स्केच(y) $\leq$ स्केच(x_i). इस प्रकार हम सबसे छोटे सूचकांक i की गणना कर सकते हैं sketch(एक्स_i) ≥ y इस प्रकार है:

1. नोड स्केच से z घटाएँ।
2. अंतर और स्थिरांक का बिटवाइज़ AND लें (10^ख)^क. यह प्रत्येक ब्लॉक के अग्रणी बिट को छोड़कर बाकी सब साफ़ कर देता है।
3. क्वेरी स्केच से छोटे स्केच वाले तत्वों से क्वेरी स्केच से बड़े तत्वों में संक्रमण के सटीक सूचकांक की पहचान करने के लिए, परिणाम का सबसे महत्वपूर्ण बिट ढूंढें।
4. इस तथ्य का उपयोग करके स्केच की रैंक i की गणना करें कि i-वें ब्लॉक के अग्रणी बिट में इंडेक्स i(b+1) है।

डेस्केचिंग

एक मनमानी क्वेरी q के लिए, समानांतर तुलना सूचकांक i की गणना इस प्रकार करती है

sketch(एक्स_i-1) ≤ sketch(क्यू) ≤ sketch(एक्स_i)

दुर्भाग्य से, यह q का सटीक पूर्ववर्ती या उत्तराधिकारी नहीं देता है, क्योंकि सभी मानों के रेखाचित्रों के बीच q के रेखाचित्र का स्थान सभी वास्तविक मानों में q के स्थान के समान नहीं हो सकता है। जो सच है वह यह है कि, सभी कुंजियों में से, या तो x_i-1 या एक्स_i q के साथ सबसे लंबा सामान्य उपसर्ग है। ऐसा इसलिए है क्योंकि q के साथ लंबे सामान्य उपसर्ग वाली किसी भी कुंजी y में q के साथ समान रूप से अधिक स्केच बिट्स होंगे, और इस प्रकार sketch(y) के करीब होगा sketch(क्यू) किसी से भी ज्यादा sketch(एक्स_j).

दो डब्ल्यू-बिट पूर्णांक ए और बी के बीच लंबाई सबसे लंबे सामान्य उपसर्ग की गणना निरंतर समय में ए और बी के बीच बिटवाइज एक्सओआर के सबसे महत्वपूर्ण बिट को ढूंढकर की जा सकती है। इसके बाद इसका उपयोग सबसे लंबे सामान्य उपसर्ग को छोड़कर सभी को छिपाने के लिए किया जा सकता है।

ध्यान दें कि p सटीक रूप से पहचानता है कि कुंजियों के सेट से q शाखाएँ कहाँ निकलती हैं। यदि q का अगला बिट 0 है, तो q का उत्तराधिकारी p1 सबट्री में समाहित है, और यदि q का अगला बिट 1 है, तो q का पूर्ववर्ती p0 सबट्री में समाहित है। यह q का सटीक स्थान निर्धारित करने के लिए निम्नलिखित एल्गोरिदम का सुझाव देता है:

1. ऐसे सूचकांक को खोजने के लिए समानांतर तुलना का उपयोग करें sketch(एक्स_i-1) ≤ sketch(क्यू) ≤ sketch(एक्स_i).
2. q और x दोनों में से सबसे लंबे सामान्य उपसर्ग p की गणना करें_i-1 या एक्स_i (दोनों में से अधिक समय लेते हुए)।
3. मान लीजिए l-1 सबसे लंबे सामान्य उपसर्ग p की लंबाई है।
   1. यदि q का l-वां बिट 0 है, तो मान लीजिए e = p10 है^w-l. के उत्तराधिकारी की खोज के लिए समानांतर तुलना का उपयोग करें sketch(इ)। यह q का वास्तविक पूर्ववर्ती है।
   2. यदि q का l-वाँ बिट 1 है, तो मान लीजिए e = p01 है^w-l. के पूर्ववर्ती की खोज के लिए समानांतर तुलना का उपयोग करें sketch(इ)। यह q का वास्तविक उत्तराधिकारी है।
4. एक बार जब q का पूर्ववर्ती या उत्तराधिकारी मिल जाता है, तो कुंजियों के सेट के बीच q की सटीक स्थिति निर्धारित की जाती है।

फ्यूजन हैशिंग

हैश तालिकाओं के लिए फ़्यूज़न ट्री का एक अनुप्रयोग विलार्ड द्वारा दिया गया था, जो हैशिंग के लिए एक डेटा संरचना का वर्णन करता है जिसमें हैश चेनिंग के साथ एक बाहरी स्तर की हैश तालिका को प्रत्येक हैश श्रृंखला का प्रतिनिधित्व करने वाले फ़्यूज़न ट्री के साथ जोड़ा जाता है। हैश चेनिंग में, एक स्थिर लोड फैक्टर वाली हैश तालिका में, एक चेन का औसत आकार स्थिर होता है, लेकिन इसके अतिरिक्त उच्च संभावना के साथ सभी चेन का आकार होता है O(log n / log log n), कहाँ n हैश की गई वस्तुओं की संख्या है। इस श्रृंखला का आकार इतना छोटा है कि एक फ़्यूज़न ट्री प्रति ऑपरेशन निरंतर समय में इसके भीतर खोज और अपडेट को संभाल सकता है। इसलिए, डेटा संरचना में सभी परिचालनों का समय उच्च संभावना के साथ स्थिर है। अधिक सटीक रूप से, इस डेटा संरचना के साथ, प्रत्येक व्युत्क्रम-अर्ध-बहुपद समय संभावना के लिए p(n) = exp((log n)^O(1)), एक स्थिरांक है C जैसे कि संभावना है कि एक ऑपरेशन मौजूद है जो समय से अधिक है C अधिकतम है p(n).

कम्प्यूटेशनल मॉडल और आवश्यक धारणाएँ

फ़्यूज़न ट्री एल्गोरिदम के लिए कम्प्यूटेशनल मॉडल एक शब्द राम है जिसमें एक विशिष्ट निर्देश सेट होता है, जिसमें अंकगणितीय निर्देश शामिल होते हैं - जोड़, घटाव और गुणा (सभी निष्पादित) सापेक्ष 2^w) और बूलियन ऑपरेशन - बिटवाइज और, नहीं आदि। एक डबल-सटीक गुणन निर्देश भी शामिल है। यह दिखाया गया है बाद वाले निर्देश को हटाने से तेजी से सॉर्ट करना असंभव हो जाता है O(n log n), जब तक कि इसे लगभग मेमोरी स्पेस का उपयोग करने की अनुमति न हो 2^w शब्द (फ़्यूज़न ट्रीज़ द्वारा उपयोग किए गए रैखिक स्थान के विपरीत), या इसके बजाय अन्य निर्देश शामिल करें.

बाहरी संबंध

• MIT CS 6.897: Advanced Data Structures: Lecture 4, Fusion Trees, Prof. Erik Demaine (Spring 2003)
• MIT CS 6.897: Advanced Data Structures: Lecture 5, More fusion trees; self-organizing data structures, move-to-front, static optimality, Prof. Erik Demaine (Spring 2003)
• MIT CS 6.851: Advanced Data Structures: Lecture 13, Fusion Tree notes, Prof. Erik Demaine (Spring 2007)
• MIT CS 6.851: Advanced Data Structures: Lecture 12, Fusion Tree notes, Prof. Erik Demaine (Spring 2012)