顧雨婷 金 冉, 韓曉臻 陳 剛 壽黎但

1(浙江萬里學院大數(shù)據(jù)與軟件工程學院 浙江 寧波 315100)2(浙江大學計算機科學與技術學院 浙江 杭州 310027)

0 引 言

隨著定位服務LBS(Location Based Service)的快速崛起，越來越多具備無線通信功能的智能移動設備出現(xiàn)在我們的日常使用中[1]。智能手機等終端設備都部署了地理應用及定位系統(tǒng)[2]，使得無線數(shù)據(jù)服務成為了工業(yè)界和學術界研究的一大熱點。空間查詢處理技術作為一項用于處理LBS請求的重要技術[3]，近年來專家學者對這項技術的深入研究從未止步，且取得了眾多喜人的研究成果。本文著重對現(xiàn)有的空間查詢處理技術進行全面系統(tǒng)化的總結與綜述。

1 問題描述

1.1 空間查詢處理的相關概念

空間查詢(Spatial Queries)是指利用空間索引技術，從海量的空間數(shù)據(jù)庫中找出滿足給定空間條件的空間實體。與傳統(tǒng)查詢不同的是，空間查詢是由地理數(shù)據(jù)庫支持的數(shù)據(jù)庫查詢。關于空間查詢處理技術，大部分現(xiàn)有的研究都是基于歐幾里德空間的，近年來，研究者考慮到了道路網(wǎng)絡中的空間查詢處理[4-8]。作為數(shù)據(jù)挖掘應用的核心，無線數(shù)據(jù)廣播環(huán)境下的空間查詢技術得到了國內外研究者的廣泛關注。

在無線數(shù)據(jù)廣播技術條件下進行的數(shù)據(jù)信息訪問主要有兩種基本方法：點對點訪問(按需訪問)和定期廣播。對于點對點訪問，移動客戶端向服務器端遞交查詢，服務器端按需處理查詢并通過預先建立的點對點信道將查詢結果返回至移動客戶端。文獻[5,8]討論了道路網(wǎng)絡中基于點對點訪問的空間關鍵字查詢處理問題。然而，這種傳統(tǒng)的用戶與服務器的點對點通信存在網(wǎng)絡超載和隱私泄露的缺點。

為了克服點對點訪問的缺點，學者們開發(fā)了無線數(shù)據(jù)廣播模式[9]，客戶端通過調諧信道來檢索數(shù)據(jù)查詢所需的信息。定期廣播通過避免上行鏈路傳輸來節(jié)省客戶端的耗電量[10]，且服務器只需監(jiān)控數(shù)據(jù)對象的信息即可滿足任意數(shù)量的移動客戶端查詢需求[1]。無線廣播模式具有高擴展性，適用于重載系統(tǒng)，能夠有效保護客戶端隱私。研究者對基于數(shù)據(jù)廣播模式進行空間查詢處理已做了深入研究[11-15]，但定期廣播也存在按序訪問和延遲較大的缺點。

1.2 無線廣播系統(tǒng)的主要性能指標

在無線廣播信道上檢索信息時，服務器通過無線信道周期性的將數(shù)據(jù)廣播給客戶端，而移動客戶端通過調諧信道來檢索需要的信息并在本地進行查詢處理。傳統(tǒng)技術利用基于磁盤的索引[7,16-18]加速道路網(wǎng)絡中的空間查詢處理，這種索引模式用于點對點的隨機訪問方法，減少查詢過程中的訪問延遲。而無線廣播模式支持順序訪問，相關學者研究引用定期廣播的空中索引，將索引位于廣播周期的數(shù)據(jù)前端來降低客戶端查詢時的調諧時間。

用于衡量客戶端性能的有兩個關鍵參數(shù)，即廣播訪問效率和能量消耗。為了降低能耗，移動用戶端的設備通常存在休眠態(tài)和活動態(tài)兩種工作狀態(tài)。當廣播信道暫未廣播至客戶端所需的數(shù)據(jù)，設備無需接收數(shù)據(jù)時處于休眠態(tài)，休眠態(tài)的能耗遠低于活動態(tài)，因此可以大大降低客戶端的使用能耗。訪問延遲和調諧時間是無線廣播系統(tǒng)的主要性能指標[19-20]。訪問延遲表示從查詢被調用到收到結果那一刻所經(jīng)過的時間。調諧時間表示客戶端收聽廣播信道所花費的時間[21]。

