一种基于路网的连续最近邻查询算法.doc

一种基于路网的连续最近邻查询算法
摘 要：在路网中，连续最近邻（Continuous Nearest Neighbor，CNN）查询在基于位置的服务中尤为关键。现有的查询处理方法大多依赖于路网中查询对象的分布密度，其他处理方法如UNICONS等改进了这些不足。然而在查询对象密集分布的路网中，存在无效计算最近邻（Nearest Neighbor，NN）的问题。针对这个问题，本文提出并证明了非交叉点子路径中的预计算方法，并基于该方法提出了CNN查询算法。该算法利用分治法以交叉点为划分依据，将查询路径划分成子路径，然后对子路径中的结点进行NN查询，从而降低了NN查询的计算代价。通过实验，验证了本文提出的查询处理方法在CNN查询中的正确性和有效性，性能优势尤为明显。
关键词：连续最近邻查询; 基于位置的服务; UNICONS; 预计算方法; 分治算法
Algorithm for CNN Query over Road Network
Wang Heng1,2 Ying-Yuan Xiao1,2
1Tianjin Key Laboratory of Intelligence Computing and Novel Software Technology, Tianjin University of Technology，300384, Tianjin
2Key Laboratory of Computer Vision and System （Tianjin University of Technology）, Ministry of Education, 300384, Tianjin
Abstract In Road Network (RN), Continuous Nearest Neighbor (CNN) query frequently used in Location-Based Services (LBS). The majority of the existing works on CNN queries are largely affected by the density of objects of interest, others such as UNICONS overcome these problems, yet there may be over-calculating problem. In this paper, we propose and proof a pre-computation theory based on non-intersection path, and then presented an algorithm for CNN query, which uses divide and conquer method to query NN on sub path, where is divided the query path into sub path based on non-intersection points, and then to reduce the computational cost. Experimental results show that our processing approach in the CNN query is correct and effective, especially the result is well performance when the intersection points sparsely distributed.
Keywords CNN; LBS; UNICONS; pre-computation; divide and conquer method
1 引言
随着移动计算、无线通讯、GIS（Geographic Information System）、以及GPS空间定位、空间网络数据库（Spatial Network Database，SNDB）等技术的迅速发展，基于位置的服务（Location-Based-Service, LBS）得到了广泛的应用。连续最近邻（Continuous Nearest Neighbor）查询[1]作为LBS中重要的查询类型，引起了国内外学者的关注。
现有的查询处理方法大多采用预计算的方法，该方法首先对路网进行处理（如空间区域划分、裁剪等），然后预先计算路网中结点的NN并进行存储，最后处理查询路径上的CNN。与其他查询处理方法相比，该方法明显提高了查询的性能，并得到深入的研究。研究成果有：Feng等人[2]提出一种启发式的区域裁剪算法，通过该算法获得预计算的查询区域（r-region），然后计算查询路径上每个结点的NN。但该方法只能解决k=1的CNN查询问题。之后，Kolahdouzan 等人[3]提出了基于VN3（Voronoi-Based Network Nearest Neighbor）[4]的CNN查询处理算法UBA（Upper Bound Algorithm）。但该方法需要进行大量的NN查询来查找划分点，并且查询NN的VN3方法，依赖于路网中查询对象的分布密度和k值的大小，计算代价相对较高，并且该方法在路网信息更新时的代价也相对较高。随后，Cho等人[5]提出了一种UNICONS（a Unique Continuous Search algorithm）处理方法，该方法首先通过预计算方法，获得查询路径中所有结点的NN对象列表，然后利用该列表，运用Dijkstra算法进行查询处理。该方法的优势是不依赖路网中查询对象的分布密度，因此表现出较好的性能。但研究发现在处理查询的候选子集时，没有考虑非交叉点子路径下查询的特殊性，从而导致了无效的预计算。近来，Huang等人[6]引入了预计算结构S-GRID（Scalable Grid）来简化空间网络，有效地计算查询的边界区域。但是该方法假设路网中边的权重为静态的，因此在静态路网中，有较好的性能；而在动态路网中，性能较差。最近，Samet等人[7]利用标签来检索最短路径四叉树的方法，进行几何裁剪路网空间，然后查询网络路径。Demiryurek等人[8]提出ER-CkNN（short for Euclidian Restriction based CkNN）方法来解决移动查询对象在动态变化的移动数据空间网络中的CNN查询。
分析现有的研究，针对UNICONS查询处理方法存在的不足，本文提出并证明了特殊路径下（具有非交叉点的路径）的预计算方法，降低了预计算的代价，并且使得预计算方法更具通用性。此外，基于该方法，本文提出一种有效的CNN查询处理算法，并通过实验对UNICONS方法和本文处理方法进行比较，验证了本文处理方法的正确性和优越性。
2 基本理论与预计算方法
2.1 NN查询的相关定义
首先，本文定义路网中NN查询相关的一些基本内容。主要包括交叉点、非交叉点、网络距离以及NN查询。
定义1 一个结点如果有三条及其以上边数汇集而成，称为交叉点。否则为非交叉点。
定义2 如果两个结点ni、nj不邻接，那么d(ni, nj)表示从ni到nj的网络最短路径长度而非欧氏距离。
定义3 NN查询就是在路网中的任意查询点q，检索最近的k个查询对象，集合Rq表示符合查询条件的点。
图1是路网（旧金山市区域路段）中的实例，其中{n1, n2,…, n20}表示路网中的结点(node)；{a, b,…, f}表示要查询的对象，假设为加油站；交叉点如图1中有三条及以上边相交的结点{n1, n2, n8,…}。查询点q 发出查询最近的2个加油站的请求，此类查询就是NN查询。此时q的查询结果Rq = {f, c}，其中q到f的网络距离为d(q, f) = d(q, n5) + d(n5, f)；q到c的网络距离为d(q, c) = d(q, n10) + d(n10, n12)+ d(n12, n11)+ d(n11, c)。

