On Comparing the Similarity and Dissimilarity Between Two Distinct Vehicular Trajectories

In this paper, we study the problem of comparing the similarity and dissimilarity between two distinct vehicular trajectories by proposing an adjacency-based metric. This approach has a broad application in building truthfulness by comparing the similarity between two vehicles and evaluating the dissimilarity between two distinct paths in hazardous materials transportation. Given two sequences $A$ and $B$ of Point of Interests (POIs) visited by two vehicles in a road/transportation network, the problem is to delete some nodes from $A$ and $B$ to obtain $A'$ and $B'$ such that the number of adjacencies in $A'$ and $B'$ is maximized. In the sequences $A'$ and $B'$ duplicated nodes are allowed, e.g., to represent road edges. We prove that this problem is NP-hard when noisy POIs are deleted and all the remaining POIs must be involved in some adjacency. On the other hand, when the adjacency involvement constraint is dropped, a variation of the problem is as hard as Exact Set Cover hence cannot be approximated within a constant factor unless P=NP. At last, we design a practical approach based on local search and show that the algorithm is very effective on simulation data.