基于動(dòng)態(tài)窗口的輪廓查詢技術(shù)研究

許興義 陶明慧

（中國(guó)人民解放軍西藏77635 部隊(duì)，西藏 錯(cuò)那856700）

1 輪廓查詢技術(shù)研究現(xiàn)狀

空間數(shù)據(jù)庫(kù)系統(tǒng)是描述、存儲(chǔ)和處理空間數(shù)據(jù)及其屬性數(shù)據(jù)的數(shù)據(jù)庫(kù)系統(tǒng)。空間數(shù)據(jù)庫(kù)是隨著GIS 的開發(fā)和應(yīng)用而發(fā)展起來(lái)的數(shù)據(jù)庫(kù)新技術(shù)。它不是獨(dú)立存在的系統(tǒng)，而是與應(yīng)用緊密結(jié)合，通常是GIS 的核心。 空間查詢優(yōu)化是空間數(shù)據(jù)庫(kù)相關(guān)技術(shù)研究的難點(diǎn)和突破點(diǎn)，輪廓查詢技術(shù)已經(jīng)成為空間查詢及優(yōu)化領(lǐng)域的熱點(diǎn)課題。 “輪廓”（Skyline）這個(gè)概念最初是2001 年Borzsonyi 等人在VLDB（Very Large Databases）會(huì)議上作為一個(gè)操作被提出來(lái)的。 由于輪廓查詢技術(shù)有著重要的理論研究?jī)r(jià)值和實(shí)際應(yīng)用價(jià)值，所以一直是相關(guān)領(lǐng)域?qū)＜覀兊难芯恐攸c(diǎn)。 下面分別介紹國(guó)內(nèi)外的研究成果。

D＆C （Divide-and-Conquer） 分治輪廓查詢方法[1]，2001 年ICDE（Interational Conference on Data Engineering）會(huì)議上，Borzsonyi 等人提出。 該方法將數(shù)據(jù)集劃分成多個(gè)分區(qū)，然后利用主存算法來(lái)分別計(jì)算每個(gè)分區(qū)內(nèi)的局部輪廓，最終的輪廓通過(guò)將局部輪廓篩選并獲得。 該方法僅對(duì)小數(shù)據(jù)集有效。因?yàn)椋绻麄€(gè)數(shù)據(jù)集符合內(nèi)存大小，那么僅需要應(yīng)用一次主存輪廓算法即可。 對(duì)于大數(shù)據(jù)集，分區(qū)的過(guò)程就需要至少一次讀和寫整個(gè)數(shù)據(jù)集，因此，導(dǎo)致嚴(yán)重的I/O 代價(jià)。 這種方法不適合在線處理，因?yàn)樗荒茉诜謪^(qū)階段完成之前返回任何輪廓點(diǎn)。

BNL （Block Nested Loop） 塊嵌套循環(huán)輪廓查詢方法[1]，2001 年ICDE 會(huì)議上，Borzsonyi 等人提出。這種方法就是基于這個(gè)思想掃描數(shù)據(jù)文件，在主存中保存一個(gè)輪廓點(diǎn)的候選列表，開始的時(shí)候列表中包含第一個(gè)數(shù)據(jù)點(diǎn)，隨后的點(diǎn)p 分3 種情況：

（1）如果p 被表中的任何一個(gè)點(diǎn)支配，那么p 會(huì)被刪除，它不是輪廓的一部分。

（2）如果p 支配列表中的任何點(diǎn)，那么p 將被插入列表中，并且列表中所有被p 支配的點(diǎn)都將被刪除。

（3）如果p 既不被支配，也不支配列表中的點(diǎn)，那么它將被插入到列表中，它有可能是輪廓的一部分。

BNL 的一個(gè)問(wèn)題就是列表可能變得比主存還要大，當(dāng)這種情況發(fā)生時(shí)，所有溢出的數(shù)據(jù)點(diǎn)都被添加到一個(gè)臨時(shí)文件中，這就需要多次執(zhí)行BNL。 BNL 的優(yōu)點(diǎn)就是它廣泛的應(yīng)用性，因?yàn)樗鼰o(wú)需索引或?qū)?shù)據(jù)文件排序就可以應(yīng)用到任意維上。BNL 的主要問(wèn)題就是對(duì)主存的依賴和在漸進(jìn)處理方面存在缺陷。

