白 梅，萇仕涵，王習(xí)特

（大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院，遼寧大連 116000）

0 概述

Skyline 是解決數(shù)據(jù)庫(kù)中多目標(biāo)決策問(wèn)題的重要手段，其可以在多維數(shù)據(jù)查詢中為用戶推薦較好的選擇，方便用戶做出決策。具體地，給定一個(gè)多維數(shù)據(jù)點(diǎn)的集合P及數(shù)據(jù)點(diǎn)p，p'∈P，如果點(diǎn)p在每個(gè)維度中的值都比p'好，并且在至少一個(gè)維度上更好，則點(diǎn)p支配p'。所有不被集合中的其他點(diǎn)支配的點(diǎn)被稱為Skyline 點(diǎn)。

近年來(lái)，隨著全球定位系統(tǒng)和無(wú)線通信技術(shù)的發(fā)展，基于位置的服務(wù)（LBS）逐漸地被越來(lái)越多的用戶所使用，LBS 系統(tǒng)的主要目的是獲取用戶所在的位置，并向用戶提供即時(shí)信息以便用戶做出決策。例如，在導(dǎo)航系統(tǒng)中，旅客在城市中是想要找到滿足自己偏好的酒店。其中用戶到酒店的距離是空間屬性，酒店的價(jià)格、評(píng)分是非空間屬性。但現(xiàn)有的基于位置的查詢只是針對(duì)單一維度進(jìn)行的查詢，解決諸如“查找距離查詢位置q最近的旅社”類似問(wèn)題，顯然，這樣單一的查詢無(wú)法滿足用戶多樣化的需求。

因此，在路網(wǎng)環(huán)境下基于位置的Skyline 查詢成為L(zhǎng)BS 研究的熱點(diǎn)。近年來(lái)，一些學(xué)者針對(duì)路網(wǎng)數(shù)據(jù)中的Skyline 問(wèn)題進(jìn)行了研究［1-3］。文獻(xiàn)［1］提出一種SSI 算法，主要是針對(duì)路網(wǎng)上每個(gè)數(shù)據(jù)點(diǎn)p計(jì)算一個(gè)Skyline 區(qū)域，只要查詢位置q位于該區(qū)域，p就是一個(gè)Skyline 點(diǎn)。然而，該方法的問(wèn)題在于提前建立的索引代價(jià)過(guò)大，并且在數(shù)據(jù)點(diǎn)更新時(shí)就不再適用。文獻(xiàn)［2］提出一種最近鄰算法，通過(guò)廣度優(yōu)先遍歷的方式找到Skyline 點(diǎn)，最近鄰算法的問(wèn)題在于用戶必須提前給定閾值邊界，否則會(huì)一直進(jìn)行下去，直到遍歷完整個(gè)路網(wǎng)。文獻(xiàn)［3］提出一種Skyline 查詢方法，該方法基于空間數(shù)據(jù)點(diǎn)構(gòu)建網(wǎng)絡(luò)Voronoi 圖，并對(duì)查詢點(diǎn)建立查詢凸包，通過(guò)網(wǎng)絡(luò)Voronoi 圖的性質(zhì)與查詢區(qū)域的位置關(guān)系對(duì)數(shù)據(jù)集約減，從而節(jié)省路網(wǎng)距離計(jì)算的開銷。然而，該方法在構(gòu)建Voronoi 圖索引時(shí)代價(jià)過(guò)大，當(dāng)數(shù)據(jù)點(diǎn)更新時(shí)就不再適用。

本文設(shè)計(jì)一種對(duì)路網(wǎng)上的數(shù)據(jù)點(diǎn)進(jìn)行管理和更新的倒排索引結(jié)構(gòu)，并提出路網(wǎng)上的Skyline 算法DSR。倒排索引結(jié)構(gòu)可用于管理路網(wǎng)數(shù)據(jù)點(diǎn)的維度，并且根據(jù)數(shù)據(jù)點(diǎn)在各個(gè)維度的值由優(yōu)到劣進(jìn)行排序，使用該索引可以對(duì)不需要計(jì)算路網(wǎng)距離的數(shù)據(jù)點(diǎn)進(jìn)行過(guò)濾，同時(shí)加快數(shù)據(jù)點(diǎn)間支配關(guān)系的判定。DSR 算法采取有效的掃描策略，只計(jì)算小部分?jǐn)?shù)據(jù)點(diǎn)的路網(wǎng)距離即可高效地進(jìn)行支配判定，在數(shù)據(jù)點(diǎn)更新的情況下給出DSR 算法的動(dòng)態(tài)維護(hù)。最終采用真實(shí)的道路網(wǎng)數(shù)據(jù)，對(duì)本文算法的高效性以及有效性進(jìn)行驗(yàn)證。

1 相關(guān)研究

