1.一种访存性能优化的车辆相似轨迹查询方法,其特征在于,基于环域计算的数据合并与删除策略,对于车牌识别数据分区域进行环域计算,计算采用三阶段MepReduce程序,具体包括:在第一阶段,进行数据预处理操作;通过Map任务去除数据中无用信息,仅保留地点、车牌号和时间三个字段;将车牌号作为Key,地点=时间作为Value输出,其中,“=”为连接符;在Reduce任务中,统计每辆车的轨迹长度,并根据地点生成区域号和环号,其中在一个区域内拥有最大环号的环域为边界环域,其余环域为普通环域,将区域号与其对应的最大环号写入区环域记录表中,并将区域号=环号=地点作为Key,时间=车牌号=轨迹长度作为Value,输出轨迹长度大于阈值的车辆;
在第二阶段,进行删除偶然伴随和去冗余操作;将第一阶段的输出作为第二阶段的输入,执行Map任务时,将输入数据直接输出给Reduce任务处理;在Reduce任务中,利用滑动时间窗口,将窗口内首车与其他车判定为点伴随关系,即为点伴随车对,并生成以车牌号i=轨迹长度i:车牌号j=轨迹长度j为Key,首车时间为Value的键值对;其中,i和j表示编号,i和j的范围为1至区域内通过的车数量;
进行点伴随车对判定:对于普通环域的点伴随车对,将车对分为有效伴随车对与偶然伴随车对,其中有效伴随车对写入有效伴随缓存结构,偶然车对写入偶然伴随记录表;若环域处理过程中内存不足,将缓存结构中的有效伴随车对持久化到磁盘,并清空偶然伴随记录表;对于边界环域的点伴随车对,都判定为有效伴随车对,直接输出到磁盘;
区域处理结束后,输出缓存结构中的有效伴随车对;
在第三阶段,计算车辆轨迹相似度;将第二阶段的输出作为第三阶段的输入,执行Map任务时,将输入数据直接输出给Reduce任务处理;在Reduce任务中,统计每个有效伴随车对的伴随次数,并利用伴随次数、轨迹长度i和轨迹长度j,计算轨迹相似度;最后输出轨迹相似度符合阈值的车对。
2.根据权利要求1所述的访存性能优化的车辆相似轨迹查询方法,其特征在于,进行点伴随车对判定,具体包括:
101,利用区环域记录表,判断当前环域是否为普通环域,若为普通环域,到102;若为边界环域,到115;
102,在有效伴随缓存结构中查找该点伴随车对,若找到,到103,否则到104;
103,更新缓存结构中的有效伴随信息,伴随次数加1;
104,在有效伴随记录表中查找该点伴随车对,若找到,到105,否则到108;
105,判断内存空间是否不足,若是,到106,否则到107;
106,将缓存结构中的有效伴随车对信息持久化到磁盘,清空偶然伴随记录表,若内存空间仍不足,清空有效伴随记录表,到105;
107,将该点伴随车对信息写入缓存结构,伴随次数加1;
108,在偶然伴随记录表中查找该点伴随车对,若找到,到109,否则到112;
109,判断内存空间是否不足,若是,到110,否则到111;
110,将缓存结构中的有效伴随车对信息持久化到磁盘,清空偶然伴随记录表,若内存空间仍不足,清空有效伴随记录表,到109;
111,将该点伴随车对信息写入缓存结构,伴随次数加1,并删除偶然伴随记录表中该车对信息,再将该车对信息写入当前环有效伴随记录表;
112,判断内存空间是否不足,若是,到113,否则到114;
113,将缓存结构中的有效伴随车对信息持久化到磁盘,清空偶然伴随记录表,若内存空间仍不足,清空有效伴随记录表,到112;
114,将该点伴随车对信息写入偶然伴随记录表;
115,判定该点伴随车对为有效伴随车对,直接输出到磁盘。
3.根据权利要求2所述的访存性能优化的车辆相似轨迹查询方法,其特征在于,所述效伴随缓存结构,位于内存中,为Hash和B+树的混合结构,Hash结构中存储点伴随车对的首车信息,每辆首车信息包含其车牌号、轨迹长度和指向与其对应的B+树的指针;B+树中存储与伴随该首车的所有伴随车信息,每辆伴随车信息包含其车牌号、轨迹长度、伴随起始时间、伴随结束时间与伴随次数;当某点伴随车对被认定为有效伴随车对时,将该车对信息写入缓存结构中,若在环域处理过程中,出现内存不足的情况,需将缓存结构中的有效伴随车对持久化到磁盘。
4.根据权利要求2所述的访存性能优化的车辆相似轨迹查询方法,其特征在于,所述偶然伴随记录表,位于内存中,共三张,每一张表对应一个环域,用于记录在当前环域和前两个环域内首次伴随的车对信息,包含首车的车牌号和轨迹长度,以及伴随车的车牌号、轨迹长度和伴随时间;三张偶然伴随记录表滚动使用,某环域对应的偶然伴随记录表的编号为该环域环号对3求模。
5.根据权利要求2所述的访存性能优化的车辆相似轨迹查询方法,其特征在于,所述有效伴随记录表,位于内存中,共两张,分别用于记录当前环域和前一环域内的有效伴随车对;当因为内存不足,需清空缓存结构和偶然伴随记录表时,点伴随车对可通过有效伴随记录表判定是否为有效伴随车对,从而避免有效信息丢失。
6.根据权利要求1所述的访存性能优化的车辆相似轨迹查询方法,其特征在于,利用伴随次数、轨迹长度i和轨迹长度j,计算轨迹相似度,如下公式:轨迹相似度=2*伴随次数/(轨迹长度i+轨迹长度j)。