2017, Vol. 28
随着车载传感器、智能手机等基于LBS的移动设备的发展和私家车数量的不断增长, 基于路网的移动对象(简称路网移动对象)数据的采集频率不断提高, 数据量日益庞大.路网移动对象查询技术的研究具有重要的社会价值和商业价值:一方面, 高效的路网移动对象数据查询技术能够为用户的出行带来便利, 同时也推动了智能交通控制、智能导航和旅游路线推荐等[1]产业的发展和社会的进步; 另一方面, 路网移动对象查询技术在滴滴、Uber等移动出行软件的推广和应用中发挥了重要作用, 为企业创造了极大的商业价值.那么, 如何高效地实现路网中移动对象数据的查询, 成为时空数据领域的一个重要的研究课题.
随着社会和企业对路网移动对象查询技术的不断需求, 近几年, 相关人员做了大量研究并取得了许多有价值的研究成果.然而, 目前缺少对这些研究成果进行归纳总结以及对研究现状的整体了解.针对以上需求, 本文主要对2008年至今的相关研究成果进行归纳和整理.
移动对象存储在移动对象数据库中, 属于时空数据库的范畴[24], 数据包括时间属性和空间属性.路网移动对象查询技术主要包括3个层面的研究:数据库索引层面、查询方法层面和隐私保护层面.其中,
● 数据库索引层面的研究主要对路网移动对象数据在数据库中的索引结构进行归纳;
● 查询方法层面的研究中, 对象包括两类:查询对象和被查询对象, 根据查询对象和被查询对象的状态不同, 又将对象分为两类:静态对象(商店、银行等)和动态对象(车辆、行人等).本文主要针对路网中的动态对象的查询技术进行综述, 即:查询对象或者被查询对象中任意一方是动态对象的查询;
● 隐私保护层面通过在移动对象的查询过程中保护位置隐私, 以提高查询过程的安全性.
路网移动对象是一类特殊的移动对象, 与自由空间下的移动对象相比, 路网移动对象具有以下3个特点.
(1) 移动对象的运动轨迹受路网的限制只能在路网内运动, 因此, 数据的索引效率受路网结构影响;
(2) 移动对象的运动过程受交通法规的约束, 例如在某些路段中必须按照既定的方向运动、必须遵守交通信号灯的管制等;
(3) 查询对象和被查询对象都位于路网中, 因此查询过程中的距离不再只表示欧式距离, 而需要计算路网距离.
本文依次从索引结构、查询方法和隐私保护3个方面对现有的路网移动对象查询研究成果进行了归纳和分析.本文第1节阐述路网移动对象查询中面临的问题与挑战.第2节对路网移动对象的索引结构进行总结和对比, 根据索引结构差异将索引归纳为3类:分层索引、分布式索引和广播索引.第3节对常见的查询类型及其采用的解决方案进行归纳和分析, 根据查询方法将查询类型分为4类:单对象连续查询、多对象并行查询、最短路径查询和路网关键字查询.其中, 单对象连续查询指查询对象为1个、被查询对象为多个的连续移动对象查询, 多对象并行查询指查询对象为多个的并行查询, 最短路径查询中归纳提高路网最短路径查询的相关方法, 路网关键字查询分析同时考虑路网距离和关键字匹配情况的一类查询.第4节从隐私保护框架和隐私保护算法两方面对路网移动对象数据进行归纳.最后, 对未来路网移动对象查询领域中可能面临的问题与挑战进行了展望.
1 问题与挑战 1.1 主要问题路网移动对象查询的环境特点和对象特点决定了查询过程中主要考虑两方面问题:(1) 路网环境表示;
(2) 移动对象处理.路网环境方面, 现有的研究主要采用数据结构中的图[3-5]来模拟实际的道路网络G=(V, E), 其中, V是图中的点集代表路段间的连接, E是图中的边集代表路段.在每条路段中, 存储一些附加信息(路段代价、等待时间等[2]).本文主要对路网移动对象处理方面的解决方案进行了分类和汇总, 从数据库索引、查询方法和隐私保护这3个层面对问题进行拆分, 面临的问题如下.
(1) 数据库索引层面:路网移动对象数据的时间属性不同, 对应的索引结构也各不相同.针对不同时间属性的数据, 如何创建高效的索引, 是提高移动对象数据索引效率的关键问题之一;
(2) 查询方法层面:如何根据路网的环境特点设计高效的查询方法以满足不同查询需求, 是查询方法层面提高移动对象查询效率的关键问题;
(3) 隐私保护层面:基于LBS的时空查询中, 需要移动对象向查询服务器提供位置信息.如何在查询过程中隐藏移动对象的位置, 是路网查询的关键性安全问题.
针对以上3个层面的问题, 我们对解决上述问题所面临的挑战进行了总结.
1.2 面临挑战移动对象在路网G=(V, E)中运动位置随着时间不断变化.分层索引结构根据数据的时间属性可以分为3种:历史数据索引、实时移动对象查询索引和数据预测索引, 分别对应历史数据、实时数据和未知数据3类数据的索引.每种索引面临的挑战如下.
(1) 历史数据索引的挑战在于如何高效地存储和确定待查询对象的运动轨迹;
(2) 实时对象索引的难点在于如何确保数据的实时性和移动对象的连续移动问题;
(3) 数据预测索引的难点在于如何提高数据预测的精确性.
此外, 分布式索引目前面临的难题是如何对海量的移动对象数据实现分布式架构下的快速索引; 广播索引面临的难题是如何降低索引周期重建的代价.
本文将路网移动对象查询中所面临的挑战归纳为以下3点.
(1) 提高数据的查询效率.决定查询效率的因素除了在数据库中创建索引以外, 还取决于对应的查询方法.根据不同的查询需求设计不同的查询方法, 降低查询代价, 一直是路网研究的热点;
(2) 连续移动对象的查询.实时状态下的移动对象在路网中不断运动, 运动过程中, 查询结果也在不断变化, 解决连续移动对象的查询, 是路网查询研究的基本挑战;
(3) 多个对象的并行查询.多个对象同时向服务器发送查询请求且查询结果在相互影响的情况下, 如何对查询结果进行合理、高效地分配, 是对查询方法的又一个挑战.
隐私安全保护的挑战在于有效地隐藏查询对象的位置信息, 同时能够快速返回正确的查询结果, 这是移动对象查询过程中的安全屏障.针对以上查询中面临的挑战, 本文分门别类地对现有研究成果中提出的解决方案进行了归纳和分析.
2 索引分类分层索引、分布式索引和广播索引, 是路网移动对象数据库中常见的3类索引结构.其中:分层索引是最早出现的路网索引结构, 通常分为两层, 上层索引空间, 下层索引时间; 分布式索引是基于分布式服务架构而提出的结构, 特点是分别在不同的服务器中创建索引; 广播索引是根据无线广播而建立的索引结构, 具有重复创建的特点.3种索引结构的具体对比见表 1.
|
Table 1 Comparation of three index structure 表 1 3种索引结构对比 |
2.1 分层索引
按照数据的历史、实时和未知这3种时间状态, 将现有的路网移动对象索引研究成果划分为如下3类:历史数据索引、实时对象索引和数据预测索引.
2.1.1 历史数据索引FNR-tree[3]是一种典型的分层索引, 上层采用二维R-tree索引路网空间, 下层采用一维R-tree索引时间.然而Güting等人[4]发现:FNR-tree中, 每条边只代表小段直线路段, 这种路网模型将增加路网的记录数和索引更新代价; 其次, 移动对象运动的开始和停止只能发生在路网的顶点中, 且移动对象不能在路段中改变运动方向和速度大小.
MON-tree[5]在FNR-tree上进行改进, 上层R-tree叶子的路段存储在hash表中(如图 1所示), 避免了对无效叶子节点的查询过程.此外, 将路段进行泛化改进路网模型, 减少路网数据的存储和索引开销.
空间填充曲线是一种特殊的索引结构, 主要有3种:Hilbert[6, 7], Sweep[8]和Z-order[8-10].实现思路是:将路网空间等区域划分(四叉树[5]等), 然后利用空间填充曲线对路网空间进行不重复编码.但是空间填充曲线在路网中应用时可能出现死空间(即:该划分区域不包含任何路段, 永远不被访问的情况).文献[11]对该类索引进行了改进, 对路段采用hilbert曲线编号.类似的索引改进还有:MOR-tree[12]是一棵多层多想关系树, 用于管理多尺度道路网络; super-node[2]对路段信息进行整合.
MON+-tree[13]在MON-tree的基础上增加了Hash表和单链表组成的复合结构, 每个移动对象对应一张单链表, 并按照移动对象的时间顺序进行存储.当查询某个对象的运动轨迹时, 只需查询确定该对象连接的单链表.但是索引需要维护复杂的链表结构.TMN-tree[16]是另一种在MON-tree索引基础上提出的索引, 主要通过在索引的第2层添加轨迹记录文件来支持移动对象的轨迹查询.
aCN-RB-tree[14]采用B-tree索引路段并将路段根据路段间的连接进行聚集, 从而支持移动对象的轨迹索引.采用聚集思想实现轨迹索引的还有丁治明等人[15]提出的UTR-tree.图 2是UTR-tree[25]的索引结构, 索引上下两层间形成一对多的对应关系, 即, 同一条路径的多个路段对应一棵下层R-tree.这种索引结构设计的优势在于:当索引移动对象的轨迹时, 能够减少索引下层R-tree的次数.
乔少杰等人[17]根据用户之间访问兴趣点的相似性特点, 提出了可扩展的CNR-tree, 索引上层采用R*-tree, 下层采用R-tree.此外, 与DISC-tree相似, 索引还包括一个辅助结构:路网映射和轨迹映射, 分别存储上层R*-tree叶子到R-tree的映射和移动对象的轨迹.
AU索引[18]中提出了活跃单元Adaptive Unit的概念, 将相似运动模式的相邻对象进行划分, 同时考虑移动对象的距离、方向和速度等因素对移动对象进行分组存放, 避免了MBR重叠造成的查询性能降低.上层R-tree用于索引路网, 中层采用Current-AU索引当前及未来位置, 下层采用Past-AU用于索引历史数据.AU中的数据在路段的起始处产生, 当对象运动到路段的末尾时, 移动对象将被存储到Past-AU结构中.
Singh等人[19]提出了一种基于磁盘的两层滑动窗口索引, 将空间区域划分成不重叠的子空间(cell), 每个cell都有一个时间索引, 该索引由B+-tree0和B+-tree1两棵B-tree组成, 两棵B-tree的时间戳入口范围分别是[0, Wmax]和[Wmax, 2Wmax](其中, Wmax=W+(L-1), [W, W+(L-1) ]是滑动窗口的大小范围).
2.1.2 实时对象索引采用缓冲区是提高实时索引效率的有效方法.Le等人[20]提出了GTR-tree索引, 采用R-tree索引路网的边, 并且为每条边分配缓冲区, 用于存储即将到来的数据.当数据达到一定的阈值后, 再转存到磁盘中.此外, 索引中还包括一张淘汰表, 存储即将被淘汰的数据, 与回收站的功能类似.然而, 淘汰表的缺点就是降低了CPU的时效.
RGTR-tree[21]摒弃了GTR-tree中的淘汰表, 并对R-tree, DiskPool和EdgeDisk进行了改进, 在R-tree的每个叶子节点对应一个缓冲区上增加一个指针, 指向一个EdgeDisk, 用于存储移动对象数据.
DBR*-tree[22]与GTR-tree不同, 采用磁盘缓冲区代替内存缓冲区, 采用两个磁盘缓冲R-buffer和I-buffer, 分别用于存储用户的更新操作和路网的中间节点, 索引将插入和删除从根节点逐层定位到叶子节点, 最终定位到叶节点中路段所存储的移动对象.同样利用缓冲区解决移动对象更新问题的时空索引还有MOVIES[23].
CR-tree[24]在R-tree的基础上进行改进, 叶子节点不存储路段MBR, 而是存储十字路口范围CR.根据路口对路网进行划分, 每个MBR用一个四元组表示, 每个四元组存储ID、周围路口、MBR范围和连接路段长度.该方法避免了将路网分段, 减少了数据的更新延迟.
丁治明等人提出了DSTR-tree[25], 索引将路网空间划分成等距格栅, 并通过格栅单元对每一条移动对象轨迹进行概略化处理, 以概略化轨迹单元为基本索引单位建立上层R-tree.通过轨迹概略化的方法, 移动对象不需要连续进行位置更新, 只需要在移动对象跨越当前格栅单元时进行轨迹更新.
DynSketch[26]是一种基于动态草图的索引, 利用Sketch草图技术避免聚集查询时路网中的重复计数问题.在DynSketch基础上又提出了DSD+[27]索引.DSD+索引除了利用动态草图外, 还利用AMH+存储空间小的特点, 提高移动对象的聚集查询效率.
Haojun等人在MOVNet[28]的基础上, 于2011年提出了C-MNDR[29], MOCNet为内存索引主要解决快照数据的索引不能支持实时状态下的连续移动对象数据的索引, C-MNDR(如图 3)上层采用网格索引索引路网, 下层增加了hash桶和链表索引移动对象, 提高数据的更新效率.
RBMO[30]利用R-tree索引路网, 索引下层包括移动对象表、路段表和连接表等3部分, 分别用于存储移动对象、路段信息和路段之间的连接.主要思想是, 利用移动对象表和路段之间的双向指针提高索引效率.
DISC-tree[1]支持大规模路网移动对象当前及将来位置的索引, 上层采用R*-tree避免空间重叠, 下层采用R-tree.此外, 索引中增加了一个由hash表和双向链表组成的辅助结构, 以提高轨迹的查询效率和索引维护效率.
Wang等人[31]吸取MON-tree和FNR-tree索引的优点, 提出了CRS索引.CRS索引在FNR-tree双层R-tree结构的基础上增加了一张Hash表和动态单向循环连接, Hash用于存储移动对象信息, 每个hash对象对应一个动态单向循环链表用于存储该移动对象的轨迹.
Komai等人[32]提出了TD-FTT索引, 用于解决旅行时间最短的路径查询.主要思想是:在每个时间片段上建立索引, 利用A*算法计算查询点与目标点之间的最短距离.但缺点是索引的创建频率相应提高了, 也就表示索引的创建代价增加.
HBSTR-tree[33]是由R-tree, B*-tree和hash表组成的索引结构.R-tree用于管理时空数据维度, 包括一个时间维和N个空间维度.Hash表用于对最新更新的移动对象数据节点进行管理, 当hash表内的移动对象数据填满时, 就可以将该节点挂到R-tree中.B*-tree主要用于定位移动对象在任何时间切片上所对应的叶节点, 然后通过B*-tree的双向指针确定移动对象轨迹.
2.1.3 数据预测索引数据预测的主要问题在于如何提高预测的精确性.Toplak等人[34]提出了一种本地化的路网优化方法, 对路网中的历史数据根据相似性进行分类, 然后利用分类结果进行训练.这种方法的预测精确性与数据集密切相关.
Jeung等人[35]提出了一种支持长期预测的模型, 根据历史数据挖掘路网中的转弯模式和位于每条路段上的最大速度, 然后利用最大似然贪婪算法对转弯后的移动对象轨迹进行预测.
Guo等人[36]通过挖掘不确定轨迹数据中的频繁序列集, 创建轨迹预测索引树FPT, FPT用于预测对象的未来轨迹.此外, FFTPA[37]利用过去及当前位置发现频繁模式, 过滤掉移动对象下一个时刻不可能出现的位置.这种方法的缺点是只能预测同一条路段上的下一个位置, 不支持跨路段预测.
Xue等人利用子路径合成方法提出了SubSyn模型[38], 该模型将历史轨迹分成等长度的片段, 采用贝叶斯分布对每个网格单元作为目的地的概率进行计算, 利用马尔可夫模型对轨迹进行建模.
Heendaliya等人[39]提出了一种路网中拥堵路段的密度预测索引RD-tree, 上层R*-tree索引路网, R*-tree的每个叶子节点连接一张hash表, 每张hash表中都附有hash桶存储运动方向, 运动方向相同的记录被一个链表连接在一起.这种设计为预测奠定了基础.
PUTI[40]利用METIS[41]对路网进行均衡划分, 将路段划分成更小的片段, 每个片段根据路段的最大限速记录最晚出发时间和最早到达时间作为基本预测单元, 利用时间概率对轨迹进行预测.由于R-tree不能支持轨迹数据索引, 因此采用R-tree结合B+-tree索引移动对象轨迹数据.其次, 由于PUTI中的轨迹模型是基于路段最大速度而建立的, 因此如果移动对象的速度太慢或者时间区间间隔太长, 得到的轨迹预测结果可能不精确.
P-tree[42]的结构如图 4所示, 其预测结果建立在两个假设之上.
(1) 假设当前对象都按照最短路径运动;
(2) 移动对象选择某条路径的概率根据路径经过的区域确定.
P-tree以当前位置作为树的根节点, 树的节点对应路网中的连接点.预测基于概率分配模型, 索引根据节点位于R-tree的位置、移动对象到该节点的时间和同级节点的个数确定沿该路径运动的概率.
乔少杰等人[43]基于隐马尔科夫模型(HMM)的自适应轨迹预测算法提出了一种自适应轨迹预测模型SATP, 基于移动对象密度的聚类进行位置密度分区和路段分段, 预测准确率较高.
2.2 分布式索引分布式索引是随着分布式架构的出现而提出的, 主要用于海量路网移动对象数据的高效分布式处理.时空数据库的分布式索引研究已经取得了一定的成果[44-48], 本节主要介绍路网环境下的研究进展.
DSI[49]索引通过将x轴和y轴的空间分成了不重叠的水平条和垂直条区域并分配到不同的服务器上进行索引.DSI索引的5大特点:1) 按条对空间进行划分, 将不同划分分配到不同的分布式节点中, 处理具有可并行性; 2) 可扩展性, DSI对空间的划分根据分布式节点的数量进行动态的调整; 3) 灵活性, 可以根据路网的倾斜程度选择垂直索引或者平行索引; 4) 第四轻量级的索引, 索引占用的内存空间小; 5) 高效性, 条状的索引区间使得不需要太多的迭代次数就能够得到KNN查询区间.DIS索引如图 5所示.
HAIL[50]借鉴Hadoop++[51]在每个数据块后面追加写的基础上, 充分利用HDFS的冗余机制在不同副本上添加不同属性的索引, 以提高对不同属性数据的索引效率.数据存储过程中, 首先通过GRR*-tree对路网进行划分, 然后将路段尽量均匀分配到每个DataNode中.在DataNode中, 分别创建时间索引和空间索引.
STCode-tree[52]在HBase上建立索引的关键是设计rowkey.STCode tree索引是一种轻量级的分布式路网索引结构, 利用STCode技术对时空数据的三维特性(经度、维度和时间)进行统一编码, 作为HBase的rowkey; 基于每一个维度建立一棵STCode tree, 用于索引对应的rowkey.STCode tree主要解决的是通过数据库rowkey提高数据的索引性能问题, 缺点是索引的建立过程太过繁琐, 针对同一个数据, 可能从不同的维度上需要建立3个索引, 随着数据维度的增加, 索引效率无疑是不高的.
SGR-tree[53]中, 每个记录的rowkey是由记录的时间、空间和移动对象ID等信息唯一确定.索引首先将空间进行网格划分; 然后, 根据移动对象建立rowkey; 最后, 利用Hilbert曲线将R-tree的MBR根据空间相关性连接在一起.SGR-tree索引在时间片上创建, 因此存在索引重建问题.
2.3 广播索引无线广播是一种“一对多”的服务器与客户端通信模式, 利用基站向周围的移动对象提供通信服务.广播按照固定的周期循环向周围的移动对象发送数据并建立索引, 图 6是路网广播索引的基本结构, 索引包括两部分:数据和索引, 索引的特点是周期重建.
ISW索引[54]基于路网空间建立二维动态坐标, 根据对象在空间的分布情况, 利用坐标对路网进行区域划分, 在每个路网子区域中建立kd-tree.整个查询区域的kd-tree森林和广播循环组成了组成ISW索引.为了提高索引查询效率, 还提出了高效的区域边界划分方法.该索引能够解决无线广播环境下的KNN查询、范围查询和RNN查询问题.
为了解决无线广播环境下的连续最近邻查询, Li等人提出了NVD-DI索引[55].索引创建过程分为3步:1) 根据路网中的移动对象数量将路网空间划分成NVD图(见图 7); 2) 将NVD图划分成矩形网格区域利用四叉树对路网进行索引; 3) 提出针对NVD图的分布式索引NVD-DI.该索引能够解决连续移动对象的最近邻查询, 查询延迟和协调时间测试表明, NVD-DI具有高效的索引性能.
BLI[56]中采用Hilbert曲线对路网进行编码, 分别利用0和1表示移动对象和路网节点.该方法能够有效减少服务器的广播频率, 提高服务器的处理性能.索引分为头文件和主索引两部分:头文件主要存储Hilbert曲线及索引号, 主索引存储图中每个节点的位信息、节点连接和移动对象位信息.
基于磁盘的索引并不适用于无线广播模型, 主要表现在两个方面:(1) 磁盘索引都是基于随机访问, 但是广播模型只支持顺序访问; (2) 基于磁盘的索引主要针对减少访问延时, 但是广播模型还需要考虑调谐时间(tuning time).NPI索引[57]对路网进行划分, 基于每个区域分别建立索引.NPI用于管理预计算数据包括路段长度矩阵和不同区域之间的边界点等信息.服务器端周期性的广播NPI索引, 客户端通过调频选择特定的区域, 过滤掉不会存在目标结果的区域提高索引效率.
此外, Liu等人[58]已经开始关注车辆的P2P通信.P2P路网通信是通过车辆与车辆之间进行信息交互, 能够有效避免车辆之间追尾等交通事故的发生.
2.4 小结(1) 分层索引基本结构是:上层采用多维索引(R-tree, R+-tree, R*-tree[59]及变体[60]、空间填充曲线等)用于索引路网, 下层采用一维索引(B-tree等)索引时间维度.为了支持轨迹查询, 索引中通常会增加一些辅助数据结构(单链表、hash表等).为了提高实时数据更新效率, 利用内存缓冲、改进路网划分和增加数据结构的方式解决.为了提高预测的精确性, 现有的研究主要从轨迹模式分析和概率预测模型两个方面给出解决方案;
(2) 分布式索引能够提高路网数据检索的并行性, 从而提高数据的索引效率.目前, 多数研究成果是基于hadoop创建分布式索引, 但是Hadoop主要针对的是历史数据的管理和索引, 对于实时数据的索引效率较低.因此, 研究还可以采用spark, storm等分布式架构解决路网索引问题.此外, 孟小峰等人[61]在2015年对云数据索引技术的相关研究进行了深入调研并做了对比分析, 该文献中提出的分布式索引同样可以借鉴到路网移动对象查询当中;
(3) 广播索引.针对路网“一对多”的服务器与客户端通信模式而提出的索引结构, 该索引更够实现快速的范围性数据广播.针对数据的实时传播问题, 文献[62]定义了广播索引的传输协议协助查询发送给目标对象.此外, 文献[63]提出了MINT, 利用无线广播索引解决P2P路网通信中的带宽限制问题.
3 查询方法 3.1 单对象连续查询本文不按查询类型[64]而是根据查询对象与被查询对象之间的运动状态将查询分为4种情况[65]:(1) 静态对象查询静态对象; (2) 静态对象查询动态对象; (3) 动态对象查询静态对象和(4) 动态对象查询动态对象.其中, 情况(1) 查询对象和被查询对象都是静态的, 不属于本文定义的移动对象范畴, 因此不做分析.
3.1.1 静态对象查询动态对象我们将查询对象静态的查询归为一类, 该类查询的典型事例是查询距离当前加油站最近的对象.路网Voronoi图[66](简称NVD)是解决这类查询的有效手段.如图 7所示:以查询点{p1, p2, p3}为中心, 将路网划分成多个不重叠的Voronoi多边形, 在每个多边形内运动的移动对象距离中心点的路网距离比到其他Voronoi多边形中心点的距离最近.查询时只需判断移动对象所在的Voronoi多边形, 有效提高移动对象的查询效率.基于Voronio图, 文献[67]提出了受限范围KNN查询和受限范围的范围查询两种查询类型的解决方案; Jing等人[68]sup>利用Voronoi图对云租赁环境下的KNN查询结果的正确性和完备性进行了验证.
此外, 冯钧等人[69]通过缩小查询区域提出了R-region, 解决连续移动对象的最近邻查询方法.Al-Khalidi等人[70]提出了下界近似范围查询算法LARS, 将查询范围缩小为索引对应的矩形区域与查询区域的重叠区域.文献[71]通过判断移动对象是否位于influence zone内, 判断是否需要重新请求RKNN.fu等人[72]则采用K-means聚类方法对路网图中的所有顶点根据距离进行聚类, 根据每个聚类中的顶点数确定代表点的个数, 预先保存代表点之间的距离, 达到减少计算代价的目的.Road Cube[73]是支持路网中的实时聚集查询的预计算方法, 利用信息检索工具只保存预计算的路网信息中语义相关的部分数据, 不保存全部的路网预计算数据, 具有高效性、实时性的聚集查询特点.文献[74]中提出了两种路径搜索策略增量路径搜索IRS和层次路由搜索HRS.IRS的思想是:逐渐找到局部最优路径, 从而避免对较远路段的重复计算问题; HRS通过在压缩路网而不是全部路网中进行路径规划和路网监测.Delling等人[75]提出了一种支持可定制化的统一框架, 在查询兴趣点时, 允许用户自己对索引代价(查询时间、空间开销)和查询时间进行权衡.此外, 该框架支持不断变化的路网.PT-Graph[76]是一种新的路网定义, 图中的每条边对应一个时间延迟函数UDF, 通过UDF计算每条边的时间延迟区间记录车辆经过该路段的延迟情况.如果旅行路线花费的时间大于阈值或者旅行时间的信任度低于阈值, 该路段即被过滤掉. Liao等人[77]针对利用覆盖图索引查询中存在的两个问题:(ⅰ)查询过程中兴趣点在图中的位置未知造成大量无用计算; (ⅱ)传统的覆盖图忽略了移动对象的分布, 提出了两种算法Guide-Forest(GF)和Object-Last(OL).GF算法的思想是:向覆盖图的每个节点中增加移动对象位于子树中的位置, 将查询空间缩小一半; OL算法是在图的创建阶段重新安排节点的创建顺序.Yuan等人[78]提出了RSKNN模型, 将社交网络对路网查询的影响考虑进KNN查询中, 提高实时查询的精确性.根据模型提出了road network-based(RN-based), social network-based(SN-based)和hybrid indexing这3种KNN查询算法, 分别对应纯路网、纯社交网络和混合网络的查询.该模型解决了大路网和社交网络环境中的路网快速计算问题, 同时提高了KNN查询的用户满意度.
3.1.2 动态对象查询静态对象路网对象在连续移动状态下的查询是一类特殊的查询, 一个简单的实例是查询移动对象在未来10分钟内运动时距其最近的3个餐厅.解决该类查询的一种方法是安全区域法, 安全区域法利用移动对象在安全区域内运动查询结果不变、不需要重复向服务器发送查询请求的特点, 有效避免重复的查询过程和服务器的通信代价.移动对象查询时只需要判断是否在安全区域内, 其中安全区域间的交界点称为安全退出点.
图 8是解决无向路网中的移动范围查询问题的典型例子, 目标是查询距离q最近的两个对象.其中, 图 8(a)是被查询点{p1, p2, p3}的在r=4时的覆盖范围, 其中, 阴影区域是{p1, p3}的安全区域.移动对象q在该区域内运动时, 查询结果为{p1, p3}不变, 图 8(b)中刻画了安全退出点.基于安全区域法解决连续移动状态下查询的成果有很多, 文献[79]采用安全区域法缩小查询范围, 解决有向路网中的范围KNN查询问题KRNN; 2013年, 文献[65]中提出了安全退出点的快速计算方法, 将静态对象的集合分为answer和no-answer两个子集, 分别存储距离查询点q最近的点集和距离q远的点集.两个集合之间满足answer集合中的任何对象到q的距离d1≪no-answer集合中的任何对象到q的距离d2, 安全退出点是两个集合分别取最小距离的值和最大距离的值的均值.Cho等人[80]采用安全区域法提出了COMET解决有向动态路网中的连续移动对象KNN查询问题, 随后又提出了CRUIS[81]解决有向路网中的移动范围查询问题.在实际的路网中, 多数据段确定了移动对象的运动方向, 不允许对象逆向行驶, 这种情况下, 移动对象的安全范围不再是图 8中的阴影区域, 需要根据移动对象下一个10分钟内的运动范围来确定.2015年, Muhammad等人[82]基于安全区域法提出的CMRNN算法解决范围最近邻查询.
除安全区域法外, 解决连续移动路网对象查询问题的策略还有:2008年, Jang等人[84]将Skyline查询的研究范围扩展到路网的连续移动对象当中, 并通过预计算Skyline每个兴趣点的最短距离范围以减少查询时Skyline的计算量; 文献[85]对距离较远的查询点进行Skyline剪枝, 避免对无效查询结果的计算; 为了解决有向路网中的RNN查询, SWIFT[86]提出了两种引理用于缩小查询范围, 提高静态有向路网中的RNN查询效率; Xu等人[30]通过剪枝算法对查询范围进行剪枝, 能够高效地解决禁止转弯路网中的移动对象反最近邻查询问题; Feng等人提出了基于多侧面空间数据集的最近邻[87]和连续最近邻CNN查询方法[88], 通过引入优先队列, 通过引入优先队列数据结构, 提高候选集合的筛选速度.实时路况能够有效提高连续查询的精确性, Zhang等人[89]基于路况的实时特性对车辆行驶时间的影响, 在2013年提出了SMashQ框架, SMashQ通过Web地图服务端获取查询点和目的地之间的实时路况计算旅行时间.此外, 用户访问查询点的时间受到查询点开放时间的限制.例如, 博物馆只在每天的9:00~17:00开放, 用户需要在该时间段内到达博物馆才能访问.文献[90]采用距离+启发式函数计算出行时间.
3.1.3 动态对象查询动态对象由于查询对象和被查询对象都在运动, 因此两者在查询过程中存在两种状态:接近和远离.解决这类问题的关键是如何提高移动过程中的快速距离计算和状态监控, 主要的解决思路是减少计算量和通信带宽.Fan等人[91]提出了MSO模型, 分别对移动对象和查询对象位于同一条边和位于不同边上运动两种情况下的关系, 从速度和方向两方面的影响因素进行分析, 避免了移动对象在同一条边中运动时的数据更新.但是该方法存在一个缺点是, 没有考虑移动对象速度变化时的高效路网数据更新.Iyer等人[92]利用运动物体的方向对查询范围进行剪枝过滤, 只选择与运动物体运行方向相同的移动对象进行查询, 从而将查询范围减半.此外, Liu等人[93]提出一种分布式处理技术, 解决移动对象的移动范围查询.该策略利用移动对象的计算能力, 只有当移动对象的运动对查询产生影响时才向服务器发送计算请求, 减少移动过程中的服务器通信.Cheema等人[94]基于安全区域提出了有效的移动对象位置不断变化的距离范围查询监测技术, 并确定和验证了安全区域中目标对象的合适数量.为了降低连续移动对象与服务器的通信代价, 文献[95]提出了一种与安全区域法类似的方案, 即:给定一个接近阈值和一系列的移动对象点, 服务器只需要监测移动对象之间的安全接近距离.Stojanovic等人[96]利用移动对象的运动模式(速度、方向、路线等)解决移动对象的连续范围查询.文献[97]弥补了文献[92]的不足, 利用运动方向剪枝的思想解决了连续移动对象的查询.此外, Nguyen等人[98]提出了利用速度分解(VP)提高路网索引效率的方法, 采用主成分分析法(PCA)和k均值聚类方法相结合的方式建立速度坐标轴(DVA), 利用k均值聚类将速度划分成k类, 通过主成分分析得到获得速度运动方向, 根据方向实现快速的查询剪枝.Sun等人[99]通过最小化聚集距离返回最优目标对象, 实现合并聚集最近邻查询(简称MANN, 分为最大(Max)最近邻聚集和综合(Sum)最近邻聚集两类).Kim等人[100]对路网中的速度模式进行动态调整, 当某路段中只有一个移动对象时, 按照上限速度运动; 当路段中有多个移动对象时, 两个移动地向之间需要保持一个安全距离.
3.2 多对象并行查询多对象并行查询指多个用户同时提出查询请求或一次查询需要同时考虑多个用户的查询.通常, Skyline查询中查询对象和被查询对象之间是1:n的对应关系, 即, 1个查询点n个兴趣点.为了应对多人的并行Skyline查询, Son等人[101]提出了n:n的并行Skyline查询方法, 对一个查询对象连续运动和多个查询对象运动两种情况下的Skyline查询分别进行分析, 对不可能成为Skyline查询结果的移动对象进行过滤, R-tree叶子只存储可能的候选Skyline对象.移动对象的运动范围可能是室内、人行横道和公路.为了能够高效地管理在多种运输模式中移动的对象, Xu等人[102]提出了一种解决跨越多种环境查询的解决方案.该方案基于时间、空间和模式这3个维度建立索引, 每个节点中存储通过空间划分的时间数据、子树指针指向和子树的运输模式3部分数据.Reza等
人[103]基于分组思想的近似查询方法对图进行分组处理, 计算每个分组中的最短距离并进行存储.当查询需要穿过该分组时, 不需要重复计算分组内的最短路径.在减少查询代价的同时, 能够确保查询结果的精确性而且摒弃了复杂的预计算过程, 实现多移动对象的连续并行查询.Ahmadi等人[104]提出了一种新的多人路径规划方法, 该方法的主要思想是同时利用宽度优先和广度优先策略逐层创建子路径规划, 最终扩展到整个路网区域获得最终的路径规划结果.
拼车问题是多对象并行查询的典型应用, 属于是多人路径规划问题.目前, 该类问题主要采用迭代计算, 但是迭代方法不能产生最优解, 同时计算量庞大.拼车问题中, 需要依次解决两个子问题:1) 如何对多个共同发出打车请求的用户和多部车辆进行分配; 2) 如何帮助司机制定最佳路线接到所有的乘客, 同时到达目的地的路程最短.
Ma等人[105]为了解决多人车辆分配问题, 在接收乘客的实时租车请求的同时, 根据时间、车的容量和价格限制等因素调度合适的出租车.车辆调度包括两个过程:(1) 云服务器通过路网索引找到所有候选出租车集合;
(2) 服务器选择最小距离增量的调度方案.图 9是针对拼车问题提出的索引树, 其中包括3个列表:时间排序列表、空间排序列表和出租车列表, 分别用于对按照时间的网格从小到大进行排序、按照距离由远及近进行排序、按照出租车调度的先后顺序排序.
|
Fig. 9 Index tree in carpool 图 9 拼车问题中的索引树 |
此外, 文献[106]中基于动态规划(DP)的路径规划, 以待查询点最为输入, 提出了两种路径规划算法, 但只适用于小范围的路网.为了支持大路网环境下的索引, Duan等人[107]对双向DP进行了改进, 提出了POP框架, 该框架中将拼车问题分为离线预处理和在线匹配两个阶段:离线处理阶段创建R-tree路网索引, 根据历史数据计算每个路段的平均旅行时间; 在线匹配阶段, 找到近似的最想节约时间的伙伴.此外, Zhang等人[108]针对OMP问题分别提出了综合值最小化和最大值最小化两种解决方案:min-sum算法将候选集空间从Q×V缩小为Q+V(查询点集Q和图的顶点集V); min-max算法通过距离函数计算所有相遇点的最大路径中最小的相遇路径规划方案.
为了解决考虑访问点顺序的并行查询, Li等人[109]提出了时间敏感的最优路径规划方法, 用于解决受访问顺序约束的路径规划.该方法中采用Douglas-Peucker算法[110]对轨迹数据进行压缩, 提高顺序约束的路径规划. TPQ[111]是旅行商问题的变体, 不仅考虑路径长度, 同时还需要考虑节点的访问顺序.Aljubayrin等人[112]对TPQ问题进行了改进, 同时考虑路径长度、经过兴趣点的顺序和每个点的代价这3方面因素.计算过程分为两步:
(1) 计算经过每个兴趣点时的聚集查询距离pd和代价pc, 分别对pd, pc赋权wd和wd(wc+wd=1), 兴趣点的代价pp=wc.pc+wd.pd, 按照代价排序, 将兴趣点加入候选集合; (2) 路径创建阶段, 以每个兴趣点的距离和代价作为Skyline的两个维度, 从候选集中选择不受其他条件约束的路径.
3.3 最短路径相关查询路网最短路径查询中, 距离特指路网距离.现有的最短路径查询算法有Dijkstra算法、A*算法[113]等, 主要解决静态对象的查询问题.为了研究移动对象的最短路径查询, 研究人员提出了多种提高路网中移动对象的最短路径查询效率的方法.
丁治明等人[114]将移动对象沿着路段运动时KNN查询中最短路径计算问题转化成静态路网中两条路段边的计算问题.当移动对象位于该条边运动时, 无需重复计算到其他兴趣点的最短路径, 从而极大地降低了在线查询的计算量.Geisberger等人[115]将移动对象的转弯代价加入最短路径计算代价当中, 提高了查询结果的精确性和真实性.Miao等人[116]基于路网的地标选择方法提出了本地化地标选择模式, 针对每个地标建立一棵最短路径树, 并计算每个地区的合适地标点的数目, 利用少量本地坐标对最短路径进行估计.由于地标的选择过程需要在线进行, 因此地标选择模式能够有效提高最短路径索引性能.Efentakis等人提出了统一化的最短路径计算框架SALT[117], 该框架结合了ALT[118], CRP[119]和GRASP[120]这3种算法的优点, 不仅能够提供高效的查询性能, 同时与之前的点对点的最短路径查询相比, 效率提高了3~4倍.Delling等人[121]利用标签使用很少的定位信息描述路段距离, 利用压缩技术将标签转换成树, 提高了最短路径查询的鲁棒性和对大路网的支持性.Zhang等人提出了一种有效的Skyline查询方法ParetoPrep[122], 主要思想是:根据Skyline的多个评价指标预计算路段的最短路径, 通过证明所有路径代价指标的最短路径必然经过路径skyline查询结果筛选最短路径.
上述最短路径查询并没有考虑实时路况的影响.如果路径前方出现堵车或者交通事故, 那么用户继续按照规划路径行驶必定会增加不必要的等待时间, 因此, 基于实时路况的最短路径计算更加合理.文献[123]中提出一种基于截止时间的路网实时数据查询方法, 根据用户的运动方向、速度、路况等因素, 解决路网中的最短路径查询问题.
路网分层划分的思想是:利用每个子路网的最短路径, 减少查询过程中对路网中路径的计算代价.这种优化策略已经在很多路网研究中得到应用.ROAD[124]是一种典型的应用, 利用两个子图的交界点计算每个子图的最短路径(shortcut).如图 10:当图中R1b中的对象需要查询到R3b中的最短路径时, 不需要重复计算R2a, R2b和R3a这3个子图, 直接利用shortcut跳过了对R2a, R2b和R3a的查询.
Zhu等人[125, 126]提出了逼近法用于解决连续最短路径查询问题, 将次区域(NR)方法与层次网络方法相结合模拟本地路网环境, 将路网划分成层次树(region tree), 形成多层捷径路网(MLSN).当初始点和目的地相差比较远时, 可以通过层次树和MLSN的捷径减少计算代价.G-tree[127]将整体路网逐层划分成规模相当的子路网(每个子路网中节点个数大致相等), 直到子路网中节点个数与设定的最小阈值相等, 此时结束对路网的划分.建立的G-tree每个节点中记录边界点的最短路径信息, 能够有效提高最短路径相关查询的效率.此外, 文献[128]和文献[75]中也采用路网分层划分的思想.
3.4 路网关键字查询与空间关键字查询[129-132]不同, 路网关键字查询需要同时考虑路网距离和关键字的匹配.路网关键字查询的相关研究主要有两类:基于评分的关键字查询和布尔关键字查询.
● 基于评分的关键字查询通过计算查询对象与被查询对象间的空间接近性和文本相关性, 分别对路网距离和文本相关性进行赋权(两者的权重之和为1).Guo等人[133]对传统的基于评分的关键字查询方法进行改进, 提出了基于连续移动对象的路网关键字查询方法RC-SK[135]:范围查询中, 用户对于离查询点较远的兴趣点其实是不感兴趣的, 如果不对这些点进行过滤, 查询过程中会引入大量的无用计算.Li等人[134]提出了一种范围受限的时空关键字查询解决方案, 首先限定关键字的查询范围, 然后再在范围内查找目标结果.Li等人[136]提出了TPRgt-tree索引, 并基于该索引提出了路网关键字的top-k查询方法.为了支持文本对比, TPRgt-tree索引的下层增加了3张表, 分别存储路段、路段的连接和每个被查询点的文本对象.随后, 基于TPRgt-tree索引, 利用产生原始结果集、剪枝和连续监测这3步, 解决了移动对象的连续top-k路网关键字查询问题.集体空间关键字查询是查找一个对象集合, 集合中的点满足全部查询关键词且距离查询点最近.CCAM[137]是解决路网集体空间关键词查询的有效索引, 索引存储在磁盘当中, 能够支持对大数据集的索引.CCAM由B+-tree和多张连接表组成, 连接表分别存储边及定点信息和被查询对象信息.路网集体空间关键词查询以分组的形式对移动对象进行存储, 同一条边上的移动对象存储在一组中, 以提高查询效率;
● 布尔关键字查询通过增加布尔值实现.Gao等人[138]提出了解决路网关键字的反top-k查询, 采用与文献[137]相同的磁盘索引, 查询过程分为过滤和精化两个阶段:过滤阶段采用布尔验证判断查询点q是不是p的tpo-k布尔空间关键字查询结果, 并利用Dijkstra算法计算候选集合的最短路径, 得到候选集合; 随后利用启发式算法, 分别根据符合要求的点个数、距离和与不符合点的相对距离对候选集进行剪枝过滤, 提高路网关键字的反top-k查询效率.文献[139]为了提高布尔路网关键字的查询效率, 提出了SG-tree索引.该索引基于G-tree的每个节点都添加一个关键字签名, 根据签名判断根节点是否包含查询关键字.SG-tree能够快速对不包含关键字的子树进行剪枝, 是一种高效的布尔路网关键字查询解决方案.
此外, 文献[140]利用G-tree索引和语义倒排索引分别用来索引路网和图片语义, 高效地实现了路网中的图片关键字查询.该问题是top-k聚合查询, 查询的本文内容从图片中进行提取, 每张图片中包含多个关键词.例如“周围哪里能买到类似款式的鞋子”, 需要同时满足鞋跟、颜色、尺码等方面都相似的鞋子作为候选对象.刘喜平等人[141]对时空关键字查询方法进行了比较全面的总结与归纳.
3.5 小结(1) 单对象连续查询.主要问题是如何减少移动对象与服务器的通信代价和计算代价.解决方法有安全区域法、预计算法、实时路况和采用路网工具(Voronoi图等).通过计算安全区域, 能够有效减少移动对象与服务器的通信频率.预计算方法的思路是:将在线处理的计算过程在离线状态下事先准备, 减少在线实时查询处理的计算量.实时路况是考虑实时路网的拥堵等情况, 提高移动对象查询的精确性.利用路网工具对路网进行划分, 有效地减少移动对象与服务器的请求次数;
(2) 多对象并行查询.其主要的解决方法是:通过分组、剪枝、动态规划等思想, 将多人的查询问题进行分解.多人拼车问题是该类问题的典型应用, 车辆调度过程还需要考虑调度的先后顺序;
(3) 最短路径查询.KNN查询、路径规划等问题当中都涉及最短路径查询, 该类问题的挑战在于如何减少重复计算.解决方法有近似计算、地标法、剪枝法和层次路网划分法.这些方法都是通过预计算部分路网的最短路径或者采用近似路径代替精确地路径计算, 提高移动对象的最短路径查询效率;
(4) 路网关键字查询.主要有基于评分和布尔关键字两种查询, 其中:基于评分的关键字查询思想是对距离和关键字匹配进行评分, 根据top-k查询返回排序靠前的查询结果; 布尔关键字查询则是通过在索引中增加的布尔值, 实现快速查询.
4 隐私保护 4.1 隐私保护框架图 11是隐私安全保护框架图, 该框架由3部分组成:移动用户、匿名服务器和位置服务器.框架思想是:用户首先将自己的位置信息提交至可信赖的匿名服务器; 在匿名服务器中, 采用隐私安全保护算法进行处理; 将经过保护的位置信息发送给应用服务器; 最后, 返回结果在匿名服务器端进行解析, 将精确查询结果返回给用户.
|
Fig. 11 Privacy protection framework based on location 图 11 基于位置的隐私保护框架图 |
4.2 隐私保护算法
隐私安全保护算法应用于匿名服务器中, 将用户发送来的精确位置通过路网隐私安全保护算法进行模糊化处理, 产生隐私安全区域, 最后将隐私安全区域发送给LBS服务器进行查询.隐私安全区域内存在包括真实移动对象和路段在内的k个用户和l条路段, 利用k-1个用户和l-1条路段将用户的真实位置隐藏起来.此外, Piao等人[142]在上述隐私保护模型的基础上提出了一种动态的匿名最小化算法DSMAS, 能够保护移动用户的位置及其他私人信息.
● Hilbert隐身算法[143-145].利用Hilbert曲线生成路网移动对象的隐身区域.当用户发出查询请求时, 首先查询Hilbert编码的区间, 然后确定存储有对象U和其他k-1个对象的桶, 该桶包围的点组成一个模糊查询区域.经过模糊化处理的这个区域提交到LBS服务器进行查询;
● 虚拟生成算法[146].主要思想是:将用户真实位置通过映射函数映射成隐匿位置, 匿名服务器将隐匿位置和真实位置同时发送给LBS服务器进行查询处理.文中选择距离当前位置最近的k个位置, 根据KNN查询结果将区域进行扩展, 生成一个模糊查询区域.该区域内所有KNN查询结果都位于模糊区域内, 这样就避免了向LBS服务器重新发起查询进行查询范围扩展的请求, 从而提高查询效率;
● 语义隐身法[147].研究发现, 位置语义同样能够导致用户隐私泄露.获得绝对的安全隐身用户在不同的位置采用截然不同的语义表示是非常重要的.根据语义对位置进行分类, 例如将诊所、医院、牙科诊所等场所分类到Health子类下面, 随后根据语义位置和服务创建语义位置图, 利用语义位置图和离线历史轨迹筛选用户的k-1个隐身用户.提出了一种针对路网连续移动对象的绝对隐私保护方法;
● 匿名证书[148].借助信任机构提供的信任证书, 并通过信任机构将查询请求发送给LBS服务器, 其中, 信任证书定时更新且不携带用户信息, 从而避免了证书被攻击者破解造成的信息泄露.
4.3 小结路网移动对象查询过程中, 查询对象的隐私保护主要通过增加安全保护的匿名服务器和隐私保护算法实现.现有隐私保护算法的主要思想是:采用数学工具、语义工具或者是第三方证书隐藏查询对象的位置信息.随着大数据时代的到来, 王璐等人[149]对基于位置大数据隐私保护方法进行了系统的归纳整理, 同样可以为路网移动对象隐私保护方面做指导.
5 总结与展望本文从索引结构、查询方法和隐私保护3个方面对路网移动对象查询技术的研究现状进行了综述.未来路网移动对象的查询技术还可以在以下几个方面得到应用或改进.
5.1 结合新硬件技术随着通信带宽、CPU、内存等硬件性能的提高, 采用新硬件环境是提高路网移动对象查询的有效手段.目前, 服务器的内存性能和内存大小都有了很大的提高, 针对内存技术创建索引也有了一些研究成果, 如PASTIS[750], CSB+-tree[151]等.其中:PASTIS利用大内存的硬件特点索引存储在内存当中, 数据则根据历史或是最近分为冷数据和热数据分别存储在磁盘和内存当中, 通过减少内存与磁盘之间的频繁调用, 提高索引效率.可持久化CSB+-tree是利用内存映射技术, 将内存索引完整的映射在外存当中进行备份.当系统突发状况重启后, 系统将外存中的备份索引直接导入内存使用, 对于需要频繁创建索引的应用来说, 能够有效节省索引创建时间.
5.2 实时分布式索引采用Hadoop实现路网移动对象的分布式查询已经初见成效, 但由于Hadoop将数据存储在磁盘当中, 因此不能很好地支持实时移动对象的查询.采用分布式的实时、高效数据库(例如Spark, Storm)解决查询问题, 是提高数据计算能力和查询效率的另一种途径.
5.3 路网堵车问题在人口密集的城市, 堵车问题已经成为一种常态.解决堵车问题有两种主要途径:政府政策调控和路网疏导.政策调控能够从宏观上解决堵车问题, 例如北京在工作日的高峰时段采取限号策略; 路网疏导是通过索引技术对未来路段的拥堵情况进行预测, 对于即将发生拥堵的路段进行分流疏导, 避免交通拥堵的发生.目前, 基于聚集查询的道路堵车问题解决方案已经初见成效, 但是还没有有效地在路网中进行实施.
5.4 套牌车筛查车辆套牌是一种违法行为.所谓套牌车是指伪造、非法套取其他车辆号码牌及行驶证等手续在道路上形式的车辆[154].套牌车事件屡见不鲜, 不但给真牌照司机带来了经济损失, 而且严重扰乱了社会治安.如何在路网中筛查套牌车, 对维护路网安全具有重要的作用.解决假牌照问题存在两点难度:首先, 同一时间内车辆的行驶数量巨大, 尤其是套牌车可能出现在不同的城市路网中; 其次, 需要应用图像识别和特征提取等知识, 其中, 路网移动对象数据对路网移动对象查询技术的研究对套牌车筛查具有重要的指导意义.
5.5 无线传感器路网随着物联网技术的发展, 国内对于无线传感器网络的研究正在不断地探索当中.无线传感器网络在智能交通方面具有重要的应用价值, 通过无线传感器, 能够将路网的移动对象数据进行采集, 能够提高数据的传输效率和查询效率.其中, 在无线传感器网络的范围查询[152]和时空聚集查询[153]方面已经产生了很多研究成果.未来无线传感器可以在路网相关的更多领域中得到有效的应用.
| [1] | Qiao SJ, Han N, Wang C, Zhu F, Tang CJ. A two-tiered dynamicindex structure of moving objects based on constrained networks. Chinese Journal of Computers, 2014(9): 1947–1958 (in Chinese with English abstract). http://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201409005.htm |
| [2] | Feng J, Zhu YL, Mukai N, Watanabe T. Search on transportation networks for location-based service. Applied Intelligence, 2007, 26(1): 69–79 . [doi:10.1007/s10489-006-0004-4] |
| [3] | Frentzos E. Indexing objects moving on fixed networks. In:Proc. of the Int'l Symp., 2003: 289–305 . [doi:10.1007/978-3-540-45072-6_17] |
| [4] | Güting RH, Almeida VTD, Ding Z. Modeling and querying moving objects in networks. VLDB Journal, 2006, 15(2): 165–190 . [doi:10.1007/s00778-005-0152-x] |
| [5] | Almeida VTD. Indexing the trajectories of moving objects in networks*. In:Proc. of the IEEE Scientific and Statistical Database Management Int'l Conf. 2004. 115-115.[doi:10.1109/SSDM.2004.1311200] |
| [6] | Gong Z, Lakshminarasimhan S, Jenkins J, Kolla H, Ethier S, Chen J, Ross R, Klasky S, Samatova NF. Multi-Level layout optimization for efficient spatio-temporal queries on ISABELA-compressed data. In:Proc. of the IEEE Parallel & Distributed Processing Symp. (IPDPS). 2012. 873-884.[doi:10.1109/IPDPS.2012.83] |
| [7] | Fox A, Eichelberger C, Hughes J, Lyon S. Spatio-Temporal indexing in non-relational distributed databases. In:Proc. of the IEEE Int'l Conf. on Big Data. 2013. 291-299.[doi:10.1109/BigData.2013.6691586] |
| [8] | Kilimci P, Kalipsiz O. Indexing of spatio-temporal data:A comparison between sweep and z-order space filling curves. In:Proc. of the Int'l Conf. on Information Society. London, 2011. 450-456. |
| [9] | Xu HB, Hao ZX. An approximate k-closest pair query algorithm based on Z curve. Journal of Computer Rearch and Development, 2008, 45(2): 310–317 (in Chinese with English abstract). http://www.cnki.com.cn/Article/CJFDTOTAL-JFYZ200802014.htm |
| [10] | Nishimura S, Das S, Agrawal D, Abbadi AE. MD-HBase:A scalable multi-dimensional data infrastructure for location aware services. In:Proc. of the IEEE Int'l Conf. on Mobile Data Management. 2011. 7-16.[doi:10.1109/MDM.2011.41] |
| [11] | Pfoser D, Jensen CS. Indexing of network constrained moving objects. In:Proc. of the 11th ACM Int'l Symp. on Advances in Geographic Information Systems. New Orleans, 2003. 25-32.[doi:10.1145/956676.956680] |
| [12] | Feng J, Watanabe T. MOR-Tree:An access structure for multi-levels of road networks on distributed environment. Trans. of the Institute of Systems Control & Information Engineers, 2003, 16: 655–661 . [doi:10.5687/iscie.16.655] |
| [13] | Zhang JM, Wang PC, Lu FJ. Research on moving objects index in road network. Computer Engineering & Applications, 2009, 45(12): 144–146 (in Chinese with English abstract). [doi:10.3778/j.issn.1002-8331.2009.12.047] |
| [14] | Lee DW, Baek SH, Bae HY. aCN-RB-Tree:Update method for spatio-temporal aggregation of moving object trajectory in ubiquitous environment. In:Proc. of the IEEE Int'l Conf. on Computational Science and Its Applications. 2009. 177-182.[doi:10.1109/ICCSA.2009.30] |
| [15] | Ding ZM, Li XN, Yu B. Indexing the historical, current, and future locations of network-constrained moving objects. Ruan Jian Xue Bao/Journal of Software, 2009, 20(12): 3193–3204 (in Chinese with English abstract). http://www.jos.org.cn/ch/reader/view_abstract.aspx?flag=1&file_no=3400&journal_id=jos [doi:10.3724/SP.J.1001.2009.03400] |
| [16] | Chang JW, Song MS, Um JH. TMN-Tree:New trajectory index structure for moving objects in spatial networks. In:Proc. of the IEEE Int'l Conf. on Computer and Information Technology. 2010. 1633-1638.[doi:10.1109/CIT.2010.289] |
| [17] | Qiao S, Han N, Zhu W, Gutierrez LA. TraPlan:An effective three-in-one trajectory-prediction model in transportation networks. IEEE Trans. on Intelligent Transportation Systems, 2015, 16(3): 1188–1198 . [doi:10.1109/TITS.2014.2353302] |
| [18] | Chen J, Meng X. Update-Efficient indexing of moving objects in road networks. Geoinformatica, 2009, 13(13): 397–424 . [doi:10.1007/s10707-008-0052-5] |
| [19] | Singh M, Zhu Q, Jagadish HV. SWST:A disk based index for sliding window spatio-temporal data. In:Proc. of the IEEE Int'l Conf. on Data Engineering. 2012. 342-353.[doi:10.1109/ICDE.2012.98] |
| [20] | Le J, Liu L, Guo Y, Ying M. Supported high-update method on road network. In:Proc. of the 4th Int'l Conf. on Wireless Communications, Networking and Mobile Computing. 2008. 1-4.[doi:10.1109/WiCom.2008.1198] |
| [21] | He K, Liu L. Efficiently indexing moving objects on road network. In:Proc. of the IEEE Computational Intelligence and Software Engineering. 2009. 1-4.[doi:10.1109/CISE.2009.5366045] |
| [22] | Liu L, Li W, Guo Y, Le J. Supporting high updates disk-based index in road network. In:Proc. of the IEEE Int'l Conf. on E-business Engineering. 2008. 517-522.[doi:10.1109/ICEBE.2008.39] |
| [23] | Dittrich J, Blunschi L, Salles MAV. MOVIES:Indexing moving objects by shooting index images. Geoinformatica, 2011, 15(4): 727–767 . [doi:10.1007/s10707-011-0122-y] |
| [24] | Feng J, Lu J, Zhu Y, Watanabe T. Index method for tracking network-constrained moving objects. In:Proc. of the KnowledgeBased Intelligent Information and Engineering Systems. Berlin, Heidelberg:Springer-Verlag, 2008. 551-558.[doi:10.1007/978-3-540-85565-1_68] |
| [25] | Ding ZM. An index structure for frequently updated network-constrained moving object trajectories. Chinese Journal of Computers, 2012, 35(7): 1448–1461 (in Chinese with English abstract). [doi:10.3724/SP.J.1016.2012.01448] |
| [26] | Feng J, Lu C, Xu S. DynSketch:A spatio-temporal aggregate index for moving objects in road networks. Int'l Journal of Intelligent Defence Support Systems, 2009, 2(2) . [doi:10.1504/IJIDSS.2009.028646] |
| [27] | Feng J, Shi YQ, Tang ZX, Rui CH. Aggragation index technique of moving objexts in road networks. Journal of Jilin University (Engineering and Technology Edition), 2014, 44(6): 1799–1805 (in Chinese with English abstract). http://www.cnki.com.cn/Article/CJFDTOTAL-JLGY201406041.htm |
| [28] | Wang H, Zimmermann R. Snapshot location-based query processing on moving objects in road networks. In:Proc. of the ACM Sigspatial Int'l Conf. on Advances in Geographic Information Systems. 2008. 1-4.[doi:10.1145/1463434.1463495] |
| [29] | Wang H, Zimmermann R. Processing of continuous location-based range queries on moving objects in road networks. IEEE Trans. on Knowledge & Data Engineering, 2011, 23(7): 1065–1078 . [doi:10.1109/TKDE.2010.171] |
| [30] | Xu L, Zhang T. Reverse nearest neighbors query for moving objects in road network. In:Proc. of the IEEE Computational Intelligence and Software Engineering. 2009. 1-4.[doi:10.1109/CISE.2009.5364547] |
| [31] | Wang Q, Yu J, Zhang Q. A comprehensive index mechanism based on road network. In:Proc. of the IEEE Consumer Electronics, Communications and Networks (CECNet). 2012. 1505-1508.[doi:10.1109/CECNet.2012.6201951] |
| [32] | Komai Y, Nguyen DH, Hara T, Nishio S. kNN search utilizing index of the minimum road travel time in time-dependent road networks. In:Proc. of the IEEE Reliable Distributed Systems Workshops (SRDSW). 2014. 131-137.[doi:10.1109/SRDSW.2014. 17] |
| [33] | Ke S, Gong J, Li S, Zhu Q, Liu X, Zhang Y. A hybrid spatio-temporal data indexing method for trajectory databases. Sensors, 2014, 14(7): 12990–13005 . [doi:10.3390/s140712990] |
| [34] | Toplak W, Koller H, Dragaschnig M, Bauer D, Asamer J. Novel road classifications for large scale traffic networks. In:Proc. of the IEEE Intelligent Transportation Systems (ITSC). 2010. 1264-1270.[doi:10.1109/ITSC.2010.5625182] |
| [35] | Jeung H, Man LY, Zhou X, Jensen CS. Path prediction and predictive range querying in road network databases. Vldb Journal, 2010, 19(4): 585–602 . [doi:10.1007/s00778-010-0181-y] |
| [36] | Guo LM, Ding ZM, Hu ZL, Chen C. Uncertain path prediction of moving objects on road netowrk. Journal of Computer Rearch and Development, 2010, 47(1): 104–112 (in Chinese with English abstract). http://www.cnki.com.cn/Article/CJFDTOTAL-JFYZ201001016.htm |
| [37] | Sasikala I, Ganesan M, John A. Uncertain data prediction on dynamic road network. In:Proc. of the IEEE Information Communication and Embedded Systems (ICICES). 2015.[doi:10.1109/ICICES.2014.7033972] |
| [38] | Xue AY, Qi J, Xie X, Zhang R, Li Y. Solving the data sparsity problem in destination prediction. Vldb Journal, 2014, 24(2): 1–25 . [doi:10.1007/s00778-014-0369-7] |
| [39] | Heendaliya L, Wisely M, Lin D, Sarvestani SS, Hurson A. Influence-Aware predictive density queries under road-network constraints. In:Proc. of the Advances in Spatial and Temporal Databases. Springer Int'l Publishing, 2015. 80-97.[doi:10. 1007/978-3-319-22363-6_5] |
| [40] | Chen L, Tang Y, Lv M, Chen G. Partition-Based range query for uncertain trajectories in road networks. Geoinformatica, 2014, 19(1): 61–84 . [doi:10.1007/s10707-014-0206-6] |
| [41] | Moulitsas I, Karypis G. Architecture aware partitioning algorithms. In:Proc. of the 8th Int'l Conf. on Algorithms and Architectures for Parallel Processing. 2008. 42-53.[doi:10.1007/978-3-540-69501-1_6] |
| [42] | Hendawi AM, Bao J, Mokbel MF, Ali M. Predictive tree:An efficient index for predictive queries on road networks. In:Proc. of the IEEE Int'l Conf. on Data Engineering. 2015. 1215-1226.[doi:10.1109/ICDE.2015.7113369] |
| [43] | Qiao SJ, Li TR, Han N, Gao YJ, Yuan CA, Wang XT, Tang CJ. Self-Adaptive trajectory prediction model for moving objects in big data environment. Ruan Jian Xue Bao/Journal of Software, 2015, 26(11): 2869–2883 (in Chinese with English abstract). http://www.jos.org.cn/ch/reader/view_abstract.aspx?flag=1&file_no=4889&journal_id=jos [doi:10.13328/j.cnki.jos.004889] |
| [44] | Zhong Y, Fang J, Zhao X. VegaIndexer:A distributed composite index scheme for big spatio-temporal sensor data on cloud. In:Proc. of the IEEE Int'l Geoscience and Remote Sensing Symp. 2013. 1713-1716.[doi:10.1109/IGARSS.2013.6723126] |
| [45] | Zhang N, Zheng G, Chen H, Chen J, Chen X. HBaseSpatial:A scalable spatial data storage based on HBase. In:Proc. of the IEEE Int'l Conf. on Trust, Security and Privacy in Computing and Communications (TrustCom). 2014. 644-651.[doi:10.1109/TrustCom. 2014.83] |
| [46] | Wang L, Zheng Y, Xie X, Ma W. A flexible spatio-temporal indexing scheme for large-scale GPS track retrieval. In:Proc. of the IEEE Int'l Conf. on Mobile Data Management. 2008. 1-8.[doi:10.1109/MDM.2008.24] |
| [47] | Eldawy A, Mokbel MF. SpatialHadoop:A MapReduce framework for spatial data. In:Proc. of the IEEE Int'l Conf. on Data Engineering. 2015. 1352-1363.[doi:10.1109/ICDE.2015.7113382] |
| [48] | Feng J, Tang Z, Wei M, Xu L. HQ-Tree:A distributed spatial index based on hadoop. Wireless Communication over Zigbee for Automotive Inclination Measurement China Communications, 2014, 11(7): 128–141 . [doi:10.1109/CC.2014.6895392] |
| [49] | Yu Z, Liu Y, Yu X, Pu KQ. Scalable distributed processing of K nearest neighbor queries over moving objects. IEEE Trans. on Knowledge & Data Engineering, 2015, 27(5): 1383–1396 . [doi:10.1109/TKDE.2014.2364046] |
| [50] | Xu X, Feng J, Lu JM, Tang ZX, Zhang LX. HINMO:A hadoop-based index for network-constrained moving objects. Journal of Computer Research and Development, 2015(S1) (in Chinese with English abstract). http://www.cnki.com.cn/Article/CJFDTOTAL-JFYZ2015S1011.htm |
| [51] | Dittrich J, Quian-Ruiz JA, Jindal A, Kargin Y, Setty V, Schad J. Hadoop++:Making a yellow elephant run like a cheetah (without it even noticing). Proc. of the Vldb Endowment, 2010, 3(12): 518–529 . https://www.researchgate.net/publication/220538761_Hadoop_Making_a_Yellow_Elephant_Run_Like_a_Cheetah_Without_It_Even_Noticing |
| [52] | Van Le H, Takasu A. A scalable spatio-temporal data storage for intelligent transportation systems based on HBase. IEEE Int'l Conf. on Intelligent Transportation Systems, 2015, 18: 2733–2738 . [doi:10.1109/ITSC.2015.439] |
| [53] | Du N, Zhan J, Zhao M, Xiao D, Xie Y. Spatio-Temporal data index model of moving objects on fixed networks using HBase. In:Proc. of the IEEE Int'l Conf. on Computational Intelligence & Communication Technology. 2015. 247-251.[doi:10.1109/CICT. 2015.32] |
| [54] | Wang Y, Xu C, Gu Y, Chen M, Yu G. Spatial query processing in road networks for wireless data broadcast. Wireless Networks, 2013, 19(4): 477–494 . [doi:10.1007/s11276-012-0479-3] |
| [55] | Li Y, Li J, Shu LC, Li Q, Li G, Yang F. Searching continuous nearest neighbors in road networks on the air. Information Systems, 2014, 42(3): 177–194 . [doi:10.1016/j.is.2014.01.003] |
| [56] | Song D, Lee KH, Park K. Bitmap lattice index in road networks. Journal of Central South University, 2014, 21(10): 3856–3863 . [doi:10.1007/s11771-014-2372-y] |
| [57] | Sun W, Chen C, Zheng B, Chen C, Liu P. An air index for spatial query processing in road networks. IEEE Trans. on Knowledge & Data Engineering, 2015, 27(2): 382–395 . [doi:10.1109/TKDE.2014.2330836] |
| [58] | Liu J, Yue X. Peer-to-Peer cooperative caching for data dissemination in urban vehicular communications. IEEE Systems Journal, 2014, 8(4): 1136–1144 . [doi:10.1109/JSYST.2013.2285611] |
| [59] | Guo W, Guo J, Hu ZY. Spatial Database Index Technology. Shanghai: Shanghai Jiao Tong University, 2006. (in Chinese with English abstract). |
| [60] | Altenis S, Jensen CS, Leutenegger ST, Lopez MA. Indexing the Positions of Continuously Moving Objects. ACM Sigmod Int'l Conf. on Management of Data, 2000, 29(2): 331–342 . [doi:10.1007/978-0-387-35973-1_618] |
| [61] | Ma YZ, Meng XF. Research on indexing for cloud data management. Ruan Jian Xue Bao/Journal of Software, 2015, 26(1): 145–166 (in Chinese with English abstract). http://www.jos.org.cn/ch/reader/view_abstract.aspx?flag=1&file_no=4688&journal_id=jos [doi:10.13328/j.cnki.jos.004688] |
| [62] | Wongdeethai S, Siripongwutikorn P. Multipath query spreading over vehicular ad-hoc networks. In:Proc. of the Computer Science and Engineering Conf. 2013. 255-260.[doi:10.1109/ICSEC.2013.6694789] |
| [63] | Lee EY, Cho HJ, Chung TS, Ryu KY. Moving range k nearest neighbor queries with quality guarantee over uncertain moving objects. Information Sciences, 2015, 325: 324–341 . [doi:10.1016/j.ins.2015.07.034] |
| [64] | Alamri S, Taniar D, Safar M. A taxonomy for moving object queries in spatial databases. Future Generation Computer Systems, 2014, 37(7): 232–242 . [doi:10.1016/j.future.2014.02.007] |
| [65] | Cho HJ, Kwon SJ, Chung TS. A safe exit algorithm for continuous nearest neighbor monitoring in road networks. Mobile Information Systems, 2013, 9(1): 37–53 . [doi:10.1155/2013/426294] |
| [66] | Zhao G, Xuan K, Rahayu W, Taniar D, Safar M, Gavrilova ML, Srinivasan B. Voronoi-Based continuous nearest neighbor search in mobile navigation. IEEE Trans. on Industrial Electronics, 2011, 58(6): 2247–2257 . [doi:10.1109/TIE.2009.2026372] |
| [67] | Xuan K, Zhao G, Taniar D, Safar M, Srinivasan B. Constrained range search query processing on road networks. Concurrency & Computation Practice & Experience, 2011, 23(5): 491–504 . [doi:10.1002/cpe.1651] |
| [68] | Jing Y, Hu L, Ku WS, Shahabi C. Authentication of k nearest neighbor query on road networks. IEEE Trans. on Knowledge & Data Engineering, 2014, 26(6): 1–1 . [doi:10.1109/TKDE.2013.174] |
| [69] | Feng J, Mukai N, Watanabe T. Incremental maintenance of all-nearest neighbors based on road network. In:Proc. of the Innovations in Applied Artificial Intelligence. Berlin, Heidelberg:Springer-Verlag, 2004. 164-169.[doi:10.1007/978-3-540-24677-0_18] |
| [70] | Al-Khalidi H, Abbas Z, Safar M. Approximate range query processing in spatial network databases. Multimedia Systems, 2013, 19(2): 151–161 . [doi:10.1007/s00530-012-0286-9] |
| [71] | Wang S, Cheema MA, Lin X. Efficiently monitoring reverse k-nearest neighbors in spatial networks. Computer Journal, 2013, 58(1): 40–56 . [doi:10.1093/comjnl/bxt115] |
| [72] | Fu Q, Sun G, Zhang Z. An efficient pre-computation technique for approximation distance query in road networks. In:Proc. of the IEEE Mobile Data Management (MDM). 2013. 131-135.[doi:10.1109/MDM.2013.82] |
| [73] | Hua Y, Feng D. A correlation-aware partial materialization scheme for near real-time automotive queries. In:Proc. of the IEEE Smart Computing (SMARTCOMP). 2014. 237-244.[doi:10.1109/SMARTCOMP.2014.7043864] |
| [74] | Xu J, Gao Y, Liu C, Zhao L, Ding Z. Efficient route search on hierarchical dynamic road networks. Distributed & Parallel Databases, 2014, 33(2): 227–252 . [doi:10.1007/s10619-014-7146-x] |
| [75] | Delling D, Werneck RF. Customizable point-of-interest queries in road networks. IEEE Trans. on Knowledge & Data Engineering, 2015, 27(3): 686–698 . [doi:10.1109/TKDE.2014.2345386] |
| [76] | Chen L. Trip planner over probabilistic time-dependent road networks. IEEE Trans. on Knowledge & Data Engineering, 2014, 26(8): 2058–2071 . [doi:10.1109/TKDE.2013.159] |
| [77] | Liao B, Leong HU, Man LY, Gong Z. Beyond millisecond latency kNN search on commodity machine. IEEE Trans. on Knowledge & Data Engineering, 2015, 27(10): 2618–2631 . [doi:10.1109/TKDE.2015.2426702] |
| [78] | Yuan Y, Lian X, Chen L, Sun Y, Wang G. RSkNN:kNN search on road networks by incorporating social influence. IEEE Trans. on Knowledge & Data Engineering, 2016, 28(6): 1575–1588 . [doi:10.1109/TKDE.2016.2518692] |
| [79] | Zeberga K, Cho HJ, Chung TS. A safe-region approach to k-RNN queries in directed road network. In:Proc. of the IEEE Int'l Conf. on Computational Science and Engineering (CSE). 2014. 818-824.[doi:10.1109/CSE.2014.167] |
| [80] | Cho HJ, Jin R, Chung TS. A collaborative approach to moving k-nearest neighbor queries in directed and dynamic road networks. Pervasive & Mobile Computing, 2014, 17: 139–156 . [doi:10.1016/j.pmcj.2014.07.002] |
| [81] | Cho HJ, Ryu K, Chung TS. An efficient algorithm for computing safe exit points of moving range queries in directed road networks. Information Systems, 2014, 41(3): 1–19 . [doi:10.1016/j.is.2013.10.008] |
| [82] | Attique M, Hailu Y, Gudetaayele S, Cho HJ, Chung TS. A safe exit approach for continuous monitoring of reverse K-nearest neighbors in road networks. British Dental Journal, 2015, 217(11): 617–617 . https://www.researchgate.net/publication/283553789_CORE_Continuous_Monitoring_of_Reverse_k_Nearest_Neighbors_on_Moving_Objects_in_Road_Networks |
| [83] | Yung D, Man LY, Lo E. A safe-exit approach for efficient network-based moving range queries. Data & Knowledge Engineering, 2012, 72(1): 126–147 . https://www.researchgate.net/publication/265052835_A_collaborative_approach_to_moving_-nearest_neighbor_queries_in_directed_and_dynamic_road_networks |
| [84] | Jang S, Yoo J. Processing continuous skyline queries in road networks. In:Proc. of the Int'l Symp. on Computer Science and ITS Applications. 2008. e3594.[doi:10.1109/CSA.2008.30] |
| [85] | Huang YK, Chang CH, Lee C. Continuous distance-based skyline queries in road networks. Information Systems, 2012, 37(7): 611–633 . [doi:10.1016/j.is.2012.02.003] |
| [86] | Qamar R, Attique M, Chung TS. A pruning algorithm for reverse nearest neighbors in directed road networks. In:Proc. of the IEEE Computer and Information Science (ICIS). 2015. 279-284.[doi:10.1109/ICIS.2015.7166606] |
| [87] | Feng J, Watanabe T. A fast search method of nearest target object in road networks. Trans. of the Institute of Systems Control & Information Engineers, 2003, 16(9): 484–491 . [doi:10.5687/iscie.16.484] |
| [88] | Feng J, Mukai N, Watanabe T. Representation of transportation network and continuous nearest neighbor search. Dbsj Letters, 2003, 2: 1–4 . https://link.springer.com/article/10.1007/s10489-006-0004-4 |
| [89] | Zhang D, Chow CY, Li Q, Zhang X, Xu Y. SMashQ:Spatial mashup framework for k-NN queries in time-dependent road networks. Distributed & Parallel Databases, 2013, 31(2): 259–287 . [doi:10.1007/s10619-012-7110-6] |
| [90] | Costa CF, Nascimento MA, Machado J. A*-Based solutions for KNN queries with operating time constraints in time-dependent road networks. In:Proc. of the IEEE Int'l Conf. on Mobile Data Management (MDM). 2014. 23-32.[doi:10.1109/MDM.2014.9] |
| [91] | Fan P, Li G, Yuan L. Continuous K-nearest neighbor processing based on speed and direction of moving objects in a road network. Telecommunication Systems, 2014, 55(3): 403–419 . [doi:10.1007/s11235-013-9795-x] |
| [92] | Iyer KBP, Shanthi V. Intelligent path finder for goal directed queries in spatial networks. In:Proc. of the Advances in Mobile Network, Communication and its Applications (MNCAPPS). 2012. 83-86.[doi:10.1109/MNCApps.2012.22] |
| [93] | Liu F, Tai TD, Hua KA. Dynamic range query in spatial network environments. In:Proc. of the Database and Expert Systems Applications. Springer Berlin Heidelberg, 2006. 254-265.[doi:10.1007/11827405_25] |
| [94] | Cheema MA, Brankovic L, Lin X, Zhang W, Wang W. Continuous monitoring of distance-based range queries. IEEE Trans. on Knowledge & Data Engineering, 2011, 23(8): 1182–1199 . [doi:10.1109/TKDE.2010.246] |
| [95] | Kriegel HP, Kröger P, Renz M. Continuous proximity monitoring in road networks. In:Proc. of the ACM Sigspatial Int'l Symp. on Advances in Geographic Information Systems. 2008. 414.[doi:10.1145/1463434.1463450] |
| [96] | Stojanovic D, Papadopoulos AN, Predic B, Djordjevic-Kajan S, Nanopoulos A. Continuous range monitoring of mobile objects in road networks. Data & Knowledge Engineering, 2008, 64(1): 77–100 . [doi:10.1016/j.datak.2007.06.021] |
| [97] | Lin CS, Wu SY. Processing directional continuous range queries for mobile objects on road networks. In:Proc. of the IEEE Int'l Conf. on Cyber Technology in Automation, Control, and Intelligent Systems. 2014.[doi:10.1109/CYBER.2014.6917484] |
| [98] | Nguyen T, He Z, Zhang R, Zhang R, Ward P. Exploiting velocity distribution skew to speed up moving object indexing. Information Systems, 2015, 51: 72–104 . [doi:10.1016/j.is.2015.03.001] |
| [99] | Sun W, Chen C, Zheng B, Chen C, Zhu L, Liu W. Fast optimal aggregate point search for a merged set on road networks. Information Sciences, 2015, 310(C): 52–68 . [doi:10.1016/j.ins.2015.03.028] |
| [100] | Kim J, Han WS, Oh J, Kim S, Yu H. Processing time-dependent shortest path queries without pre-computed speed information on road networks. Information Sciences, 2014, 255(1): 135–154 . [doi:10.1016/j.ins.2013.07.009] |
| [101] | Son W, Hwang SW, Ahn HK. MSSQ:Manhattan spatial skyline queries. Information Systems, 2014, 40(1): 67–83 . [doi:10.1016/j.is.2013.10.001] |
| [102] | Xu J, Güting RH, Zheng Y. The TM-RTree:An index on generic moving objects for range queries. Geoinformatica, 2014, 19(3): 487–524 . [doi:10.1007/s10707-014-0218-2] |
| [103] | Reza RM, Ali ME, Hashem T. Group processing of simultaneous shortest path queries in road networks. In:Proc. of the IEEE Int'l Conf. on Mobile Data Management. 2015. 125-139.[doi:10.1109/MDM.2015.70] |
| [104] | Ahmadi E, Nascimento MA. A mixed breadth-depth first search strategy for sequenced group trip planning queries. In:Proc. of the IEEE Int'l Conf. on Mobile Data Management. 2015.[doi:10.1109/MDM.2015.49] |
| [105] | Ma S, Zheng Y, Wolfson O. Real-Time city-scale taxi ridesharing. IEEE Trans. on Knowledge & Data Engineering, 2015, 27(7): 1782–1795 . [doi:10.1109/TKDE.2014.2334313] |
| [106] | Li RH, Qin L, Yu J, Mao R. Optimal multi-meeting-point route search. IEEE Trans. on Knowledge & Data Engineering, 2016, 28(3): 770–784 . [doi:10.1109/TKDE.2015.2492554] |
| [107] | Duan X, Jin C, Wang X. POP:A passenger-oriented partners matching system. In:Proc. of the IEEE Data Engineering Workshops (ICDEW). 2015. 117-118.[doi:10.1109/ICDEW.2015.7129560] |
| [108] | Yan D, Zhao Z, Ng W. Efficient processing of optimal meeting point queries in Euclidean space and road networks. Knowledge and Information Systems, 2015, 42(2): 319–351 . [doi:10.1007/s10115-013-0686-y] |
| [109] | Li M, Li X, Yin J. TORD problem and its solution based on big trajectories data. IEEE Trans. on Intelligent Transportation Systems, 2015: 1–12 . [doi:10.1109/TITS.2015.2491269] |
| [110] | Visvalingam M, Whyatt JD. The Douglas-Peucker algorithm for line simplification:Re-evaluation through visualization. In:Proc. of the Computer Graphics Forum. Elsevier North-Holland, Inc., 1990. 213-228. |
| [111] | Li FF, Cheng DH, Hadjieleftheriou M, Kollios G, Teng SH. On trip planning queries in spatial databases. In:Proc. of the Advances in Spatial and Temporal Databases. Berlin, Heidelberg:Springer-Verlag, 2005. 273-290.[doi:10.1007/11535331_16] |
| [112] | Aljubayrin S, He Z, Zhang R. Skyline trips of multiple POIs categories. In:Proc. of the Database Systems for Advanced Applications. Springer Int'l Publishing, 2015. 189-206.[doi:10.1007/978-3-319-18123-3_12] |
| [113] | Goto T, Kosaka T, Noborio H. On the heuristics of A* or A algorithm in ITS and robot path-planning. In:Proc. of the Int'l Conf. on Intelligent Robots and Systems, Vol.2. 2003. 1159-1166.[doi:10.1109/IROS.2003.1248802] |
| [114] | Yin X, Ding Z, Li J. Moving continuous neighbor queries in spatial network databases. In:Proc. of the IEEE World Congress on Computer Science and Information Engineering. 2009. 535-541.[doi:10.1109/CSIE.2009.626] |
| [115] | Geisberger R, Vetter C. Efficient routing in road networks with turn costs. In:Proc. of the Experimental Algorithms. Berlin, Heidelberg:Springer-Verlag, 2011. 100-111.[doi:10.1007/978-3-642-20662-7_9] |
| [116] | Qiao M, Cheng H, Chang L, Yu J. Approximate shortest distance computing:A query-dependent local landmark scheme. IEEE Trans. on Knowledge & Data Engineering, 2012, 26(1): 462–473 . [doi:10.1109/TKDE.2012.253] |
| [117] | Efentakis A, Pfoser D, Vassiliou Y. SALT:A unified framework for all shortest-path query variants on road networks. In:Proc. of the Experimental Algorithms. Springer Int'l Publishing, 2014. 298-311.[doi:10.1007/978-3-319-20086-6_23] |
| [118] | Goldberg AV, Harrelson C. Computing the shortest path:A search meets graph theory. In:Proc. of the Soda. Society for Industrial and Applied Mathematics. 2010. 156-165. |
| [119] | Delling D, Werneck RF. Faster customization of road networks. In:Proc. of the Experimental Algorithms. 2013. 30-42.[doi:10.1007/978-3-642-38527-8_5] |
| [120] | Efentakis A, Pfoser D. GRASP:Extending graph separators for the single-source shortest-path problem. In:Proc. of the Algorithms. Berlin, Heidelberg:Springer-Verlag, 2014. 358-370.[doi:10.1007/978-3-662-44777-2_30] |
| [121] | Delling D, Goldberg AV, Pajor T, Werneck R. Robust distance queries on massive networks. In:Proc. of the Algorithms. Berlin, Heidelberg:Springer-Verlag, 2014. 321-333.[doi:10.1007/978-3-662-44777-2_27] |
| [122] | Shekelyan M, Jossé G, Schubert M. ParetoPrep:Efficient lower bounds for path skylines and fast path computation. In:Proc. of the Advances in Spatial and Temporal Databases. Springer Int'l Publishing, 2015. 40-58.[doi:10.1007/978-3-319-22363-6_3] |
| [123] | Gupta A, Lakshmi J, Nandy SK. Real time routing in road networks. In:Proc. of the IEEE 4th Int'l Conf. on Big Data and Cloud Computing. 2014. 9-16.[doi:10.1109/BDCloud.2014.85] |
| [124] | Lee KCK, Lee WC, Zheng B, Tian Y. ROAD:A new spatial object search framework for road networks. IEEE Trans. on Knowledge & Data Engineering, 2010, 24(3): 547–560 . [doi:10.1109/TKDE.2010.243] |
| [125] | Zhu CJ, Lam KY, Cheng RCK, Poon CK. On using broadcast index for efficient execution of shortest path continuous queries. Information Systems, 2015, 49(C): 142–162 . [doi:10.1016/j.is.2014.12.005] |
| [126] | Zhu CJ, Lam KY, Han S. Approximate path searching for supporting shortest path queries on road networks. Information Sciences, 2015, 325: 409–428 . [doi:10.1016/j.ins.2015.06.045] |
| [127] | Zhong R, Li G, Tan KL, Zhou L, Gong Z. G-Tree:An efficient and scalable index for spatial search on road networks. IEEE Trans. on Knowledge & Data Engineering, 2015, 27: 2175–2189 . [doi:10.1109/TKDE.2015.2399306] |
| [128] | Yan D, Cheng J, Ng W, Liu S. Finding distance-preserving subgraphs in large road networks. In:Proc. of the IEEE Data Engineering (ICDE). 2013. 625-636.[doi:10.1109/ICDE.2013.6544861] |
| [129] | Felipe ID, Hristidis V, Rishe N. Keyword search on spatial databases. In:Proc. of the IEEE Int'l Conf. on Data Engineering. 2008. 656-665.[doi:10.1109/ICDE.2008.4497474] |
| [130] | Hariharan R, Hore B, Li C, Mehrotra S. Processing Spatial-Keyword (SK) Queries in Geographic Information Retrieval Systems. In:Proc. of the Int'l Conf. on Scientific & Statistical Database Management, 2007.[doi:10.1109/SSDBM.2007.22] |
| [131] | Zhou Y, Xie X, Wang C, Guo Y, Ma W. Hybrid index structures for location-based web search. In:Proc. of the ACM CIKM Int'l Conf. on Information and Knowledge Management. 2005. 155-162.[doi:10.1145/1099554.1099584] |
| [132] | Li Z, Lee KCK, Zheng B, Lee W, Lee D, Wang X. IR-Tree:An efficient index for geographic document search. IEEE Trans. on Knowledge & Data Engineering, 2011, 23(4): 585–599 . [doi:10.1109/TKDE.2010.149] |
| [133] | Zhang D, Chee YM, Mondal A, Tung A, Kitsuregawa M. Keyword search in spatial databases:Towards searching by document. In:Proc. of the IEEE Int'l Conf. on Data Engineering. 2009. 688-699.[doi:10.1109/ICDE.2009.77] |
| [134] | Guo L, Shao J, Aung HH, Tan K. Efficient continuous top-k spatial keyword queries on road networks. Geoinformatica, 2014, 19(1): 29–60 . [doi:10.1007/s10707-014-0204-8] |
| [135] | Li W, Guan J, Zhou S. Efficiently evaluating range-constrained spatial keyword query on road networks. In:Proc. of the Database Systems for Advanced Applications. Berlin, Heidelberg:Springer-Verlag, 2014. 283-295.[doi:10.1007/978-3-662-43984-5_21] |
| [136] | Li YH, Li GH, Shu LC. Continuous monitoring of top-k spatial keyword queries in road networks. Journal of Information Science and Engineering, 2015, 31: 1831–1848 . http://www.airitilibrary.com/Publication/Index?DocID=10162364-201511-201511180003-201511180003-1831-1848 |
| [137] | Gao Y, Zhao J, Zheng B, Chen G. Efficient collective spatial keyword query processing on road networks. IEEE Trans. on Intelligent Transportation Systems, 2015, 8(1): 1–12 . [doi:10.1109/TITS.2015.2477837] |
| [138] | Gao Y, Qin X, Zheng B, Chen G. Efficient reverse top-k Boolean spatial keyword queries on road networks. IEEE Trans. on Knowledge & Data Engineering, 2015, 27(5): 1205–1218 . [doi:10.1109/TKDE.2014.2365820] |
| [139] | Fang H, Zhao P, Sheng VS, Wu J, Xu J, Liu A, Cui Z. Effective spatial keyword query processing on road networks. In:Proc. of the Databases Theory and Applications. Springer Int'l Publishing, 2015. 194-206.[doi:10.1007/978-3-319-19548-3_16] |
| [140] | Zhao P, Kuang X, Sheng VS, Xu J, Wu J, Cui Z. Scalable top-k spatial image search on road networks. In:Proc. of the Database Systems for Advanced Applications. Springer Int'l Publishing, 2015. 379-396.[doi:10.1007/978-3-319-18123-3_23] |
| [141] | Liu XP, Wan CX, Liu DX, Liao GQ. Survey on spatial keyword search. Ruan Jian Xue Bao/Journal of Software, 2016, 27(2): 329–347 (in Chinese with English abstract). http://www.jos.org.cn/ch/reader/view_abstract.aspx?flag=1&file_no=4934&journal_id=jos [doi:10.13328/j.cnki.jos.004934] |
| [142] | Piao C, Li X. Privacy preserving-based recommendation service model of mobile commerce and anonimity algorithm. In:Proc. of the IEEE e-Business Engineering (ICEBE). 2015. 420-427.[doi:10.1109/ICEBE.2015.77] |
| [143] | Kim YK, Hossain A, Hossain AA, Chang JW. Hilbert-Order based spatial cloaking algorithm in road network. Concurrency & Computation Practice & Experience, 2013, 25(1): 143–158 . [doi:10.1002/cpe.2844] |
| [144] | Dang TK, Nguyen VN, Vu DL, Kung J. Utilizing spatio-temporal data index for location privacy protection. In:Proc. of the Database and Expert Systems Applications (DEXA). 2013. 15-20.[doi:10.1109/DEXA.2013.7] |
| [145] | Um JH, Kim HD, Chang JW. An advanced cloaking algorithm using Hilbert curves for anonymous location based service. In:Proc. of the IEEE Int'l Conf. on Privacy, Security, Risk and Trust. 2010. 1093-1098.[doi:10.1109/SocialCom.2010.162] |
| [146] | Gustav YH, Wu X, Ren Y, Wang Y, Zhang F. Dummy based privacy preservation in continuous querying road network services. In:Proc. of the IEEE Cyber-Enabled Distributed Computing and Knowledge Discovery (CyberC). 2014. 94-101.[doi:10.1109/CyberC.2014.24] |
| [147] | Gustav YH, Wu X, Ren Y, Wang Y, Zhang F. Achieving absolute privacy preservation in continuous query road network services. In:Proc. of the Advanced Data Mining and Applications. Springer Int'l Publishing, 2014. 279-292.[doi:10.1007/978-3-319-14717-8_22] |
| [148] | Chim TW, Yiu SM, Hui LCK, Li VOK. VSPN:VANET-based secure and privacy-preserving navigation. IEEE Trans. on Computers, 2014, 63(2): 510–524 . [doi:10.1109/TC.2012.188] |
| [149] | Wang L, Meng XF. Location privacy preservation in big data era:A survey. Ruan Jian Xue Bao/Journal of Software, 2014, 25(4): 693–712 (in Chinese with English abstract). http://www.jos.org.cn/ch/reader/view_abstract.aspx?flag=1&file_no=4551&journal_id=jos [doi:10.13328/j.cnki.jos.004551] |
| [150] | Ray S. Towards high performance spatio-temporal data management systems. In:Proc. of the IEEE Int'l Conf. on Mobile Data Management (MDM). 2014. 19-22.[doi:10.1109/MDM.2014.61] |
| [151] | Sun F, Wang L. Performance analysis of B+-tree and CSB+-tree in main memory database. In:Proc. of the IEEE Workshop on Electronics, Computer and Applications. 2014. 265-268.[doi:10.1109/IWECA.2014.6845607] |
| [152] | Liu L, Qin XL, Zheng GN, Li BH. An energy-efficient spatial window query processing algorithm in wireless sensor networks. Chinese Journal of Computers, 2011, 34(5): 763–778 (in Chinese with English abstract). [doi:10.3724/SP.J.1016.2011.00763] |
| [153] | Wang TC, Qin XL, Liu L, Ding YW. Secure and energy-efficient spatial data aggregation algorithm in wireless sensor networks. Ruan Jian Xue Bao/Journal of Software, 2014, 25(8): 1671–1684 (in Chinese with English abstract). http://www.jos.org.cn/ch/reader/view_abstract.aspx?flag=1&file_no=4663&journal_id=jos [doi:10.13328/j.cnki.jos.004663] |
| [154] | Ren SL, Tao YB, Lin H. Interactive visual analysis of fake plate vehicles detection. Journal of Computer-Aided Design & Computer Graphics, 2016, 28(11): 1887–1897 (in Chinese with English abstract). [doi:10.3969/j.issn.1003-9775.2016.11.010] |
| [1] | 乔少杰, 韩楠, 王超, 祝峰, 唐常杰. 基于路网的移动对象动态双层索引结构. 计算机学报, 2014(9): 1947–1958. http://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201409005.htm |
| [9] | 徐红波, 郝忠孝. 一种基于Z曲线近似k-最近对查询算法. 计算机研究与发展, 2008, 45(2): 310–317. http://www.cnki.com.cn/Article/CJFDTOTAL-JFYZ200802014.htm |
| [13] | 张敬敏, 王培崇, 路凤佳. 道路网络中的移动对象索引方法研究. 计算机工程与应用, 2009, 45(12): 144–146. [doi:10.3778/j.issn.1002-8331.2009.12.047] |
| [15] | 丁治明, 李肖南, 余波. 网络受限移动对象过去、现在及将来位置的索引. 软件学报, 2009, 20(12): 3193–3204. http://www.jos.org.cn/ch/reader/view_abstract.aspx?flag=1&file_no=3400&journal_id=jos [doi:10.3724/SP.J.1001.2009.03400] |
| [25] | 丁治明. 一种适合于频繁位置更新的网络受限移动对象轨迹索引. 计算机学报, 2012, 35(7): 1448–1461. [doi:10.3724/SP.J.1016.2012.01448] |
| [27] | 冯钧, 史涯晴, 唐志贤, 芮彩华. 路网移动对象聚集索引技术. 吉林大学学报:工学版, 2014, 44(6): 1799–1805. http://www.cnki.com.cn/Article/CJFDTOTAL-JLGY201406041.htm |
| [36] | 郭黎敏, 丁治明, 胡泽林, 陈超. 基于路网的不确定性轨迹预测. 计算机研究与发展, 2010, 47(1): 104–112. http://www.cnki.com.cn/Article/CJFDTOTAL-JFYZ201001016.htm |
| [43] | 乔少杰, 李天瑞, 韩楠, 高云君, 元昌安, 王晓腾, 唐常杰. 大数据环境下移动对象自适应轨迹预测模型. 软件学报, 2015, 26(11): 2869–2883. http://www.jos.org.cn/ch/reader/view_abstract.aspx?flag=1&file_no=4889&journal_id=jos [doi:10.13328/j.cnki.jos.004889] |
| [50] | 许潇, 冯钧, 陆佳民, 唐志贤, 张立霞. HINMO:基于Hadoop平台的路网移动对象分布式索引结构. 计算机研究与发展, 2015(S1). http://www.cnki.com.cn/Article/CJFDTOTAL-JFYZ2015S1011.htm |
| [59] | 郭薇, 郭菁, 胡志勇. 空间数据库索引技术. 上海: 上海交通大学出版社, 2006. |
| [61] | 马友忠, 孟小峰. 云数据管理索引技术研究. 软件学报, 2015, 26(1): 145–166. http://www.jos.org.cn/ch/reader/view_abstract.aspx?flag=1&file_no=4688&journal_id=jos [doi:10.13328/j.cnki.jos.004688] |
| [141] | 刘喜平, 万常选, 刘德喜, 廖国琼. 空间关键词搜索研究综述. 软件学报, 2016, 27(2): 329–347. http://www.jos.org.cn/ch/reader/view_abstract.aspx?flag=1&file_no=4934&journal_id=jos [doi:10.13328/j.cnki.jos.004934] |
| [149] | 王璐, 孟小峰. 位置大数据隐私保护研究综述. 软件学报, 2014, 25(4): 693–712. http://www.jos.org.cn/ch/reader/view_abstract.aspx?flag=1&file_no=4551&journal_id=jos [doi:10.13328/j.cnki.jos.004551] |
| [152] | 刘亮, 秦小麟, 郑桂能, 李博涵. 能量高效的无线传感器网络空间范围查询处理算法. 计算机学报, 2011, 34(5): 763–778. [doi:10.3724/SP.J.1016.2011.00763] |
| [153] | 王涛春, 秦小麟, 刘亮, 丁有伟. 无线传感器网络中安全高效的空间数据聚集算法. 软件学报, 2014, 25(8): 1671–1684. http://www.jos.org.cn/ch/reader/view_abstract.aspx?flag=1&file_no=4663&journal_id=jos [doi:10.13328/j.cnki.jos.004663] |
| [154] | 任水林, 陶煜波, 林海. 交互式套牌车可视识别与分析. 计算机辅助设计与图形学学报, 2016, 28(11): 1887–1897. [doi:10.3969/j.issn.1003-9775.2016.11.010] |