ABSTRACT
In the external memory model, the size of the internal memory is a parameter. There are situations where the memory transfer between two levels of the memory hierarchy dominates the running time, which is often the case when the size of the data exceeds the size of main memory. An important paradigm for constructing algorithms for batched problems in an internal memory setting is to use a dynamic data structure to process a sequence of updates. Buffer trees can be used as subroutines in the standard sweep line algorithm in order to get an optimal external memory algorithm for orthogonal segment intersection. Buffer trees provide a natural amortized implementation of priority queues for application which involve time dependent processing like discrete event simulation, line sweeping, and list ranking. In the B+ tree variant, all the items are stored in the leaves, and the leaves are linked together in symmetric order to facilitate range queries and sequential access.
