External memory algorithm - Revision history

Cornmazes at 21:20, 19 January 2025

2025-01-19T21:20:32Z

← Previous revision		Revision as of 21:20, 19 January 2025
Line 1:		Line 1:
			{{short description\|Algorithms for processing data too large to fit into a computer's main memory at once}}
	In [[computing]], '''external memory algorithms''' or '''out-of-core algorithms''' are [[algorithms]] that are designed to process data that are too large to fit into a computer's [[main memory]] at once. Such algorithms must be optimized to efficiently fetch and access data stored in slow bulk memory ([[auxiliary memory]]) such as [[hard drives]] or [[tape drives]], or when memory is on a [[computer network]].<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=Algorithms and Data Structures for External Memory\|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> External memory algorithms are analyzed in the '''external memory model'''.		In [[computing]], '''external memory algorithms''' or '''out-of-core algorithms''' are [[algorithms]] that are designed to process data that are too large to fit into a computer's [[main memory]] at once. Such algorithms must be optimized to efficiently fetch and access data stored in slow bulk memory ([[auxiliary memory]]) such as [[hard drives]] or [[tape drives]], or when memory is on a [[computer network]].<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=Algorithms and Data Structures for External Memory\|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> External memory algorithms are analyzed in the '''external memory model'''.

Headbomb: ce

2024-05-08T02:22:41Z

← Previous revision		Revision as of 02:22, 8 May 2024
Line 1:		Line 1:
	In [[computing]], '''external memory algorithms''' or '''out-of-core algorithms''' are [[algorithms]] that are designed to process data that are too large to fit into a computer's [[main memory]] at once. Such algorithms must be optimized to efficiently fetch and access data stored in slow bulk memory ([[auxiliary memory]]) such as [[hard drives]] or [[tape drives]], or when memory is on a [[computer network]].<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=Algorithms and Data Structures for External Memory\|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> External memory algorithms are analyzed in the '''external memory model'''.		In [[computing]], '''external memory algorithms''' or '''out-of-core algorithms''' are [[algorithms]] that are designed to process data that are too large to fit into a computer's [[main memory]] at once. Such algorithms must be optimized to efficiently fetch and access data stored in slow bulk memory ([[auxiliary memory]]) such as [[hard drives]] or [[tape drives]], or when memory is on a [[computer network]].<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=Algorithms and Data Structures for External Memory\|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> External memory algorithms are analyzed in the '''external memory model'''.

	== Model ==		== Model ==

Citation bot: Added journal. | Use this bot. Report bugs. | Suggested by Abductive | Category:Analysis of algorithms | #UCB_Category 42/47

2024-03-18T03:22:58Z

Added journal. | Use this bot. Report bugs. | Suggested by Abductive | Category:Analysis of algorithms | #UCB_Category 42/47

← Previous revision		Revision as of 03:22, 18 March 2024
Line 1:		Line 1:
	In [[computing]], '''external memory algorithms''' or '''out-of-core algorithms''' are [[algorithms]] that are designed to process data that are too large to fit into a computer's [[main memory]] at once. Such algorithms must be optimized to efficiently fetch and access data stored in slow bulk memory ([[auxiliary memory]]) such as [[hard drives]] or [[tape drives]], or when memory is on a [[computer network]].<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=Algorithms and Data Structures for External Memory\|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> External memory algorithms are analyzed in the '''external memory model'''.		In [[computing]], '''external memory algorithms''' or '''out-of-core algorithms''' are [[algorithms]] that are designed to process data that are too large to fit into a computer's [[main memory]] at once. Such algorithms must be optimized to efficiently fetch and access data stored in slow bulk memory ([[auxiliary memory]]) such as [[hard drives]] or [[tape drives]], or when memory is on a [[computer network]].<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=Algorithms and Data Structures for External Memory\|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> External memory algorithms are analyzed in the '''external memory model'''.

	== Model ==		== Model ==

PetraMagna: cite book should not have a journal; duplicate of series parameter

2023-11-28T01:39:04Z

cite book should not have a journal; duplicate of series parameter

← Previous revision		Revision as of 01:39, 28 November 2023
Line 1:		Line 1:
	In [[computing]], '''external memory algorithms''' or '''out-of-core algorithms''' are [[algorithms]] that are designed to process data that are too large to fit into a computer's [[main memory]] at once. Such algorithms must be optimized to efficiently fetch and access data stored in slow bulk memory ([[auxiliary memory]]) such as [[hard drives]] or [[tape drives]], or when memory is on a [[computer network]].<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=Algorithms and Data Structures for External Memory~~\|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> External memory algorithms are analyzed in the '''external memory model'''.		In [[computing]], '''external memory algorithms''' or '''out-of-core algorithms''' are [[algorithms]] that are designed to process data that are too large to fit into a computer's [[main memory]] at once. Such algorithms must be optimized to efficiently fetch and access data stored in slow bulk memory ([[auxiliary memory]]) such as [[hard drives]] or [[tape drives]], or when memory is on a [[computer network]].<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=Algorithms and Data Structures for External Memory\|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> External memory algorithms are analyzed in the '''external memory model'''.

	== Model ==		== Model ==

Cedar101: /* Algorithms */ \frac

2023-10-16T08:45:50Z

Algorithms: \frac

← Previous revision		Revision as of 08:45, 16 October 2023
Line 10:		Line 10:
	Algorithms in the external memory model take advantage of the fact that retrieving one object from external memory retrieves an entire block of size {{mvar\|B}}. This property is sometimes referred to as locality.		Algorithms in the external memory model take advantage of the fact that retrieving one object from external memory retrieves an entire block of size {{mvar\|B}}. This property is sometimes referred to as locality.

	Searching for an element among {{mvar\|N}} objects is possible in the external memory model using a [[B-tree]] with branching factor {{mvar\|B}}. Using a B-tree, searching, insertion, and deletion can be achieved in <math>O(\~~log _B~~ N)</math> time (in [[Big O notation]]). [[Information theory\|Information theoretically]], this is the minimum [[running time]] possible for these operations, so using a B-tree is [[asymptotically optimal]].<ref name="Aggarwal88"/>		Searching for an element among {{mvar\|N}} objects is possible in the external memory model using a [[B-tree]] with branching factor {{mvar\|B}}. Using a B-tree, searching, insertion, and deletion can be achieved in <math>O(\log_B N)</math> time (in [[Big O notation]]). [[Information theory\|Information theoretically]], this is the minimum [[running time]] possible for these operations, so using a B-tree is [[asymptotically optimal]].<ref name="Aggarwal88"/>

	[[External sorting]] is sorting in an external memory setting. External sorting can be done via distribution sort, which is similar to [[quicksort]], or via a <math>\tfrac{M}{B}</math>[[K-way merge algorithm\|-way merge sort]]. Both variants achieve the [[asymptotically optimal]] runtime of <math>O\left(\~~tfrac~~{N}{B} \log _{\~~tfrac~~{M}{B}} \~~tfrac~~{N}{B}\right)</math> to sort {{mvar\|N}} objects. This bound also applies to the [[fast Fourier transform]] in the external memory model.<ref name="Vitter"/>		[[External sorting]] is sorting in an external memory setting. External sorting can be done via distribution sort, which is similar to [[quicksort]], or via a <math>\tfrac{M}{B}</math>[[K-way merge algorithm\|-way merge sort]]. Both variants achieve the [[asymptotically optimal]] runtime of <math>O\left(\frac{N}{B} \log _{\frac{M}{B}} \frac{N}{B}\right)</math> to sort {{mvar\|N}} objects. This bound also applies to the [[fast Fourier transform]] in the external memory model.<ref name="Vitter"/>

	The permutation problem is to rearrange {{mvar\|N}} elements into a specific [[permutation]]. This can either be done either by sorting, which requires the above sorting runtime, or inserting each element in order and ignoring the benefit of locality. Thus, permutation can be done in <math>O\left(\min \left(N, \~~tfrac~~{N}{B} \log _{\~~tfrac~~{M}{B}} \~~tfrac~~{N}{B}\right)\right)</math> time.		The permutation problem is to rearrange {{mvar\|N}} elements into a specific [[permutation]]. This can either be done either by sorting, which requires the above sorting runtime, or inserting each element in order and ignoring the benefit of locality. Thus, permutation can be done in <math>O\left(\min \left(N, \frac{N}{B} \log _{\frac{M}{B}} \frac{N}{B}\right)\right)</math> time.

	== Applications ==		== Applications ==

Cedar101: /* Algorithms */ \left \right

2023-10-16T08:43:23Z

Algorithms: \left \right

← Previous revision		Revision as of 08:43, 16 October 2023
Line 8:		Line 8:

	== Algorithms ==		== Algorithms ==
	Algorithms in the external memory model take advantage of the fact that retrieving one object from external memory retrieves an entire block of size ~~<math>~~B~~</math>~~. This property is sometimes referred to as locality.		Algorithms in the external memory model take advantage of the fact that retrieving one object from external memory retrieves an entire block of size {{mvar\|B}}. This property is sometimes referred to as locality.

	Searching for an element among ~~<math>~~N~~</math>~~ objects is possible in the external memory model using a [[B-tree]] with branching factor ~~<math>~~B~~</math>~~. Using a B-tree, searching, insertion, and deletion can be achieved in <math>O(\log _B N)</math> time (in [[Big O notation]]). [[Information theory\|Information theoretically]], this is the minimum [[running time]] possible for these operations, so using a B-tree is [[asymptotically optimal]].<ref name="Aggarwal88"/>		Searching for an element among {{mvar\|N}} objects is possible in the external memory model using a [[B-tree]] with branching factor {{mvar\|B}}. Using a B-tree, searching, insertion, and deletion can be achieved in <math>O(\log _B N)</math> time (in [[Big O notation]]). [[Information theory\|Information theoretically]], this is the minimum [[running time]] possible for these operations, so using a B-tree is [[asymptotically optimal]].<ref name="Aggarwal88"/>

	[[External sorting]] is sorting in an external memory setting. External sorting can be done via distribution sort, which is similar to [[quicksort]], or via a <math>\tfrac{M}{B}</math>[[K-way merge algorithm\|-way merge sort]]. Both variants achieve the [[asymptotically optimal]] runtime of <math>O(\tfrac{N}{B} \log _{\tfrac{M}{B}} \tfrac{N}{B})</math> to sort {{mvar\|N}} objects. This bound also applies to the [[fast Fourier transform]] in the external memory model.<ref name="Vitter"/>		[[External sorting]] is sorting in an external memory setting. External sorting can be done via distribution sort, which is similar to [[quicksort]], or via a <math>\tfrac{M}{B}</math>[[K-way merge algorithm\|-way merge sort]]. Both variants achieve the [[asymptotically optimal]] runtime of <math>O\left(\tfrac{N}{B} \log _{\tfrac{M}{B}} \tfrac{N}{B}\right)</math> to sort {{mvar\|N}} objects. This bound also applies to the [[fast Fourier transform]] in the external memory model.<ref name="Vitter"/>

	The permutation problem is to rearrange ~~<math>~~N~~</math>~~ elements into a specific [[permutation]]. This can either be done either by sorting, which requires the above sorting runtime, or inserting each element in order and ignoring the benefit of locality. Thus, permutation can be done in <math>O(\min (N, \tfrac{N}{B} \log _{\tfrac{M}{B}} \tfrac{N}{B}))</math> time.		The permutation problem is to rearrange {{mvar\|N}} elements into a specific [[permutation]]. This can either be done either by sorting, which requires the above sorting runtime, or inserting each element in order and ignoring the benefit of locality. Thus, permutation can be done in <math>O\left(\min \left(N, \tfrac{N}{B} \log _{\tfrac{M}{B}} \tfrac{N}{B}\right)\right)</math> time.

	== Applications ==		== Applications ==

Citation bot: Add: title. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | #UCB_CommandLine

2023-09-02T13:26:41Z

Add: title. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | #UCB_CommandLine

← Previous revision		Revision as of 13:26, 2 September 2023
Line 3:		Line 3:
	== Model ==		== Model ==
	[[File:External memory.svg\|thumb\|The cache on the left holds <math>\tfrac{M}{B}</math> blocks of size <math>B</math> each, for a total of {{mvar\|M}} objects. The external memory on the right is unbounded.]]		[[File:External memory.svg\|thumb\|The cache on the left holds <math>\tfrac{M}{B}</math> blocks of size <math>B</math> each, for a total of {{mvar\|M}} objects. The external memory on the right is unbounded.]]
	External memory algorithms are analyzed in an idealized [[model of computation]] called the external memory model (or '''I/O model''', or '''disk access model'''). The external memory model is an [[abstract machine]] similar to the [[RAM model\|RAM machine model]], but with a [[Cache (computing)\|cache]] in addition to [[main memory]]. The model captures the fact that read and write operations are much faster in a [[cache (computing)\|cache]] than in [[main memory]], and that [[Reading (computer)\|reading]] long contiguous blocks is faster than reading randomly using a [[disk read-and-write head]]. The [[running time]] of an [[algorithm]] in the external memory model is defined by the number of reads and writes to memory required.<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> The model was introduced by Alok Aggarwal and [[Jeffrey Vitter]] in 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> The external memory model is related to the [[Cache-oblivious algorithm#Idealized cache model\|cache-oblivious model]], but algorithms in the external memory model may know both the [[Block (data storage)\|block size]] and the [[Cache (computing)\|cache]] size. For this reason, the model is sometimes referred to as the '''cache-aware model'''.<ref name="Demaine02">{{cite conference\|last1=Demaine\|first1=Erik\|author1-link=Erik Demaine\|year=2002\|title=Cache-Oblivious Algorithms and Data Structures\|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>		External memory algorithms are analyzed in an idealized [[model of computation]] called the external memory model (or '''I/O model''', or '''disk access model'''). The external memory model is an [[abstract machine]] similar to the [[RAM model\|RAM machine model]], but with a [[Cache (computing)\|cache]] in addition to [[main memory]]. The model captures the fact that read and write operations are much faster in a [[cache (computing)\|cache]] than in [[main memory]], and that [[Reading (computer)\|reading]] long contiguous blocks is faster than reading randomly using a [[disk read-and-write head]]. The [[running time]] of an [[algorithm]] in the external memory model is defined by the number of reads and writes to memory required.<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\|title= I/O Model of Computation\|display-authors= 29\|isbn= 978-0-387-35544-3}}</ref> The model was introduced by Alok Aggarwal and [[Jeffrey Vitter]] in 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> The external memory model is related to the [[Cache-oblivious algorithm#Idealized cache model\|cache-oblivious model]], but algorithms in the external memory model may know both the [[Block (data storage)\|block size]] and the [[Cache (computing)\|cache]] size. For this reason, the model is sometimes referred to as the '''cache-aware model'''.<ref name="Demaine02">{{cite conference\|last1=Demaine\|first1=Erik\|author1-link=Erik Demaine\|year=2002\|title=Cache-Oblivious Algorithms and Data Structures\|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>

	The model consists of a [[processor (computing)\|processor]] with an internal memory or [[cache (computing)\|cache]] of size {{mvar\|M}}, connected to an [[infinity\|unbounded]] external memory. Both the internal and external memory are divided into [[Block (data storage)\|blocks]] of size {{mvar\|B}}. One input/output or memory transfer operation consists of moving a block of {{mvar\|B}} contiguous elements from external to internal memory, and the [[running time]] of an algorithm is determined by the number of these input/output operations.<ref name="Aggarwal88"/>		The model consists of a [[processor (computing)\|processor]] with an internal memory or [[cache (computing)\|cache]] of size {{mvar\|M}}, connected to an [[infinity\|unbounded]] external memory. Both the internal and external memory are divided into [[Block (data storage)\|blocks]] of size {{mvar\|B}}. One input/output or memory transfer operation consists of moving a block of {{mvar\|B}} contiguous elements from external to internal memory, and the [[running time]] of an algorithm is determined by the number of these input/output operations.<ref name="Aggarwal88"/>

OAbot: Open access bot: doi added to citation with #oabot.

2023-01-29T04:01:22Z

Open access bot: doi added to citation with #oabot.

← Previous revision		Revision as of 04:01, 29 January 2023
Line 3:		Line 3:
	== Model ==		== Model ==
	[[File:External memory.svg\|thumb\|The cache on the left holds <math>\tfrac{M}{B}</math> blocks of size <math>B</math> each, for a total of {{mvar\|M}} objects. The external memory on the right is unbounded.]]		[[File:External memory.svg\|thumb\|The cache on the left holds <math>\tfrac{M}{B}</math> blocks of size <math>B</math> each, for a total of {{mvar\|M}} objects. The external memory on the right is unbounded.]]
	External memory algorithms are analyzed in an idealized [[model of computation]] called the external memory model (or '''I/O model''', or '''disk access model'''). The external memory model is an [[abstract machine]] similar to the [[RAM model\|RAM machine model]], but with a [[Cache (computing)\|cache]] in addition to [[main memory]]. The model captures the fact that read and write operations are much faster in a [[cache (computing)\|cache]] than in [[main memory]], and that [[Reading (computer)\|reading]] long contiguous blocks is faster than reading randomly using a [[disk read-and-write head]]. The [[running time]] of an [[algorithm]] in the external memory model is defined by the number of reads and writes to memory required.<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> The model was introduced by Alok Aggarwal and [[Jeffrey Vitter]] in 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}}</ref> The external memory model is related to the [[Cache-oblivious algorithm#Idealized cache model\|cache-oblivious model]], but algorithms in the external memory model may know both the [[Block (data storage)\|block size]] and the [[Cache (computing)\|cache]] size. For this reason, the model is sometimes referred to as the '''cache-aware model'''.<ref name="Demaine02">{{cite conference\|last1=Demaine\|first1=Erik\|author1-link=Erik Demaine\|year=2002\|title=Cache-Oblivious Algorithms and Data Structures\|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>		External memory algorithms are analyzed in an idealized [[model of computation]] called the external memory model (or '''I/O model''', or '''disk access model'''). The external memory model is an [[abstract machine]] similar to the [[RAM model\|RAM machine model]], but with a [[Cache (computing)\|cache]] in addition to [[main memory]]. The model captures the fact that read and write operations are much faster in a [[cache (computing)\|cache]] than in [[main memory]], and that [[Reading (computer)\|reading]] long contiguous blocks is faster than reading randomly using a [[disk read-and-write head]]. The [[running time]] of an [[algorithm]] in the external memory model is defined by the number of reads and writes to memory required.<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> The model was introduced by Alok Aggarwal and [[Jeffrey Vitter]] in 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> The external memory model is related to the [[Cache-oblivious algorithm#Idealized cache model\|cache-oblivious model]], but algorithms in the external memory model may know both the [[Block (data storage)\|block size]] and the [[Cache (computing)\|cache]] size. For this reason, the model is sometimes referred to as the '''cache-aware model'''.<ref name="Demaine02">{{cite conference\|last1=Demaine\|first1=Erik\|author1-link=Erik Demaine\|year=2002\|title=Cache-Oblivious Algorithms and Data Structures\|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>

	The model consists of a [[processor (computing)\|processor]] with an internal memory or [[cache (computing)\|cache]] of size {{mvar\|M}}, connected to an [[infinity\|unbounded]] external memory. Both the internal and external memory are divided into [[Block (data storage)\|blocks]] of size {{mvar\|B}}. One input/output or memory transfer operation consists of moving a block of {{mvar\|B}} contiguous elements from external to internal memory, and the [[running time]] of an algorithm is determined by the number of these input/output operations.<ref name="Aggarwal88"/>		The model consists of a [[processor (computing)\|processor]] with an internal memory or [[cache (computing)\|cache]] of size {{mvar\|M}}, connected to an [[infinity\|unbounded]] external memory. Both the internal and external memory are divided into [[Block (data storage)\|blocks]] of size {{mvar\|B}}. One input/output or memory transfer operation consists of moving a block of {{mvar\|B}} contiguous elements from external to internal memory, and the [[running time]] of an algorithm is determined by the number of these input/output operations.<ref name="Aggarwal88"/>

Voidxor: /* See also */ Rm duplicate links per MOS:DUPLINK. Alphabetize per MOS:SEEALSO.

2023-01-21T03:03:58Z

See also: Rm duplicate links per MOS:DUPLINK. Alphabetize per MOS:SEEALSO.

← Previous revision		Revision as of 03:03, 21 January 2023
Line 27:		Line 27:

	==See also==		==See also==
	*[[External sorting]]
⚫	*[[Online algorithm]]
⚫	*[[Streaming algorithm]]
	*[[Cache-oblivious algorithm]]		*[[Cache-oblivious algorithm]]
⚫	*[[Parallel external memory]]
	*[[External memory graph traversal]]		*[[External memory graph traversal]]
		⚫	*[[Online algorithm]]
		⚫	*[[Parallel external memory]]
		⚫	*[[Streaming algorithm]]

	==References==		==References==

FrederalBacon: Reverted edits by 121.200.48.26 (talk): editing tests (HG) (3.4.10)

2022-08-24T04:05:39Z

Reverted edits by 121.200.48.26 (talk): editing tests (HG) (3.4.10)

← Previous revision		Revision as of 04:05, 24 August 2022
Line 15:		Line 15:

	The permutation problem is to rearrange <math>N</math> elements into a specific [[permutation]]. This can either be done either by sorting, which requires the above sorting runtime, or inserting each element in order and ignoring the benefit of locality. Thus, permutation can be done in <math>O(\min (N, \tfrac{N}{B} \log _{\tfrac{M}{B}} \tfrac{N}{B}))</math> time.		The permutation problem is to rearrange <math>N</math> elements into a specific [[permutation]]. This can either be done either by sorting, which requires the above sorting runtime, or inserting each element in order and ignoring the benefit of locality. Thus, permutation can be done in <math>O(\min (N, \tfrac{N}{B} \log _{\tfrac{M}{B}} \tfrac{N}{B}))</math> time.

	by poornaa

	== Applications ==		== Applications ==

← Previous revision		Revision as of 08:45, 16 October 2023
Line 10:		Line 10:
	Algorithms in the external memory model take advantage of the fact that retrieving one object from external memory retrieves an entire block of size {{mvar\|B}}. This property is sometimes referred to as locality.		Algorithms in the external memory model take advantage of the fact that retrieving one object from external memory retrieves an entire block of size {{mvar\|B}}. This property is sometimes referred to as locality.

	Searching for an element among {{mvar\|N}} objects is possible in the external memory model using a [[B-tree]] with branching factor {{mvar\|B}}. Using a B-tree, searching, insertion, and deletion can be achieved in <math>O(\~~log _B~~ N)</math> time (in [[Big O notation]]). [[Information theory\|Information theoretically]], this is the minimum [[running time]] possible for these operations, so using a B-tree is [[asymptotically optimal]].<ref name="Aggarwal88"/>		Searching for an element among {{mvar\|N}} objects is possible in the external memory model using a [[B-tree]] with branching factor {{mvar\|B}}. Using a B-tree, searching, insertion, and deletion can be achieved in <math>O(\log_B N)</math> time (in [[Big O notation]]). [[Information theory\|Information theoretically]], this is the minimum [[running time]] possible for these operations, so using a B-tree is [[asymptotically optimal]].<ref name="Aggarwal88"/>

	[[External sorting]] is sorting in an external memory setting. External sorting can be done via distribution sort, which is similar to [[quicksort]], or via a <math>\tfrac{M}{B}</math>[[K-way merge algorithm\|-way merge sort]]. Both variants achieve the [[asymptotically optimal]] runtime of <math>O\left(\~~tfrac~~{N}{B} \log _{\~~tfrac~~{M}{B}} \~~tfrac~~{N}{B}\right)</math> to sort {{mvar\|N}} objects. This bound also applies to the [[fast Fourier transform]] in the external memory model.<ref name="Vitter"/>		[[External sorting]] is sorting in an external memory setting. External sorting can be done via distribution sort, which is similar to [[quicksort]], or via a <math>\tfrac{M}{B}</math>[[K-way merge algorithm\|-way merge sort]]. Both variants achieve the [[asymptotically optimal]] runtime of <math>O\left(\frac{N}{B} \log _{\frac{M}{B}} \frac{N}{B}\right)</math> to sort {{mvar\|N}} objects. This bound also applies to the [[fast Fourier transform]] in the external memory model.<ref name="Vitter"/>

	The permutation problem is to rearrange {{mvar\|N}} elements into a specific [[permutation]]. This can either be done either by sorting, which requires the above sorting runtime, or inserting each element in order and ignoring the benefit of locality. Thus, permutation can be done in <math>O\left(\min \left(N, \~~tfrac~~{N}{B} \log _{\~~tfrac~~{M}{B}} \~~tfrac~~{N}{B}\right)\right)</math> time.		The permutation problem is to rearrange {{mvar\|N}} elements into a specific [[permutation]]. This can either be done either by sorting, which requires the above sorting runtime, or inserting each element in order and ignoring the benefit of locality. Thus, permutation can be done in <math>O\left(\min \left(N, \frac{N}{B} \log _{\frac{M}{B}} \frac{N}{B}\right)\right)</math> time.

	== Applications ==		== Applications ==