图1 旧金山市区域路网查询实例

2.2 预计算方法
引理1 假设查询点q位于邻接边上，其中Rq表示在邻接边上满足条件的查询对象的集合，O表示位于邻接边上的查询对象的集合，而Rni 和 Rnj则表示在结点ni 和 nj处满足条件的查询对象的集合。则：Rq (O ∪ Rni ∪ Rnj )。
引理2 假设查询点q在查询路径path = {ni1, ni2, …, nij}的任意位置，Rq表示在path的任何位置，满足条件的查询对象的集合；Opath表示所有落在path上的对象的集合；而Rnik (1 k j)表示在path的任意结点nik (1 k j)上满足查询条件的对象的集合。
则：Rq Opath ∪ Rni1 ∪… ∪Rnik ∪… ∪ Rnij
引理3 如果Rstart = Rend 并且 Osubpath ⊂ Rstart，当且仅当在subpath中没有划分点。
其中，引理1陈述了邻接边上的NN查询处理方法；引理2扩展引理1，得到整个路径中的NN查询；而引理3给出了判断划分点的条件。这些引理在文献[5]中进行了详细证明。
2.3 子路径预计算方法
基于引理1和引理2，本文将预计算方法扩展到特殊路径中，提出了适用于非交叉点路径的预计算方法，得到引理4，并给予证明。而引理3判断划分点的条件，同样也适用于引理4。
引理4 假设在非交叉点子路径subpath ={ni,1, ni,2, …, ni,j}上，其中，Rsubpath表示在subpath的任意位置，满足查询条件的对象的集合；Osubpath表示所有落在subpath上的对象的集合；而Rni,k (1 k j)表示在subpath的任意结点ni,k(1 k j)上满足查询条件的对象的集合。
则： Rsubpath Osubpath ∪ Rni,1 ∪ Rni,j
证明：对查询点 q ∈ subpath，Rq表示在q点满足查询条件的对象的集合。
则由引理2可得： Rq Osubpath ∪ Rni,1 ∪ Rni,2 … ∪ Rni,j
假设q在任意的边 (1 k < j)上，则最近邻的网络距离d(q, p)可以定义为：
d(q, p) = min {(d(p, ni,1) + d(ni,1, ni,2) + … + d(ni,k-1, ni,k) + d(ni,k, q)), ( d(q, ni,k+1) + d(ni,k+1, ni,k+2) + … + d(ni,j-1, ni,j) + d(ni,j, p)), (d(q, ni,k+1) + d(ni,k+1, oa)), (d(oa, ni,k) + d(ni,k, q)), (d(oa, q))}; 其中，oa ∈ Osubpath，p 是 q的NN。
为了证明p ∈ Osubpath ∪ Rni,1 ∪ Rni,j，
即(p ∈ Osubpath ∪ p ∈ Rni,1 ∪ p ∈ Rni,j) ó ￢ ( p Osubpath ∩ p Rni,1 ∩ p Rni,j )
假设p Rni,1，那么 p’ 是ni,1 (即 p’ ∈ Rni,1)的NN。于是有(d(p, ni,1) + d(ni,1, ni,2) + … + d(ni,k-1, ni,k) + d(ni,k, q)) > (d(p’, ni,i) + d(ni,1, ni,2) + … + d(ni,k-1, nk) + d(ni,k, q))
因此，q的NN不是p而是p’，这与之前的定义矛盾。同理可以证明p Osubpath 和 p Rni。最终得证Rq Osubpath ∪ Rni,1 ∪ Rni,j (q 在subpath的任意边上)。证毕。□
图2详细解释了引理3的基本思想。其中，查询路径subpath = {n1, n3, n5, n10, n12}，查询对象a, b, c, d, e 和 f，n1, n12是交叉点。那么，查询路网中k = 2个NNs，可以得Rn1 = {a, f}，Rn12 = {c, e}，Op = {f}。而Rn3 = {f, a}，Rn5 = {f, a}， Rn10 = {c, e}。因此，Rsubpath Osubpath ∪ Rn1 ∪ Rn12，与引理4结论相符。