1.3 空間查詢語言

查詢語言是與數(shù)據(jù)庫交互的主要手段，采用關系數(shù)據(jù)庫的結構化查詢語言(SQL)不支持空間數(shù)據(jù)類型和空間查詢與分析。為了處理包含位置信息的空間數(shù)據(jù)及以GIS為代表的空間信息技術，研究者在空間數(shù)據(jù)類型和空間操作函數(shù)的基礎上，對標準SQL進行擴展，實現(xiàn)了能夠處理空間數(shù)據(jù)并進行空間分析的空間查詢語言[22-24]。

2 空中索引技術

空中索引攜帶數(shù)據(jù)對象的相關信息，并將其廣播至移動客戶端，客戶端通過檢索空中索引來確定查詢所需數(shù)據(jù)段到達的時間，并進行訪問，空中索引技術通常用于節(jié)約移動客戶端的能耗[1]。(1，m)索引方案[21]是無線廣播周期中最常見的索引結構。如圖1所示，(1，m)索引方案將整個廣播數(shù)據(jù)段劃分為m等份，并將索引信息放置在數(shù)據(jù)項的每個1/m分數(shù)之前進行廣播[13,21,25]，索引在一個廣播周期內廣播m次，移動客戶端可通過檢索索引信息預測查詢數(shù)據(jù)到達的時間，并在數(shù)據(jù)段到達時再調入廣播信道。(1，m)索引方案中重復的索引信息延長了廣播周期，所以需花費較長的時間來響應索引，增加了訪問延遲，但是，它有效降低了查詢的調諧時間。

圖1 (1，m)索引方案

3 研究現(xiàn)狀

空中索引用于定期廣播的方法，移動客戶端通過空中索引來檢索用戶查詢所需的數(shù)據(jù)內容，數(shù)據(jù)檢索是空間查詢處理領域中的一個重要內容，檢索的效率將直接影響到數(shù)據(jù)查詢的效率。使用索引可有效減少訪問延遲和調諧時間，從而降低客戶端能耗，提高空間查詢處理效率。針對無線廣播環(huán)境下的空間查詢處理，國內外有許多研究成果，大致可分為三類：歐式空間下的空間查詢處理、道路網(wǎng)絡環(huán)境下的空間查詢處理以及無線廣播環(huán)境下的空間查詢處理。

3.1 歐式空間下的空間查詢處理

早期的空間查詢處理方法只考慮歐式空間中的查詢，圖2討論了支持空間查詢處理的多種索引結構。

圖2 空間查詢處理的索引結構分類

(1) 基于R樹的索引 R樹索引結構[26]是用于空間查詢的基本索引結構，圖3表示出了二維空間下的最小邊界矩陣，圖4則是它相對應的R數(shù)索引結構。文獻[20]描述了在傳統(tǒng)的順序訪問R樹上進行精確的kNN搜索，并對已建立的kNN搜索算法進行優(yōu)化。文獻[27]提出的改進基于R樹的kNN查詢處理技術允許kNN搜索從廣播周期的中間開始。R樹的變體R*樹[28]也是一種傳統(tǒng)的空間索引，可以有效地支持無線廣播環(huán)境中的范圍查詢，但無法進行類似于kNN查詢[29]這類查詢結果不確定的空間查詢處理。另有學者研發(fā)了一種混合索引結構[30]，這種索引結構將倒排索引和R*樹結構相結合用于處理空間關鍵字查詢，且不同的組合方案能夠處理相應的空間查詢處理。文本優(yōu)先的方案可用于處理范圍查詢和布爾kNN查詢，空間優(yōu)先方案用于處理范圍查詢和Top-k查詢。文獻[31-32]提出了基于R樹變體的索引結構，這種索引結構在計算最小邊界矩陣時合并相似文檔，適用于處理范圍查詢和布爾kNN查詢。另有D樹[33]結構可用于處理無線廣播環(huán)境中的NN查詢。

圖3 最小邊界矩陣

圖4 R樹索引結構

