Research On Partition-based Range Query For Uncertain Trajectories In Road Networks

As the fast development of Location Based Services (LBS) applications, query processing of moving objects (MOs) becomes a hot topic in the field of moving objects databases (MODs). The movement of MO is always in the form of trajectory, and the information between two continuous samples is uncertain. Most of the previous research work is based on the Euclidean space and represents the uncertainty model as sheared cylinders or space-time prisms. However, in many applications, e.g. traffic management, the movements of MOs are constrained by road network environment. The former management methods cannot work well in this situation. In this paper, we construct an uncertain trajectory model, by assuming availability of a maximal speed on each road segment. For these settings, we present a partition-based uncertain trajectory index (PUTI) to find the possible MOs within the space and time range in road networks. It provides appropriate groups to gather segment units of trajectories according to their network distances. And then an efficient algorithm for range query is proposed based on the index. At last, the experiments demonstrate that PUTI significantly outperforms the MON-tree, and the accuracy of query result is higher.