图2路径的NNs查询

3 CNN查询及其算法
3.1 查询处理方法
基于引理4，本文提出了一种分治查找子路径中结点的NN处理方法，具体过程如下：
第一步：通过查询路径中邻接边的数目大于2的结点，即交叉点。然后根据交叉点将路径划分成子路径，并且按照从查询路径的开始结点到结束结点按序保存；
第二步：对子路径集合中每条子路径，查询子路径开始和结束结点的最近邻，根据引理3进行判断。如果存在划分点，通过分治查找子路径中结点的NNs。
第三步：组合各子路径的查询结果，得到最终CNN的划分点和查询结果。
3.2 算法描述
根据以上查询处理过程，本文对各个算法进行详细的描述，具体如下：
算法1描述了第一步中根据交叉点将查询路径划分成子路径，并按序将子路径保存的处理过程。其中getCount(node)用于获得结点的邻接边数目；set_Subpath(subpathId, startId, endId)用于保存子路径。
算法 1 Split_Path(path)
Input: path (Query path over RN)
Output: set of subpath
begin
1. /*For each node in the path, checking it is intersection point or not*/
2. for each node in path
3. v_count = getCount(node);
4. if v_count > 2 then
5. set_Subpath(subpathId, startId, endId);
6. end if
7. end for
end

算法2描述了第二步中查询子路径中开始和结束结点的NNs，以及扫描子路径上查询对象的处理方法。首先，定义一些在路网中的原操作：nearestNeighbors(Networks, nodeQuery, noNNs)用于基于路网Networks查询nodeQuery结点的n个NNs；getCost()用于获得查询NN的代价；Scan_Subpath(subpath)用于获得查询路径上的NNs集合。则具体算法描述如下：

算法 2 Get_ NN_SE
Input: subpath (a segment with non-intersection points) ;
k ( the number of NNs to be retrieved)
Output: sets of NNs about start and end point
begin
1. /* Returns the shortest paths of the k nearest neighbors from the start node.*/
2. Path[] Rstart := nearestNeighbors(Net, nstart, k)
3. /* Returns the shortest paths of the k nearest neighbors from the end node.*/
4. Path[] Rend := nearestNeighbors(Net, nend , k)
5. for each path in Rstart
6. nstart_ Pathcost [i] := getCost() //Get the path cost
7. end for
8. for each path in Rend
9. nend_ Pathcost [i] := getCost() //Get the path cost
10. end for
11. /* Scanning the subpath, and store the interest points among the subpath */
12. Osubpath := Scan_Subpath(subpath)
end

