基于動態窗口的輪廓查詢技術研究

許興義 陶明慧

（中國人民解放軍西藏77635 部隊，西藏 錯那856700）

1 輪廓查詢技術研究現狀

空間數據庫系統是描述、存儲和處理空間數據及其屬性數據的數據庫系統。空間數據庫是隨著GIS 的開發和應用而發展起來的數據庫新技術。它不是獨立存在的系統，而是與應用緊密結合，通常是GIS 的核心。 空間查詢優化是空間數據庫相關技術研究的難點和突破點，輪廓查詢技術已經成為空間查詢及優化領域的熱點課題。 “輪廓”（Skyline）這個概念最初是2001 年Borzsonyi 等人在VLDB（Very Large Databases）會議上作為一個操作被提出來的。 由于輪廓查詢技術有著重要的理論研究價值和實際應用價值，所以一直是相關領域專家們的研究重點。 下面分別介紹國內外的研究成果。

D＆C （Divide-and-Conquer） 分治輪廓查詢方法[1]，2001 年ICDE（Interational Conference on Data Engineering）會議上，Borzsonyi 等人提出。 該方法將數據集劃分成多個分區，然后利用主存算法來分別計算每個分區內的局部輪廓，最終的輪廓通過將局部輪廓篩選并獲得。 該方法僅對小數據集有效。因為，如果整個數據集符合內存大小，那么僅需要應用一次主存輪廓算法即可。 對于大數據集，分區的過程就需要至少一次讀和寫整個數據集，因此，導致嚴重的I/O 代價。 這種方法不適合在線處理，因為它不能在分區階段完成之前返回任何輪廓點。

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

（1）如果p 被表中的任何一個點支配，那么p 會被刪除，它不是輪廓的一部分。

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

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

BNL 的一個問題就是列表可能變得比主存還要大，當這種情況發生時，所有溢出的數據點都被添加到一個臨時文件中，這就需要多次執行BNL。 BNL 的優點就是它廣泛的應用性，因為它無需索引或將數據文件排序就可以應用到任意維上。BNL 的主要問題就是對主存的依賴和在漸進處理方面存在缺陷。

位圖輪廓查詢方法（Bitmap）[2]，2001 年VLDB 會議上，Tan 等人提出。 將所有的信息在位圖中編碼來確定一個點是否在輪廓上。 位圖法的效率依賴于位圖操作的速度。 這個輪廓的計算是昂貴的，因為對于每一個要檢測的數據點，必須檢索所有點的位圖來得到對應位。 如果不同值的數目非常大，那么，空間代價可能會很高。而且這種方法不適合動態數據集。

NN（Nearest Neighbor）最近鄰輪廓查詢方法[3]，2002 年VLDB 會議上，Donald Kossmann 等人提出。 它利用最近鄰查詢的結果來遞歸劃分數據空間，分別求得輪廓。最近鄰方法的查詢速度比前幾種方法都快，但是對于高維數據來說，該方法存在嚴重的空間重合問題。

SFS（Sort Filter Shyline）排序過濾輪廓查詢方法，2003 年ICDE 會議上，Chomicki 等人提出了BNL 的改進方法。 根據一個優先選擇函數首先對整個數據集進行排序， 候選點按照分值以升序插入到列表中，因為具有低分值的點可以支配大量的點，因此，使得修剪更有效。 SFS展現出漸進的特點，因為數據的預排序能夠確保支配點p’的點p 必須在p’之前被訪問，因此，能夠立即將插入到列表中的點作為輪廓點進行輸出。然而SFS 不得不掃描整個數據文件才能返回一個完整的輪廓。

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

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

表1 幾種輪廓查詢技術的比較

基于以上分析， 本論文將采用基于動態窗口的輪廓查詢技術，可以較好解決以上查詢方法存在的缺陷。

2 動態窗口輪廓查詢技術

2.1 空間數據庫輪廓查詢示例

在d 維空間中，輪廓是一個d 維點的集合，點集合是由在所有維上不被其它任何一個點支配的點組成。 假定一個點的集合P1，P2，…，Ps， 點Pi支配點Pj當且僅當點Pi在任意軸上的坐標都不大于點Pj對應的坐標。 查詢結果返回所有的點Pm，Pm是不被任一個Pn支配的點。

輪廓在涉及多標準決策的應用中起著非常重要的作用。 例如，在出行選擇交通工具時，有火車和飛機可供選擇，可是飛機價格比火車票貴一些，但乘坐火車花費路途時間又太長，如何選擇適合自己最佳的方案，輪廓的計算可有效解決這樣的問題。 如圖1 所示：

圖1 輪廓的示例

用x 軸來表示乘坐交通工具的價格，用y 軸來表示路途花費的時間，兩個坐標軸表示的事物不同，所以單位尺度表示的意義也不同。坐標系中的點表示花費的時間。

點a,b,c 是最優候選集，這3 個點不被空間中任何其它對象支配，其它的點相對這3 個點不是費時長就是價格高或者二者都有，都不理想。 點a 時間相對來說長，有最長的時間但是價格低，點b 時間相對a來說短一些，但是價格相對高一些，點c 價格最高，但花時最少，根據用戶自己的實際情況可選擇不同的出行方式。

2.2 基于動態窗口查詢的輪廓查詢算法