位圖輪廓查詢方法（Bitmap）[2]，2001 年VLDB 會(huì)議上，Tan 等人提出。 將所有的信息在位圖中編碼來(lái)確定一個(gè)點(diǎn)是否在輪廓上。 位圖法的效率依賴于位圖操作的速度。 這個(gè)輪廓的計(jì)算是昂貴的，因?yàn)閷?duì)于每一個(gè)要檢測(cè)的數(shù)據(jù)點(diǎn)，必須檢索所有點(diǎn)的位圖來(lái)得到對(duì)應(yīng)位。 如果不同值的數(shù)目非常大，那么，空間代價(jià)可能會(huì)很高。而且這種方法不適合動(dòng)態(tài)數(shù)據(jù)集。

NN（Nearest Neighbor）最近鄰輪廓查詢方法[3]，2002 年VLDB 會(huì)議上，Donald Kossmann 等人提出。 它利用最近鄰查詢的結(jié)果來(lái)遞歸劃分?jǐn)?shù)據(jù)空間，分別求得輪廓。最近鄰方法的查詢速度比前幾種方法都快，但是對(duì)于高維數(shù)據(jù)來(lái)說(shuō)，該方法存在嚴(yán)重的空間重合問(wèn)題。

SFS（Sort Filter Shyline）排序過(guò)濾輪廓查詢方法，2003 年ICDE 會(huì)議上，Chomicki 等人提出了BNL 的改進(jìn)方法。 根據(jù)一個(gè)優(yōu)先選擇函數(shù)首先對(duì)整個(gè)數(shù)據(jù)集進(jìn)行排序， 候選點(diǎn)按照分值以升序插入到列表中，因?yàn)榫哂械头种档狞c(diǎn)可以支配大量的點(diǎn)，因此，使得修剪更有效。 SFS展現(xiàn)出漸進(jìn)的特點(diǎn)，因?yàn)閿?shù)據(jù)的預(yù)排序能夠確保支配點(diǎn)p’的點(diǎn)p 必須在p’之前被訪問(wèn)，因此，能夠立即將插入到列表中的點(diǎn)作為輪廓點(diǎn)進(jìn)行輸出。然而SFS 不得不掃描整個(gè)數(shù)據(jù)文件才能返回一個(gè)完整的輪廓。

BBS（Branch and Bound Skyline）分支限界輪廓查詢方法，2005 年TODS（Transactions on Database Systems）會(huì)議上，D.Papadias 等人提出。它與前面的最近鄰輪廓查詢方法類似，采用分支限界矩形圖，通過(guò)深度優(yōu)先遍歷算法來(lái)進(jìn)行輪廓查詢，該方法沒(méi)有考慮到用戶后期篩選計(jì)算的方便性，缺少一定的實(shí)際應(yīng)用性，不能很好地滿足用戶的需求。

以上幾種輪廓查詢技術(shù)的比較如表1 所示。

表1 幾種輪廓查詢技術(shù)的比較

基于以上分析， 本論文將采用基于動(dòng)態(tài)窗口的輪廓查詢技術(shù)，可以較好解決以上查詢方法存在的缺陷。

2 動(dòng)態(tài)窗口輪廓查詢技術(shù)

2.1 空間數(shù)據(jù)庫(kù)輪廓查詢示例

在d 維空間中，輪廓是一個(gè)d 維點(diǎn)的集合，點(diǎn)集合是由在所有維上不被其它任何一個(gè)點(diǎn)支配的點(diǎn)組成。 假定一個(gè)點(diǎn)的集合P1，P2，…，Ps， 點(diǎn)Pi支配點(diǎn)Pj當(dāng)且僅當(dāng)點(diǎn)Pi在任意軸上的坐標(biāo)都不大于點(diǎn)Pj對(duì)應(yīng)的坐標(biāo)。 查詢結(jié)果返回所有的點(diǎn)Pm，Pm是不被任一個(gè)Pn支配的點(diǎn)。