算法3则通过算法1获得的查询集合，运用引理3判断是否存在划分点。如果存在划分点，则进行分治查找子路径中的结点。其主要思想是利用分治法来计算划分点，并以引理3作为终止条件。如果不符合引理3，则算法退化为邻接边上计算划分点的处理方法。其中，findSplit_Points (k, R)用于获得邻接边上划分点，并保存到集合Rsplit中。

算法 3 Div_Conq_CNN_SP (subpath, k)
Input: subpath (a segment with non-intersection points) ; k (the number of NNs to be retrieved)
Output: sets of split point among subpath
begin
1. Get_ NN_SE (subpath, k)
2. if Rstart = Rend and Osubpath Rstart then
3. return /* no split point is on subpath */
4. else if nstart and nend are not adjacent then
5. Rmid :=nearestNeighbors(Net, nmid , k)
6. for each path in Rmid
7. nmid_ Pathcost [i] := getCost() //Get the path cost
8. end for
9. /*subpathsm is the sub of subpath from start point to middle point*/
10. Div_Conq_CNN_SP(subpathsm , k)
11. /*subpathme is the sub of subpath from middle point to end point*/
12. Div_Conq_CNN_SP(subpathme , k)
13. else /* Degenerate into a common question on adjacent edge */
14. /* Find Split Points (k, R) and save the result into Rsplit */
15 Rsplit := findSplit_Points (k , R)
16. end if
end

于是，根据以上的处理方法，CNN查询处理过程如算法4所示。其中，Partition(path, instersectionPoints[])根据交叉点划分为子路径，Combine(CNNsub)将分治查找各子路径的集合合并，得到最终的查询结果。

算法 4 CNN_ Search (path, k)
Input: path (the given path for queries) ; k (the number of NNs to be retrieved)*/
Output: sets of split points among path
begin
1. /*Partition the path into subpaths by intersection points set*/
2. Path [] subpath := Split_Path(path)
3. for each sub in subpath
4. Rsubpath := Div_Conq_CNN_SP(sub, k)
5. end for
6. /* Combining the CNNs to the final result*/
7. Rpath := Combine(CNNsub)
end

3.3 性能分析
算法4表明，算法的时间复杂度主要取决于子路径的数目m。因此，在稀疏的路网中表现更加突出。算法3中的分治查询子路径的处理方法的时间复杂度为O(ln(n))，n表示子路径上结点的数目。因此该方法的时间复杂度最好为O(ln(n))，最差为O(m*ln(n))。
4 实验验证
实验的评估标准为：本文的处理方法和UNICONS处理方法在页请求次数和CPU执行时间两方面进行比较。
实验的硬件配置：Intel 2.40GHz CPU，512MB内存。软件环境：Linux操作系统 + Oracle 11g；编程语言：PL/SQL。
实验数据是California样例数据[9]。实验数据描述如下：结点数｜N｜=21047, 边数｜E｜=21692。选取的查询对象类型有：医院：Category ID：30，记录数｜R｜=835；湖：Category ID：33，记录数｜R｜=2636；公园：Category ID：44，记录数｜R｜=6900；学校：Category ID：50，记录数｜R｜=11173。选取的查询路径为两条交叉点密度分布不同的路径，交叉点密度分别为0.12和0.51。
在交叉点分布密度为0.12的路径中，查询最近邻的数目k值（横轴），与页请求次数（纵轴）之间的关系如图3所示。
由图3可以看出，随着查询最近邻数目k的增加，页请求次数基本呈指数增长。由于查询对象分布不均，图形表现出凹凸现象，但随着查询对象密度的增大，曲线表现的更加圆滑，但性能优势也因查询对象密度的增大有所降低。
从图3中可以看出，本文采用的处理方法比UNICONS方法优势明显，页访问次数基本上减少了一倍。

(a) Hospitals (835)
(b) Lakes (2636)

(c) Parks (6900)
(d) Schools (11173)
图3 最近邻数k与页请求次数的关系图

图4描述了查询最近邻数目k，与CPU执行时间代价（纵轴）的关系。从图中可以看出，随着k值的增大，CPU执行时间成指数增长。并且本文采用的处理方法明显优于UNICONS处理方法。

(a) Hospitals (835)
(b) Lakes (2636)

