Among the various types of spatio-temporal queries, the most common ones involve window queries in time. In particular, timestamp (or timeslice) queries retrieve all the objects that intersect a window at a specific timestamp. Interval queries include multiple consecutive timestamps. Although several indexes have been developed for either type, currently there does not exist a structure that can efficiently process both query types. This is a significant problem due to the fundamental importance of these queries in any spatio-temporal system that deals with historical information retrieval. Our paper addresses the problem by proposing the MV3R-tree, a structure that utilizes the concepts of multi-version B-trees and 3D R-trees. Extensive experimentation proves that MV3R-trees compare favorably with specialized structures aimed at timestamp and interval window queries, both in terms of time and space requirements.
展开▼
