Prof. Jeff Vitter
Duke University and INRIA Sophia Antipolis
Title: Online Geometric Data Structures in External Memory
Abstract. The data sets for many of today's geometric applications are too large to fit within the computer's internal memory and must instead be stored on external storage devices such as disks. A major performance bottleneck can be the input/output communication (or~I/O) between the external and internal memories. In this talk we discuss a variety of online data structures for geometric problems in external memory---some very old and some very new---such as B-trees (for dictionaries and 1-D range search), buffer trees (for batched dynamic problems), interval trees with weight-balanced B-trees (for stabbing queries), priority search trees (for 3-sided 2-D range search), and R-trees and other spatial structures. We also discuss several open problems along the way.