基于過濾率估算的WFS服務空間連接優化策略

藍貴文, 陳　騏, 陳天偉

(桂林理工大學 a.測繪地理信息學院;b.廣西空間信息與測繪重點實驗室, 廣西 桂林　541004)

?

基于過濾率估算的WFS服務空間連接優化策略

藍貴文, 陳騏, 陳天偉

(桂林理工大學 a.測繪地理信息學院;b.廣西空間信息與測繪重點實驗室, 廣西 桂林541004)

摘要：網絡要素服務是一種基于HTTP協議訪問和更新矢量地理要素的接口規范。在面向Web服務的應用環境下, 用戶的查詢請求往往需要訪問多個WFS服務，并且將服務的結果綜合后得到最終結果。由于在WFS服務端生成GML、 網絡間傳輸、 客戶端解析等都需要耗費較長時間, 成為WFS服務分布式集成應用的瓶頸。本文基于空間半連接和迭代區域劃分的分布式WFS服務查詢優化策略, 為避免針對各子區域盲目地執行空間半連接, 提出一種基于過濾率估算的改進方法, 即根據在各子區域采用不同下載方法的空間對象過濾預估效果, 決定其數據下載方法。實驗證明, 預先估算過濾率可提高優化策略的穩定性。

關鍵詞：網絡要素服務;空間連接;過濾率;查詢優化

開放式地理信息聯盟(open GIS consortium,OGC)制定的網絡要素服務(web featire services,WFS)規范[1]定義了基于HTTP協議訪問和更新矢量地理要素的接口, 被認為是功能最為強大、 應用前景最好的一種數據服務[2]。在面向WEB服務的應用環境下, 用戶的查詢請求往往需要訪問多個服務并且將服務結果綜合后得到最終結果[3-5]。由于在WFS服務器端生成GML、 網絡間傳輸、 客戶端解析都需要較長時間, 研究如何從不同站點的WFS服務中查詢符合條件的空間對象集合, 減少查詢執行代價, 具有重要的應用價值。

面向WFS服務的空間連接查詢, 是一種特殊的分布式空間連接。目前國內外在分布式空間連接方面, 已進行了大量的研究, 典型者如陳犖[6]、 David.J.Abel等[7], 其應用目的主要針對分布式數據庫環境。在此環境下, 各個網絡節點可以感知其他節點數據的數據組織結構甚至索引結構并加以利用, 如陳犖[6]基于此特點提出了一種空間半聯接索引的解決方案。與上述應用環境不同, WFS服務作為一個軟件組件, 除了提供數據訪問接口之外, 服務內部的數據組織、 索引結構對客戶端是完全封閉的, 各WFS服務之間不能相互直接通信, 所有數據交換都以客戶端為中轉站, 使得常用的分布式空間連接優化策略難以用于提高WFS服務之間的空間連接查詢效率。

要提高多個WFS服務的空間連接查詢速度, 一是要確保各WFS服務能具有較好的響應速度, 如在服務器端采用空間索引技術, 或是優化GML Application Schema的定義降低GML 文檔的內容冗余[3]；二是在客戶端進行優化, 如文獻[7-9], 總體而言還沒有引起太多關注，客戶端主要通過盡量過濾掉那些不可能出現在查詢結果中的空間對象, 以減少查詢導致的網絡傳輸代價, 以及服務端生成及客戶端解析GML文檔所產生的開銷。針對面向二路的WFS服務空間連接查詢, 筆者曾結合空間半連接的思想, 通過對整體上沒有表現出數據傾斜的兩個數據集進行區域劃分, 利用各局部區域表現出的數據傾斜特性, 采用相應的查詢處理策略, 以達到降低網絡數據傳輸費用的目的[8]，但未對各子區域的非備選空間對象的過濾效果進行評估, 因此在處理策略的選擇上具有一定的盲目性。本文對二路空間連接查詢中兩個數據集在各子區域中的過濾效果進行評估, 以達到在各子區域選擇合適的處理策略之目的。

1研究思路和方法

1.1面向WFS服務的二路空間半連接

