Efficient Semantic Trajectory Similarity Search

Trajectory similarity search is a basic operation in spatial data analysis for nonterrestrial networks applications, such as asset tracking, maritime transportation, and urban air mobility. In many real-world applications (e.g., Flickr, Bikely, and Foursquare), users are allowed to share comments or experiences along with their trajectories, called semantic trajectories. In this article, we study a new type of similarity search on semantic trajectories, which takes into account spatial and textual information together. Given a query trajectory <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$t_{q}$ </tex-math></inline-formula> and a similarity threshold <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\theta $ </tex-math></inline-formula>, semantic trajectory similarity search retrieves all trajectories whose spatial-textual similarity to <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$t_{q}$ </tex-math></inline-formula> is no greater than <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\theta $ </tex-math></inline-formula>. To address the problem efficiently, we first develop a novel bitmap-based index, called SET-tree, to organize the semantic trajectory hierarchically. It contains two types of bitmaps, global gram bitmap and positional gram bitmap, that enable us to efficiently prune the search space by spatial and textual similarity simultaneously. Besides, we develop some novel upper and lower bounds on textual and spatial similarity for pruning. We provide the spatial-side enhancement and the textual-side enhancement for further improvement. Finally, we report on extensive experiments using real and synthetic trajectory data sets that offer insight into the performance of our algorithm, and show that our algorithm is capable of achieving superior efficiency and good scalability.