輪廓在涉及多標(biāo)準(zhǔn)決策的應(yīng)用中起著非常重要的作用。 例如，在出行選擇交通工具時(shí)，有火車和飛機(jī)可供選擇，可是飛機(jī)價(jià)格比火車票貴一些，但乘坐火車花費(fèi)路途時(shí)間又太長(zhǎng)，如何選擇適合自己最佳的方案，輪廓的計(jì)算可有效解決這樣的問(wèn)題。 如圖1 所示：

圖1 輪廓的示例

用x 軸來(lái)表示乘坐交通工具的價(jià)格，用y 軸來(lái)表示路途花費(fèi)的時(shí)間，兩個(gè)坐標(biāo)軸表示的事物不同，所以單位尺度表示的意義也不同。坐標(biāo)系中的點(diǎn)表示花費(fèi)的時(shí)間。

點(diǎn)a,b,c 是最優(yōu)候選集，這3 個(gè)點(diǎn)不被空間中任何其它對(duì)象支配，其它的點(diǎn)相對(duì)這3 個(gè)點(diǎn)不是費(fèi)時(shí)長(zhǎng)就是價(jià)格高或者二者都有，都不理想。 點(diǎn)a 時(shí)間相對(duì)來(lái)說(shuō)長(zhǎng)，有最長(zhǎng)的時(shí)間但是價(jià)格低，點(diǎn)b 時(shí)間相對(duì)a來(lái)說(shuō)短一些，但是價(jià)格相對(duì)高一些，點(diǎn)c 價(jià)格最高，但花時(shí)最少，根據(jù)用戶自己的實(shí)際情況可選擇不同的出行方式。

2.2 基于動(dòng)態(tài)窗口查詢的輪廓查詢算法

2.2.1 算法思想[4-10]

基于動(dòng)態(tài)窗口查詢的輪廓查詢算法通過(guò)窗口查詢q 來(lái)訪問(wèn)所有輪廓點(diǎn)集合中的點(diǎn)，是將單個(gè)輪廓查詢轉(zhuǎn)換為多個(gè)不同的動(dòng)態(tài)窗口查詢，只有查詢窗口的右邊界是移動(dòng)的。 查詢窗口不斷變化來(lái)縮小查詢空間，訪問(wèn)有可能是輪廓上的點(diǎn)，并且每個(gè)數(shù)據(jù)點(diǎn)只訪問(wèn)一次。不用訪問(wèn)空間對(duì)象集合中的全部數(shù)據(jù)點(diǎn)。

如圖2 所示，N1，N2是空間中的兩個(gè)最小邊界矩形（Minimum Bounding Rectangle，MBR），MBR 是用來(lái)界定地圖大小的，確保要查詢的空間信息都在該范圍內(nèi)，MBR 可人為設(shè)定，一般以地圖的左下角和右上角標(biāo)注。 首先生成一個(gè)查詢窗口q，窗口的長(zhǎng)q.length 是與y 軸距離最近的MBR 到y(tǒng) 軸的距離，即q.length=|0F|(0 是原點(diǎn))，其寬q.width是與x 軸距離最遠(yuǎn)的MBR 到x 軸的距離，即q.width=|AF|。搜索到點(diǎn)a和h 在查詢窗口q 中，因?yàn)樵诓樵兇翱趦?nèi)只有空間數(shù)據(jù)點(diǎn)a 和h，沒(méi)有其它的點(diǎn)的橫坐標(biāo)小于點(diǎn)a 和h，且h 的縱坐標(biāo)小于a 的縱坐標(biāo)，所以點(diǎn)h 支配點(diǎn)a,點(diǎn)h 是輪廓點(diǎn)的點(diǎn)。 點(diǎn)h 支配矩形ABCD 內(nèi)的數(shù)據(jù)點(diǎn)，因此矩形ABCD 內(nèi)的所有點(diǎn)肯定不是輪廓中的點(diǎn)，有可能成為輪廓中的點(diǎn)的數(shù)據(jù)點(diǎn)必定在矩形DCEF 內(nèi)，下一步就不必對(duì)矩形ABCD 進(jìn)行搜索了，只要對(duì)矩形DCEF 進(jìn)行搜索即可。 那么就以點(diǎn)h(點(diǎn)D)為查詢窗口的一個(gè)頂點(diǎn)對(duì)矩形DCEF 進(jìn)行搜索，采用相同的方法不斷修剪查詢空間。

圖2 輪廓查詢分析

圖3 查詢的有效區(qū)域

