Efficient location-based search of trajectories with location importance

摘要

Given a database of trajectories and a set of query locations, location-based trajectory search finds trajectories in the database that are close to all the query locations. Location-based trajectory search has many applications such as providing reference routes for travelers who are planning a trip to multiple places of interest. However, previous studies only consider the spatial aspect of trajectories, which is inadequate for real applications. For example, one may obtain the reference route of a tourist who just passed by a place of interest without paying a visit. We propose the \(k\) Important Connected Trajectories (k-ICT) query by associating trajectories with location importance. For any query location, the result trajectories should contain an important point close to it. We describe an effective method to infer the importance of trajectory points from the temporal information. We also propose efficient R-tree-based and grid-based algorithms to answer \(k\)-ICT queries, and verify the efficiency of our algorithms through extensive experiments on both real and synthetic datasets.