近年來(lái)，在路網(wǎng)環(huán)境下的Skyline 查詢處理引起研究人員的關(guān)注。CHOMICKI 等［4］介紹了Skyline 的相關(guān)概念，并提出一些基礎(chǔ)計(jì)算方法。DONG 等［5］提出組合式Skyline 的求解算法，并給出相關(guān)的更新算法。文獻(xiàn)［6］提出空間Skyline 的概念，即將路網(wǎng)距離換為歐式距離作為求解時(shí)考慮的一個(gè)維度。

DENG 等［7］提出在路網(wǎng)上進(jìn)行Skyline 查詢的方法，給出了相對(duì)應(yīng)的算法，并圍繞此問(wèn)題，提出了相對(duì)應(yīng)的協(xié)同擴(kuò)張、下界約束等算法。然而，算法在大型路網(wǎng)上的距離計(jì)算成本過(guò)大。SAFAR 等［2］提出在路網(wǎng)上運(yùn)用NN 算法，以查詢點(diǎn)為起點(diǎn)進(jìn)行廣度優(yōu)先遍歷，創(chuàng)建候選表，每掃描到一個(gè)數(shù)據(jù)點(diǎn)就與候選表的數(shù)據(jù)點(diǎn)進(jìn)行比較，直到達(dá)到閾值邊界。

另外，文獻(xiàn)［1］提出的SSI 算法，提前是為每個(gè)路網(wǎng)上的數(shù)據(jù)點(diǎn)計(jì)算一個(gè)查詢區(qū)域Skyline scope，只要發(fā)起查詢的位置在該區(qū)域上，該數(shù)據(jù)點(diǎn)就是一個(gè)Skyline 點(diǎn)。然而，該算法提前建立索引代價(jià)過(guò)大，且每當(dāng)發(fā)生數(shù)據(jù)點(diǎn)的更新時(shí)，整個(gè)索引需要重新計(jì)算。文獻(xiàn)［8-10］的算法都是在該索引基礎(chǔ)上進(jìn)行擴(kuò)展而來(lái)。

文獻(xiàn)［1］在針對(duì)路網(wǎng)環(huán)境下基于位置的Skyline查詢提出了Cdε-SQ（Continuous d-ε-Skyline Query）和CKnn-SQ（Continuous K nearest neighbor-Skyline Query）兩種算法。Cdε-SQ 的主要目的是為了節(jié)省路網(wǎng)距離計(jì)算的開銷，而CKnn-SQ 的主要目的是返回距離查詢位置最近的k個(gè)Skyline 數(shù)據(jù)點(diǎn)。然而，文獻(xiàn)［1］算法在路網(wǎng)距離計(jì)算方面存在一定缺陷，故而查詢效率較低。隨后，HUANG 等［11］又提出了在動(dòng)態(tài)路網(wǎng)上的Skyline 查詢。

文獻(xiàn)［9-10，12］介紹了多重屬性道路網(wǎng)（MCN）中傳統(tǒng)Skyline 查詢問(wèn)題（MCN Skyline）。MCN 中每條邊具有多維屬性，例如該邊的長(zhǎng)度、經(jīng)過(guò)該邊所需要的時(shí)間、經(jīng)過(guò)該邊的費(fèi)用等。

LIN［13］等與ZHOU［14］等研究了路網(wǎng)環(huán)境下針對(duì)移動(dòng)對(duì)象的Skyline 查詢。該查詢假設(shè)路網(wǎng)上所有的查詢對(duì)象的位置都在不斷變化，查詢結(jié)果隨時(shí)都在更新。XU［15］等研究了路網(wǎng)環(huán)境下針對(duì)用戶發(fā)起查詢位置的隱私保護(hù)問(wèn)題。TAO［16］等研究了流環(huán)境中的Skyline 計(jì)算。HUANG［17］等解決了在具有時(shí)變信息的動(dòng)態(tài)道路網(wǎng)絡(luò)中有效處理天際線內(nèi)連續(xù)查詢的問(wèn)題。LIU［18］等提出一種ZINC模型，結(jié)合ZB 樹的優(yōu)勢(shì)，并支持高效的Skyline 計(jì)算。

2 問(wèn)題描述

本節(jié)給出路網(wǎng)下基于位置的Skyline 問(wèn)題的形式化定義。表1為本文所使用的符號(hào)。

表1 符號(hào)含義Table 1 Meaning of symbols

2.1 問(wèn)題定義

道路網(wǎng)絡(luò)建模為無(wú)向加權(quán)圖G=（V，E，W），其中：V是道路頂點(diǎn)集合；E是道路邊集合；W是邊長(zhǎng)的集合。本文中討論的距離都是路網(wǎng)上的最短路徑距離。

