Voronoi Based Spatial Query For Trajectory Data In Spatial Networks

Query processing for trajectory data is very important to spatio-temporal databases. Most of the research work in this field is based on the Euclidean space. However, in many applications, the spatio-temporal trajectories of moving objects are distributed in spatial network environment intensively, and the movements of moving objects are constrained by given network segments. Under such circumstances, existing Euclidean-based methods are ineffective. In this paper, we present a Network Voronoi Diagram (NVD) based method, to solve k nearest query and range query problem on a huge amount of spatio-temporal trajectories in spatial networks. The basic idea is space partition. A large network space is partitioned into many small cells. So, for each query, only a small number of cells other than the whole network space was processed. And the databse system becomes more efficient by this way. The experiments demonstrated that our method is very efficient even when the trajectory datasets are huge.