受限網絡模糊對象最近鄰查詢

高 峻，郝忠孝,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