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