基于回溯的移动对象时序轨迹在线化简方法.pdf

第 44卷 第 2期 湖 南 大 学 学 报 (自然 科 学 版 ) V0I_44，No．2 2 O 1 7 年 2 月 JournalofHunanUniversity(Natura1Sciences) Feb．2017 文章编号 ：1674—2974(2017)02-0149—08 DOI：10．16339／j．cnki．hdxbzkb．2017．02．021 基 于 回 溯 的移 动 对 象 时 序 轨 迹 在 线 化 简 方 法 李想 ，章登义 (武汉大学 计算机学院，湖北 武汉 430072) 摘 要：针对从移动端采集到的移动对象原始轨迹序列的化简，定义了一种回溯化简框 架，通过线性预测来控制化简的时机，对当前时刻到回溯的历史轨迹的起始时刻之间的原始 轨迹进行离线化简，化简采用时态距离作为误差度量方法．在 回溯化简框架下，首先利用每 次离线化简后新产生的化简点构建 多个向量，通过向量计算出预测速度方向，旨在缩小预测 方向与未来真实速度方向的差异 ；然后利用点集合存储有向无环图中必需访 问边来降低最 优线化简算法的时间复杂度．第 1组实验表明，相对于直接使用最近两个位置点计算速度方 向，抖动较为剧烈的原始轨迹在新的预测速度方向下的化简率更高，说 明预测速度方向比切 线速度方向更接近移动对象的未来运动方向；第2组实验表 明，优化后离线化简算法的时间 性能有所提高，说 明减少边的访 问量确实能够降低算法的时间开销． 关键词 ：移动对象数据库；轨迹 ；化简；回溯；线性预测；时态距离 中图分类号 ：TP301 文献标志码 ：A BacktrackingBasedM ethodforOn—line TrajectorySimplificationofMovingObjects LIXiang ，ZHANG Dengyi (SchoolofComputer。WuhanUniversity，Wuhan 430072，China) Abstract：Forthesimplificationfortheoriginaltrajectorysequenceofthemovingobjectcollectedfrom themobiledevices，thispaperdefinedakindofbacktrackingbasedsimplificationframework，whichused thelinearpredictionandlengthofsimplificationqueuetodominatethetimeofsimplification，andsimpli— fledtheoriginaltrajectorysequencebetweenthepresentmomentandstartingtimeofaretrospectivehis— toricaltrajectoryadoptingthemethodoftemporaldistanceastheerrormetric．Inthebacktrackingbased simplification framework，thispaperfirstutilizedthenew reducedpointstoconstructseveralvectorsand predictedthevelocity，whichcouldnarrow thegapbetweenthepredictionandactualvelocityinthefuture． Thispaperthenutilizedthepointsetstostoretheedgesinthedirectedacyclicgraphneededintheaccess toreduc