David.J.Abel等提出了分布式空間數據庫中空間半連接處理的思想[8],由于WFS服務作為一個軟件組件,除了提供數據訪問接口之外,服務內部的數據組織對客戶端是完全封閉的,在兩個WFS服務之間采用空間半連接處理,其過程如圖1所示。

圖1　面向WFS服務的二路空間半連接處理過程Fig.1　Workflow of spatial semi-join between two WFSs

設數據集R、 S由A、B兩個服務提供, 可以根據一定的評判條件選擇從A服務下載符合查詢條件的數據R到本地, 然后把R中各空間對象的MBR(R)傳送到B, MBR(R)作為用于查詢的幾何過濾條件, 獲取數據集S的子集, 在本地對R和S′連接, 得到結果。顯然, 空間半連接策略通過過濾掉非候選對象達到減少網絡傳輸代價的目的。

需要注意的是, 圖1中查詢也可能先請求B, 這取決于采用何種評判條件, 一般先分別向A、B服務查詢R、 S的對象數目|R|、 |S|, 優先下載對象數目為min(|R|, |S|)的數據集, 在已知兩個數據集中每個對象的平均數據量r0、 s0時, 也可優先下載數據量為min(|R|×r0, |S|×s0)的數據集, 再在另一服務上作空間半連接。空間半連接策略并非對每種情形都有效, 最惡劣情況下被過濾的對象數目為0, 因此需要對過濾效果進行估算。

1.2非備選空間對象過濾率估計

進行空間半連接的作用在于過濾掉一些不可能在最終結果集中出現的空間對象, 以達到減少網絡數據傳輸代價、 GML生成及解析代價的目的。本文用過濾率來評定空間半連接的過濾效果, 即被過濾掉的空間對象個數與不作優化時所需傳輸的空間對象個數的比值。

設R、 S兩個數據集的對象數目|R|、 |S|, 執行某空間連接后的配對數為N，N可表示[10]為

(1)

NingAn等[11]、ChengyuSun等[12]提出改進的估算公式:

(2)

(3)

假定空間對象均勻分布, 可知, R中任一空間對象的最小包圍矩形(MBR), 與S中任一空間對象的MBR, 相互碰撞的概率為SelectivityA, B。對于R數據集任一空間對象, S數據集中與其發生碰撞的空間對象數目的數學期望為

ER(NS)=|S|×SelectivityA, B,

(4)R中最終出現在結果中的空間對象個數估值為|rR|=min(|R|, N)。反之,也可以用同樣的方法來估算ES(NR)、 |rS|。對R、 S的過濾率可定義為

(5)

可知, 如果過濾率FR太低, 執行空間半連接策略難以起到過濾效果。

對于圖1中A、B兩個WFS服務, 若先下載R到客戶端, 再在B服務上執行空間半連接策略, 網絡傳輸代價預期為|S|×s0-rS×s0+|R|×r0;反之，|R|×r0-rR×r0+|S|×s0。

d=(|S|×s0-rS×s0+|R|×r0)-

(|R|×r0-rR×r0+|S|×s0)

=rR×r0-rS×s0。

(6)

顯然, 若d?0, 應采用先從A服務下載R的策略;d?0，則應采用先從B服務下載S的策略;d≈0空間半連接策略效果不明顯。

2基于區域劃分的二路WFS服務空間連接優化策略

以上選擇率、 過濾率的估算公式是基于空間對象在概率意義上呈均勻空間分布情形下推導而得的, 因此如果在大范圍內應用, 當空間對象數目較多時, 估算值與實際情況差距較大。一般將查詢范圍劃分為多個相對小的子區域, 本文采用文獻[7]中提出的迭代區域劃分方法, 然后測定兩個數據集子區域范圍的空間對象數目。對任一子區域, 當其中的一個數據集在該范圍內的對象數目少于一個設定的值M時, 認為不再需要進一步劃分。本文對每個子區域分別用式(3)、 式(5)計算其選擇率、 過濾率, 通過式(5)、 式(6)確定各子區域應采用的下載策略。由于空間對象在各子區域比整個查詢區域更趨近均勻空間分布, 選擇率、 過濾率估值更準確, 同時可以更好地利用子區域的數據傾斜來改進過濾效果。

