Authors: Hiroyuki Dekihara, Ryo Furukawa, Yasuaki Nakamura
Tags: 1998, conceptual modeling
A spatio-temporal data structure, called the PMD-tree (Persistent Multi-Dimensional tree), has been proposed for managing the lice intervals and locatoins of spatial objects. The PMD-tree provides efficient spatial and temporal searches not only for the current version of the data set but also the older versions of the data set. In the paper, novel concepts of time space bounding box (TSBB) and motion list are introduced to the PMD-tree to manage moving spatial objects efficiently. TSBB is an extended bounding box for a moving object that covers the trajectory of the object. As an object moves, a TSBB corresponding to the object is enlarged to enclose hte trajectory of the object. A TSBB is divided, when it becomes greater than a limit. A relation of an object and corresponding TSBBs are managed by a doubly connected linked list, called motion list. TSBBs are also managed by the PMD-tree. When a spatial and/or temporal query is given, TSBBs that intersect with the given spatio-temporal range are found by means of the PMD-tree. Then, tracing the motion lists of the TSBBs the objects that satisfies the query can be found. Introduceing the concept of TSBB and motion list to the PMD-tree, moving objcets can be efficiently managed and be quickly found for spatio-temporal queries. By the series of simulation tests, the storage requirements and search performances are evaluated for several types of moving objects.Read the full paper here: https://link.springer.com/chapter/10.1007/978-3-540-49121-7_44
