基于位置的可拼接轨迹对搜索

发布时间：2021-07-12 10:39

　　移动设备的快速发展,生成了大量轨迹.基于位置的轨迹搜索,是指给定一组查询点,从数据集中检索top-k条轨迹,但是所得到的轨迹可能不能近距离通过所有查询点.利用轨迹可拼接的想法,提出基于位置的可拼接轨迹对搜索,使用户利用轨迹对得到的轨迹更加近距离地通过所有查询点.在搜索终止过程,给出可拼接的轨迹对搜索过程的有效终止条件.真实的数据集验证了所提方法的有效性. 

【文章来源】：北京理工大学学报. 2019,39(03)北大核心EICSCD

【文章页数】：7 页

【部分图文】：

图１轨迹和查询点Ｆｉｇ．１Ｔｒａｊｅｃｔｏｒｉｅｓａｎｄｑｕｅｒｙｐｏｉｎｔｓ

使得通过Ｔ可以找到与它形成可拼接轨迹对的所有轨迹．为了减少所占内存和重复索引，每条轨迹的倒排表只储存比该轨迹编号小的轨迹，在搜索过程中只需要读取倒排表即可．如图２，设Ｔ１上的轨迹点ｐ１，５所在网格为ａ，对ａ及其周围８个网格中的轨迹点进行搜索，即粗线框中的轨迹点，找到轨迹点ｐ２，４到ｐ１，５的距离小于ｅ，由于ｐ２，４所在轨迹为Ｔ２，因此，为Ｔ２创建倒排表，利用Ｔ２可以找到Ｔ１．图２网格索引Ｆｉｇ．２Ｇｒｉｄｉｎｄｅｘ３查询过程本文中的方法是基于Ｒ－ｔｒｅｅ的最佳优先ＮＮ搜索和ＧＨ算法框架提出的．候选集生成的首要任务就是检索每个查询点的最邻近的轨迹点，是该阶段的重要组成部分．在这项工作中，利用最佳优先策略搜索最近的轨迹点．定义５［１９］ＭｉｎＤｉｓｔ距离ｎ维欧式空间中的轨迹点ｐ到该空间内某一最小边界矩形Ｒ（ｓ，ｔ）的最小距离定义为ＭｉｎＤｉｓｔ，用ＭｉｎＤｉｓｔ（ｐ，Ｒ（ｓ，ｔ））表示ＭｉｎＤｉｓｔ（ｐ，Ｒ）＝∑ｎｉ＝１ｐｉ－ｒｉ２，ｒｉ＝ｓｉｐｉ＜ｓｉｔｉｐｉ＞ｔｉｐｉ烅烄烆其他．（４）最佳优先策略维持一个优先队列来储存Ｒ－ｔｒｅｅ中所有浏览过的结点，优先队列使用查询点到某个最小边界矩形的ＭｉｎＤｉｓｔ距离排序，最初，队列中只含有根结点，然后将根结点的孩子结点分别入队，并删除根结点，再选择此时队列中ＭｉｎＤｉｓｔ值最小的结点（

【参考文献】：
硕士论文
[1]大数据下空间数据索引和kNN查询技术的研究[D]. 董亭亭.大连理工大学 2013



本文编号：3279758