以子區域邊界作為幾何查詢條件, 各子區域邊界上的空間對象存在重復計數現象。作為WFS服務的客戶端, 數據未下載前, 無法確定重復計數。為了消除重復計數, 采用以下解決方法:(1)獲取數據集在查詢范圍內空間對象的總數目及包含在各子區域內的空間對象數目;(2)以各子區域內部的空間對象個數為權, 利用加權法把跨越各邊界的對象分配給各網格區域, 減少利用邊界作為幾何條件查詢邊界要素的代價。

各子區域的下載策略確定之后,調用WFS服務的GetFeature接口下載數據。以4×4格網區域劃分為例(圖2),用黑色、白色填充表達適用空間半連接策略的子區域,對黑色區域,應為先從A服務下載數據,然后在B服務對該子區域進行空間半連接;反之，白色子區域為先從B服務下載數據;斜線填充表達不適用空間半連接策略的子區域。由于WFS服務協議支持一個請求內可以包含多個查詢條件,為避免多次請求,所有數據下載過程采用如下方式:(1)以所有黑色子區域、 斜線子區域的空間范圍作為查詢幾何條件,從A服務下載數據;以所有白色子區域、 斜線子區域的空間范圍作為查詢幾何條件, 從B服務下載數據。(2)在B服務對黑色區域進行空間半連接, 在A服務對白色區域進行空間半連接,獲取備選空間對象到客戶端。

圖2　各子區域的空間連接執行策略選擇Fig.2　Determination of execution plans for spatial joins of sub-areas

3實驗結果及分析

本文設計了模擬實驗對所提出的優化策略進行性能測試, 并與直接下載方法進行性能比較分析。

在實驗中, 設置3個計算機節點, 其中兩臺為數據集服務器, 安裝ArcGIS Engine Runtime、 .Net Framework 3.5、 IIS7.5, 部署使用C#語言編寫的查詢請求處理程序及相關空間數據集;一臺客戶端計算機, 部署使用C#語言編寫的執行查詢請求的客戶端程序。實驗環境為100 M局域網, 網絡響應速度小于1 ms。實驗數據取自ArcGIS 9.3附帶的實驗數據中美國鐵路數據集(圖層名為rail100k, Polyline型要素, 約13萬條記錄)、 水系數據集(圖層名為dtl_wat, Polygon 型要素, 約39萬條記錄)。 查詢條件為在查詢窗口內相距不超過1.0 km的所有鐵路與水系要素的配對。

設定3種查詢范圍300 km×300 km、 200 km×200 km、 100 km×100 km。隨機選定查詢區域后, 對該查詢區域內分別采用M=100、 50、 10以及直接下載方法, 對其所耗費的時間進行對比分析。令X為直接下載方法所需時間與優化方法所需時間的比值, 則 “明顯優于”定義為X>1.5;“略優于”, 1.0

當查詢范圍為300 km×300 km時, 在查詢范圍內的兩個空間數據集中空間對象數目之和基本在1 000左右。對實驗結果進行分析發現, 該優化方法在絕大多數情形下取得了較好的優化效果;約10%劣于直接下載法的情形, 主要是隨機選中之區域, 在區域劃分之后子區域仍不適于作空間半連接, 而區域劃分及過濾率計算引起開銷所致。當M值設置得過大時, 導致區域劃分不充分, 會導致過濾效果不明顯;當查詢范圍較小、 兩個數據集數據分布比較均勻時, 過濾效果也會不明顯, 需要設置合理的M值來抑制過度區域劃分。此外, 在同等條件下與未采用過濾率作為子區域執行策略選擇依據, 進行對比實驗, 約17%(38次)略劣于或劣于直接下載法, 顯然本文算法的穩定性得以提高。

表1　實驗結果對比Table 1　Experiment comparison of two strategies　　　次

參考文獻:

[1]OGC 09-025r2, OpenGIS Web Feature Service 2.0 Interface Standard[S].

[2]賈文玨, 龔健雅, 李斌. Web 要素服務的優化方法[J].測繪學報, 2005, 34(2):168-174.

