SeTPR*-tree: Efficient Buffering for Spatiotemporal Indexes Via Shared Execution

In this paper, we study the problem of efficient spatiotemporal indexing of moving objects. In order to reduce the frequency of object location updates, a linear motion model is used to model the near future location of moving objects. A number of existing spatiotemporal indexes have already been proposed for indexing these models. However, these indexes are either designed to offer high query performance or high update performance. Therefore, they are all ill suited to handle situations where both queries and updates arrive at a high rate. In this paper, we propose the (STPR)-T-e*-tree which extends the TPR*-tree to more efficiently use a limited-sized RAM buffer for processing queries in batches and rapidly arriving updates. We provide both theoretical and empirical evidence of the effectiveness of the (STPR)-T-e*-tree in improving query and update performance. We have conducted extensive experiments using a recognized spatiotemporal benchmark on a solid state drive. The (STPR)-T-e*-tree simultaneously outperforms the best tested index optimized for queries by up to a factor of 5.6 for query I/O and outperforms the best tested index for updates by up to a factor of 11.5 for update I/O.