(2) 基于網(wǎng)格的索引 在文獻[34]中，Mouratidis等提出了適用于快照和持續(xù)查詢的廣播網(wǎng)格索引方法BGI，由于網(wǎng)格單元的尺寸小且能夠有效更新查詢對象，BGI將網(wǎng)格單元作為索引。文獻[35]引入了一種稱為網(wǎng)格分區(qū)索引的新型索引方法，網(wǎng)格分區(qū)索引是基于維諾圖構建的，它在支持按需訪問和周期性廣播的模式下進行NN搜索[36]。另外，文獻[37]討論了基于網(wǎng)格的地理文本索引問題，且提出了兩種基于網(wǎng)格單元的索引方案，即空間基本索引(ST)和文本基本索引(TS)。研究人員還提出了幾種相似的網(wǎng)格索引[38-40]來處理空間查詢處理工作。

(3) 基于空間填充的索引 基于空間填充的索引結構通常將倒排文件與空間填充曲線相結合，如希爾伯特空間填充曲線和Z曲線。文獻[41]提出了一種倒排文件與希爾伯特曲線相結合的索引結構，且在文獻[42]中提出的幾種混合索引結構中，SFC-QUAD索引結構是最優(yōu)的。這種索引結構將倒排文件與Z曲線結合在一起，通過遍歷四叉樹的方式獲取Z曲線的順序，并使用優(yōu)化方法來壓縮倒排文件，使得SFC-QUAD索引能夠有效地處理范圍查詢。

(4) 其他類型的空間查詢處理 文獻[25]提出了一種通用的客戶端-服務器體系結構，實用新型空間查詢處理算法來支持無線廣播環(huán)境中的移動連續(xù)最近鄰查詢(MCNNQ)。文獻[43]討論了給定移動的空間查詢和關鍵字的Top-k空間關鍵字查詢的處理問題。文獻[44]討論了給定具體位置、方向和關鍵字的方向感知空間關鍵字查詢問題。文獻[45-46]討論了反向空間關鍵詞最近鄰查詢，它返回最符合條件的k個答案。文獻[47]和文獻[48]分別介紹了一種新穎的空間關鍵字覆蓋問題和級別感知集體空間關鍵字(LCSK)查詢問題。

然而，上述方法只能在歐幾里德空間中運行，但現(xiàn)實生活中對象的運動是受道路網(wǎng)絡限制的，因此這些方法不能直接運用在真實道路網(wǎng)絡中。

3.2 道路網(wǎng)絡環(huán)境下的空間查詢處理

道路網(wǎng)絡是一個表示為G=(V,E)的二維空間，其中V是對象節(jié)點的集合，E是邊的集合。每個節(jié)點v=(v.x,v.y)表示道路交叉點或路網(wǎng)中的對象節(jié)點的位置，每個e=(vi,vj,w)表示節(jié)點vi和vj之間的路段，其中w為邊的長度。節(jié)點和邊是道路網(wǎng)絡的基本要素。

在傳統(tǒng)的空間數(shù)據(jù)庫中，道路網(wǎng)絡中的空間查詢處理已經(jīng)有了很多的研究成果。文獻[16]利用R樹來存儲數(shù)據(jù)對象以及路網(wǎng)中的道路交叉點和路段，同時提出了IER和INE兩種算法來處理用戶查詢，查詢效率取決于路網(wǎng)中的對象密度。道路網(wǎng)絡的運行模式與普通地理空間系統(tǒng)不同，由于路網(wǎng)中對象受限于網(wǎng)絡上的位置，M-Tree索引[49]能夠索引任何度量空間中的數(shù)據(jù)，結合截斷路網(wǎng)嵌入(tRNE)的M樹索引可進行路網(wǎng)中的范圍查詢及kNN查詢處理，適合于遠距離查詢處理的大型系統(tǒng)。

文獻[18]提出了一種基于NVDs的VN3方法來處理kNN查詢。另外，網(wǎng)絡嵌入框架[7]、基于DS的方案[50]以及最短路徑四叉樹(SPQ)[17]都被用來處理kNN查詢搜索問題。在道路網(wǎng)絡中處理多個kNN查詢，文獻[51]提出了漸進技術，這種技術有選擇性的將查詢結果緩存在主存儲器中，并將其用于查詢處理。另外提出的六種緩存算法中，“懶惰”聚類方法在大多數(shù)情況下的性能是最優(yōu)的。文獻[52]討論了空間網(wǎng)絡數(shù)據(jù)庫中基于組的k最近鄰查詢(GKNN)，使查詢所獲得的一組興趣點到一組查詢點的網(wǎng)絡距離之和最小化。為了處理道路網(wǎng)絡中在線LBS應用的kNN查詢問題，研究人員將研究重點從改進查詢處理時間轉移到了用戶查詢的響應時間問題。文獻[53]提出了一種新的查詢框架，稱為SHI。SHI框架中包含查詢處理和列隊處理的操作，逐組進行查詢檢索，減少用戶查詢的等待時間。文獻[54]還研究了道路網(wǎng)絡上反向空間和文本k最近鄰(RSTkNN)查詢問題，將網(wǎng)絡鄰近度和文本相關性結合，且提供了幾種空間關鍵字修剪方法來過濾大量不合格對象，最小化搜索空間，將兩種有效的驗證技術集成到RSTkNN查詢中。

