Origin-destination trajectory diversity analysis: Efficient top-k diversified search

Given a pair of Origin-Destination (OD) locations, the set of trajectories passing from the original to destination, usually possesses the nature to reflect different traveling patterns between OD. In general, the higher diversity these trajectories have, the more various traveling behaviors and greater robustness of the connectivity can be revealed, which highly raises the value of transportation analysis towards the corresponding OD pair. Therefore, in this paper, we introduce a comprehensive and rational measure for trajectory diversity, on top of which we propose a novel query, Top-k Diversified Search (TkDS), that aims to find a set of k OD pairs among all the given OD pairs such that the trajectories traversing in-between have the highest diversity. Owing to the intrinsic characteristics of trajectory data, the computational cost for diversity is considerably high. Thus we present an efficient bounding algorithm with early termination to filter the candidates that are impossible to contribute the result. Finally, we demonstrate some case studies for trajectory diversity on real world dataset and give a comprehensive performance evaluation on the Top-k Diversified Search.