Multidimensional Data Structures: Review and Outlook

This chapter presents simple and efficiently balanced multidimensional tree structures that are useful for real-time applications. It also describes balanced multidimensional and weighted trees as well as their applications in physical database organization, information retrieval, and computational geometry problems. The performance of a multidimensional data structure is measured in terms of three quantities—the preprocessing cost, the storage cost, and the access cost. The multidimensional data structures, such as the k-d trees, quadtrees, and range trees, are comparison-based data structures. Weighted trees and multidimensional trees are related to each other. One can start from an efficient weighted one-dimensional tree structure and use it for constructing efficient multidimensional or even efficient weighted multidimensional tree structures by using it appropriately for implementing nodes of TRIES. Balanced multidimensional and weighted trees have applications in areas, such as physical database organization, information retrieval, self-organizing file structures, and computational geometry.