The multidimensional persistent tree: A spatiotemporal data management structure suitable for spatial search
Teruhiko Teraoka, Minoru Maruyama, Y. Nakamura, Shogo Nishida · Systems and Computers in Japan · 1996
Abstract Multidimensional data structures have been proposed for management of spatial data including points, lines, and regions. Concomitantly, more research on temporal databases as a way to handle temporal information is needed. Although the management of spatiotemporal data becomes increasingly important in geographic information systems and computer‐aided design, these data structures cannot manage spatiotemporal data efficiently. In this paper, the MP‐tree (multidimensional persistent tree) is proposed for handling multidimensional data with insertion/deletion version without the loss of efficiency of a spatial search. The MP‐tree is developed by extending conventional spatial data structure using techniques of Persistent Search Tree. The advantages and disadvantages of conventional methods with respect to both search and memory efficiency are discussed. Finally, using computer simulations, the MP‐tree is shown to have better performances for both range search and spatiotemporal search.