在本文中，要求數(shù)據(jù)點(diǎn)的位置不能重合，給定數(shù)據(jù)點(diǎn)p∈P，每個(gè)數(shù)據(jù)點(diǎn)由多個(gè)非空間維度和一個(gè)空間維度組成，其中P的非空間屬性集合為Dcont=｛d1，d2，…，dm｝，數(shù)據(jù)點(diǎn)可以表示為p=，其中p［di］表示p在維度di上的值。P的空間屬性表示為dspatial，任意數(shù)據(jù)點(diǎn)p的空間屬性值是p的地理位置坐標(biāo)，用一個(gè)三元組表示，其中，vi和vj表示p的路網(wǎng)中所在邊的兩端頂點(diǎn)，distance 表示p到道路頂點(diǎn)vi的距離，dis（p，q）表示數(shù)據(jù)點(diǎn)p和q的路網(wǎng)上的最短距離。

圖1 給出Skyline 查詢的示例，其中每個(gè)數(shù)據(jù)點(diǎn)對(duì)應(yīng)一條旅社記錄，具有評(píng)分、價(jià)格2 個(gè)維度（注意，在該示例中用戶希望評(píng)分越高越好和價(jià)格越低越好）。所以，根據(jù)圖1 中的旅社信息列表來(lái)評(píng)估，數(shù)據(jù)點(diǎn)p1支配p4，因?yàn)閜1評(píng)分維度和p4相同，在價(jià)格維度優(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ù)點(diǎn)的空間屬性。如圖1 所示，在z市中一共有20 家酒店（p1～p20），用戶在q位置召開會(huì)議，他想找到合適的酒店來(lái)給參會(huì)人員安排住宿，希望找到在價(jià)格和評(píng)分方面有優(yōu)勢(shì)并且距離開會(huì)地點(diǎn)近的酒店。在這種情況下，當(dāng)用戶從位置q發(fā)起查詢時(shí)，需要首先計(jì)算每個(gè)酒店到用戶的距離，然后結(jié)合價(jià)格、評(píng)分，來(lái)找到q的Skyline 結(jié)果集?？梢钥闯?，p4的價(jià)格和評(píng)分優(yōu)于p3（見(jiàn)圖1），并且因?yàn)閜4比p3更接近q（即p4在空間維度上更好），則p4支配p3。最終，基于位置q返回滿足用戶條件的酒店集合是｛p1，p4，p5，p6，p7，p12，p13，p16，p17｝。

定義1（空間支配）給定路網(wǎng)G上的數(shù)據(jù)點(diǎn)集合P和查詢位置q，p1，p2∈P，p1關(guān)于q空間支配p2（記作p1?q p2）需要滿足以下2 個(gè)條件：

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ù)點(diǎn)集合P和查詢位置q，道路網(wǎng)Skyline 點(diǎn)集合就是不被其他數(shù)據(jù)點(diǎn)關(guān)于位置q空間支配的點(diǎn)的集合，記作SKY（q，P）＝｛p2｜p1，p2∈Pp1?q p2｝。

例2利用圖1 的數(shù)據(jù)集舉例說(shuō)明，若不考慮其空間屬性，得到的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］來(lái)快速計(jì)算路網(wǎng)上任意數(shù)據(jù)點(diǎn)到查詢位置間的最短路網(wǎng)距離。

G-tree 是將道路網(wǎng)遞歸地劃分為子網(wǎng)絡(luò)，并在子網(wǎng)絡(luò)的頂部構(gòu)造樹結(jié)構(gòu)索引，其中每個(gè)G-tree 節(jié)點(diǎn)都對(duì)應(yīng)一個(gè)子網(wǎng)絡(luò)。針對(duì)圖1 對(duì)應(yīng)的路網(wǎng)結(jié)構(gòu)，進(jìn)行的圖劃分結(jié)構(gòu)如圖2（a）所示，建立好的G-tree 索引如圖2（b）所示。其中，各非葉節(jié)點(diǎn)內(nèi)都存儲(chǔ)了該節(jié)點(diǎn)對(duì)應(yīng)子圖內(nèi)邊界點(diǎn)集合以及相應(yīng)的距離矩陣，各葉節(jié)點(diǎn)內(nèi)存儲(chǔ)了該子圖內(nèi)邊界點(diǎn)到該子圖內(nèi)其余路網(wǎng)節(jié)點(diǎn)的距離矩陣。

定義3（邊界點(diǎn)）給定圖G的子圖Gi，節(jié)點(diǎn)b1∈Vi，節(jié)點(diǎn)b2不屬于Vi。若滿足?（b1，b2）∈E，則稱節(jié)點(diǎn)b1、b2為邊界點(diǎn)，B（Gi）為Gi內(nèi)的邊界點(diǎn)集合。

給定數(shù)據(jù)點(diǎn)p∈P，以及查詢位置q，下面介紹借助G-tree 索引，求出distance（p，q）。