(c) Parks (6900)
(d) Schools (11173)
图4 最近邻数k与CPU执行时间关系图

在交叉点分布密度为0.51的路径中，随着查询最近邻数k值（横轴）变化，页请求次数（纵轴）的表现如图5所示。从图5可以看出，本文采用的处理方法性能优势明显降低，并且当k较小时，与UNICONS方法的页访问次数基本一致。但随着k的增大，性能仍然优于UNICONS方法。同样，随着查询对象密度的增大，性能优势明显降低。

(a) Hospitals (835)
(b) Lakes (2636)

(c) Parks (6900)
(d) Schools (11173)
图5 最近邻数k与页请求次数的关系图

图6描述了查询最近邻数k，与CPU执行时间代价（纵轴）的关系。其表现与页访问次数密切相关，性能表现与页访问次数也基本一致。

(a) Hospitals (835)
(b) Lakes (2636)

(c) Parks (6900)
(d) Schools (11173)
图6 最近邻数k与CPU执行时间关系图

从以上实验结果可以发现，在交叉点分布稀疏的路径上，无论是页访问次数，还是CPU执行时间，本文的处理方法比UNICONS处理方法在性能上基本提高了一倍，优势明显。在交叉点分布稠密的路径上，本文的处理方法性能有明显的退化，但随着k值的增大，性能仍然优于UNICONS方法。总之，本文提出的处理方法在查询性能上明显优于UNICONS处理方法。
5 结束语
本文主要基于路网的连续最近邻查询处理技术，提出了非交叉点子路径上的预计算方法，并利用该方法提出一种新的分治查询子路径的最近邻查询算法。同时通过实验与UNICONS处理方法在页访问次数和CPU执行时间两方面进行比较，结果表明本文提出的查询处理方法有明显的性能优势。但是本文提出的方法也存在一定的问题，在交叉点分布密集的情况下，性能有明显的退化，这是需要继续解决的问题。此外，本文提出的方法在移动数据空间网络中的CNN查询性能，也是本人进一步研究的问题。
参考文献
[1] Y. Tao, D. Papadias and Q. Shen. Continuous Nearest Neighbor Search[C]// Proceedings of the 28th International Conference on Very Large Data Base (VLDB). Hang Kong, China: ACM Press, 2002: 287-298.
[2] J. Feng and T. Watanabe. Search of Continuous Nearest Target Objects along Route on Large Hierarchical Road Network[C]//Proc. of the Data Engineering Workshop. New York, USA: ACTA Press, 2003: 33-41.
[3] M. Kolahdouzan and C. Shahabi: Continuous K-Nearest Neighbor Queries in Spatial Network Databases[C]//Proceedings of the Second Workshop on Spatio-Temporal Database Management ( STDBM). Toronto, Canada: Citeseer, 2004: 33-40.
[4] M. Kolahdouzan and C. Shahabi: Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases[C]//Proceedings of the 30th International Conference on Very Large Data Base (VLDB). Toronto, Canada: ACM Press, 2004: 840-851.
[5] H.J. Cho, C.W Chung. An Efficient and Scalable Approach to CNN Queries in a Road Network//Proceedings of the 31st VLDB Conference. Trondheim, Norway: ACM Press, 2005: 865-876.
[6] Huang X., Jensen C.S., H. Lu, and S. Saltenis. S-grid: A versatile approach to efficient query processing in spatial networks[C]//Processing of the 10th International Symposium on Spatial and Temporal Databases (SSTD). Boston, USA: Springer, 2007: 93-111.
[7] H. Samet, J. Sankaranarayanan, and H. Alborzi. Scalable network distance browsing in spatial databases[C]//Proceedings of the ACM International Conference on Management of Data(SIGMOD). Vancouver, Canada: ACM Press, 2008: 43-54.
[8] U. Demiryurek, F. Banaei-Kashani, and C. Shahabi. Efficient continuous nearest neighbor query in spatial networks using euclidean restriction[C]//Processing of the 11th International Symposium on Spatial and Temporal Databases (SSTD). Aalborg, Denmark: Springer, 2009: 25-43.
[9] California Road Network and Points of Interest. http://www.cs.fsu.edu/~lifeifei/SpatialDataset
.htm.