對(duì)于每一個(gè)查詢到的輪廓上的點(diǎn)p 來(lái)說(shuō)，都對(duì)應(yīng)著一個(gè)有效區(qū)域V，這個(gè)有效區(qū)域V 就是以點(diǎn)p 為左上角頂點(diǎn)的區(qū)域。 如圖3 所示，點(diǎn)p 是剛查詢到的輪廓點(diǎn)，陰影區(qū)就是點(diǎn)p 對(duì)應(yīng)的有效區(qū)，接下來(lái)要查找的輪廓點(diǎn)都在這個(gè)有效區(qū)V 內(nèi)。 因?yàn)閰^(qū)域A 內(nèi)的空間數(shù)據(jù)點(diǎn)已經(jīng)經(jīng)過(guò)查詢判斷，區(qū)域B 內(nèi)的點(diǎn)全部被點(diǎn)p 支配，所以只有區(qū)域V 是輪廓點(diǎn)所在的區(qū)域。 這樣就只對(duì)這點(diǎn)p 的有效區(qū)進(jìn)行查詢，不必對(duì)整個(gè)空間進(jìn)行查詢。

2.2.2 算法描述

算法說(shuō)明和分析中用到的符號(hào)表示如下：

S 表示空間數(shù)據(jù)點(diǎn)集；p 表示空間數(shù)據(jù)點(diǎn)集s 中的數(shù)據(jù)點(diǎn)；L 表示輪廓列表；Li表示輪廓列表中第i 個(gè)輪廓點(diǎn)；Pn表示第n 個(gè)查詢窗口；VU表示查詢窗口上邊界的速率；VB表示查詢窗口下邊界的速率，VR表示查詢窗口右邊界的速率；N 表示MBR 構(gòu)成的中間結(jié)點(diǎn)；q.length表示查詢窗口q 的長(zhǎng)度；q.width 表示查詢窗口q 的寬度；p.x 表示數(shù)據(jù)點(diǎn)p 的x 坐標(biāo)；p.y 表示數(shù)據(jù)點(diǎn)p 的x 坐標(biāo)和y 坐標(biāo)。

基于動(dòng)態(tài)窗口查詢的輪廓查詢算法具體描述如下[11]：

輸入：空間數(shù)據(jù)點(diǎn)集S

輸出：輪廓點(diǎn)集L 及其對(duì)應(yīng)的查詢窗口

Begin

Step1:L=Φ;VU=0; VB=0;VL=0;VR=1;

q1.length=0;

q1.width=Maxdist_x(Ni);

n=1;

Step2:while q 的右邊界沒(méi)有到達(dá)所有MBR 的右邊界do

If N 與q 相交then

{將N 中落入q 中的點(diǎn)進(jìn)行比較，y 軸坐標(biāo)最小的點(diǎn)Pi插入L 中，Li=Pi;

以點(diǎn)Pi為查詢窗口的左上頂點(diǎn)，且n=n+1;

Qn.length=0; Qnwidth=‖Pi.y‖ ;

IfPi.y=Pi.y(i＜j) then

Pj從列表中刪除；}

Return(Li, qn);

Return(Li, qn);

End while

End

2.2.3 算法分析

基于動(dòng)態(tài)窗口查詢的輪廓查詢算法將單個(gè)輪廓查詢轉(zhuǎn)換為多個(gè)不同的動(dòng)態(tài)窗口查詢，只有查詢窗口的右邊界是移動(dòng)的，其他邊界都是靜止的。 算法僅需要對(duì)有效區(qū)內(nèi)的空間數(shù)據(jù)點(diǎn)進(jìn)行查詢，無(wú)須對(duì)整個(gè)空間的數(shù)據(jù)點(diǎn)進(jìn)行搜索查詢，有效地減少了查詢空間，被訪問(wèn)點(diǎn)的數(shù)量明顯減少。

查詢窗口只訪問(wèn)輪廓點(diǎn)和與輪廓點(diǎn)具有部分相同坐標(biāo)的點(diǎn)，并且每個(gè)數(shù)據(jù)點(diǎn)只訪問(wèn)一次。 被查詢窗口檢索到數(shù)據(jù)點(diǎn)不一定就是輪廓點(diǎn)，需要根據(jù)其坐標(biāo)情況進(jìn)一步的判斷才行。 被檢索到的數(shù)據(jù)點(diǎn)主要有下面3 種情況：