例3圖2 展示了如何計(jì)算從q到p20的距離，首先通過(guò)距離排序列表找到距離q和p20最近的邊界點(diǎn)v2和v21。隨后通過(guò)哈希表（將邊界點(diǎn)映射到葉子節(jié)點(diǎn)）找到葉子節(jié)點(diǎn)G3（對(duì)于v2）和G6（對(duì)于v21），它們的最小公共祖先節(jié)點(diǎn)是G0，通過(guò)節(jié)點(diǎn)G3、G1、G2、G6來(lái)計(jì)算最短路網(wǎng)距離，圖2（c）中每個(gè)元素代表。通過(guò)動(dòng)態(tài)規(guī)劃算法最終可以得到distance（q，p20）=35，如圖2（c）所示，最短路徑包括q、v2、v3、v21、p20。

圖2 基于G-tree 索引的路網(wǎng)距離Fig.2 Distance of road network based on G-tree index

3 查詢處理算法DSR

本節(jié)介紹管理路網(wǎng)數(shù)據(jù)點(diǎn)的倒排索引，利用該索引提出DSR 查詢處理方法對(duì)數(shù)據(jù)提前進(jìn)行處理，并過(guò)濾剪枝數(shù)據(jù)集，使得進(jìn)行Skyline 查詢時(shí)不必掃描整個(gè)路網(wǎng)數(shù)據(jù)集，避免大量計(jì)算路網(wǎng)距離的開銷。

3.1 管理路網(wǎng)數(shù)據(jù)點(diǎn)的倒排索引

對(duì)于路網(wǎng)上的數(shù)據(jù)點(diǎn)，采用特殊的倒排索引結(jié)構(gòu)進(jìn)行管理，在建立倒排索引時(shí)只針對(duì)將非空間維度的屬性映射到倒排索引中，對(duì)于距離維度，在使用時(shí)才進(jìn)行計(jì)算。具體地，對(duì)數(shù)據(jù)點(diǎn)在每一個(gè)維度上的值都按照從優(yōu)到劣的順序進(jìn)行排序，距離維度初始時(shí)為空。

掃描策略：由于數(shù)據(jù)點(diǎn)可能在不同維度上表現(xiàn)各不相同，因此在掃描過(guò)程中，用count 變量表示已經(jīng)在該維度上掃描過(guò)的數(shù)據(jù)點(diǎn)個(gè)數(shù)。對(duì)每一個(gè)數(shù)據(jù)點(diǎn)pi維護(hù)一個(gè)num 變量，表示數(shù)據(jù)點(diǎn)被掃描過(guò)的次數(shù)。每次掃描時(shí)都選擇count 值最小的維度，按照數(shù)據(jù)點(diǎn)由好到壞的順序進(jìn)行掃描（若數(shù)據(jù)點(diǎn)值相同，則進(jìn)行支配關(guān)系的判定）。

值得注意的是，針對(duì)距離維度，數(shù)據(jù)點(diǎn)的掃描順序是在路網(wǎng)上從查詢點(diǎn)q開始進(jìn)行廣度遍歷，按照距離q由近及遠(yuǎn)的順序進(jìn)行處理，建立堆H用于存儲(chǔ)距離維度已處理的信息。初始H=｛｝，每次取堆首元素處理，若處理的元素是查詢點(diǎn)或路網(wǎng)節(jié)點(diǎn)，則找到與該節(jié)點(diǎn)相連的數(shù)據(jù)點(diǎn)或路網(wǎng)節(jié)點(diǎn)重新加入堆中并按與q的路網(wǎng)距離進(jìn)行排序。若堆首元素是數(shù)據(jù)點(diǎn)，直接進(jìn)行Skyline 結(jié)果判定，把該數(shù)據(jù)點(diǎn)加入距離維度，同時(shí)距離維度的count 值加1。

例4如圖3 所示，當(dāng)?shù)谝淮螔呙璧骄嚯x維度時(shí)，建立堆H，H=｛｝。初始處理q，找到與q直接相連的路網(wǎng)節(jié)點(diǎn)及數(shù)據(jù)點(diǎn)v2、p3和v8，將其加入堆中，H=｛，，｝。然后處理v2，此時(shí)出堆的元素為路網(wǎng)節(jié)點(diǎn)，找到與v2相連的數(shù)據(jù)點(diǎn)以及路網(wǎng)節(jié)點(diǎn)加入H中，此時(shí)，H=｛，，，，，｝。

圖3 距離維度掃描示例Fig.3 Example of distance dimension scanning

隨后處理p3，此時(shí)出堆的元素為數(shù)據(jù)點(diǎn)，即距離維度第一次掃描到的數(shù)據(jù)點(diǎn)是p3，進(jìn)行Skyline 結(jié)果判定，把該數(shù)據(jù)點(diǎn)加入距離維度，同時(shí)距離維度的count 值加1。

掃描結(jié)束點(diǎn)：當(dāng)數(shù)據(jù)點(diǎn)pi在所有維度上都被掃描過(guò)一次時(shí)，稱pi為掃描結(jié)束點(diǎn)。