但是，IER、INE和NVD三種代表性的方法都存在著低效率的問題。因此，文獻[55]提出了一種單波前啟發(fā)式搜索(SWH)的kNN算法，利用一種新的啟發(fā)式功能，顯著減少內存處理成本組件和空間網(wǎng)絡訪問成本。為了解決CkNN查詢問題，研究人員提出了基于逐步增量網(wǎng)絡擴展技術(PINE)的DAR算法和eDAR算法[56]。相比基于VN3的方法，eDAR能夠花費更少的響應時間來進行最短距離計算和kNN查詢。文獻[57]中提出的IMA算法和GMA算法同樣適用于處理道路網(wǎng)絡中移動客戶端的CkNN查詢處理問題，且監(jiān)測查詢對象和查詢點的移動，及時計算更新查詢結果。這些方法會在客戶端略微移動更新時返回兩個重復的查詢結果，一種包括修剪和精煉的方法[58]可解決這一問題，但這種方法存在客戶端需以固定的速度進行移動的局限性。針對這一局限性，文獻[59]提出了一種有效的方法來處理道路網(wǎng)絡中以不確定速度移動的客戶端的連續(xù)kNN查詢問題。

隨著基于位置的服務(LBSs)的快速發(fā)展，空間數(shù)據(jù)庫作為LBSs的核心組成部分，文獻[60]將位置相關信息和用戶查詢分別稱為空間對象和位置相關空間查詢(LDSQ)，并且提出了一種用于處理位置相關空間查詢(LDSQ)的系統(tǒng)框架ROAD，能夠有效降低網(wǎng)絡遍歷耗時。為了解決LBS在處理路網(wǎng)中空間查詢處理所產生的用戶位置隱私問題，需要基于網(wǎng)絡的匿名化處理框架(NAP)[61]對用戶的位置進行模糊處理，并在保證用戶隱私的基礎上實現(xiàn)低計算通信成本和查詢處理的快速響應。

為了提高查詢效率，許多研究人員開始設計分布式空中索引來優(yōu)化路網(wǎng)中的空間查詢處理。文獻[62]中提出了一種將底層道路網(wǎng)絡的網(wǎng)絡維諾圖(NVD)結構劃分為一組網(wǎng)格單元并對網(wǎng)格單元進行編號的方法，并且基于這種方法討論了基于NVD的分布式空中索引NVD-DI[13]來處理CN3B查詢。當查詢點附近存在足夠多的數(shù)據(jù)對象時，對比高精度的網(wǎng)絡距離范圍檢索，近似查詢與精確查詢具有一樣甚至更好的效果，且查詢處理的成本更低。文獻[63]中提出了ARER和ARNE兩種方法。ARER確定道路網(wǎng)絡中靜態(tài)點周圍感興趣對象的位置，通過減少查詢預計算的次數(shù)盡快獲取查詢結果；ARNE則是在預定義的路徑內確定興趣對象的位置，從而排除位于下限與搜索范圍之內的任何節(jié)點，減少預先計算和錯誤對象數(shù)量。

大部分研究者都關注在無向道路網(wǎng)絡，文獻[64]針對有向道路網(wǎng)絡中的Top-k空間偏好查詢進行研究，提出了一種名為PSA的偏好查詢搜索算法，基于特征對象的修剪與分組最小化用于數(shù)據(jù)對象排名所耗費的查詢處理成本，有效縮短查詢處理時間。圖5呈現(xiàn)了一個有向道路網(wǎng)絡中的top-k空間偏好查詢示例。另有研究者提出了一種新類型的查詢，即反向Top-k布爾空間關鍵字(RkBSK)查詢[65]，采用考慮空間和文本信息的修剪啟發(fā)式算法來縮小檢索空間。在網(wǎng)絡環(huán)境中，空間對象Top-k查詢算法的查詢效率是衡量查詢性能的重要指標。文獻[66]對傳統(tǒng)的基于Top-k空間數(shù)據(jù)的快照查詢方法和連續(xù)查詢方法進行了改進，采用了底層快照查詢算法來解決單個關鍵字查詢的空間問題，使該算法的通信消耗和通信頻率均小于STM算法。

