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

2014-09-02 21:10:20許興義陶明慧

科技視界 2014年22期

許興義　陶明慧

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

【關鍵詞】動態窗口；輪廓查詢技術

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所示。

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

2 動態窗口輪廓查詢技術

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

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

輪廓在涉及多標準決策的應用中起著非常重要的作用。例如，在出行選擇交通工具時，有火車和飛機可供選擇，可是飛機價格比火車票貴一些，但乘坐火車花費路途時間又太長，如何選擇適合自己最佳的方案，輪廓的計算可有效解決這樣的問題。如圖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進行搜索，采用相同的方法不斷修剪查詢空間。

對于每一個查詢到的輪廓上的點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]：

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所示。

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

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

繼續查詢窗口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個空間位置為輪廓點。

綜上所述，窗口查詢掃過的區域如圖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]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]劉國華，等.數據庫新理論、方法及技術導論[M].電子工業出版社，2006.

[責任編輯：湯靜]