基于时空标签轨迹的k近邻模式匹配查询

摘要

Spatio-temporal label trajectories extended traditional spatio-temporal trajectories with semantic labels. k nearest neighbor pattern match was proposed to return the k nearest trajectories that fulfilled the temporal pattern condi-tion. The Label R-Tree (LR-Tree for short) was proposed, which appending a label table and adding label bitmap in each entry, and k nearest neighbor pattern match query algorithm based on LR-Tree was designed. Using both real and syn-thetic datasets, the LR-Tree was extensively evaluated in comparison with 3DR-Tree, SETI and TB-Tree. The experimental re-sults demonstrate that LR-Tree showing better pruning ability, and verify the effectiveness of proposed algorithm and index.%时空标签轨迹在传统的时空轨迹数据基础之上融入了具有语义含义的标签信息,丰富了移动对象数据.针对该数据提出k近邻模式匹配查询,即在给定时间区间内匹配相应的模式且距离查询轨迹最近的k条轨迹.设计并实现标签R树(LR-Tree),即增加标签表并在R树每项中添加标签位图,及基于LR-Tree的k近邻模式匹配查询算法.通过真实数据和合成数据将LR-Tree与3DR-Tree、SETI及TB-Tree进行对比,实验表明LR-Tree具有更好的剪枝能力,从而验证了所提算法及索引的有效性.