[3]白玉琪, 楊崇俊.空間信息搜索引擎研究[J].中國礦業大學學報, 2004, 33(1):90-94.

[4]Jiang J, Yang C J, Ren Y C. A spatial information crawler for open GIS WFS[C]//Geoinformatics 2008 and Joint Conference on GIS and Built Environment(Volume 7143), Guangzhou:SPIE, 2008, 7143:2C-1-C-9.

[5]吳華意, 劉哲, 徐開明.地理信息服務集成的級聯模式及其應用[J].測繪科學, 2010, 35(6):212-214.

[6]陳葷.分布式地理空間數據服務集成研究技術研究[D]. 長沙:國防科學技術大學, 2005.

[7]Abel D J, Ooi B C, Tan K L, et al. Spatial join strategies in distributed spatial DBMS[C]//Max J. Egenhofer, John R. Herring. Advances in Spatial Databases, Lecture Notes in Computer Science, 1995, 951:348-367.

[8]藍貴文, 黃全義, 周曉青.一種面向WFS服務的分布式空間連接查詢優化策略[J]. 武漢大學學報:信息科學版, 2009, 34(6):654-658.

[9]Gao B B, Xie C J, Sheng W T. Spatial grid services for adaptive spatial query optimization[C]//Geoinformatics 2008 and Joint Conference on GIS and Built Environment. Guangzhou: SPIE, 2008, 7143:0P-1-0P-9.

[10]Mamoulis N, Papadias D. Multiway spatial joins[J]. ACM Transactions on Database Systems, 2001, 26(4): 424-475.

[11]An N, Yang Z Y, Sivasubramanium A. Selectivity estimation for spatial joins[C]//Proceedings of 17th IEEE International Conference on Data Engineering.IEEE Computer Society,2001:368-375.

[12]Sun C Y, Agrawal D, El Abbadi A. Selectivity estimation for spatial joins with geometric selections[C]//Proceeding of 8th International Conference on Extending Database Technology Prague,Advances in Database Technolog—EDBT 2002.Heidelberg:Springer, 2002,2287:609-626.

文章編號:1674-9057(2016)02-0310-04

doi:10.3969/j.issn.1674-9057.2016.02.019

收稿日期：2014-10-28

基金項目：國家自然科學基金項目(41261088);廣西空間信息與測繪重點實驗室主任基金項目(桂科能1207115-11);廣西“八桂學者”專項經費項目

作者簡介：藍貴文(1977—), 男, 博士, 副教授, 研究方向:地理信息系統,gwlan_770728@163.com。

中圖分類號：P208

文獻標志碼：A

Spatial join optimization of web feature services based on early filtering estimation

LAN Gui-wen, CHEN Qi, CHEN Tian-wei

(a.College of Geomatics and Geoinformation; b.Guangxi Key Laboratory of Spatial Information and Geomatics, Guilin University of Technology, Guilin 541004,China)

Abstract:The OpenGIS Web Feature Service (WFS) Interface Standard provides an interface allowing requests and updates for geographical features across the web by the HTTP protocol. In such a web-service-oriented environment, an issued query may invovle two or more spatial datasets that are provided by different services at different sites. The processes of generating GML document in the WFS server, transmitting it to and parsing it at the client site, are very time-consuming, which causes a bottleneck to application of WFSs for distributed spatial data integration. This paper examines the query optimization strategy of spatial joins between OGC-compliant WFSs, based on the methods of spatial semi-join and partition based spatial-merge join. To avoid blindness of spatial semi-join operations of sub-areas, an improved strategy is proposed in this paper. In early phase the filtering ratios of spatial semi-joins for all the sub-areas are estimated and used to generate execution plans of spatial semi-join operations. The experimental result illustrates that compared with the previous methods, the proposed strategy can improve the performance of spatial joins between two WFSs.

Key words:web feature service; spatial join; filter ratio; query optimization

引文格式：藍貴文, 陳騏, 陳天偉.基于過濾率估算的WFS服務空間連接優化策略[J].桂林理工大學學報，2016,36(2):310-313.