एक्सटर्नल मेमोरी एल्गोरिदम: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
[[ कम्प्यूटिंग | कम्प्यूटिंग]] में, | [[ कम्प्यूटिंग | कम्प्यूटिंग]] में, '''एक्सटर्नल मेमोरी [[एल्गोरिदम]]''' या आउट-ऑफ-कोर एल्गोरिदम ऐसे एल्गोरिदम हैं जो डेटा को संसाधित करने के लिए डिज़ाइन किए गए हैं जो कंप्यूटर की मुख्य मेमोरी में फिट होने के लिए अधिक बड़े हैं। ऐसे एल्गोरिदम को स्लो बुलक मेमोरी (सहायक मेमोरी) जैसे [[हार्ड ड्राइव्ज़|हार्ड ड्राइव]] या [[टेप ड्राइव]] में संग्रहीत डेटा को कुशलतापूर्वक लाने और एक्सेस करने के लिए अनुकूलित किया जाना चाहिए, या जब मेमोरी [[ संगणक संजाल |कंप्यूटर नेटवर्क]] पर होती हैं। <ref>{{Cite journal|author=Vitter, J. S.|title=External Memory Algorithms and Data Structures: Dealing with MASSIVE DATA|journal= ACM Computing Surveys|volume= 33|issue=2|pages=209–271| year= 2001|doi=10.1145/384192.384193|citeseerx=10.1.1.42.7064|s2cid=2155038}}</ref><ref name="Vitter">{{Cite book|author=Vitter, J. S.|url=http://www.ittc.ku.edu/~jsv/Papers/Vit.IO_book.pdf|title=बाहरी मेमोरी के लिए एल्गोरिदम और डेटा संरचनाएं|journal=Foundations and Trends in Theoretical Computer Science|volume=2|issue=4|pages=305–474|series=Series on Foundations and Trends in Theoretical Computer Science|publisher=Now Publishers|location=Hanover, MA|year=2008|doi=10.1561/0400000014|isbn=978-1-60198-106-6|citeseerx=10.1.1.140.3731}}</ref> एक्सटर्नल मेमोरी एल्गोरिदम का विश्लेषण एक्सटर्नल मेमोरी मॉडल में किया जाता है। | ||
== मॉडल == | == मॉडल == | ||
[[File:External memory.svg|thumb|बायीं ओर कैश रखा हुआ है <math>\tfrac{M}{B}</math> आकार के ब्लॉक <math>B</math> प्रत्येक, कुल के लिए {{mvar|M}} वस्तुएं। दाहिनी ओर की | [[File:External memory.svg|thumb|बायीं ओर कैश रखा हुआ है <math>\tfrac{M}{B}</math> आकार के ब्लॉक <math>B</math> प्रत्येक, कुल के लिए {{mvar|M}} वस्तुएं। दाहिनी ओर की एक्सटर्नल मेमोरी असीमित है।]]एक्सटर्नल मेमोरी [[कलन विधि|एल्गोरिदम विधि]] का विश्लेषण गणना के आदर्श मॉडल में किया जाता है जिसे एक्सटर्नल मेमोरी मॉडल (या आई/ओ मॉडल, या डिस्क एक्सेस मॉडल) कहा जाता है। एक्सटर्नल मेमोरी मॉडल [[रैम मॉडल]] के समान [[अमूर्त मशीन]] है, किन्तु मुख्य मेमोरी के अतिरिक्त यह [[कैश (कंप्यूटिंग)]] के साथ होती हैं। मॉडल इस तथ्य को पकड़ता है कि मुख्य मेमोरी की तुलना में कैश (कंप्यूटिंग) में पढ़ने और लिखने का संचालन अधिक शीघ्र होता है, और [[ डिस्क पढ़ने और लिखने वाला शीर्ष |डिस्क पढ़ने और लिखने वाला शीर्ष]] का उपयोग करके यादृच्छिक रूप से पढ़ने की तुलना में (कंप्यूटर) लंबे सन्निहित ब्लॉकों को पढ़ना शीघ्रता से होता है। एक्सटर्नल मेमोरी मॉडल में एल्गोरिदम का [[ कार्यकारी समय |कार्यकारी समय]] आवश्यक मेमोरी में पढ़ने और लिखने की संख्या से परिभाषित होता है।<ref name="Springer">{{cite encyclopedia |encyclopedia= Encyclopedia of Database Systems|pages= 1333–1334|year= 2009|publisher= [[Springer Science+Business Media]]|doi= 10.1007/978-0-387-39940-9_752|last1 = Zhang|first1 = Donghui|last2= Tsotras|first2= Vassilis J.|last3= Levialdi|first3= Stefano|last4= Grinstein|first4= Georges|last5= Berry|first5= Damon Andrew|last6= Gouet-Brunet|first6= Valerie|last7= Kosch|first7= Harald|last8= Döller|first8= Mario|last9= Döller|first9= Mario|last10= Kosch|first10= Harald|last11= Maier|first11= Paul|last12= Bhattacharya|first12= Arnab|last13= Ljosa|first13= Vebjorn|last14= Nack|first14= Frank|last15= Bartolini|first15= Ilaria|last16= Gouet-Brunet|first16= Valerie|last17= Mei|first17= Tao|last18= Rui|first18= Yong|last19= Crucianu|first19= Michel|last20= Shih|first20= Frank Y.|last21= Fan|first21= Wenfei|last22= Ullman-Cullere|first22= Mollie|last23= Clark|first23= Eugene|last24= Aronson|first24= Samuel|last25= Mellin|first25= Jonas|last26= Berndtsson|first26= Mikael|last27= Grahne|first27= Gösta|last28= Bertossi|first28= Leopoldo|last29= Dong|first29= Guozhu|last30= Su|first30= Jianwen|display-authors= 29|isbn= 978-0-387-35544-3|chapter= I/O Model of Computation}}</ref> यह मॉडल 1988 में आलोक अग्रवाल और [[जेफरी विटर]] द्वारा प्रस्तुत किया गया था।<ref name="Aggarwal88">{{cite journal|last1=Aggarwal|first1=Alok|last2=Vitter|first2=Jeffrey|author2-link=Jeffrey Vitter|title=The input/output complexity of sorting and related problems|journal=[[Communications of the ACM]]|volume=31|issue=9|pages=1116–1127|date=1988|doi=10.1145/48529.48535|s2cid=6264984|url=https://hal.inria.fr/inria-00075827|doi-access=free}}</ref> एक्सटर्नल मेमोरी मॉडल कैश-ओब्लिवियस एल्गोरिथम यह आदर्शित कैश मॉडल हैं |कैश-ओब्लिवियस मॉडल से संबंधित है, किन्तु एक्सटर्नल मेमोरी मॉडल में एल्गोरिदम [[ब्लॉक (डेटा भंडारण)|ब्लॉक (डेटा संग्रहण)]] और कैश (कंप्यूटिंग) आकार दोनों को जान सकता है। इस कारण से, मॉडल को कभी-कभी कैश-अवेयर मॉडल के रूप में जाना जाता है।<ref name="Demaine02">{{cite conference|last1=Demaine|first1=Erik|author1-link=Erik Demaine|year=2002|title=कैश-ओब्लिवियस एल्गोरिदम और डेटा संरचनाएं|url=http://erikdemaine.org/papers/BRICS2002/paper.pdf|conference=Lecture Notes from the EEF Summer School on Massive Data Sets|location=Aarhus|publisher=BRICS}}</ref> | ||
मॉडल में | मॉडल में [[प्रोसेसर (कंप्यूटिंग)]] होता है जिसमें आंतरिक मेमोरी या आकार {{mvar|M}}, का कैश होता है, अनंत एक्सटर्नल मेमोरी से जुड़ा है। इसमें आंतरिक और एक्सटर्नल दोनों मेमोरी को आकार {{mvar|B }} के ब्लॉक (डेटा स्टोरेज) में विभाजित किया गया है | इनपुट/आउटपुट या मेमोरी ट्रांसफर ऑपरेशन में {{mvar|B }} सन्निहित अवयवों के ब्लॉक को एक्सटर्नल से आंतरिक मेमोरी में ले जाना सम्मिलित है, और एल्गोरिदम का चलने का समय संख्या से निर्धारित होता है यह इनपुट/आउटपुट ऑपरेशन होता हैं।<ref name="Aggarwal88"/> | ||
== एल्गोरिदम == | == एल्गोरिदम == | ||
एक्सटर्नल मेमोरी मॉडल में एल्गोरिदम इस तथ्य का लाभ उठाते हैं कि एक्सटर्नल मेमोरी से ऑब्जेक्ट को पुनर्प्राप्त करने से आकार का पूर्ण <math>B </math> ब्लॉक पुनर्प्राप्त हो जाता है | इस संपत्ति को कभी-कभी स्थानीयता भी कहा जाता है। | |||
ब्रांचिंग फैक्टर <math>B </math> के साथ [[ बी-वृक्ष |बी-ट्री]] का उपयोग करके एक्सटर्नल मेमोरी मॉडल में <math>N </math> ऑब्जेक्ट के मध्य अवयव की खोज संभव होती है। बी-ट्री का उपयोग करके, खोज, इंसर्शन और डिलेशनन को <math>O(\log _B N)</math> समय में ([[ बिग ओ अंकन |बिग ओ नोटेशन]] में) प्राप्त किया जा सकता है। [[सूचना सिद्धांत]] रूप से, यह इन परिचालनों के लिए न्यूनतम संभव समय है, इसलिए इसमें बी-ट्री का उपयोग करना असम्बद्ध रूप से इष्टतम होता है। <ref name="Aggarwal88"/> | |||
एक्सटर्नल सॉर्टिंग एक्सटर्नल मेमोरी सेटिंग में सॉर्टिंग है। एक्सटर्नल सॉर्टिंग वितरण सॉर्ट के माध्यम से की जा सकती है, जो क्विक सॉर्ट के समान होती है, यह <math>\tfrac{M}{B}</math>- [[के-वे मर्ज एल्गोरिदम|के-वे मर्ज सॉर्ट एल्गोरिदम]] के माध्यम से की जा सकती है। दोनों वेरिएंट एन ऑब्जेक्ट्स को सॉर्ट करने के लिए <math>O(\tfrac{N}{B} \log _{\tfrac{M}{B}} \tfrac{N}{B})</math> के एसिम्प्टोटिक रूप से इष्टतम रनटाइम को प्राप्त करते हैं। यह सीमा एक्सटर्नल मेमोरी मॉडल में [[फास्ट फूरियर ट्रांसफॉर्म]] पर भी प्रयुक्त होती है। <ref name="Vitter"/> | |||
क्रमपरिवर्तन समस्या | क्रमपरिवर्तन समस्या <math>N </math> तत्वों को विशिष्ट [[परिवर्तन|क्रम परिवर्तन]] में पुनर्व्यवस्थित करना है। या यह तब सॉर्टिंग द्वारा किया जा सकता है, जिसके लिए उपरोक्त सॉर्टिंग रनटाइम की आवश्यकता होती है, यह प्रत्येक अवयव को क्रम में सम्मिलित करके और स्थानीयता के लाभ को अप्रत्यक्ष करके किया जा सकता है। इस प्रकार, यह क्रमपरिवर्तन <math>O(\min (N, \tfrac{N}{B} \log _{\tfrac{M}{B}} \tfrac{N}{B}))</math> समय में किया जा सकता है। | ||
== अनुप्रयोग == | == अनुप्रयोग == | ||
एक्सटर्नल मेमोरी मॉडल मेमोरी पदानुक्रम को कैप्चर करता है, जिसे डेटा संरचनाओं का विश्लेषण करने में उपयोग किए जाने वाले अन्य सामान्य मॉडल, जैसे [[रैंडम-एक्सेस मशीन]], में मॉडल नहीं किया जाता है, और डेटा संरचनाओं के लिए निचली सीमा प्रमाणित करने के लिए उपयोगी है। यह मॉडल उन एल्गोरिदम का विश्लेषण करने के लिए भी उपयोगी होता है जो आंतरिक मेमोरी में फिट होने के लिए अधिक बड़े डेटासेट पर काम करते हैं।<ref name="Aggarwal88"/> | |||
ऐसे विशिष्ट उदाहरण [[भौगोलिक सूचना प्रणाली]] होते है, यह विशेष रूप से [[डिजिटल उन्नयन मॉडल|डिजिटल एलिवेशन मॉडल]] होते हैं, इसमें पूर्ण डेटा सेट सरलता से अनेक [[गीगाबाइट]] में होते हैं और यहां तक कि यह [[टेराबाइट|टेराबाइट्स]] डेटा से भी अधिक हो जाता है। | |||
यह कार्यप्रणाली [[सेंट्रल प्रोसेसिंग यूनिट]] से आगे तक | यह कार्यप्रणाली [[सेंट्रल प्रोसेसिंग यूनिट]] से आगे तक विस्तारित हुई है और इसमें [[ ग्राफ़िक्स प्रोसेसिंग युनिट |ग्राफ़िक्स प्रोसेसिंग यूनिट]] कंप्यूटिंग के साथ-साथ मौलिक [[ अंकीय संकेत प्रक्रिया |अंकीय संकेत प्रक्रिया]] भी सम्मिलित होती है। ग्राफिक्स प्रोसेसिंग यूनिट (जीपीजीपीयू) पर सामान्य प्रयोजन कंप्यूटिंग में, कम मेमोरी वाले शक्तिशाली ग्राफिक्स कार्ड (जीपीयू) (अधिक परिचित सिस्टम मेमोरी की तुलना में, जिसे प्रायः [[ रैंडम एक्सेस मेमोरी |रैंडम एक्सेस मेमोरी]] के रूप में संदर्भित किया जाता है) इसका उपयोग अपेक्षाकृत स्लो सीपीयू-टू-जीपीयू के साथ किया जाता है। जीपीयू मेमोरी तब ट्रांसफर की जाती हैं (जब गणना की बैंडविड्थ के साथ तुलना की जाती है)। | ||
== इतिहास == | == इतिहास == | ||
विशेषण के रूप में आउट-ऑफ-कोर शब्द का प्रारंभिक उपयोग 1962 में उन उपकरणों के संदर्भ में किया गया था जो [[आईबीएम 360]] की [[ चुंबकीय-कोर मेमोरी | | विशेषण के रूप में "आउट-ऑफ-कोर" शब्द का प्रारंभिक उपयोग 1962 में उन उपकरणों के संदर्भ में किया गया था जो [[आईबीएम 360]] की [[ चुंबकीय-कोर मेमोरी |कोर मेमोरी]] के अतिरिक्त अन्य हैं। <ref>{{cite book |author=<!--Staff writer(s); no by-line.--> |title=नासा एसपी|url=https://books.google.com/books?id=oOOj8pHh6t8C&q=%22out-of-core%22+algorithm |publisher=NASA |page=276 |date=1962}}</ref> एल्गोरिदम के संबंध में "आउट-ऑफ-कोर" शब्द का प्रारंभिक उपयोग 1971 में सामने आया था। <ref>{{cite book |title=संकट में कंप्यूटर|url=https://books.google.com/books?id=eHVQAAAAMAAJ&q=%22out-of-core%22 |publisher=ACM |page=296 |date=1971}}</ref> | ||
==यह भी देखें== | ==यह भी देखें== | ||
*[[कैश-विस्मृत एल्गोरिथ्म]] | *[[कैश-विस्मृत एल्गोरिथ्म|कैश-ओब्लिवियस एल्गोरिथ्म]] | ||
*[[बाहरी मेमोरी ग्राफ़ ट्रैवर्सल]] | *[[बाहरी मेमोरी ग्राफ़ ट्रैवर्सल|एक्सटर्नल मेमोरी ग्राफ़ ट्रैवर्सल]] | ||
*[[ऑनलाइन एल्गोरिदम]] | *[[ऑनलाइन एल्गोरिदम]] | ||
* | *पैरेलल एक्सटर्नल मेमोरी | ||
*[[स्ट्रीमिंग एल्गोरिदम]] | *[[स्ट्रीमिंग एल्गोरिदम]] | ||
| Line 39: | Line 34: | ||
== | ==एक्सटर्नल संबंध== | ||
*[http://www.tau.ac.il/~stoledo/Bib/Pubs/pp01-qr.pdf Out of Core SVD and QR] | *[http://www.tau.ac.il/~stoledo/Bib/Pubs/pp01-qr.pdf Out of Core SVD and QR] | ||
*[http://cis.poly.edu/chiang/Vis02-tutorial4.pdf Out of core graphics] | *[http://cis.poly.edu/chiang/Vis02-tutorial4.pdf Out of core graphics] | ||
Revision as of 21:11, 8 August 2023
कम्प्यूटिंग में, एक्सटर्नल मेमोरी एल्गोरिदम या आउट-ऑफ-कोर एल्गोरिदम ऐसे एल्गोरिदम हैं जो डेटा को संसाधित करने के लिए डिज़ाइन किए गए हैं जो कंप्यूटर की मुख्य मेमोरी में फिट होने के लिए अधिक बड़े हैं। ऐसे एल्गोरिदम को स्लो बुलक मेमोरी (सहायक मेमोरी) जैसे हार्ड ड्राइव या टेप ड्राइव में संग्रहीत डेटा को कुशलतापूर्वक लाने और एक्सेस करने के लिए अनुकूलित किया जाना चाहिए, या जब मेमोरी कंप्यूटर नेटवर्क पर होती हैं। [1][2] एक्सटर्नल मेमोरी एल्गोरिदम का विश्लेषण एक्सटर्नल मेमोरी मॉडल में किया जाता है।
मॉडल
एक्सटर्नल मेमोरी एल्गोरिदम विधि का विश्लेषण गणना के आदर्श मॉडल में किया जाता है जिसे एक्सटर्नल मेमोरी मॉडल (या आई/ओ मॉडल, या डिस्क एक्सेस मॉडल) कहा जाता है। एक्सटर्नल मेमोरी मॉडल रैम मॉडल के समान अमूर्त मशीन है, किन्तु मुख्य मेमोरी के अतिरिक्त यह कैश (कंप्यूटिंग) के साथ होती हैं। मॉडल इस तथ्य को पकड़ता है कि मुख्य मेमोरी की तुलना में कैश (कंप्यूटिंग) में पढ़ने और लिखने का संचालन अधिक शीघ्र होता है, और डिस्क पढ़ने और लिखने वाला शीर्ष का उपयोग करके यादृच्छिक रूप से पढ़ने की तुलना में (कंप्यूटर) लंबे सन्निहित ब्लॉकों को पढ़ना शीघ्रता से होता है। एक्सटर्नल मेमोरी मॉडल में एल्गोरिदम का कार्यकारी समय आवश्यक मेमोरी में पढ़ने और लिखने की संख्या से परिभाषित होता है।[3] यह मॉडल 1988 में आलोक अग्रवाल और जेफरी विटर द्वारा प्रस्तुत किया गया था।[4] एक्सटर्नल मेमोरी मॉडल कैश-ओब्लिवियस एल्गोरिथम यह आदर्शित कैश मॉडल हैं |कैश-ओब्लिवियस मॉडल से संबंधित है, किन्तु एक्सटर्नल मेमोरी मॉडल में एल्गोरिदम ब्लॉक (डेटा संग्रहण) और कैश (कंप्यूटिंग) आकार दोनों को जान सकता है। इस कारण से, मॉडल को कभी-कभी कैश-अवेयर मॉडल के रूप में जाना जाता है।[5]
मॉडल में प्रोसेसर (कंप्यूटिंग) होता है जिसमें आंतरिक मेमोरी या आकार M, का कैश होता है, अनंत एक्सटर्नल मेमोरी से जुड़ा है। इसमें आंतरिक और एक्सटर्नल दोनों मेमोरी को आकार B के ब्लॉक (डेटा स्टोरेज) में विभाजित किया गया है | इनपुट/आउटपुट या मेमोरी ट्रांसफर ऑपरेशन में B सन्निहित अवयवों के ब्लॉक को एक्सटर्नल से आंतरिक मेमोरी में ले जाना सम्मिलित है, और एल्गोरिदम का चलने का समय संख्या से निर्धारित होता है यह इनपुट/आउटपुट ऑपरेशन होता हैं।[4]
एल्गोरिदम
एक्सटर्नल मेमोरी मॉडल में एल्गोरिदम इस तथ्य का लाभ उठाते हैं कि एक्सटर्नल मेमोरी से ऑब्जेक्ट को पुनर्प्राप्त करने से आकार का पूर्ण ब्लॉक पुनर्प्राप्त हो जाता है | इस संपत्ति को कभी-कभी स्थानीयता भी कहा जाता है।
ब्रांचिंग फैक्टर के साथ बी-ट्री का उपयोग करके एक्सटर्नल मेमोरी मॉडल में ऑब्जेक्ट के मध्य अवयव की खोज संभव होती है। बी-ट्री का उपयोग करके, खोज, इंसर्शन और डिलेशनन को समय में (बिग ओ नोटेशन में) प्राप्त किया जा सकता है। सूचना सिद्धांत रूप से, यह इन परिचालनों के लिए न्यूनतम संभव समय है, इसलिए इसमें बी-ट्री का उपयोग करना असम्बद्ध रूप से इष्टतम होता है। [4]
एक्सटर्नल सॉर्टिंग एक्सटर्नल मेमोरी सेटिंग में सॉर्टिंग है। एक्सटर्नल सॉर्टिंग वितरण सॉर्ट के माध्यम से की जा सकती है, जो क्विक सॉर्ट के समान होती है, यह - के-वे मर्ज सॉर्ट एल्गोरिदम के माध्यम से की जा सकती है। दोनों वेरिएंट एन ऑब्जेक्ट्स को सॉर्ट करने के लिए के एसिम्प्टोटिक रूप से इष्टतम रनटाइम को प्राप्त करते हैं। यह सीमा एक्सटर्नल मेमोरी मॉडल में फास्ट फूरियर ट्रांसफॉर्म पर भी प्रयुक्त होती है। [2]
क्रमपरिवर्तन समस्या तत्वों को विशिष्ट क्रम परिवर्तन में पुनर्व्यवस्थित करना है। या यह तब सॉर्टिंग द्वारा किया जा सकता है, जिसके लिए उपरोक्त सॉर्टिंग रनटाइम की आवश्यकता होती है, यह प्रत्येक अवयव को क्रम में सम्मिलित करके और स्थानीयता के लाभ को अप्रत्यक्ष करके किया जा सकता है। इस प्रकार, यह क्रमपरिवर्तन समय में किया जा सकता है।
अनुप्रयोग
एक्सटर्नल मेमोरी मॉडल मेमोरी पदानुक्रम को कैप्चर करता है, जिसे डेटा संरचनाओं का विश्लेषण करने में उपयोग किए जाने वाले अन्य सामान्य मॉडल, जैसे रैंडम-एक्सेस मशीन, में मॉडल नहीं किया जाता है, और डेटा संरचनाओं के लिए निचली सीमा प्रमाणित करने के लिए उपयोगी है। यह मॉडल उन एल्गोरिदम का विश्लेषण करने के लिए भी उपयोगी होता है जो आंतरिक मेमोरी में फिट होने के लिए अधिक बड़े डेटासेट पर काम करते हैं।[4]
ऐसे विशिष्ट उदाहरण भौगोलिक सूचना प्रणाली होते है, यह विशेष रूप से डिजिटल एलिवेशन मॉडल होते हैं, इसमें पूर्ण डेटा सेट सरलता से अनेक गीगाबाइट में होते हैं और यहां तक कि यह टेराबाइट्स डेटा से भी अधिक हो जाता है।
यह कार्यप्रणाली सेंट्रल प्रोसेसिंग यूनिट से आगे तक विस्तारित हुई है और इसमें ग्राफ़िक्स प्रोसेसिंग यूनिट कंप्यूटिंग के साथ-साथ मौलिक अंकीय संकेत प्रक्रिया भी सम्मिलित होती है। ग्राफिक्स प्रोसेसिंग यूनिट (जीपीजीपीयू) पर सामान्य प्रयोजन कंप्यूटिंग में, कम मेमोरी वाले शक्तिशाली ग्राफिक्स कार्ड (जीपीयू) (अधिक परिचित सिस्टम मेमोरी की तुलना में, जिसे प्रायः रैंडम एक्सेस मेमोरी के रूप में संदर्भित किया जाता है) इसका उपयोग अपेक्षाकृत स्लो सीपीयू-टू-जीपीयू के साथ किया जाता है। जीपीयू मेमोरी तब ट्रांसफर की जाती हैं (जब गणना की बैंडविड्थ के साथ तुलना की जाती है)।
इतिहास
विशेषण के रूप में "आउट-ऑफ-कोर" शब्द का प्रारंभिक उपयोग 1962 में उन उपकरणों के संदर्भ में किया गया था जो आईबीएम 360 की कोर मेमोरी के अतिरिक्त अन्य हैं। [6] एल्गोरिदम के संबंध में "आउट-ऑफ-कोर" शब्द का प्रारंभिक उपयोग 1971 में सामने आया था। [7]
यह भी देखें
- कैश-ओब्लिवियस एल्गोरिथ्म
- एक्सटर्नल मेमोरी ग्राफ़ ट्रैवर्सल
- ऑनलाइन एल्गोरिदम
- पैरेलल एक्सटर्नल मेमोरी
- स्ट्रीमिंग एल्गोरिदम
संदर्भ
- ↑ Vitter, J. S. (2001). "External Memory Algorithms and Data Structures: Dealing with MASSIVE DATA". ACM Computing Surveys. 33 (2): 209–271. CiteSeerX 10.1.1.42.7064. doi:10.1145/384192.384193. S2CID 2155038.
- ↑ 2.0 2.1 Vitter, J. S. (2008). बाहरी मेमोरी के लिए एल्गोरिदम और डेटा संरचनाएं (PDF). pp. 305–474. CiteSeerX 10.1.1.140.3731. doi:10.1561/0400000014. ISBN 978-1-60198-106-6.
{{cite book}}:|journal=ignored (help) - ↑ Zhang, Donghui; Tsotras, Vassilis J.; Levialdi, Stefano; Grinstein, Georges; Berry, Damon Andrew; Gouet-Brunet, Valerie; Kosch, Harald; Döller, Mario; Döller, Mario; Kosch, Harald; Maier, Paul; Bhattacharya, Arnab; Ljosa, Vebjorn; Nack, Frank; Bartolini, Ilaria; Gouet-Brunet, Valerie; Mei, Tao; Rui, Yong; Crucianu, Michel; Shih, Frank Y.; Fan, Wenfei; Ullman-Cullere, Mollie; Clark, Eugene; Aronson, Samuel; Mellin, Jonas; Berndtsson, Mikael; Grahne, Gösta; Bertossi, Leopoldo; Dong, Guozhu; et al. (2009). "I/O Model of Computation". Encyclopedia of Database Systems. Springer Science+Business Media. pp. 1333–1334. doi:10.1007/978-0-387-39940-9_752. ISBN 978-0-387-35544-3.
- ↑ 4.0 4.1 4.2 4.3 Aggarwal, Alok; Vitter, Jeffrey (1988). "The input/output complexity of sorting and related problems". Communications of the ACM. 31 (9): 1116–1127. doi:10.1145/48529.48535. S2CID 6264984.
- ↑ Demaine, Erik (2002). कैश-ओब्लिवियस एल्गोरिदम और डेटा संरचनाएं (PDF). Lecture Notes from the EEF Summer School on Massive Data Sets. Aarhus: BRICS.
- ↑ नासा एसपी. NASA. 1962. p. 276.
- ↑ संकट में कंप्यूटर. ACM. 1971. p. 296.