圖5 有向道路網(wǎng)絡中top-k空間偏好查詢的示例

3.3 無線廣播環(huán)境下的空間查詢處理

無線數(shù)據(jù)廣播是向道路網(wǎng)絡中的客戶端傳播數(shù)據(jù)的有效策略。在無線移動環(huán)境中，由于低帶寬，有限的能量和容量以及移動性，空間查詢處理是一個具有挑戰(zhàn)性的問題。由于無線廣播環(huán)境具有較高的可擴展性，并且能夠同時向大量移動客戶端發(fā)送信息，學者們開始研究無線廣播模式下基于位置信息的查詢(LBQ)處理問題。

為了適應無線數(shù)據(jù)廣播環(huán)境，文獻[67]研究了通過R樹索引在廣播環(huán)境中處理NN搜索，而文獻[27]提出了在廣播R樹上進行高效地kNN查詢搜索。無線廣播環(huán)境中的新索引ISW[37]通過合理的機制及預計算界限，可以有效處理基于ISW的kNN搜索、范圍查詢和RNN查詢。文獻[68]采用無線廣播模型來提供路網(wǎng)中的LBSs，提出EB和NR兩種方法支持最短路徑計算，并在此基礎上提出了一種稱為BagIndex[69]的空中索引，用于道路網(wǎng)絡中的最短路勁查詢處理，有效降低客戶端能耗。隨著移動客戶端數(shù)量的增加，空間查詢處理對于可擴展性的要求越來越高，文獻[70]采用無線廣播模式令移動客戶端收聽廣播并在本地處理查詢。

另有研究人員提出了一種基于網(wǎng)格單元的非平面廣播分布式索引GDIN[71]的數(shù)據(jù)調度方案。它能夠使關注度高的查詢對象在廣播信道上高頻率的出現(xiàn)，可用于窗口查詢處理，使移動客戶端只訪問用戶查詢所需的數(shù)據(jù)項?；谧畲筮吔缇仃嚨姆植际娇罩兴饕鼶AIM[13]使用MaxBRs來過濾無線廣播信道上的熱門數(shù)據(jù)項，并在廣播周期內重復熱門數(shù)據(jù)，從而縮短廣播周期的長度。網(wǎng)絡分區(qū)索引NPI[1]將道路網(wǎng)絡劃分為多個區(qū)域，構建空中索引來攜帶每個區(qū)域的預計算信息，并且通過無線廣播周期地廣播至移動客戶端，從而進行高效的空間查詢處理。NPI的索引結構包含三個部分，如圖6所示。

圖6 網(wǎng)絡分區(qū)索引(NPI)結構

但NPI并不是一個完全的分布式索引結構，針對NPI沒有解決的帶寬、移動性等問題，研究者基于NPI的空中索引提出了一種稱為SAI[72-73]的空間空中索引，這種索引使用最優(yōu)混合廣播(OHB)調度和自適應協(xié)同緩存(ACC)，能夠用于道路網(wǎng)絡中的空間查詢。SAI相較于NPI具有更高的查詢性能，且降低了能源消耗和搜索空間。文獻[74]又提出了一種基于NPI的混合空間空中索引(HSAI)，其中混合廣播調度，基于自適應XOR的網(wǎng)絡編碼和自適應協(xié)作高速緩存能夠有效地用于道路網(wǎng)絡中的空間查詢。

基于擴展的希爾伯特曲線，完全分布式空中索引IEI[75]劃分底層路網(wǎng)傳感器網(wǎng)絡，可用于處理kNN查詢、CkNN查詢和范圍查詢。但是，當網(wǎng)格單元較大時，廣播周期的幀數(shù)也會變多，IEI索引必須多次傳輸才能使移動客戶端獲取所查詢的數(shù)據(jù)。由于適合廣播環(huán)境的索引結構必須考慮數(shù)據(jù)傳遞的順序，索引大小和選擇性調整。文獻[76]研發(fā)了一種基于網(wǎng)格的輕量級比特序列空中索引，稱為二進制四叉樹，該索引允許對數(shù)據(jù)進行順序搜索和選擇性調整，所提出的空間搜索算法在范圍查詢和k近鄰查詢中能夠以最小的訪問延遲和調諧時間提供準確的檢索答案。