2.2.1 算法思想[4-10]

基于動態窗口查詢的輪廓查詢算法通過窗口查詢q 來訪問所有輪廓點集合中的點，是將單個輪廓查詢轉換為多個不同的動態窗口查詢，只有查詢窗口的右邊界是移動的。 查詢窗口不斷變化來縮小查詢空間，訪問有可能是輪廓上的點，并且每個數據點只訪問一次。不用訪問空間對象集合中的全部數據點。

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

圖2 輪廓查詢分析

圖3 查詢的有效區域

對于每一個查詢到的輪廓上的點p 來說，都對應著一個有效區域V，這個有效區域V 就是以點p 為左上角頂點的區域。 如圖3 所示，點p 是剛查詢到的輪廓點，陰影區就是點p 對應的有效區，接下來要查找的輪廓點都在這個有效區V 內。 因為區域A 內的空間數據點已經經過查詢判斷，區域B 內的點全部被點p 支配，所以只有區域V 是輪廓點所在的區域。 這樣就只對這點p 的有效區進行查詢，不必對整個空間進行查詢。

2.2.2 算法描述

算法說明和分析中用到的符號表示如下：

S 表示空間數據點集；p 表示空間數據點集s 中的數據點；L 表示輪廓列表；Li表示輪廓列表中第i 個輪廓點；Pn表示第n 個查詢窗口；VU表示查詢窗口上邊界的速率；VB表示查詢窗口下邊界的速率，VR表示查詢窗口右邊界的速率；N 表示MBR 構成的中間結點；q.length表示查詢窗口q 的長度；q.width 表示查詢窗口q 的寬度；p.x 表示數據點p 的x 坐標；p.y 表示數據點p 的x 坐標和y 坐標。

基于動態窗口查詢的輪廓查詢算法具體描述如下[11]：

輸入：空間數據點集S

輸出：輪廓點集L 及其對應的查詢窗口

Begin

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

q1.length=0;

q1.width=Maxdist_x(Ni);

n=1;

Step2:while q 的右邊界沒有到達所有MBR 的右邊界do

If N 與q 相交then

{將N 中落入q 中的點進行比較，y 軸坐標最小的點Pi插入L 中，Li=Pi;

以點Pi為查詢窗口的左上頂點，且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 算法分析

基于動態窗口查詢的輪廓查詢算法將單個輪廓查詢轉換為多個不同的動態窗口查詢，只有查詢窗口的右邊界是移動的，其他邊界都是靜止的。 算法僅需要對有效區內的空間數據點進行查詢，無須對整個空間的數據點進行搜索查詢，有效地減少了查詢空間，被訪問點的數量明顯減少。

查詢窗口只訪問輪廓點和與輪廓點具有部分相同坐標的點，并且每個數據點只訪問一次。 被查詢窗口檢索到數據點不一定就是輪廓點，需要根據其坐標情況進一步的判斷才行。 被檢索到的數據點主要有下面3 種情況：

1）有多個數據點同時落入查詢窗口中，即這些數據點具有相同的x 坐標。 如圖4 所示。

圖4 情況1 多個數據點落入查詢窗口

圖5 情況2 落入查詢窗口的數據點與輪廓點部分坐標相等

2）新落入窗口的數據點與上一個插入到輪廓列表L 中的輪廓點具有相同的y 坐標，根據輪廓的支配定義可知，新點被支配，不是輪廓點，所以將新點刪除。 如圖5 所示。

3）落入查詢窗口但又不滿足前兩個條件的數據點肯定是輪廓上的點，將其加入輪廓列表L 中。

3 基于動態窗口輪廓查詢技術設計與實現

下面舉例對基于動態窗口查詢的輪廓查詢算法對人員管理信息系統中的數據對象（靜態數據對象）進行輪廓查詢，詳細分析并說明其具體查詢過程。

假設有空間數據點集S，S={a,b,c,d,e,f,g,h,i}，空間數據點的坐標分別 為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)分 別 表 示 流 動 人 員 暫 住 地、流 動 人 員 工 作地、發現流動人員位置、執法人員固定執勤點、發現大量流動人員位置、執法人員流動執勤點、臨檢人員、臨檢固定點、臨檢發現流動人員處、執法單位駐地、地方政府所在位置、臨檢流動點，如圖6 所示。

根據這些點，生成其MBR 如圖7 所示。

圖6 空間數據

圖7 MBR

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

圖8 L={a}

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

圖9 L={a,i}

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

圖10 L={a,i}

圖11 L={a,i,k}

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

按照上面的方法繼續執行，當查詢窗口到達MBR 的右邊界時，結束查詢。 如圖12 所示，查詢結束，最終結果L={a,i,k}。

圖13 是查詢所得的輪廓，輪廓上有數據點a,i,k 即流動人員暫住地、 臨檢發現流動人員處和地方政府所在位置3 個空間位置為輪廓點。

圖12 L={a,i,k}

圖13 查詢所得的輪廓

綜上所述，窗口查詢掃過的區域如圖14 陰影部分所示，空間直線右上側的點不在查詢范圍內， 所以在查詢過程中不必對它們進行訪問，從而大大減少結點訪問數。

圖14 查詢區域

［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］劉國華,等.數據庫新理論、方法及技術導論[M].電子工業出版社,2006.