1）有多個(gè)數(shù)據(jù)點(diǎn)同時(shí)落入查詢窗口中，即這些數(shù)據(jù)點(diǎn)具有相同的x 坐標(biāo)。 如圖4 所示。

圖4 情況1 多個(gè)數(shù)據(jù)點(diǎn)落入查詢窗口

圖5 情況2 落入查詢窗口的數(shù)據(jù)點(diǎn)與輪廓點(diǎn)部分坐標(biāo)相等

2）新落入窗口的數(shù)據(jù)點(diǎn)與上一個(gè)插入到輪廓列表L 中的輪廓點(diǎn)具有相同的y 坐標(biāo)，根據(jù)輪廓的支配定義可知，新點(diǎn)被支配，不是輪廓點(diǎn)，所以將新點(diǎn)刪除。 如圖5 所示。

3）落入查詢窗口但又不滿足前兩個(gè)條件的數(shù)據(jù)點(diǎn)肯定是輪廓上的點(diǎn)，將其加入輪廓列表L 中。

3 基于動(dòng)態(tài)窗口輪廓查詢技術(shù)設(shè)計(jì)與實(shí)現(xiàn)

下面舉例對(duì)基于動(dòng)態(tài)窗口查詢的輪廓查詢算法對(duì)人員管理信息系統(tǒng)中的數(shù)據(jù)對(duì)象（靜態(tài)數(shù)據(jù)對(duì)象）進(jìn)行輪廓查詢，詳細(xì)分析并說(shuō)明其具體查詢過(guò)程。

假設(shè)有空間數(shù)據(jù)點(diǎn)集S，S={a,b,c,d,e,f,g,h,i}，空間數(shù)據(jù)點(diǎn)的坐標(biāo)分別 為a(1,9)，b(2,10)，c(4,8)，d(6,7)，e(10,8)，f(7,5)，g(5,6)，h(4,4)，i(3,2)，j(10,4)，k(9,1)，m(6,2)，n(8,3)分 別 表 示 流 動(dòng) 人 員 暫 住 地、流 動(dòng) 人 員 工 作地、發(fā)現(xiàn)流動(dòng)人員位置、執(zhí)法人員固定執(zhí)勤點(diǎn)、發(fā)現(xiàn)大量流動(dòng)人員位置、執(zhí)法人員流動(dòng)執(zhí)勤點(diǎn)、臨檢人員、臨檢固定點(diǎn)、臨檢發(fā)現(xiàn)流動(dòng)人員處、執(zhí)法單位駐地、地方政府所在位置、臨檢流動(dòng)點(diǎn)，如圖6 所示。

根據(jù)這些點(diǎn)，生成其MBR 如圖7 所示。

圖6 空間數(shù)據(jù)

圖7 MBR

假設(shè)所有空間數(shù)據(jù)點(diǎn)都在坐標(biāo)系的第一象限中，建立坐標(biāo)系。 設(shè)輪廓點(diǎn)集為L(zhǎng)，查詢過(guò)程：首先輪廓點(diǎn)集L 設(shè)為Φ，生成一個(gè)查詢窗口q，查詢窗口的一個(gè)頂點(diǎn)在原點(diǎn)0，其長(zhǎng)q.length 是與y 軸距離最近的MBR 到y(tǒng) 軸的距離，其寬q.width 是與x 軸距離最遠(yuǎn)的MBR 到x 軸的距離， 如圖8 所示。 當(dāng)前檢索到點(diǎn)a 落在查詢窗口內(nèi)， 將點(diǎn)a 插入L中，L={a}即首先檢索到的是流動(dòng)人員暫住地，并成為首個(gè)輪廓點(diǎn)。

圖8 L={a}