此外，研究人員針對傳感器網(wǎng)絡[77-82]也做出了許多相關的工作。在無線傳感器網(wǎng)絡中種構建空中索引的基本任務之一是確定傳感器能夠快速準確的參與區(qū)域查詢操作，而大多數(shù)現(xiàn)有的研究工作僅僅集中于為單個屬性的傳感器構建空中索引。文獻[83]提出了一種新的節(jié)能啟發(fā)式密度聚類模型，用于構建一個多屬性的空間索引樹，這種索引結構稱為MFSI樹。它將多屬性傳感器的節(jié)點組織成樹層次結構，可以有效地在索引樹中進行多區(qū)域屬性的聚合查詢，利用MFSI樹的多查詢聚合技術可以顯著降低能耗，延長網(wǎng)絡生命周期。與此同時，現(xiàn)有的WSN中的帶寬資源有限，根據(jù)數(shù)據(jù)存儲模型的特征，基于數(shù)據(jù)屬性的空中索引SIQ[84]主要用于查詢WSN中的節(jié)點信息，SIQ只存儲用于構建索引的葉節(jié)點，且SIQ使用的數(shù)據(jù)屬性是空間索引的內容，故構建此類索引的成本較低，能夠有效監(jiān)控數(shù)據(jù)并進行多屬性范圍的查詢操作。

近年來，如何提高空間查詢效率、能耗最小化以及最大限度降低路線成本仍然是研究者們的關注熱點[85]。為了解決無線廣播環(huán)境下道路網(wǎng)絡中的空間關鍵字查詢處理問題，文獻[86]提出了一種新的索引策略，即時空文本索引結構ST2I，它采用無上下文的文本映射算法對文本進行數(shù)字編碼，減少內存占用和無關對象的檢索數(shù)量，降低查詢處理時間。文獻[87-88]提出了兩種近似算法和精確算法來處理道路網(wǎng)絡上的集體空間關鍵字查詢(CSKQ)問題。另外，文獻[89]設計了一種四簇雙濾波R樹(QDR-Tree)的雙層混合索引結構，用于處理屬性感知空間關鍵字查詢(ASKQ)問題。該索引基于層次聚類算法構建了四簇樹(QC-Tree)，并使用kernel k-means聚類算法對關鍵字進行分類。

由于經(jīng)濟高效的云計算的出現(xiàn)，云計算可在服務器上虛擬化存儲和計算資源，并向可信用戶提供數(shù)據(jù)?；贛apReduce平臺的真正的分布式空中索引方法M-Quadtree[90]和DIM[91]在MapReduce框架下構建了索引，滿足了MapReduce的并行化要求，并在Hadoop平臺上進行了查詢與實驗，有效減少調諧時間和訪問延遲，極大地優(yōu)化了查詢的效率。

文獻[92]設計了一種名為SKQAI的空中索引，它結合了路網(wǎng)加權四叉樹、關鍵字四叉樹和距離矩陣陣列，并提出了高效的算法用于處理布爾范圍查詢、Top-k查詢和排序空間查詢處理。文獻[93]討論了使用分布式R樹索引的位置查詢，它支持以并行方式執(zhí)行查詢，其性能優(yōu)于空間R樹索引。另外，在空間查詢處理的應用場景中，我們不再只需要考慮單個用戶，而是要考慮一組用戶對于多個查詢點的需求[94-98]。對于基于組的關鍵字感知路線問題(GKAR)查詢問題，文獻[99]提出了兩種近似算法、兩種精確算法以及一種貪婪算法來解決這個問題。一種面向數(shù)據(jù)的索引方法QUASII[100]通過逐步對數(shù)據(jù)進行排序的同時生成面向數(shù)據(jù)的層次結構，來減少數(shù)據(jù)反映時長并節(jié)約增量索引的成本。

3.4 空間連接查詢