定理1對(duì)于數(shù)據(jù)點(diǎn)pi，若其被掃描過(guò)的次數(shù)與維度數(shù)相同，則對(duì)于未掃描過(guò)的數(shù)據(jù)點(diǎn)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，對(duì)于掃描到的在維度di上的數(shù)據(jù)點(diǎn)pi，若pi不被di上已掃描過(guò)的Skyline 點(diǎn)支配，則pi是Skyline 點(diǎn)。

證明若?pj支配pi，根據(jù)支配的定義，pj支配pi，需滿足條件之一為?dj∈Dcont∪｛dspatial｝，pj［dj］不差于pi［dj］；然而，定理2 給定條件中pj在維度di上的掃描次序在pi之后，即pi在維度di上優(yōu)于pj，與支配定義矛盾。得證。

如圖4 所示，當(dāng)掃描到價(jià)格維度的數(shù)據(jù)點(diǎn)p1時(shí)，只將其與p17進(jìn)行空間支配關(guān)系比較即可，而不用與p16、p20比較，大幅提高了計(jì)算效率。因此，對(duì)每一個(gè)維度di建立結(jié)果集Ri，存儲(chǔ)該維度上已掃描過(guò)的所有Skyline 點(diǎn)。

圖4 初始倒排索引應(yīng)用示例Fig.4 Example of initial inverted index application

數(shù)據(jù)點(diǎn)處理策略：根據(jù)掃描策略可知，當(dāng)前維度掃描到的數(shù)據(jù)點(diǎn)只有可能被當(dāng)前維度結(jié)果集Ri中的數(shù)據(jù)點(diǎn)支配，同時(shí)，若數(shù)據(jù)點(diǎn)pi在當(dāng)前維度確定為Skyline 點(diǎn)時(shí)，只處理1 次，在其他維度再次掃描到pi時(shí)，只對(duì)pi的計(jì)數(shù)器加1，每個(gè)數(shù)據(jù)點(diǎn)第一次被掃描時(shí)，計(jì)算其距離維度上的值。

3.2 DSR 算法

本節(jié)描述算法DSR 查詢的全過(guò)程。首先對(duì)整個(gè)數(shù)據(jù)集建立倒排索引，隨后針對(duì)維度di∈Dcont∪｛dspatial｝建立結(jié)果集Ri，然后根據(jù)掃描策略開始掃描維度（若掃描維度為dspatial時(shí)，借助堆H進(jìn)行廣度遍歷），在得到待處理數(shù)據(jù)集Pi后，利用G-tree 索引，計(jì)算其中數(shù)據(jù)點(diǎn)的距離維度，隨后與Ri中的數(shù)據(jù)點(diǎn)進(jìn)行支配關(guān)系的判定，將不被支配的數(shù)據(jù)點(diǎn)加入到結(jié)果集R中，最后輸出結(jié)果集。

算法1DSR 算法描述

算法1 第2 行通過(guò)建立倒排索引來(lái)維護(hù)數(shù)據(jù)。第3 行～第22 行是算法主體，第5 行根據(jù)count 值確定掃描維度di，若di不是距離維度，則在得到待處理數(shù)據(jù)集后，算法第10 行使用基于G-tree 索引的動(dòng)態(tài)規(guī)劃算法來(lái)計(jì)算Pi中數(shù)據(jù)點(diǎn)的最短路徑距離，其計(jì)算代價(jià)為O（lbf×|V|）2，V是路網(wǎng)上節(jié)點(diǎn)的個(gè)數(shù)，f為G-tree 上節(jié)點(diǎn)的分支數(shù)量。算法第12 行～第23 行是算法的主體，每掃描到一次數(shù)據(jù)點(diǎn)，若該數(shù)據(jù)點(diǎn)不被Pi中其他數(shù)據(jù)點(diǎn)空間支配且num 值為0，則將數(shù)據(jù)點(diǎn)加入到Ri中且num 值加1，當(dāng)有一個(gè)數(shù)據(jù)點(diǎn)的num 值與維度數(shù)相同時(shí)，此時(shí)，該數(shù)據(jù)點(diǎn)為掃描結(jié)束點(diǎn)，結(jié)束算法。DSR 算法主要受|Ri|的影響，|Ri|為在維度di上的結(jié)果集，這部分算法的計(jì)算代價(jià)為O（|Ri|×|d|）。算法第25 行返回Skyline 結(jié)果集R，算法整體時(shí)間復(fù)雜度為O（lbf×|V|×|Ri|×|d|）2。

