0 摘要

定位设备数量的增加促进了对两个基本问题的研究：基于路网的距离计算和将移动对象作为POI的查询处理能力。现有研究几乎没有能够同时解决这两个问题的技术，本文提出一个新方法解决持续性范围查询问题，提出了一个支持路网上移动对象基于位置的快照查询的索引（MOVNet），介绍了几个特征实现持续性查询。为了减轻频繁的对象更新对算法性能的影响，本文引入了一种基于最短路径的树（SD-Tree），它可以保留和重用路网的连通性及距离信息。

1 引言

基于位置的服务，包括道路辅助、基于位置的游戏以及位置共享的社交网路，增加了设计新颖可伸缩的基于位置的服务的研究兴趣。

已有的技术结合了POI移动性研究和网络距离计算其中之一，在路网中进行POI移动性研究的主要挑战来自两个方面：1）高效地对象位置更新管理；2）提供快速网络距离计算。

基于位置的快照查询处理：MOVNet，集中式双重索引结构。磁盘上是R*-tree，用来存储路网的连通性信息；内存中是网格索引，用来高效处理移动对象的位置更新。（索引设计原因：1）R-tree被广泛用于大规模静态空间数据集的高效处理；2）网格索引被验证适合对动态空间数据的管理。）

持续性查询处理：（挑战）内存和计算资源的昂贵消耗，（动机）持续性研究提供一个关于对象运动变化的长期视角，适合用于检测。（本文解决）1）扩展MOVNet，给每个网格增加connecting vertices，提前计算每个网格中的距离表；2）提出基于最短距离的树（SD-Tree），保留用于持续性查询处理的网络连通性和距离信息。

2 相关研究工作

网络距离下的静态POI的空间查询：Papadias【03VLDB】欧式受限和网络扩展算法，以欧式距离作为下界；VN^3方法【04VLDB】，Voronoi区域划分，避免在线的距离计算；【08SIGMOD】为降低提前计算的距离的存储空间，对距离进行编码。

网络中的静态POI的持续性KNN查询：Shahaibi【04STDBM】相交检测和上界算法，计算路径上所有节点的近邻；Hu【06EDBT】提出一个基于树的结构记录路网的图拓扑，传统的网络扩展被替换为树中的可以被提前计算的路径扩展。

评价：这些研究工作都是针对静态的POI，提前的距离计算使查询非常高效，但是却不能应用于动态环境中持续移动的POI。

欧式距离下的移动POI空间查询：基于树结构的索引被广泛应用于静态的空间数据，但在动态的位置更新的情况下面临昂贵的重建代价；TPR-Tree【03VLDB】【00SIGMOD】和B^x【04VLDB】树假设移动对象的运动可以被表示为一个函数，该函数仅在对象速度发生变化的时候需要改变；将网格索引用于简单高效的移动对象管理中，用以降低更新和查询代价；Hu【05SIGMOD】提出safe region的概念用以减少用户客户端的位置更新；Yu【05ICDE】根据前一个KNN的最远距离，定义一个搜索区域。

评价：这些技术仅考虑欧式距离的计算，不适合基于网络距离计算的应用场景。

网络路径距离下动态POI的查询：Jensen【03GIS】提出概要结构进行对象更新和KNN查询，与本文的MOVNet不同在于MOVNet是一个集中式结构来周期性更新对象位置，而Jensen的方法假设用户愿意参与KNN查询；Mouratidis【06VLDB】提出IMA和GMA，基于内存的结构存储网络连通性，难以应对大的路网数据；Stojanovic【08DKE】提出了一个监测静态和移动对象范围近邻查询的方法。

评价：这些研究需要移动对象愿意向服务器提前发送位置记录，从而将移动到路径上的POI作为候选结果。

---

总结：已有持续性的计算主要解决动态数据的更新，路网距离的预计算、存储与查询，近邻查询三大问题。动态数据更新的解决思路主要有：1）采用网格索引进行对象管理；2）采用safe region对移动对象的位置更新进行过滤。路网距离预计算与查询的解决思路主要有：1）采用MBR相交检测或者空间上界进行过滤；2）基于树结构记录路网的拓扑关系，并提前计算树中的路径距离。近邻查询的解决思路有：在假设移动对象会提前报告自己位置更新的前提下，监测已有的范围内近邻的变化，从而对静态和移动对象的范围近邻进行监测。

---

3 系统设计

本章包括数据结构设计和持续性范围近邻查询算法（C-MNDR）。后者又分为初始化计算、移动对象更新和Overview。

3.1 数据结构设计

双重索引结构进行快照查询处理，包括：1）基于磁盘的R*-tree，存储静态的路网数据，边被存储为端点的MBR；2）基于内存的网格索引，存储移动POI的位置，当对象向服务器发送位置更新时，服务器触发一个路网匹配程序将对象定位到路段上。

Connecting Vertices：网格单元中至少有一条邻接边跨越网格单元边界。例如，图1中c(0,1)中的v1,v2,v3和v5。

POI：路网中的移动对象。例如，图1中的m1,m2,...。

图1 网格索引示例

Object List：移动对象列表。  Object Array：移动对象的信息表。

Connecting Vertex List：某个网格单元的连接节点与其他网格单元中相连的节点的邻接表及距离。

当发起一个查询时，会以该查询所在的网格单元的边界作为MBR去磁盘中检索该网格单元中的边，并在内存中构建如下图模型。该模型包括：

Vertex List：网格单元内的顶点列表。

Edge List：网格单元内每个顶点邻接的边的列表，包括另一个顶点和边长。

Vertex Coordinates：节点的坐标信息表。

例：图2是图1中c(0,1)在内存中的图模型。

图2 C-MNDR的数据结构

3.2 持续性范围近邻查询算法

持续性基于网络距离的范围查询：给定查询点q，距离阈值d，网络G，移动对象集M，时间段[t1,t2]，持续性基于网络距离的范围查询返回在时间段[t1,t2]内，每个时刻下与查询点网络距离在d范围内的对象集。

解决方法：获得初始时刻的查询结果，在后续的时刻监测POI位置的改变，更新查询结果。

3.2.1 计算初始查询结果

第一步：构建查询点所在的网格单元的图模型。

第二步：计算q到每个节点的迪杰斯特拉距离（最短路径距离）。

第三步：从q开始扩展边，将在d范围内的边（节点）入队列，若q到connecting vertex的距离小于d，则继续扩展其他网格（读数，构建图模型）。

第四步：获取范围内的移动对象。根据前面的节点距离计算结果，计算查询点到对象的距离，并将小于d的插入结果集。

3.2.2 SD-tree——监测被持续性查询影响到的边

SD-tree：是一个由在查询范围内的节点构成的树结构，根节点是查询点q，由根节点到下面每个节点的路径就是查询点到该路网节点的最短路径。如图3所示。

图3 SD-tree示例

SD-tree的分支构建了一个对查询点的范围近邻的监测区域，在持续性查询中，只需持续检测该区域的变化即可完成查询结果的更新。

（对于查询点q位置发生变化时SD-tree的更新问题，本介绍省略，感兴趣者自行阅读论文。）

3.2.3 完整的持续性范围查询处理过程

第一步：收到查询请求后，实现查询结果的初始化处理。初次查询完成的同时，构建完成相应的SD-tree。

第二步：MOVNet检测查询点q的位置是否改变：没变，只需对SD-tree进行监测；不在SD-tree区域内，重新执行第一步；还在SD-tree内，则对检测区域进行调整。