THE MULTIDIMENSIONAL PERSISTENT TREE - A SPATIOTEMPORAL DATA MANAGEMENT STRUCTURE SUITABLE FOR SPATIAL SEARCH

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 informatio n is needed. Although the management of spatiotemporal data becomes in creasingly important in geographic information systems and computer-ai ded design, these data structures cannot manage spatiotemporal data ef ficiently. In this paper, the MP-tree (multidimensional persistent tre e) is proposed for handling multidimensional data with insertion/delet ion version without the loss of efficiency of a spatial search. The MP -tree is developed by extending conventional spatial data structure us ing techniques of Persistent Search Tree. The advantages and disadvant ages of conventional methods with respect to both search and memory ef ficiency are discussed. Finally, using computer simulations, the MP-tr ee is shown to have better performances for both range search and spat iotemporal search.