然后查詢窗口q 改為以點(diǎn)a 為一頂點(diǎn)， 其寬q.width 是-‖a.y‖,其中‖a.y‖表示點(diǎn)a 到x 軸的距離， 負(fù)號(hào)表示y 軸負(fù)方向的長(zhǎng)度，這樣點(diǎn)a 是查詢窗口的左上角頂點(diǎn)。 相反，正號(hào)表示y 軸正方向的長(zhǎng)度，那么點(diǎn)a 就是查詢窗口的左下角頂點(diǎn)。 查詢窗口q 的長(zhǎng)q.length 由0開始不斷增加，直到查詢到中間輸入，并且有空間點(diǎn)落入查詢窗口中。如圖9 所示，點(diǎn)i 落入查詢窗口，i.y≠a.y，則將點(diǎn)i 插入L 中，L={a，i}即臨檢發(fā)現(xiàn)流動(dòng)人員處成為輪廓點(diǎn)。

圖9 L={a,i}

接著，查詢窗口q 改為以點(diǎn)i 為一頂點(diǎn)，其寬q.width 是-‖i.y‖，其長(zhǎng)q.length 由0 開始不斷增加，直到有空間點(diǎn)落入查詢窗口中。 如圖10 所示，點(diǎn)m 落入查詢窗口，m.y=i.y，因?yàn)辄c(diǎn)m 被點(diǎn)i 支配，則點(diǎn)m不插入到L 中，所以L={a,i}。

圖10 L={a,i}

圖11 L={a,i,k}

繼續(xù)查詢窗口q 改為以點(diǎn)m 為一頂點(diǎn)，其寬q.width 是-‖m.y‖,其長(zhǎng)q.length 由0 開始不斷增加，直到把空間點(diǎn)落入查詢窗口中。 如圖11 所示，點(diǎn)k 落入q 中，k.y=i.y，將點(diǎn)k 插入L 中，L={a,i,k}即地方政府所在位置成為第3 個(gè)輪廓點(diǎn)。

按照上面的方法繼續(xù)執(zhí)行，當(dāng)查詢窗口到達(dá)MBR 的右邊界時(shí)，結(jié)束查詢。 如圖12 所示，查詢結(jié)束，最終結(jié)果L={a,i,k}。

圖13 是查詢所得的輪廓，輪廓上有數(shù)據(jù)點(diǎn)a,i,k 即流動(dòng)人員暫住地、 臨檢發(fā)現(xiàn)流動(dòng)人員處和地方政府所在位置3 個(gè)空間位置為輪廓點(diǎn)。

圖12 L={a,i,k}

圖13 查詢所得的輪廓

綜上所述，窗口查詢掃過(guò)的區(qū)域如圖14 陰影部分所示，空間直線右上側(cè)的點(diǎn)不在查詢范圍內(nèi)， 所以在查詢過(guò)程中不必對(duì)它們進(jìn)行訪問(wèn)，從而大大減少結(jié)點(diǎn)訪問(wèn)數(shù)。

圖14 查詢區(qū)域

［1］BorzsonyiS,KossmannD,StockerK.The Sky line Operator[C]. ICDE, 2001.

［2］Tan K, Eng P,Ooi B,Efficient Progressive Skyline Computation[C].VLDB,2001.

［3］Kossmann D,Ramsak F,Rost S.Shooting Stars in the Sky: an Online Algorit -hm for Skyline Queries[C].VLDB,2002.

［4］Yu Jing, Liu Xin,Liu Guo-hua.A Window-based Algorithm for Skyline Queri -es[J].Computer Society,2005,9.

［5］Stojmenovic I,MiyakawaM.An Optimal Parallel Algorithm for Solving the Maximal Elements Problem in thePlane[J].Parallel Computing,1988,7.

［6］Matousek J.Computing Dominances in En [C]//information Pro-cessing Letters,1991,38.

［7］Roussopoulos N,Kelly S,Vincent F.Nearest Neighbor Queries[C].SIGMOD,1995.

［8］HjaltasonG,SametH.DistanceBrowsinginSpatialDatabases[C].ACMTODS,1999,24.

［9］Kossmann D Rost S Rost S.Shooting Stars in the Sky:an Online Algorithm for Skyline Queries[C].VLDB,2002.

［10］Wang Wei-ping,Li Jian-zhong,Zhang Dong-dong,Guo Long-jiang.Sliding Wi -ndow Based Method for Processing Continuous J-A Queries on Data Streams[J].Journal of Software,April 2006.

［11］劉國(guó)華,等.數(shù)據(jù)庫(kù)新理論、方法及技術(shù)導(dǎo)論[M].電子工業(yè)出版社,2006.