在空間數(shù)據(jù)庫管理系統(tǒng)中，空間連接是一種重要操作，由于高復雜性和大量的空間數(shù)據(jù)，空間連接需要高處理成本。在歐式空間中，空間連接指的是在用戶給定的兩個或多個多維空間數(shù)據(jù)集中，檢索出符合給出空間查詢條件的一組空間對象對。而空間連接查詢則是一種常見的多路查詢，即從兩個多維空間數(shù)據(jù)集中檢索出滿足空間謂詞的空間對象，其中，空間謂詞有如相交、相鄰及包含等[101-102]。

在分布式空間連接查詢領域，具有代表性的是二路連接查詢與多路連接查詢。目前，空間連接查詢算法大致可以分為兩類：基于直接連接的優(yōu)化算法以及基于半連接的優(yōu)化算法。文獻[103]在半連接操作的基礎上提出了一種SDD-1算法，該算法減少了數(shù)據(jù)查詢的連接關系，從而降低連接查詢時的網(wǎng)絡傳輸數(shù)量。同樣基于半連接操作的優(yōu)化算法還有1-PSJ[104-105]等。另外，文獻[106]提出的自適應多級算法以及文獻[107]提出的站點依賴算法都是基于直接連接操作的優(yōu)化算法，自適應多級算法利用平面掃描和雙向節(jié)點的放大對距離對象進行快速剪枝，而站點依賴算法是對不同站點上符合用戶查詢條件的查詢關系進行分片處理再將其合并。針對面向網(wǎng)絡要素服務(WFS)的分布式連接查詢，文獻[108-109]分別介紹了哈希合并連接算法HMJ和對稱哈希鏈接算法，將哈希表中的哈希值進行排序和連接。由于哈希連接算法需要花費較長時間進行排序，文獻[110-111]都通過建立索引來優(yōu)化空間連接查詢。

4 研究展望

近年來，空間查詢處理技術的發(fā)展取得了很大的進步，研究者們研發(fā)出了多種用于空間查詢處理操作的高效空中索引以及相應的查詢算法，但目前在空間查詢這一技術領域內仍有許多問題需要進行改善，概括下來包括以下幾個方面：

1) 傳統(tǒng)多維數(shù)據(jù)索引的擴展性不夠好，僅能夠用于單服務器，在分布式空中索引的研究中需要支持多服務器的空間檢索，進行并行構建，減少經(jīng)典空間數(shù)據(jù)索引帶來的空間冗余問題，改善數(shù)據(jù)量負載不平衡。

2) 基于線性化技術的空中索引可以對空間數(shù)據(jù)進行降維度操作，且支持高擴展性，并行度高，但該方法并不適合空間范圍查詢，在空間數(shù)據(jù)更新之后會出現(xiàn)數(shù)據(jù)不平衡的問題。

3) 針對有效處理多個查詢的問題，以及一組查詢用戶的查詢需求，需要研究的方向不僅包括查詢區(qū)域和查詢屬性的重復，還包括解決值域重疊的問題。

4) 對于一些具備太多關鍵詞的數(shù)據(jù)對象，研究的方向需要設計一個統(tǒng)一的成本函數(shù)來避免這一問題，并將成本函數(shù)與集體空間關鍵字查詢處理相結合，擴展至其他的距離度量。

5) 不同空間查詢算法的使用范圍有限，將已經(jīng)提出的查詢算法擴展至其他查詢類型，如天際線查詢等也是一個很好的研究方向。

5 結 語

空間查詢是從空間數(shù)據(jù)庫中查找出滿足用戶條件的空間目標的過程，查找條件與空間位置有關。在許多應用領域，如GIS中，空間查詢操作無處不在，且空間查詢處理的性能是這些應用系統(tǒng)成功的關鍵所在?？罩兴饕夹g作為空間數(shù)據(jù)庫的關鍵技術之一，其目的是為了在空間數(shù)據(jù)庫中快速定位到所查詢的數(shù)據(jù)對象，是快速、高效地查詢、檢索和顯示空間查詢處理結果的重要指標。

本文在對空間查詢處理技術的相關概念和算法進行深入研究的基礎上，總結了歐式空間、道路網(wǎng)絡及無線廣播環(huán)境下常見的用于空間查詢處理的空中索引及查詢算法，并詳細描述了各類索引及算法的適用范圍和優(yōu)缺點。但是，對于移動客戶端進行空間查詢處理時所產生的訪問延遲與調諧時間的平衡，仍需眾多研究人員的不懈努力。