例5在圖5（a）中，在初始時(shí)各維度計(jì)數(shù)值分別為0、0、0。第一次掃描順序?yàn)閮r(jià)格維度，掃描到的數(shù)據(jù)點(diǎn)為p17，此時(shí)維度計(jì)數(shù)器被更新為1、0、0，p17掃描次數(shù)更新為1。接著處理評(píng)分維度，掃描到的數(shù)據(jù)點(diǎn)為p16、p20，維度計(jì)數(shù)器被更新為1、2、0，p16、p20掃描次數(shù)更新為1、1。接著處理距離維度，堆H處理的第一個(gè)數(shù)據(jù)點(diǎn)是p4，維度計(jì)數(shù)器被更新為1、2、1，p4掃描次數(shù)更新為1。這樣一直掃描下去，直到p9的掃描次數(shù)更新為3，此時(shí)p9成為掃描結(jié)束點(diǎn)，算法結(jié)束，最終結(jié)果集R=｛p1，p3，p4，p6，p7，p9，p16，p17｝。從圖5（b）可以看到，DSR 算法僅計(jì)算了少部分?jǐn)?shù)據(jù)點(diǎn)的路網(wǎng)距離。

圖5 掃描策略應(yīng)用示例Fig.5 Example of scanning strategy application

4 DSR 算法動(dòng)態(tài)維護(hù)

DSR 算法的動(dòng)態(tài)維護(hù)主要是在路網(wǎng)環(huán)境下，當(dāng)數(shù)據(jù)點(diǎn)發(fā)生更新時(shí)DSR 算法的動(dòng)態(tài)維護(hù)。動(dòng)態(tài)維護(hù)主要包括新增數(shù)據(jù)點(diǎn)的處理以及失效數(shù)據(jù)點(diǎn)的處理兩個(gè)操作。

4.1 失效數(shù)據(jù)點(diǎn)的處理

定理3假設(shè)數(shù)據(jù)點(diǎn)pi在維度di∈Dtotal上已經(jīng)被掃描過(guò)，若數(shù)據(jù)點(diǎn)pi只被數(shù)據(jù)點(diǎn)pold空間支配，且pold不是掃描結(jié)束點(diǎn)，則pi在維度di上的值一定不好于pold，且優(yōu)于當(dāng)前掃描位置處的數(shù)據(jù)點(diǎn)。

證明若只滿足pold?qpi，則?di∈Dcont∪｛dspatial｝，pold［di］不差于pi［di］，即在維度di上，pold掃描位置一定不差于pi，假設(shè)當(dāng)前掃描位置處數(shù)據(jù)點(diǎn)為pj，若pj?q pi不成立，則需滿足?di∈Dcont∪｛dspatial｝，pi［di］好于pj［di］，即在維度di上，pi掃描位置好于pj。得證。

若pold不在現(xiàn)有的各個(gè)維度的結(jié)果集合并集中，則直接在倒排索引中刪去。如果pold屬于結(jié)果集合，則首先需要找到所有只被pold空間支配的數(shù)據(jù)點(diǎn)，具體做法是根據(jù)定理3，對(duì)所有已掃描過(guò)pold的維度上表現(xiàn)不好于pold但是優(yōu)于當(dāng)前掃描位置的數(shù)據(jù)點(diǎn)取交集，加入到候選集合Rt中。再將Rt中的數(shù)據(jù)點(diǎn)與R中的Skyline 點(diǎn)進(jìn)行空間支配關(guān)系的判定，Rt中不被R的任意Skyline 點(diǎn)空間支配的數(shù)據(jù)點(diǎn)即是只被pold空間支配的數(shù)據(jù)點(diǎn)。隨后，判斷pold是否為掃描結(jié)束點(diǎn)。若pold是掃描結(jié)束點(diǎn)，則pold失效后算法未結(jié)束，需要找到新的掃描結(jié)束點(diǎn)pend。

例6如圖6 所示，若被刪除的數(shù)據(jù)點(diǎn)是p9，則p9是Skyline 點(diǎn)，若此時(shí)的掃描位置為p1，對(duì)在所有維度上表現(xiàn)不優(yōu)于p9但是優(yōu)于p1的數(shù)據(jù)點(diǎn)取交集，如圖6中的黑框部分所示，對(duì)黑框部分中的數(shù)據(jù)點(diǎn)取交集，將不在R中的數(shù)據(jù)點(diǎn)加入到候選集Rt中，得到Rt=｛p5，p8，p13，p15，p20，p12｝，將Rt中的數(shù)據(jù)點(diǎn)與R進(jìn)行空間支配關(guān)系判定后，得到最終只被p9支配的數(shù)據(jù)點(diǎn)為p5、p8、p13、p20。隨后，由于p9是掃描結(jié)束點(diǎn)，因此算法繼續(xù)運(yùn)行直到找到新的掃描結(jié)束點(diǎn)，輸出最終結(jié)果集。

圖6 動(dòng)態(tài)維護(hù)應(yīng)用示例Fig.6 Example of dynamic maintenance application

4.2 新插入數(shù)據(jù)點(diǎn)的處理

