| Article ID: | iaor20117043 |
| Volume: | 36 |
| Issue: | 4 |
| Start Page Number: | 343 |
| End Page Number: | 359 |
| Publication Date: | Aug 2003 |
| Journal: | Algorithmica |
| Authors: | Chin Francis Y L, Ting Hing-Fung, Wun-Tat Chan |
| Keywords: | combinatorial optimization |
We present a technique for designing external memory data structures that support batched operations I/ O efficiently. We show how the technique can be used to develop external versions of a search tree, a priority queue, and a segment tree, and give examples of how these structures can be used to develop I/ O‐efficient algorithms. The developed algorithms are either extremely simple or straightforward generalizations of known internal memory algorithms–given the developed external data structures.