External Memory Geometric Datastructures

Many massive dataset applications involve geometric data (or data that can be interpreted geometrically) Points, lines, polygons Data need to be stored in data structures on external storage media such that on-line queries can be answered I/O-efficiently Data often need to be maintained during dynamic updates,Data sets in large applications are often too massive to fit completely inside the computer's internal memory. The resulting input/output communication (or I/O) between fast internal memory and slower external memory (such as disks) can be a major performance bottleneck. During the last decade a major body of research has been devoted to the development of efficient external memory algorithms, where the goal is to exploit locality in order to reduce the I/O costs Examples: Phone: Wireless tracking Consumer: Buying patterns (supermarket checkout) Geography: NASA satellites generate 1.2 TB per day