Trajectory Comparison in a Vehicular Network I: Computing a Consensus Trajectory

In this paper, we investigate the problem of computing a consensus trajectory of a vehicle giving the history of Points of Interest (POIs) visited by the vehicle over certain period of time. The problem originates from building the social connection between two vehicles in a vehicular network. Formally, given a set of m trajectories (sequences \(S_i\)’s over a given alphabet \(\varSigma \), each with length at most O(n), with \(n=|\varSigma |\)), the problem is to compute a target (median) sequence T over \(\varSigma \) such that the sum of similarity measure (i.e., number of adjacencies) between T and all \(S_i\)’s is maximized. For this version, we show that the problem is NP-hard and we present a simple factor-2 approximation. If T has to be a permutation, then we show that the problem is still NP-hard but the approximation factor can be improved to 1.5. We implement the greedy algorithm and a variation of it which is based on a more natural greedy search. Using simulated data over two months (e.g., \(m=60\)) and variants of \(|S_i|\) and \(\varSigma \) (e.g., \(30\le |S_i|\le 100\) and \(30\le |\varSigma | \le 60\)), the empirical results are very promising and with the local adjustment algorithm the actual approximation factor is between 1.5 and 1.6 for all the cases.