Indoor Uncertain Semantic Trajectory Similarity Join

作     者：Hong-Bo Yin Dong-Hua Yang Kai-Qi Zhang Hong Gao Jian-Zhong Li 尹洪波;杨东华;张开旗;高宏;李建中

作者机构：Faculty of ComputingHarbin Institute of TechnologyHarbin 150001China Center of AnalysisMeasurement and ComputingHarbin Institute of TechnologyHarbin 150001China Faculty of Computer Science and Control EngineeringShenzhen Institute of Advanced TechnologyChinese Academy of SciencesShenzhen 518055China 

出 版 物：《Journal of Computer Science & Technology》 (计算机科学技术学报(英文版))

年 卷 期：2024年第39卷第6期

页      面：1441-1465页

核心收录：

学科分类：0711[理学-系统科学] 07[理学] 08[工学] 081101[工学-控制理论与控制工程] 0811[工学-控制科学与工程] 071102[理学-系统分析与集成] 081103[工学-系统工程] 

基　　金：supported by the National Natural Science Foundation of China under Grant Nos.U22A2025,U19A2059,61732003,61832003,U1811461,and 62102119 the Key Research and Development Projects of the Ministry of Science and Technology of China under Grant No.2019YFB2101902 

主　　题：filtering-and-verification framework indoor uncertain semantic trajectory inverted index trajectory similarity join 

摘      要：With the widespread deployment of indoor positioning systems, an unprecedented scale of indoor trajectories is being produced. By considering the inherent uncertainties and the text information contained in such an indoor trajectory, a new definition named Indoor Uncertain Semantic Trajectory is 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. With these applications in mind, we provide a purposeful definition of an 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. The results of extensive experiments demonstrate the superior performance of the proposed work.