External Geometric Data Structures

Many modern applications store and process datasets much larger than the main memory of even state-of-the-art high-end machines. Thus massive and dynamically changing datasets often need to be stored in space efficient data structures on external storage devices such as disks, and in such cases the Input/Output (or I/O) communication between internal and external memory can become a major performance bottleneck. Many massive dataset applications involve geometric data (for example, points, lines, and polygons) or data that can be interpreted geometrically. Such applications often perform queries that correspond to searching in massive multidimensional geometric databases for objects that satisfy certain spatial constraints. Typical queries include reporting the objects intersecting a query region, reporting the objects containing a query point, and reporting objects near a query point.While development of practically efficient (and ideally also multi-purpose) external memory data structures (indexes) has always been a main concern in the database community, most data structure research in the algorithms community has focused on worst-case efficient internal memory data structures. Recently however, there has been some cross-fertilization between the two areas. In this talk we discuss some of the recent advances in the development of dynamic and worst-case efficient external memory geometric data structures. We focus on fundamental structures for important one- and two-dimensional range searching related problems, and try to highlight some of the fundamental techniques used to develop such structures. More comprehensive surveys of external data structure results, as well as external memory algorithms, can e.g. be found in [1-3].