Indoor Uncertain Semantic Trajectory Similarity Join

With the widespread deployment of indoor positioning systems, an unprecedented scale of indoor trajectories are being produced. By considering the inherent uncertainties and the text information contained in such an indoor trajectory, a new definition named the indoor uncertain semantic trajectory is firstly defined in this paper. In this paper, we focus on a new primitive, yet quite essential query named Indoor Uncertain Semantic Trajectory similarity Join (IUST-Join for short), which is to match all similar pairs of indoor uncertain semantic trajectories from two sets. IUST-Join targets a number of essential indoor applications. And with these applications in mind, we provide a purposeful definition of the indoor uncertain semantic trajectory similarity metric named IUS. To process IUST-Join more efficiently, both an inverted index on indoor uncertain semantic trajectories named 3IST and the first acceleration strategy are proposed to form a filtering-and-verification framework, where most invalid pairs of indoor uncertain semantic trajectories are pruned at quite low computation cost. And based on this filtering-and-verification framework, we present a highly-efficient algorithm named indoor Uncertain semantic trajectory Similarity join Processing (USP for short). In addition, lots of novel and effective acceleration strategies are proposed and embedded in the USP Algorithm. Thanks to these techniques, both the time complexity and the time overhead of the USP Algorithm are further reduced. Extensive experiments have been done, and the results demonstrate superior performance of our methods.