本文從以下2 個(gè)方面考慮pnew本身是否會(huì)成為空間Skyline 點(diǎn)以及pnew是否會(huì)支配掉結(jié)果集中的點(diǎn)：1）如果pnew不受任何維度上的結(jié)果集中的數(shù)據(jù)點(diǎn)支配，則pnew是空間Skyline 點(diǎn)，將其加入到該維度對(duì)應(yīng)的結(jié)果集中，反之，pnew被支配掉；2）根據(jù)定理1，首先需要將結(jié)果集中的數(shù)據(jù)點(diǎn)與pnew進(jìn)行支配關(guān)系的判定（不在結(jié)果集中的數(shù)據(jù)點(diǎn)一定被空間支配），因此需要將各個(gè)維度上結(jié)果集的并集中的數(shù)據(jù)點(diǎn)與pnew進(jìn)行支配關(guān)系的判定（不在結(jié)果集中的數(shù)據(jù)點(diǎn)一定被空間支配），隨后在結(jié)果集中過(guò)濾掉所有被pnew空間支配的數(shù)據(jù)點(diǎn)。

算法2 描述了DSR 算法更新維護(hù)過(guò)程的細(xì)節(jié)。當(dāng)數(shù)據(jù)點(diǎn)發(fā)生更新時(shí)，算法需要找到所有僅只被pold空間支配的數(shù)據(jù)點(diǎn)，具體做法是：首先，找到候選集合Rt中所有只被pold空間支配的數(shù)據(jù)點(diǎn)，其次，每找到一個(gè)數(shù)據(jù)點(diǎn)就與R比較，判斷其是否被R中的其他數(shù)據(jù)點(diǎn)空間支配。如果只能被pold空間支配，則將其從候選集中取出添加到結(jié)果集中。算法第17 行～第23 行描述了在有新插入數(shù)據(jù)點(diǎn)pnew的情況下DSR的動(dòng)態(tài)維護(hù)。

算法2DSR 算法動(dòng)態(tài)維護(hù)

算法2 第3 行～第11 行描述了當(dāng)?shù)古潘饕械臄?shù)據(jù)點(diǎn)失效時(shí)的情形，若pold屬于結(jié)果集合，根據(jù)算法第3 行～第11 行，算法找到只被pold支配的數(shù)據(jù)點(diǎn)的計(jì)算代價(jià)為O（|Rt|）。若pold不屬于結(jié)果集合，算法只需要O（1）次操作，第13 行～第17 行描述了在有新插入數(shù)據(jù)點(diǎn)pnew的情況下DSR 的動(dòng)態(tài)維護(hù)。在處理新插入數(shù)據(jù)點(diǎn)pnew時(shí)，需要判定pnew是否被R中的數(shù)據(jù)點(diǎn)支配，在最壞情況下，要將pnew與R中所有數(shù)據(jù)點(diǎn)進(jìn)行比較，計(jì)算代價(jià)為O（|Ri|×|d|），隨后，刪除掉所有被pnew支配的數(shù)據(jù)點(diǎn)，DSR 算法動(dòng)態(tài)維護(hù)的計(jì)算代價(jià)為O（|Ri|×|d|）。

5 實(shí)驗(yàn)結(jié)果與分析

本節(jié)主要驗(yàn)證所提DSR 算法的性能。該實(shí)驗(yàn)環(huán)境配置為Inter Core i5 7300HQ 2.50 GHz CPU，8 GB內(nèi)存，1T 硬盤，Windows 10 操作系統(tǒng)的PC。算法用C++語(yǔ)言編寫。為驗(yàn)證本文所提算法的有效性，將SSI 算法和BSS 算法作為對(duì)比實(shí)驗(yàn)。

設(shè)定對(duì)于G-tree，設(shè)定f為4，τ為64。本文使用真實(shí)路網(wǎng)數(shù)據(jù)驗(yàn)證算法性能。真實(shí)數(shù)據(jù)采用的是兩個(gè)真實(shí)的路網(wǎng)數(shù)據(jù)集，出處來(lái)自GitHub 開源項(xiàng)目TransportationNetworks（網(wǎng)址為https：//github.com/bstabler/TransportationNetworks），第1 個(gè)路線圖是奧爾登堡羅德（德國(guó)的一個(gè)城市）網(wǎng)絡(luò)，由約6 000 個(gè)節(jié)點(diǎn)和7 000 條邊組成，第2 個(gè)路線圖是加利福尼亞公路網(wǎng)，其中包含21 048 個(gè)節(jié)點(diǎn)和21 693 條邊。這些數(shù)據(jù)集的統(tǒng)計(jì)信息如表1 所示。實(shí)驗(yàn)?zāi)J(rèn)在道路網(wǎng)絡(luò)上模擬生成1 000 個(gè)對(duì)象。每個(gè)對(duì)象都有3 個(gè)非空間屬性，其值均勻分布在［0，100］范圍內(nèi)。實(shí)驗(yàn)參數(shù)如表2 所示。

表2 實(shí)驗(yàn)參數(shù)Table 2 Experimental parameters

