許興義　陶明慧

【摘 要】本文通過對幾種輪廓查詢技術(shù)的比較，選擇基于動態(tài)窗口的輪廓查詢技術(shù)作為研究對象，對其算法思想、算法描述和算法分析進行了詳細的闡述，并結(jié)合流動人員管理信息系統(tǒng)對其進行了具體的設(shè)計與實現(xiàn)。

【關(guān)鍵詞】動態(tài)窗口；輪廓查詢技術(shù)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2.1 算法思想[4-10]

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

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

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

2.2.2 算法描述

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

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

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

2.2.3 算法分析

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

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

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

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

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

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

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

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

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

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

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

假設(shè)所有空間數(shù)據(jù)點都在坐標(biāo)系的第一象限中，建立坐標(biāo)系。設(shè)輪廓點集為L，查詢過程：首先輪廓點集L設(shè)為Φ，生成一個查詢窗口q，查詢窗口的一個頂點在原點0，其長q.length是與y軸距離最近的MBR到y(tǒng)軸的距離，其寬q.width是與x軸距離最遠的MBR到x軸的距離，如圖8所示。當(dāng)前檢索到點a落在查詢窗口內(nèi)，將點a插入L中，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}即臨檢發(fā)現(xiàn)流動人員處成為輪廓點。

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

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

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

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

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

【參考文獻】

[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]Hjaltason G，Samet H.Distance Browsing in Spatial Databases[C].ACM TODS， 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]劉國華，等.數(shù)據(jù)庫新理論、方法及技術(shù)導(dǎo)論[M].電子工業(yè)出版社，2006.

[責(zé)任編輯：湯靜]

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

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

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

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

【參考文獻】

[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]Hjaltason G，Samet H.Distance Browsing in Spatial Databases[C].ACM TODS， 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]劉國華，等.數(shù)據(jù)庫新理論、方法及技術(shù)導(dǎo)論[M].電子工業(yè)出版社，2006.

[責(zé)任編輯：湯靜]

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

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

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

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

【參考文獻】

[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]Hjaltason G，Samet H.Distance Browsing in Spatial Databases[C].ACM TODS， 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]劉國華，等.數(shù)據(jù)庫新理論、方法及技術(shù)導(dǎo)論[M].電子工業(yè)出版社，2006.

[責(zé)任編輯：湯靜]