K近邻近似模式匹配查询

K Nearest Neighbor Approximate Pattern Match Query

随着智能终端的广泛普及,传统的移动对象描述中增加了许多语义相关信息.现有语义移动对象查询大多在语义匹配的前提下再进一步考虑时空属性,造成部分结果在时空维度距离较远.为此,针对时空标签轨迹的语义描述,提出近似模式匹配,并给出相关定义表示,以考虑轨迹语义部分匹配查询条件.在此基础上,提出K近邻近似模式匹配查询,以实现同时考虑时空距离和语义匹配程度,引入新的剪枝策略,并给出基于标签R树的K近邻近似模式匹配查询算法.实验结果表明,与基于RR-Tree,3DR-Tree,TB-Tree及SETI索引的查询算法对比,在不同参数下,基于LR-Tree的K近邻近似模式匹配算法表现出更好的剪枝能力.

With the proliferation of smart terminals,many semantic information has been added to the traditional moving objects. Existing moving object query with semantic attributes further consider the space-time attributes under the premise of semantic matching,which leads to far distance over spatial and temporal dimensions in some results. Motivated by this,approximate pattern match query is developed with formal representations of relevant definition according to semantic descriptions of spatio-temporal label trajectory,which considering semantic matching pattern partially. Based on this,k nearest neighbor approximate pattern match query is introduced which put the spatio-temporal distance and semantic matching degree in the same priority,a new pruning strategy is introduced,and corresponding algorithm based on LR-Tree is presented. Experiment results show that k nearest neighbor approximate pattern match query based on LR-Tree showing better pruning ability contrasting with query algorithms based on RR-Tree,3 DR-Tree,TB-Tree and SETI under different parameters.