受限网络模糊对象最近邻查询

高 峻，郝忠孝,2

受限网络模糊对象最近邻查询

高 峻1，郝忠孝1,2

(1. 哈尔滨理工大学计算机科学与技术学院，哈尔滨 150080；2. 哈尔滨工业大学计算机科学与技术学院，哈尔滨 150001)

针对网络空间中有范围约束、不确定对象的最近邻查询问题，提出范围受限的网络空间模糊对象最近邻查询概念，并根据查询顺序的不同，给出NN-R查询算法和R-NN查询算法。两种算法均采用网络位置信息与连接信息分别存储的方式，使用聚类文件进行组织，减少I/O操作。NN-R算法在近邻查询过程中利用查询对象与受限范围的α-距离作为约束，缩小搜索范围。R-NN算法将受限范围内查询对象的欧氏近邻作为候选对象，利用欧氏距离的下界性与易求性降低时间复杂度。两种算法时间复杂度分别为((log1||+(|*|3+1)log2||+log(lg1))和(log4(+1)log1||+log)。实验结果表明，在各自适用条件下，两种算法均有较好的性能。

确定网络；范围约束；模糊最近邻；α-距离；邻接表；R树

1 概述

随着地理信息系统、空间数据库、物联网、交通控制、多媒体系统和机器人学等领域的发展，复杂空间数据查询的理论与方法成为近年来研究的热点和难点。由于空间数据量庞大，数据结构复杂，数据类型多样，实际应用中对空间数据的查询技术提出了越来越高的要求。当前，如何高效地实现空间数据对象的最近邻查询技术成为空间查询研究的重点。

目前，对自由空间和受限的网络空间中的最近邻查询的研究已取得一定的成果。针对自由空间中最近邻查询方法的研究往往局限在单一空间环境下，在现实需求中覆盖还不够全面。现实中存在自由空间的位置信息和网络空间的连接信息相结合的需求，如在路网中行驶的汽车要找到离它当前位置最近的某区域内的加油站，这就需要受限的网络空间最近邻查询。文献[1]将自由空间与网络空间结合，使用自由空间约束来限制允许路径，如找到仅经过某些区域的最短路径。文献[2]将路网中最近邻查询转化为高维自由空间最近邻查询。文献[3]提出一种结合自由空间和网络空间信息的架构，利用自由空间的位置信息和网络空间的连接信息有效地缩小搜索空间，该方法侧重于空间查询处理的通用性。文献[4]给出位置确定路径的点近邻查询方法。以上研究的受限空间网络和空间对象均是确定的，均未考虑对象的不确定性，所提出的方法在实际应用中具有一定的局限性。空间对象的不确定性导致空间查询和空间分析变得更为复杂。

目前，针对对象不确定性的研究主要集中在自由空间，一般使用概率理论对不确定对象进行处理：如文献[5]给出移动对象环境下不确定对象的概率查询方法；文献[6]给出不确定对象的概率近邻查询方法；文献[7]给出一种支持概率k近邻查询的不确定高维索引。使用模糊集理论对不确定对象进行的处理主要集中在数据类型和运算定义上[8]，而在空间查询方面研究较少。在网络空间，文献[9]对路网中不确定对象使用概率方法给出一种范围查询分析方法；文献[10]给出模糊对象的两种近邻查询方法ad-hoc kNN查询和range kNN查询；文献[11]将路网中不确定对象建模为一区域，然后对这一区域进行近邻查询；文献[12]给出一种受限网络环境下的不确定对象的概率查询方法。

本文基于自由空间模糊对象的最近邻查询，提出范围受限的网络空间模糊对象最近邻查询概念，并根据查询的处理顺序不同，给出两种范围受限的网络空间模糊对象最近邻查询算法：NN-R算法和R-NN算法。两种算法在数据存储形式上均采用网络连接信息，位置信息与模糊对象分别存储方式，其中，连接信息使用邻接表存储，B+树索引；位置信息和模糊对象均采用R树索引，用指针相连。NN-R算法先进行近邻查询再进行范围查询，使用网络空间模糊对象与受限范围的-距离来缩小搜索空间；R-NN算法先进行范围查询再进行近邻查询，利用自由空间欧氏距离的易求性和网络空间距离的关系特点降低时间复杂度。

2 基本概念

为了研究范围受限的网络空间模糊对象最近邻查询方法，本节首先形式化定义了一些重要的基本概念。

定义5(网络空间模糊对象的α-距离) 已知网络空间及其上的模糊对象和、和间的α-距离为：

定义6(网络空间模糊对象与确定范围的α-距离) 已知网络空间及其上的模糊对象和确定范围，确定范围与网络空间交点分别为1,2,…,p。和间的α-距 离为：

定义8(范围受限的网络空间模糊对象k近邻查询) 已知网络空间及其上的模糊对象集、自然数、域值、查询对象、范围约束，范围受限的网络空间模糊k-近邻查询给出位于内与有最小α-距离的个对象。

图1为基本概念示例图。在图1中，设网络空间模糊对象集={,,,}，其中，模糊对象={<1,0.3>,<2,0.6>, <3,0.1>}，1、2、3为模糊对象的模糊点(图中白色圆点)，0.3、0.6、1分别为模糊点对的隶属度。下同，={<1, 0.2>,<2,0.7>,<3,1>}、={<1,0.3>,<2,0.7>,<3,0.9>}、= {<1,0.5>,<2,0.8>,<3,0.9>}。=1、=0.8，查询对象={<1, 0.6>,<2,0.7>,<3,0.9>}(图中黑色圆点)。为范围约束，用虚线方框表示，与网络空间交点分别为1、2、3、4(图中灰色圆点)。

图1 基本概念示例

网络空间模糊对象的核心集A={3}，支撑集A={1,2,3}，α-截集(=0.5)，0,5={2,3}。网络空间模糊对象的α-截集(=0.5)，0.5={2,3}。

网络空间模糊对象和的α-距离：

网络空间模糊对象与确定范围的α-距离：

网络空间模糊对象1-近邻查询给出中与有最小0.8-距离的对象，要找到位于区域内的与有最小0.8-距离的模糊对象，则结果为。

3 数据存储方法

网络空间相对稳定，而网络空间中对象相对更新较快，为便于研究，使用网络空间与对象分离的框架结构。

3.1 网络空间

已知网络空间，将其连接信息与位置信息分别处理，使用聚类文件组织，用指针相连。连接信息建模为无向加权图=(,)，结点集为网络空间交点和特殊点，边集表示结点间连接性及网络距离，假定两结点间网络距离是对称的。图1网络空间模糊对象的图模型如图2所示。

图2 网络空间的图模型

(1)用邻接表对网络空间连接信息进行存储

为减少I/O操作，减少搜索时间，有效搜索结点邻接表，空间相邻结点邻接表用Z序放在同一页，邻接表所在页按结点序用B+树索引，图2中图模型的存储形式如图3所示。

图3 网络空间的邻接表

以图2中结点1为例，1有2个邻接点2和5，其邻接表1(虚线圆)包括形式相同的两项(虚线椭圆)，以第一项为例，其形式为<2,2,1,2,0>，其中，2是1的邻接点；2表示12间的网络距离；1,2为指向边12的具体抽象数据类型所在页的指针；0为指向边12上对象所在页指针。在12具体抽象数据类型前后分别设置指针指向1和2邻接表所在页1(2、3、4同理)。其他结点邻接表同1。

(2)用R树对网络空间位置信息索引

部分网络空间的R树如图4所示。设结点容量为3，有边相连结点以它们的最小边界矩形(Minimum Boundary Rectangle, MBR)的形式放在同一叶结点，如有边相连的结点1和5的最小边界矩形3(粗线所示)放在叶结点；叶结点还存放指向边具体抽象数据类型所在页的指针1,5；包含空间相近边的MBR放在同一中间结点，如包含边34和边811的2(虚线所示)放在中间结点，其他同理，直到根结点。

图4 网络空间的R树

3.2 网络空间模糊对象

用R树对网络空间模糊对象索引。部分网络空间模糊对象的R树如图5所示。设结点容量为3，将同一网络空间模糊对象模糊点的最小边界矩形放在同一叶结点，如模糊对象的最小边界矩形为1(粗线所示)放在叶结点；叶结点还存放指向空间模糊对象模糊点具体数据所在位置指针pt和网络位置指针pt；包含相近模糊对象的MBR放在同一中间结点，如包含模糊对象和的6(虚线所示)放在中间结点，其他同理，直到根结点。

图5 模糊对象的R树

4 范围受限的网络模糊对象近邻查询算法

范围受限的网络模糊对象近邻查询问题涉及两种查询：范围查询和近邻查询。根据两种查询的处理顺序，查询方法可分为两种：一种是先进行近邻查询，然后再对近邻查询结果进行范围查询，记为NN-R。另一种是先进行范围查询，然后再进行近邻查询，记为R-NN。

4.1 NN-R算法

NN-R算法中图的连接信息采用邻接表表示，图的位置信息与图中对象分别用R树索引。

NN-R算法的具体描述如算法1所示。其中，()表示确定的网络位置；(vv)表示确定边vv上存在对象；cover表示边上对象的集合；表示候选对象集，规模为(>)。

算法1 NN-R

输入域值，受限范围，模糊对象R树根结点，空间网络位置R树的根结点，查询对象，近邻查询个数

输出查询对象受限范围内的模糊k-近邻

begin

result=Ø;

vivj=confirm(q);

Scover=confirm(vivj);

candidate_NN=Scover={D1,D2,…,Dh};

dα–max=dα(q,Dh); //若Dh=Ø则dα–max=∞

Q=<(vi,dα(q,vi)),(vj,dα(q,vj))>;

De-queue the node v in Q with the smallest dα(q,v);

While dα(q,v)≥dα–min(q,RC) and

dα(q,v)≤min(dα–max,dα–max(q, RC))

for each non-visited adjacent node vxof v do

Scover=confirm(vxv);

en-queue(vx,dα(q,vx));

de-queue the next node v in Q

while |result| < k

for each object D in candidate_NN

|result|=|result|+1;

return result;

end

若不使用循环条件限制，则需访问包含候选对象的所有页，判断所有候选对象是否满足约束条件，假设约束范围不包含任何候选对象甚至不包含任何目标对象，算法仍需继续搜索，直至整个查询空间。NN-R算法利用查询对象与约束范围的α-距离进行限制，避免此种情况发生。在搜索过程中，当候选对象与查询对象的α-距离在受限范围与查询对象的α-距离之外时，则停止，减少不必要的页面访问，从而减少I/O操作。

NN-R算法分析：空间网络位置R树叶结点中有边的具体抽象数据类型所在页指针，而具体抽象数据类型前后分别设置指针指向结点邻接表所在页，因此若网络边数为||，R树结点容量为1，则确定查询对象网络位置所需时间复杂度为(log1||)；邻接表所在页按结点序用B+树索引，且邻接表中有指针指向边上对象所在页，因此若网络结点数为||，B+树结点容量为2，则确定边上存在对象所需时间复杂度为(log2||)；计算查询对象与候选对象的α-距离的时间复杂度为(log)；对候选对象进行排序，若设模糊对象个数为，则排序的时间复杂度最坏情况下为(lg)；设受限范围内结点的个数为|*|，结点的最大度为3，则对结点的每个邻接点，确定边上存在对象所需时间复杂度最坏情况下为(|*|3log2||)；判断候选对象是否在受限范围内的时间复杂度为()。NN-R算法时间复杂度为：((log1||+(|*|3+1)log2||+log(lg1))。

4.2 R-NN算法

R-NN算法中图的连接信息也采用邻接表表示，图的位置信息与图中对象也分别用R树索引。

R-NN算法思想：先从自由空间角度确定受限范围内查询对象的欧氏k-近邻集，作为候选对象集；然后确定及候选对象的网络空间位置；使用Dijkstra算法计算与候选对象的α-距离，将候选对象按到查询对象的α-距离做升序排列，放入优先队列；对其他受限范围内模糊对象，运行循环不变式：确定的下一个欧氏近邻，若其与的欧氏距离小于优先队列中的最大α-距离，则计算其与的α-距离，再与最大α-距离比较，若小于则插入队列，重新计算优先队列中的最大α-距离，直到某个对象与的欧氏距离大于优先队列中的最大α-距离。

R-NN算法的具体描述如算法2所示。表示查询对象受限范围内欧氏最近邻集；()表示的下一个欧氏近邻；d(,)表示与目标对象的欧氏距离。

算法2 R-NN

输入域值，受限范围，模糊对象R树根结点，空间网络位置R树的根结点，查询对象，近邻查询个数

输出查询对象受限范围内的模糊k-近邻

begin

result=Ø;

E_NN= {D1,D2,…,Dk};

vivj=confirm(q);

for each object D in E_NN do

vi’vj’=confirm(D);

compute dα(q,D);

result={D1,D2,…,Dk}

dα–max=dα(q,Dk);

repeat

next_E_NN(q) = (D,dE(q,D));

if dE(q,D)

compute dα(q,D);

if dα(q,D)

insert D into result;

dα–max=dα(q,Dk);

untill dE(q,D)>dα–max;

return result;

end

自由空间相对网络空间的计算代价要小，近似计算相对准确计算代价要小，利用欧氏距离的下界性，R-NN算法减少了网络空间计算，推迟了精确计算，从而降低CPU处理时间和I/O代价。

R-NN算法分析：若模糊对象个数为，模糊对象R树结点容量为4，则确定受限范围内查询对象的欧氏k-近邻的时间复杂度为(log4)；确定对象网络位置的时间复杂度为((+1)log1||)；计算d(,)时间复杂度为(log)。R-NN算法时间复杂度为(log4(+1)log1||+log)。

5 算法性能测试

为了进一步测试算法的性能，在2.0 GHz双核处理器、1 GB内存、Windows XP平台上用Visual C++6.0进行实验分析。实验数据集是旧金山道路网络数据[13]。受限范围是根据路网最大直径比例随机截取的方形区域，记为=边长/路网最大直径。模糊数据是模拟器产生的服从均匀分布路网上的点数据。网络数据与模糊数据按文中所述索引结构存储，页面大小为4 KB。LRU缓存容量为网络数据和R-树规模的10%。每个实验随机进行10次查询，所得结果平均值作为NN-R算法和R-NN算法性能比较的依据。性能指标为CPU处理时间和I/O代价。

实验1 测试数据集规模对算法性能的影响。实验结果如图6所示，其中，=0.01；=10；0.8。当数据规模较小时，因数据与查询对象距离较大，NN-R算法增加了许多不必要的网络距离计算和页面访问，CPU时间和I/O次数均较大，随着数据集规模增大，性能有所提高。而R-NN算法的CPU时间和I/O次数均较低，这是因为受限范围确定，所以只需访问必要的页面，相关数据放入缓存进行本地访问即可。

图6 数据集规模对算法性能的影响

实验2 测试受限范围对算法性能的影响。实验结果如图7所示。其中，数据集规模为20 KB；=10；0.8。随着的增大，两种算法的CPU时间和I/O代价都增加。这是因为增大，NN-R算法中以查询点到最小最大距离为上下界的剪枝范围加大。而R-NN算法当较小时，CPU时间明显优于NN-R算法，而当很大时，优势下降，这是因为的筛选作用降低。但R-NN的I/O代价始终优于NN-R。

图7 受限范围RC对算法性能的影响

实验3 测试最近邻查询数对算法性能的影响。实验结果如图8所示。其中，=0.01；数据集规模为20 KB；0.8。随着值的增加，两种算法的性能均下降，但下降幅度不同，NN-R性能下降较大，这是因为增加了网络距离计算和页面访问，而R-NN则受值影响较小。

图8 最近邻查询数k对算法性能的影响

实验4 测试域值对算法性能的影响。实验的结果如图9所示。其中，=0.01；数据集规模为20 KB；=10。随值增大，两种算法的CPU时间都略有减少，而I/O代价变化不大。这是因为值增大，需要计算的点间网络距离增多，所以使CPU时间增大，而模糊对象的访问是一次完成，不受值影响，因此对I/O代价影响较小。

图9 域值α对算法性能的影响

实验分别从数据集规模、受限范围、最近邻查询数和域值等方面对两种算法性能进行了测试。实验结果表明，R-NN算法受数据集规模、最近邻查询数和域值的影响较小，而受受限范围的影响较大；NN-R算法受域值的影响较小，而受其他方面影响均较大，但随数据集规模增大，性能反而有所提高。综上所述，R-NN算法在范围约束较小时性能较好，在数据集规模较小、最近邻查询数较大情况下比NN-R算法更有效；NN-R算法适合于数据较密集、受限范围相对较大、最近邻查询数较小情况下使用。

6 结束语

针对确定网络空间中查询对象与数据集均不确定，且目标对象有范围约束情况下的近邻查询问题，提出范围受限的网络空间模糊对象近邻查询概念，并根据查询的处理顺序不同，给出两种查询算法：NN-R算法和R-NN算法。实验结果表明在各自适用条件下，两种算法均有较好的性能，而在范围约束适中，数据分布较均匀的情况下，性能优势不明显，因此，下一步的研究是同时考虑范围查询与近邻查询，提高算法性能。

[1] Huang Yunwu, Jing Ning, Rundensteiner E A. Integrated Query Processing Strategies for Spatial Path Queries [C]//Proceedings of the 13th International Conference on Data Engineering. Birmingham, UK: IEEE Press, 1997: 477-486.

[2] Shahabi C, Kolahdouzan M, Sharifzadeh M A. Road Network Embedding Technique for K Nearest Neighbor Search in Moving Object Databases[J]. Geoinformatica, 2003, 7(3): 255-273.

[3] Papadias D. Query Processing in Spatial Network Data-bases[C]// Proceedings of the 29th International Conference on Very Large Data Bases. Berlin, Germany: ACM Press, 2003: 802-813.

[4] 高 峻, 郝忠孝. 空间数据库平面曲线的点最近邻查询[J].计算机工程, 2012, 38(15): 46-49.

[5] Cheng R, Kalashnikov D V, Prabhakar S. Querying Imprecise Data in Moving Object Environments[J]. IEEE Transactions on Knowledge and Data Engineering, 2004, 16(9): 1112-1127.

[6] Hans-Peter K, Peter K, Matthias R. Probabilistic Nearest- Neighbor Query on Uncertain Objects[C]//Proceedings of the 12th International Conference on Database Systems for Advanced Applications. Berlin, Germany: Springer-Verlag, 2007: 337- 348.

[7] 庄 毅. ISU-Tree: 一种支持概率近邻查询的不确定高维索引[J]. 计算机学报, 2010, 33(10): 1934-1941.

[8] Schneider M. Fuzzy Topological Predicates, Their Properties, and Their Integration into Query Languages[C]//Proceedings of the 9th ACM International Symposium on Advances in Geographic Information Systems. New York, USA: ACM Press, 2001: 9-14.

[9] 陈逸菲, 秦小麟. NU2RA: 一种路网中不确定移动对象范围查询分析方法[J]. 计算机研究与发展, 2010, 47(6): 1060-1065.

[10] Zheng Kai, Fung Pui-Cheong, Zhou Xiaofang. K-Nearest Neighbor Search for Fuzzy Objects[C]//Proceedings of 2010 ACM SIGMOD International Conference on Management of Data. New York, USA: ACM Press, 2010: 699-710.

[11] Bao J, Chow C Y, Mokbel M F, et al. Efficient Evaluation of k-range Nearest Neighbor Queries in Road Networks[C]// Proceedings of the 11th International Conference on the Mobile Data Management. Kansas City, USA: IEEE Press, 2010: 115-124.

[12] 高 峻, 郝忠孝. 受限网络移动对象的概率最近邻查询[J].计算机工程, 2013, 39(7): 26-30, 44.

[13]Roussopoulos N, Kelley S, Vincent F. Nearest Neighbor Queries[C]//Proceedings of 1995 ACM SIGMOD International Conference on Management of Data. San Jose, USA: ACM Press, 1995: 71-79.

编辑 陆燕菲

Nearest Neighbor Query for Fuzzy Object in Constraint Network

GAO Jun1, HAO Zhong-xiao1,2

(1. College of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080, China; 2. College of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China)

Aiming at nearest neighbor query for uncertain object with range constraint in network, the concept of nearest neighbor query for fuzzy object in constraint network is put forward. According to the query sequence, two query algorithms are proposed: NN-R and R-NN. In the way of storage, the two algorithms all use the index structure that spatial location information separated from network space connection information, and they use clustering file organization to reduce I/O operation. NN-R algorithm reduces the search area by using minimum and maximum α-distance between fuzzy object and range constraint. R-NN algorithm uses Euclidean nearest neighbors as the candidates. It declines the complexity by using that Euclidean distance can be computed easily and is the bottom boundary of the network distance. The complexity of the algorithms is respectively((log1||+(|*|3+1)log2||+log(lg1)) and(log4(+1)log1||+log). Experimental results show that the two algorithms all have better performance in the condition of their own applied area.

certain network; range constraint; fuzzy nearest neighbor; α-distance; adjacent table; R tree

1000-3428(2014)03-0039-07

A

TP311.13

黑龙江省自然科学基金资助项目(F200821)。

高 峻(1972－)，女，副教授、博士研究生，主研方向：时空数据库技术；郝忠孝，教授、博士生导师。

2013-07-12

2013-09-16 E-mail：hustgj@tom.com

10.3969/j.issn.1000-3428.2014.03.008