Snapshot and continuous points-based trajectory search

• DOI: 10.1007/s10707-016-0267-9
• Publication Date: 2016-08-17T07:25:40Z
• Authors: Shuyao Qi; Dimitris Sacharidis; Panagiotis Bouros; Nikos Mamoulis
• Keywords: Snapshot (computer storage)

Trajectory data capture the traveling history of moving objects such as people or vehicles. With the proliferation of GPS and tracking technologies, huge volumes of trajectories are rapidly generated and collected. Under this, applications such as route recommendation and traveling behavior mining call for efficient trajectory retrieval. In this paper, we first focus on distance-to-points trajectory search; given a collection of trajectories and a set query points, the goal is to retrieve the top-k trajectories that pass as close as possible to all query points. We advance the state-of-the-art by combining existing approaches to a hybrid nearest neighbor-based method while also proposing an alternative, more efficient spatial range-based approach. Second, we investigate the continuous counterpart of distance-to-points trajectory search where the query is long-standing and the set of returned trajectories needs to be maintained whenever updates occur to the query and/or the data. Third, we propose and study two practical variants of distance-to-points trajectory search, which take into account the temporal characteristics of the searched trajectories. Through an extensive experimental analysis with real trajectory data, we show that our range-based approach outperforms previous methods by at least one order of magnitude for the snapshot and up to several times for the continuous version of the queries.