5.1 數(shù)據(jù)點(diǎn)數(shù)量變化對(duì)算法性能的影響

在第1 組實(shí)驗(yàn)中，本文研究了非空間維度的變化對(duì)SSI、BSS 算法以及本文DSR 算法的性能影響。圖7 所示為數(shù)據(jù)點(diǎn)集規(guī)模變化的實(shí)驗(yàn)結(jié)果。可以看出，SSI 算法要優(yōu)于本文DSR 算法以及BSS 算法，這是因?yàn)镾SI 算法提前計(jì)算了所有數(shù)據(jù)點(diǎn)兩兩之間的空間支配關(guān)系以及互相之間的距離，只用確定查詢位置q的位置，即可直接返回結(jié)果集。而DSR 算法的效率遠(yuǎn)遠(yuǎn)優(yōu)于BSS 算法，這是因?yàn)镈SR 算法在映射后采用倒排索引進(jìn)行掃描，在找到掃描結(jié)束點(diǎn)后，可以直接結(jié)束算法，節(jié)省了計(jì)算時(shí)間與計(jì)算成本。

圖7 數(shù)據(jù)點(diǎn)數(shù)量對(duì)查詢時(shí)間的影響Fig.7 Impact of data points number on query time

5.2 數(shù)據(jù)點(diǎn)更新速度對(duì)查詢性能的影響

在第2 組實(shí)驗(yàn)中，本文研究了數(shù)據(jù)點(diǎn)更新變化對(duì)BSS、SSI 算法以及本文DSR 算法的性能的影響。如圖8 所示，數(shù)據(jù)點(diǎn)更新速度從1 到150?？梢钥闯?，隨著數(shù)據(jù)點(diǎn)更新速度的增加，3 種算法的性能都有所下降，但DSR 算法遠(yuǎn)遠(yuǎn)優(yōu)于BSS 算法以及SSI 算法，主要是由于后者需要進(jìn)行大量的路網(wǎng)距離計(jì)算，而基于倒排索引的DSR 算法只需要計(jì)算部分?jǐn)?shù)據(jù)點(diǎn)的路網(wǎng)距離，在找到掃描結(jié)束點(diǎn)之后，就能直接返回整個(gè)Skyline 結(jié)果集。

圖8 數(shù)據(jù)點(diǎn)更新速度對(duì)查詢時(shí)間的影響Fig.8 Impact of data point update speed on query time

5.3 數(shù)據(jù)點(diǎn)數(shù)量對(duì)索引建立時(shí)間的影響

在第3 組實(shí)驗(yàn)中，本文研究了數(shù)據(jù)點(diǎn)數(shù)量的變化對(duì)SSI、BSS 算法及本文DSR 算法性能的影響。如圖9 所示，數(shù)據(jù)點(diǎn)數(shù)量從范圍為500 到2 000?？梢钥吹?，隨著數(shù)據(jù)點(diǎn)規(guī)模的增加，3 種算法索引的建立時(shí)間性能都有所增加，但是DSR 算法遠(yuǎn)遠(yuǎn)優(yōu)于另外2 種算法，主要原因是由于BBS 算法需要進(jìn)行大量的數(shù)據(jù)點(diǎn)路網(wǎng)距離計(jì)算，而SSI 索引的建立需要計(jì)算好所有數(shù)據(jù)點(diǎn)之間的兩兩支配關(guān)系，以及遍歷整個(gè)路網(wǎng)集，可以看到當(dāng)數(shù)據(jù)集增加到一定規(guī)模后，計(jì)算代價(jià)過(guò)大。而DSR 算法不需要直接計(jì)算出數(shù)據(jù)點(diǎn)之間的距離，所需的倒排索引以及G-Tree 索引的建立時(shí)間明顯優(yōu)于前兩種算法。

圖9 數(shù)據(jù)點(diǎn)數(shù)量對(duì)索引建立時(shí)間及大小的影響Fig.9 Impact of number of data points on index creation time and size

6 結(jié)束語(yǔ)

本文提出一種在路網(wǎng)環(huán)境下基于倒排索引的Skyline 查詢優(yōu)化方法。將管理路網(wǎng)數(shù)據(jù)點(diǎn)的倒排索引引入Skyline 查詢，在查詢前進(jìn)行大量的過(guò)濾剪枝，從而提高實(shí)驗(yàn)的查詢效率。在引入倒排索引的基礎(chǔ)上，采用提前分組的形式對(duì)算法進(jìn)行優(yōu)化，提高對(duì)數(shù)據(jù)點(diǎn)過(guò)濾的有效性，加快算法的計(jì)算速度。實(shí)驗(yàn)結(jié)果驗(yàn)證了本文算法的高效性。下一步將運(yùn)用DSR 算法從數(shù)據(jù)集中快速返回給用戶可控?cái)?shù)量的Skyline 結(jié)果，以達(dá)到提高算法查詢效率、幫助用戶快速?zèng)Q策的目的。