KSQ: Top-k Similarity Query on Uncertain Trajectories

Similarity search on spatiotemporal trajectories has a wide range of applications. Most of existing research focuses on certain trajectories. However, trajectories often are uncertain due to various factors, for example, hardware limitations and privacy concerns. In this paper, we introduce p-distance, a novel and adaptive measure that is able to quantify the dissimilarity between two uncertain trajectories. Based on this measure of dissimilarity, we define top-k similarity query (KSQ) on uncertain trajectories. A KSQ returns the k trajectories that are most similar to a given trajectory in terms of p-distance. To process such queries efficiently, we design UTgrid for indexing uncertain trajectories and develop query processing algorithms that make use of UTgrid for effective pruning. We conduct an extensive experimental study on both synthetic and real data sets. The results indicate that UTgrid is an effective indexing method for similarity search on uncertain trajectories. Our query processing using UTgrid dramatically improves the query performance and scales well in terms of query time and I/O.