基于位置的路網Skyline 查詢處理研究
2022-01-14 03:02:08萇仕涵王習特
計算機工程 2022年1期
白 梅，萇仕涵，王習特
（大連海事大學信息科學技術學院，遼寧大連 116000）
0 概述
Skyline 是解決數據庫中多目標決策問題的重要手段，其可以在多維數據查詢中為用戶推薦較好的選擇，方便用戶做出決策。具體地，給定一個多維數據點的集合P及數據點p，p'∈P，如果點p在每個維度中的值都比p'好，并且在至少一個維度上更好，則點p支配p'。所有不被集合中的其他點支配的點被稱為Skyline 點。
近年來，隨著全球定位系統和無線通信技術的發展，基于位置的服務（LBS）逐漸地被越來越多的用戶所使用，LBS 系統的主要目的是獲取用戶所在的位置，并向用戶提供即時信息以便用戶做出決策。例如，在導航系統中，旅客在城市中是想要找到滿足自己偏好的酒店。其中用戶到酒店的距離是空間屬性，酒店的價格、評分是非空間屬性。但現有的基于位置的查詢只是針對單一維度進行的查詢，解決諸如“查找距離查詢位置q最近的旅社”類似問題，顯然，這樣單一的查詢無法滿足用戶多樣化的需求。
因此，在路網環境下基于位置的Skyline 查詢成為LBS 研究的熱點。近年來，一些學者針對路網數據中的Skyline 問題進行了研究［1-3］。文獻［1］提出一種SSI 算法，主要是針對路網上每個數據點p計算一個Skyline 區域，只要查詢位置q位于該區域，p就是一個Skyline 點。然而，該方法的問題在于提前建立的索引代價過大，并且在數據點更新時就不再適用。文獻［2］提出一種最近鄰算法，通過廣度優先遍歷的方式找到Skyline 點，最近鄰算法的問題在于用戶必須提前給定閾值邊界，否則會一直進行下去，直到遍歷完整個路網。文獻［3］提出一種Skyline 查詢方法，該方法基于空間數據點構建網絡Voronoi 圖，并對查詢點建立查詢凸包，通過網絡Voronoi 圖的性質與查詢區域的位置關系對數據集約減，從而節省路網距離計算的開銷。然而，該方法在構建Voronoi 圖索引時代價過大，當數據點更新時就不再適用。
本文設計一種對路網上的數據點進行管理和更新的倒排索引結構，并提出路網上的Skyline 算法DSR。倒排索引結構可用于管理路網數據點的維度，并且根據數據點在各個維度的值由優到劣進行排序，使用該索引可以對不需要計算路網距離的數據點進行過濾，同時加快數據點間支配關系的判定。DSR 算法采取有效的掃描策略，只計算小部分數據點的路網距離即可高效地進行支配判定，在數據點更新的情況下給出DSR 算法的動態維護。最終采用真實的道路網數據，對本文算法的高效性以及有效性進行驗證。
1 相關研究
近年來，在路網環境下的Skyline 查詢處理引起研究人員的關注。CHOMICKI 等［4］介紹了Skyline 的相關概念，并提出一些基礎計算方法。DONG 等［5］提出組合式Skyline 的求解算法，并給出相關的更新算法。文獻［6］提出空間Skyline 的概念，即將路網距離換為歐式距離作為求解時考慮的一個維度。
DENG 等［7］提出在路網上進行Skyline 查詢的方法，給出了相對應的算法，并圍繞此問題，提出了相對應的協同擴張、下界約束等算法。然而，算法在大型路網上的距離計算成本過大。SAFAR 等［2］提出在路網上運用NN 算法，以查詢點為起點進行廣度優先遍歷，創建候選表，每掃描到一個數據點就與候選表的數據點進行比較，直到達到閾值邊界。
另外，文獻［1］提出的SSI 算法，提前是為每個路網上的數據點計算一個查詢區域Skyline scope，只要發起查詢的位置在該區域上，該數據點就是一個Skyline 點。然而，該算法提前建立索引代價過大，且每當發生數據點的更新時，整個索引需要重新計算。文獻［8-10］的算法都是在該索引基礎上進行擴展而來。
文獻［1］在針對路網環境下基于位置的Skyline查詢提出了Cdε-SQ（Continuous d-ε-Skyline Query）和CKnn-SQ（Continuous K nearest neighbor-Skyline Query）兩種算法。Cdε-SQ 的主要目的是為了節省路網距離計算的開銷，而CKnn-SQ 的主要目的是返回距離查詢位置最近的k個Skyline 數據點。然而，文獻［1］算法在路網距離計算方面存在一定缺陷，故而查詢效率較低。隨后，HUANG 等［11］又提出了在動態路網上的Skyline 查詢。
文獻［9-10，12］介紹了多重屬性道路網（MCN）中傳統Skyline 查詢問題（MCN Skyline）。MCN 中每條邊具有多維屬性，例如該邊的長度、經過該邊所需要的時間、經過該邊的費用等。
LIN［13］等與ZHOU［14］等研究了路網環境下針對移動對象的Skyline 查詢。該查詢假設路網上所有的查詢對象的位置都在不斷變化，查詢結果隨時都在更新。XU［15］等研究了路網環境下針對用戶發起查詢位置的隱私保護問題。TAO［16］等研究了流環境中的Skyline 計算。HUANG［17］等解決了在具有時變信息的動態道路網絡中有效處理天際線內連續查詢的問題。LIU［18］等提出一種ZINC模型，結合ZB 樹的優勢，并支持高效的Skyline 計算。
2 問題描述
本節給出路網下基于位置的Skyline 問題的形式化定義。表1為本文所使用的符號。
表1 符號含義Table 1 Meaning of symbols
2.1 問題定義
道路網絡建模為無向加權圖G=（V，E，W），其中：V是道路頂點集合；E是道路邊集合；W是邊長的集合。本文中討論的距離都是路網上的最短路徑距離。
在本文中，要求數據點的位置不能重合，給定數據點p∈P，每個數據點由多個非空間維度和一個空間維度組成，其中P的非空間屬性集合為Dcont=｛d1，d2，…，dm｝，數據點可以表示為p=
圖1 給出Skyline 查詢的示例，其中每個數據點對應一條旅社記錄，具有評分、價格2 個維度（注意，在該示例中用戶希望評分越高越好和價格越低越好）。所以，根據圖1 中的旅社信息列表來評估，數據點p1支配p4，因為p1評分維度和p4相同，在價格維度優于p4。
圖1 Skyline 查詢示例Fig.1 Example of Skyline query
例1如圖1（b）所示，p1的地理坐標為（v9，v10，3），表示p1在v9、v10邊上，p1到v9的距離為3。查詢位置q的地理坐標為（v2，v8，4）。
與傳統的Skyline 查詢不同，在道路網絡中處理Skyline 查詢需要考慮數據點的空間屬性。如圖1 所示，在z市中一共有20 家酒店（p1～p20），用戶在q位置召開會議，他想找到合適的酒店來給參會人員安排住宿，希望找到在價格和評分方面有優勢并且距離開會地點近的酒店。在這種情況下，當用戶從位置q發起查詢時，需要首先計算每個酒店到用戶的距離，然后結合價格、評分，來找到q的Skyline 結果集。可以看出，p4的價格和評分優于p3（見圖1），并且因為p4比p3更接近q（即p4在空間維度上更好），則p4支配p3。最終，基于位置q返回滿足用戶條件的酒店集合是｛p1，p4，p5，p6，p7，p12，p13，p16，p17｝。
定義1（空間支配）給定路網G上的數據點集合P和查詢位置q，p1，p2∈P，p1關于q空間支配p2（記作p1?q p2）需要滿足以下2 個條件：
1）?di∈Dcont∪｛dspatial｝，p1［di］不差于p2［di］；
2）?dj∈Dcont∪｛dspatial｝，p1［dj］好于p2［dj］。
定義2（路網Skyline 集合）給定路網G上的數據點集合P和查詢位置q，道路網Skyline 點集合就是不被其他數據點關于位置q空間支配的點的集合，記作SKY（q，P）＝｛p2｜p1，p2∈Pp1?q p2｝。
例2利用圖1 的數據集舉例說明，若不考慮其空間屬性，得到的Skyline 集合為｛p1，p6，p7，p9，p16，p17，p20｝，但在加入了空間屬性后，得到的Skyline 集合變為了｛p1，p3，p4，p6，p7，p9，p16，p17｝。
2.2 G-tree 索引
本文采用G-tree 索引［19］來快速計算路網上任意數據點到查詢位置間的最短路網距離。
G-tree 是將道路網遞歸地劃分為子網絡，并在子網絡的頂部構造樹結構索引，其中每個G-tree 節點都對應一個子網絡。針對圖1 對應的路網結構，進行的圖劃分結構如圖2（a）所示，建立好的G-tree 索引如圖2（b）所示。其中，各非葉節點內都存儲了該節點對應子圖內邊界點集合以及相應的距離矩陣，各葉節點內存儲了該子圖內邊界點到該子圖內其余路網節點的距離矩陣。
定義3（邊界點）給定圖G的子圖Gi，節點b1∈Vi，節點b2不屬于Vi。若滿足?（b1，b2）∈E，則稱節點b1、b2為邊界點，B（Gi）為Gi內的邊界點集合。
給定數據點p∈P，以及查詢位置q，下面介紹借助G-tree 索引，求出distance（p，q）。
例3圖2 展示了如何計算從q到p20的距離，首先通過距離排序列表找到距離q和p20最近的邊界點v2和v21。隨后通過哈希表（將邊界點映射到葉子節點）找到葉子節點G3（對于v2）和G6（對于v21），它們的最小公共祖先節點是G0，通過節點G3、G1、G2、G6來計算最短路網距離，圖2（c）中每個元素代表
圖2 基于G-tree 索引的路網距離Fig.2 Distance of road network based on G-tree index
3 查詢處理算法DSR
本節介紹管理路網數據點的倒排索引，利用該索引提出DSR 查詢處理方法對數據提前進行處理，并過濾剪枝數據集，使得進行Skyline 查詢時不必掃描整個路網數據集，避免大量計算路網距離的開銷。
3.1 管理路網數據點的倒排索引
對于路網上的數據點，采用特殊的倒排索引結構進行管理，在建立倒排索引時只針對將非空間維度的屬性映射到倒排索引中，對于距離維度，在使用時才進行計算。具體地，對數據點在每一個維度上的值都按照從優到劣的順序進行排序，距離維度初始時為空。
掃描策略：由于數據點可能在不同維度上表現各不相同，因此在掃描過程中，用count 變量表示已經在該維度上掃描過的數據點個數。對每一個數據點pi維護一個num 變量，表示數據點被掃描過的次數。每次掃描時都選擇count 值最小的維度，按照數據點由好到壞的順序進行掃描（若數據點值相同，則進行支配關系的判定）。
值得注意的是，針對距離維度，數據點的掃描順序是在路網上從查詢點q開始進行廣度遍歷，按照距離q由近及遠的順序進行處理，建立堆H用于存儲距離維度已處理的信息。初始H=｛
例4如圖3 所示，當第一次掃描到距離維度時，建立堆H，H=｛
圖3 距離維度掃描示例Fig.3 Example of distance dimension scanning
隨后處理p3，此時出堆的元素為數據點，即距離維度第一次掃描到的數據點是p3，進行Skyline 結果判定，把該數據點加入距離維度，同時距離維度的count 值加1。
掃描結束點：當數據點pi在所有維度上都被掃描過一次時，稱pi為掃描結束點。
定理1對于數據點pi，若其被掃描過的次數與維度數相同，則對于未掃描過的數據點pj（pj的掃描次數為0）都一定被pi支配。
證明根據支配的定義，假設pj不被pi支配，則?dj∈Dcont∪｛dspatial｝，pj［dj］好于pi［dj］。即在維度dj上pj的掃描次序在pi之前，違背了給定的條件，在所有維度上pi的掃描次序優于pj。得證。
定理2給定維度di，對于掃描到的在維度di上的數據點pi，若pi不被di上已掃描過的Skyline 點支配，則pi是Skyline 點。
證明若?pj支配pi，根據支配的定義，pj支配pi，需滿足條件之一為?dj∈Dcont∪｛dspatial｝，pj［dj］不差于pi［dj］；然而，定理2 給定條件中pj在維度di上的掃描次序在pi之后，即pi在維度di上優于pj，與支配定義矛盾。得證。
如圖4 所示，當掃描到價格維度的數據點p1時，只將其與p17進行空間支配關系比較即可，而不用與p16、p20比較，大幅提高了計算效率。因此，對每一個維度di建立結果集Ri，存儲該維度上已掃描過的所有Skyline 點。
圖4 初始倒排索引應用示例Fig.4 Example of initial inverted index application
數據點處理策略：根據掃描策略可知，當前維度掃描到的數據點只有可能被當前維度結果集Ri中的數據點支配，同時，若數據點pi在當前維度確定為Skyline 點時，只處理1 次，在其他維度再次掃描到pi時，只對pi的計數器加1，每個數據點第一次被掃描時，計算其距離維度上的值。
3.2 DSR 算法
本節描述算法DSR 查詢的全過程。首先對整個數據集建立倒排索引，隨后針對維度di∈Dcont∪｛dspatial｝建立結果集Ri，然后根據掃描策略開始掃描維度（若掃描維度為dspatial時，借助堆H進行廣度遍歷），在得到待處理數據集Pi后，利用G-tree 索引，計算其中數據點的距離維度，隨后與Ri中的數據點進行支配關系的判定，將不被支配的數據點加入到結果集R中，最后輸出結果集。
算法1DSR 算法描述
算法1 第2 行通過建立倒排索引來維護數據。第3 行～第22 行是算法主體，第5 行根據count 值確定掃描維度di，若di不是距離維度，則在得到待處理數據集后，算法第10 行使用基于G-tree 索引的動態規劃算法來計算Pi中數據點的最短路徑距離，其計算代價為O（lbf×|V|）2，V是路網上節點的個數，f為G-tree 上節點的分支數量。算法第12 行～第23 行是算法的主體，每掃描到一次數據點，若該數據點不被Pi中其他數據點空間支配且num 值為0，則將數據點加入到Ri中且num 值加1，當有一個數據點的num 值與維度數相同時，此時，該數據點為掃描結束點，結束算法。DSR 算法主要受|Ri|的影響，|Ri|為在維度di上的結果集，這部分算法的計算代價為O（|Ri|×|d|）。算法第25 行返回Skyline 結果集R，算法整體時間復雜度為O（lbf×|V|×|Ri|×|d|）2。
例5在圖5（a）中，在初始時各維度計數值分別為0、0、0。第一次掃描順序為價格維度，掃描到的數據點為p17，此時維度計數器被更新為1、0、0，p17掃描次數更新為1。接著處理評分維度，掃描到的數據點為p16、p20，維度計數器被更新為1、2、0，p16、p20掃描次數更新為1、1。接著處理距離維度，堆H處理的第一個數據點是p4，維度計數器被更新為1、2、1，p4掃描次數更新為1。這樣一直掃描下去，直到p9的掃描次數更新為3，此時p9成為掃描結束點，算法結束，最終結果集R=｛p1，p3，p4，p6，p7，p9，p16，p17｝。從圖5（b）可以看到，DSR 算法僅計算了少部分數據點的路網距離。
圖5 掃描策略應用示例Fig.5 Example of scanning strategy application
4 DSR 算法動態維護
DSR 算法的動態維護主要是在路網環境下，當數據點發生更新時DSR 算法的動態維護。動態維護主要包括新增數據點的處理以及失效數據點的處理兩個操作。
4.1 失效數據點的處理
定理3假設數據點pi在維度di∈Dtotal上已經被掃描過，若數據點pi只被數據點pold空間支配，且pold不是掃描結束點，則pi在維度di上的值一定不好于pold，且優于當前掃描位置處的數據點。
證明若只滿足pold?qpi，則?di∈Dcont∪｛dspatial｝，pold［di］不差于pi［di］，即在維度di上，pold掃描位置一定不差于pi，假設當前掃描位置處數據點為pj，若pj?q pi不成立，則需滿足?di∈Dcont∪｛dspatial｝，pi［di］好于pj［di］，即在維度di上，pi掃描位置好于pj。得證。
若pold不在現有的各個維度的結果集合并集中，則直接在倒排索引中刪去。如果pold屬于結果集合，則首先需要找到所有只被pold空間支配的數據點，具體做法是根據定理3，對所有已掃描過pold的維度上表現不好于pold但是優于當前掃描位置的數據點取交集，加入到候選集合Rt中。再將Rt中的數據點與R中的Skyline 點進行空間支配關系的判定，Rt中不被R的任意Skyline 點空間支配的數據點即是只被pold空間支配的數據點。隨后，判斷pold是否為掃描結束點。若pold是掃描結束點，則pold失效后算法未結束，需要找到新的掃描結束點pend。
例6如圖6 所示，若被刪除的數據點是p9，則p9是Skyline 點，若此時的掃描位置為p1，對在所有維度上表現不優于p9但是優于p1的數據點取交集，如圖6中的黑框部分所示，對黑框部分中的數據點取交集，將不在R中的數據點加入到候選集Rt中，得到Rt=｛p5，p8，p13，p15，p20，p12｝，將Rt中的數據點與R進行空間支配關系判定后，得到最終只被p9支配的數據點為p5、p8、p13、p20。隨后，由于p9是掃描結束點，因此算法繼續運行直到找到新的掃描結束點，輸出最終結果集。
圖6 動態維護應用示例Fig.6 Example of dynamic maintenance application
4.2 新插入數據點的處理
本文從以下2 個方面考慮pnew本身是否會成為空間Skyline 點以及pnew是否會支配掉結果集中的點：1）如果pnew不受任何維度上的結果集中的數據點支配，則pnew是空間Skyline 點，將其加入到該維度對應的結果集中，反之，pnew被支配掉；2）根據定理1，首先需要將結果集中的數據點與pnew進行支配關系的判定（不在結果集中的數據點一定被空間支配），因此需要將各個維度上結果集的并集中的數據點與pnew進行支配關系的判定（不在結果集中的數據點一定被空間支配），隨后在結果集中過濾掉所有被pnew空間支配的數據點。
算法2 描述了DSR 算法更新維護過程的細節。當數據點發生更新時，算法需要找到所有僅只被pold空間支配的數據點，具體做法是：首先，找到候選集合Rt中所有只被pold空間支配的數據點，其次，每找到一個數據點就與R比較，判斷其是否被R中的其他數據點空間支配。如果只能被pold空間支配，則將其從候選集中取出添加到結果集中。算法第17 行～第23 行描述了在有新插入數據點pnew的情況下DSR的動態維護。
算法2DSR 算法動態維護
算法2 第3 行～第11 行描述了當倒排索引中的數據點失效時的情形，若pold屬于結果集合，根據算法第3 行～第11 行，算法找到只被pold支配的數據點的計算代價為O（|Rt|）。若pold不屬于結果集合，算法只需要O（1）次操作，第13 行～第17 行描述了在有新插入數據點pnew的情況下DSR 的動態維護。在處理新插入數據點pnew時，需要判定pnew是否被R中的數據點支配，在最壞情況下，要將pnew與R中所有數據點進行比較，計算代價為O（|Ri|×|d|），隨后，刪除掉所有被pnew支配的數據點，DSR 算法動態維護的計算代價為O（|Ri|×|d|）。
5 實驗結果與分析
本節主要驗證所提DSR 算法的性能。該實驗環境配置為Inter Core i5 7300HQ 2.50 GHz CPU，8 GB內存，1T 硬盤，Windows 10 操作系統的PC。算法用C++語言編寫。為驗證本文所提算法的有效性，將SSI 算法和BSS 算法作為對比實驗。
設定對于G-tree，設定f為4，τ為64。本文使用真實路網數據驗證算法性能。真實數據采用的是兩個真實的路網數據集，出處來自GitHub 開源項目TransportationNetworks（網址為https：//github.com/bstabler/TransportationNetworks），第1 個路線圖是奧爾登堡羅德（德國的一個城市）網絡，由約6 000 個節點和7 000 條邊組成，第2 個路線圖是加利福尼亞公路網，其中包含21 048 個節點和21 693 條邊。這些數據集的統計信息如表1 所示。實驗默認在道路網絡上模擬生成1 000 個對象。每個對象都有3 個非空間屬性，其值均勻分布在［0，100］范圍內。實驗參數如表2 所示。
表2 實驗參數Table 2 Experimental parameters
5.1 數據點數量變化對算法性能的影響
在第1 組實驗中，本文研究了非空間維度的變化對SSI、BSS 算法以及本文DSR 算法的性能影響。圖7 所示為數據點集規模變化的實驗結果。可以看出，SSI 算法要優于本文DSR 算法以及BSS 算法，這是因為SSI 算法提前計算了所有數據點兩兩之間的空間支配關系以及互相之間的距離，只用確定查詢位置q的位置，即可直接返回結果集。而DSR 算法的效率遠遠優于BSS 算法，這是因為DSR 算法在映射后采用倒排索引進行掃描，在找到掃描結束點后，可以直接結束算法，節省了計算時間與計算成本。
圖7 數據點數量對查詢時間的影響Fig.7 Impact of data points number on query time
5.2 數據點更新速度對查詢性能的影響
在第2 組實驗中，本文研究了數據點更新變化對BSS、SSI 算法以及本文DSR 算法的性能的影響。如圖8 所示，數據點更新速度從1 到150。可以看出，隨著數據點更新速度的增加，3 種算法的性能都有所下降，但DSR 算法遠遠優于BSS 算法以及SSI 算法，主要是由于后者需要進行大量的路網距離計算，而基于倒排索引的DSR 算法只需要計算部分數據點的路網距離，在找到掃描結束點之后，就能直接返回整個Skyline 結果集。
圖8 數據點更新速度對查詢時間的影響Fig.8 Impact of data point update speed on query time
5.3 數據點數量對索引建立時間的影響
在第3 組實驗中，本文研究了數據點數量的變化對SSI、BSS 算法及本文DSR 算法性能的影響。如圖9 所示，數據點數量從范圍為500 到2 000。可以看到，隨著數據點規模的增加，3 種算法索引的建立時間性能都有所增加，但是DSR 算法遠遠優于另外2 種算法，主要原因是由于BBS 算法需要進行大量的數據點路網距離計算，而SSI 索引的建立需要計算好所有數據點之間的兩兩支配關系，以及遍歷整個路網集，可以看到當數據集增加到一定規模后，計算代價過大。而DSR 算法不需要直接計算出數據點之間的距離，所需的倒排索引以及G-Tree 索引的建立時間明顯優于前兩種算法。
圖9 數據點數量對索引建立時間及大小的影響Fig.9 Impact of number of data points on index creation time and size
6 結束語
本文提出一種在路網環境下基于倒排索引的Skyline 查詢優化方法。將管理路網數據點的倒排索引引入Skyline 查詢，在查詢前進行大量的過濾剪枝，從而提高實驗的查詢效率。在引入倒排索引的基礎上，采用提前分組的形式對算法進行優化，提高對數據點過濾的有效性，加快算法的計算速度。實驗結果驗證了本文算法的高效性。下一步將運用DSR 算法從數據集中快速返回給用戶可控數量的Skyline 結果，以達到提高算法查詢效率、幫助用戶快速決策的目的。
