基于带序兴趣区域的轨迹查询的扩张搜索扩展算法

摘要

本发明公开了一种基于带序兴趣区域的轨迹查询的扩张搜索扩展算法，包括如下步骤：1：初始设置全局空间密度相关性下限LB＝0，全局空间密度相关性上限UB＝+∞；2：从查询区域中心中选择一组查询源；3：对每个查询源进行Dijkstra扩展算法，每次扩展距离最小的点；4：计算空间密度的上限和下限，更新LB和UB；5：判断LB>UB或所有搜索半径超过ε+p.dist/2是否成立，如成立则进入下一步；如不成立，则回到上一步；6：根据空间密度上限的值对轨迹进行排序；7：按照轨迹排序进一步细化，返回具有最大空间密度相关性的轨迹。本发明解决了传统轨迹搜索(TSL)对TSR查询无效的问题，进一步减小了搜索空间，避免重叠区域的遍历，且能有效处理带序列的TSR查询。