一種基于路網(wǎng)的多源聚合距離Skyline查詢算法

摘 要：基于路網(wǎng)距離的多源Skyline查詢在地圖服務中廣泛使用，但現(xiàn)有的Skyline查詢方法對于復雜的路網(wǎng)距離計算效率低下，并且隨著查詢點數(shù)量的增加查詢結果集變得過于龐大，無法為用戶提供精簡有效的查詢結果。為了提高查詢結果的有效性和查詢效率，提出一種基于最小聚合距離的倒排索引Skyline查詢算法，該算法對道路網(wǎng)建立QG-tree索引，提高聚合距離的計算效率；同時對興趣點集建立倒排索引，結合剪枝策略對興趣點進行檢索，減少聚合距離計算和支配判定的開銷，有效地提高查詢效率。在真實道路網(wǎng)上的實驗表明，所提出的算法效率比現(xiàn)有算法DSR和N3S快1～3個數(shù)量級，可以有效地處理道路網(wǎng)環(huán)境下多源Skyline查詢問題。

關鍵詞：道路網(wǎng)；Skyline查詢；最小聚合距離；倒排索引

中圖分類號：TP311.13 文獻標志碼：A

文章編號：1001-3695（2023）02-032-0504-07

doi：10.19734/j.issn.1001-3695.2022.06.0351

Multi-source aggregate distance Skyline query algorithm based on road network

Song Zhiyuan1，Ma Hui2，Liu Yi1

（1.School of Computer Science amp; Technology，Guangdong University of Technology，Guangzhou 510006，China；2.School of Artificial Intelligence，Shenzhen Ploytechnic，Shenzhen Guangdong 518055，China）

Abstract：Multi-source Skyline query based on road network distance is widely used in map services.However，the existing Skyline query methods are inefficient for complex road network distance calculation，and with the increasing of the number of the query point，the query result set becomes too large to provide users with tidy and effective query results.In order to improve the validity of the query results and the query efficiency，this paper proposed an inverted index Skyline query algorithm based on the minimum aggregation distance，which established QG-tree index for road network to improve the calculation efficiency of aggregation distance.And it established an inverted index for the points of interest set to retrieve the points of interest combined with pruning strategy，which reduced the overhead of aggregation distance calculation and the domination determination，and effectively improved the query efficiency.Finally，experiments on the real road network show that the efficiency of the proposed algorithm is 1～3 orders of magnitude faster than that of the existing algorithms DSR and N3S，and it can effectively handle the multi-source Skyline query problem in the road network.

Key words：road network；Skyline query；minimum aggregate distance；inverted index

0 引言

傳統(tǒng)的Skyline查詢是指在一個興趣點集中檢索不被其他點支配的興趣點。考慮兩個具有多維屬性的興趣點A、B，若A在每個維度上的屬性值都不比B差，且至少在某一個維度上的屬性值優(yōu)于B，則稱A支配B。例如，游客需要查找一個價格便宜、評分高的酒店，Skyline查詢返回一組在價格、評分兩個方面都不比其他酒店差的酒店集合。

近年來，隨著定位技術和智能手機的快速發(fā)展，基于位置的Skyline查詢廣泛應用在地圖服務中。傳統(tǒng)的Skyline查詢并未考慮查詢用戶的位置信息，并且只是針對單一查詢用戶。而實際生活中，用戶會考慮與目的地之間路程的遠近，并且由多個查詢用戶共同發(fā)起查詢，例如三個位于城市中不同位置的好友需要聚餐，希望找到價格便宜、評分高且距離三人近的餐廳。本文研究基于路網(wǎng)的多源Skyline查詢，在傳統(tǒng)的Skyline查詢的基礎上，考慮興趣點與多個查詢點之間的距離屬性。

現(xiàn)有的基于位置的多源Skyline查詢存在以下不足：a）部分查詢算法采用歐氏距離度量空間距離，而在實際生活中路網(wǎng)距離更符合應用需求，提供的查詢結果更加精確，例如位于河兩邊的兩點之間的歐氏距離雖然很近，但實際需要走更長的路網(wǎng)距離才能到達河對岸；b）部分查詢算法盡管使用路網(wǎng)距離，但在路網(wǎng)距離的計算上采用傳統(tǒng)的Dijkstra算法求解最短路徑，在大規(guī)模路網(wǎng)上Dijkstra算法的路網(wǎng)距離計算效率低下；c）隨著查詢點數(shù)量的增加，查詢需要考慮興趣點與查詢點之間的路網(wǎng)距離增多，路網(wǎng)距離計算和支配判定的開銷增加。同時，根據(jù)支配的定義，支配判定考慮的屬性維度越多，興趣點被支配的概率降低，導致查詢結果集的尺寸變得過于龐大，無法為查詢用戶提供精簡有效的查詢結果。

針對上述問題，本文提出了一種基于最小聚合距離的倒排索引Skyline查詢算法（inverted index Skyline query based on minimum aggregate distance，IMA）來解決道路網(wǎng)環(huán)境下多源Skyline查詢問題。本文的主要貢獻如下：a）提出采用一個聚合距離代替興趣點與查詢點之間的多個路網(wǎng)距離，減少支配判定需要考慮的屬性維度數(shù)，解決由查詢點數(shù)量增加帶來的問題；b）采用QG-tree索引對道路網(wǎng)進行遞歸地劃分建模，提高聚合距離的計算效率，從而提高查詢效率；c）采用倒排索引對興趣點集進行管理，結合剪枝策略對興趣點進行檢索，剪枝過濾興趣點，實現(xiàn)檢索部分興趣點即可得到查詢結果，減少聚合距離計算和支配判定的開銷，從而提高查詢效率。采用真實的道路網(wǎng)數(shù)據(jù)進行大量的實驗，對算法性能進行評估，驗證了算法的有效性。

1 相關工作

Borzsony等人［1］最早在數(shù)據(jù)庫中引入Skyline查詢，并提出了嵌套循環(huán)算法（block nested loops，BNL）和分治法（divided and conquer，Damp;C）。隨著Skyline查詢技術的快速發(fā)展，提出了更多的Skyline查詢類型，如反Skyline查詢［2］、基于MapReduce的Skyline查詢［3］、海量數(shù)據(jù)動態(tài)Skyline查詢［4］等。然而上述Skyline查詢無法為用戶提供基于位置的Skyline查詢服務。Sharifzadeh等人［5］提出了空間Skyline查詢，并提出了基于R-tree的B2S2算法和基于Voronoi圖的VS2算法；隨后，文獻［6，7］分別對基于社交網(wǎng)絡的內(nèi)聚組Skyline查詢、障礙空間中的Skyline查詢進行了研究。

傳統(tǒng)空間Skyline查詢算法都是基于理想的歐氏距離，無法適用于復雜的道路網(wǎng)環(huán)境。因此，Deng等人［8］將空間Skyline查詢拓展到復雜的道路網(wǎng)環(huán)境中，并提出了三種基于路網(wǎng)距離的多源Skyline查詢算法，分別是歐氏距離約束算法（Euclidean distance constraint，EDC）、協(xié)同擴展算法（collaborative expansion，CE）以及下界約束算法（lower bound constraint，LBC），其中CE算法通過查找查詢點的共同最近鄰點來實現(xiàn)對興趣點集的剪枝，EDC和LBC算法則是利用歐氏距離對興趣點集進行剪枝，減少路網(wǎng)距離計算的開銷。然而上述三種算法在剪枝過程中仍會產(chǎn)生大量的候選點，路網(wǎng)距離計算的開銷巨大，導致查詢效率低下。Safar等人［9］提出了基于最近鄰的N3S（network nearest neighbor Skyline）算法，通過查找查詢點的最近鄰點，找到第一個共同最近鄰點確定為Skyline點，再計算每個查詢點與其他查詢點的最近鄰點之間的路網(wǎng)距離，最后進行支配判定。該算法通過查找共同最近鄰點來縮小查詢范圍，減少路網(wǎng)距離計算的次數(shù)，從而提高查詢效率。

隨著對基于路網(wǎng)距離的Skyline查詢的深入研究，基于路網(wǎng)距離的連續(xù)Skyline查詢［10～12］、移動Skyline查詢［13，14］、動態(tài)路網(wǎng)Skyline查詢［15，16］、top-k Skyline查詢［17］和K-支配Skyline查詢［18］等相繼出現(xiàn)。出于對查詢用戶的隱私保護問題，Huang［16］提出了基于位置范圍的隱私保護Skyline 查詢，將查詢點模糊為一個位置范圍，計算興趣點與位置范圍邊界交點的路網(wǎng)距離，避免路網(wǎng)距離的重復計算。

對于解決基于路網(wǎng)距離的Skyline查詢問題，提高路網(wǎng)距離的計算效率是最關鍵的工作之一。現(xiàn)有算法提出了利用最近鄰［19，20］、Voronoi圖［21］等方法提高路網(wǎng)距離的計算效率。Zhong等人［22，23］提出了對道路網(wǎng)建立G-tree索引來提高路網(wǎng)距離的計算效率，遞歸地將道路網(wǎng)劃分為子網(wǎng)絡，每個子網(wǎng)絡對應一個樹節(jié)點，預先處理每個樹節(jié)點的邊界點和距離矩陣。基于預先處理的結果，并結合基于裝配的方法可以容易地計算道路網(wǎng)中任何兩點之間的最短路徑距離。在此基礎上，文獻［24］提出了DSR算法（dynamic Skyline processing based on road network）來提高道路網(wǎng)中單源Skyline查詢的效率，并解決興趣點的更新維護問題。

2 問題描述與定義

道路網(wǎng)多源Skyline查詢包含道路網(wǎng)、興趣點集以及查詢點集三個組成部分。道路網(wǎng)用一個無向加權圖G=（V，E，W）表示，其中V是道路網(wǎng)頂點集合，E是道路網(wǎng)邊集合，W是邊長度集合。對于道路網(wǎng)中的兩個頂點a和b，用dist（a，b）表示兩點之間的路網(wǎng)距離，即最短路徑距離。

給定一個道路網(wǎng)，如圖1（a）所示，有12個餐廳p1，…，p12和兩個查詢點q1、q2隨機分布在道路網(wǎng)上，每個餐廳具有價格、評分兩個屬性，每一個餐廳為一個興趣點。圖1（b）列出每個餐廳的價格、評分屬性以及到查詢點q1、q2的路網(wǎng)距離。

定義1 聚合距離。給定路網(wǎng)中一個興趣點p和一個查詢點集Q={q1，…，qk}，聚合距離定義為

dagg（p，Q）=∑q∈Qdist（p，q）（1）

使用一個聚合距離代替興趣點與查詢點之間的多個路網(wǎng)距離。例如，圖1中興趣點p1的聚合距離dagg（p1，Q）=47，p3的聚合距離dagg（p3，Q）=20，p4的聚合距離dagg（p4，Q）=26。

定義2 興趣點。給定的一個具有n+1維屬性的興趣點集P={p1，…，pm}，其中p［i］表示興趣點p在維度i上的屬性值，前n維表示興趣點的自身屬性（即價格、評分等），第n+1維表示興趣點與查詢點之間的聚合距離dagg（p，Q）。

例如，圖1給定一個具有三維屬性的興趣點集P={p1，…，p12}，p1［1］=150為p1在價格維度的屬性值， p1［2］=6為p1在評分維度的屬性值，p1［3］=47為p1在聚合距離維度的屬性值。

為了便于解釋，假設興趣點p和查詢點q位于道路網(wǎng)的頂點上，如果p或者q不是道路網(wǎng)頂點，可以把p或者q映射到道路網(wǎng)中與其距離最近的頂點。

定義3 道路網(wǎng)多源Skyline查詢。給定一個查詢點集Q和一個具有n+1維屬性的興趣點集P，基于路網(wǎng)的Skyline查詢返回一個興趣點集P的子集R，R中的每一個興趣點都不被P中其他興趣點支配。

例1 圖1給出了一個道路網(wǎng)多源Skyline查詢示例。假設圖1（a）道路網(wǎng)上兩個查詢用戶q1、q2要找到一個價格低、評分高且距離兩個查詢用戶近的餐廳聚餐。

在本例中，當僅要找一個價格低、評分高的餐廳時，得到Skyline查詢結果集R1={p3，p11，p12}。但在將興趣點與每個查詢點之間的路網(wǎng)距離加入查詢考慮范圍后，p12的價格、評分屬性都不比p6、p8差，且p12距離兩個查詢用戶更近，那么p12支配p6、p8，多源Skyline查詢結果集R2={p2，p3，p4，p5，p7，p11，p12}。使用一個聚合距離代替興趣點與查詢點的多個路網(wǎng)距離的多源Skyline查詢，p3的價格、評分屬性都不比p4差，且dagg（p3，Q）=20lt;dagg（p4，Q）=26，則p3支配p4。最終，多源Skyline查詢結果集R3={p3，p7，p11，p12}。

根據(jù)支配的定義，支配判定需要考慮的屬性維度的增加會降低興趣點被支配的概率。對比R1、R2和R3可以發(fā)現(xiàn)，將興趣點與查詢點之間的路網(wǎng)距離加入查詢考慮范圍后，查詢結果集的尺寸變大。不僅降低了查詢結果的精簡性和有效性，而且增加了路網(wǎng)距離計算和支配判定的開銷。相比R2，R3的尺寸更小。因此，使用一個聚合距離dagg（p，Q）來代替興趣點與查詢點之間的多個路網(wǎng)距離，減少由查詢點數(shù)量增加帶來的影響。

3 基于路網(wǎng)的多源聚合距離Skyline查詢算法

為了有效地處理道路網(wǎng)環(huán)境下多源Skyline查詢問題，本文提出了基于最小聚合距離的倒排索引Skyline查詢算法。首先對興趣點集建立倒排索引，結合剪枝策略對興趣點進行剪枝處理，快速地完成對興趣點的檢索；同時，對道路網(wǎng)進行遞歸地劃分，建立QG-tree索引。在預處理的距離矩陣和查詢距離矩陣的基礎上，通過基于裝配的方法可以容易地計算出道路網(wǎng)中任意興趣點的聚合距離，并且采用最小聚合距離優(yōu)先策略迭代地遍歷G-tree，檢索具有最小聚合距離的興趣點。

3.1 倒排索引

針對路網(wǎng)中大量的興趣點，如果對每個興趣點都進行聚合距離計算和支配判定，那么需要巨大的開銷，極大地影響了查詢效率。因此，需要對興趣點進行管理和剪枝過濾，實現(xiàn)檢索部分興趣點得到查詢結果，減少聚合距離計算和支配判定的開銷。

對于興趣點集，采用倒排索引進行管理，興趣點自身屬性維度中的興趣點按屬性值由優(yōu)到劣排序。對于聚合距離維度，初始為空，只有當檢索到聚合距離維度時，計算出一個具有最小聚合距離的興趣點作為檢索的對象。根據(jù)支配的定義，興趣點按屬性值由優(yōu)到劣排序，保證不被其他點支配的興趣點優(yōu)先被檢索，加快完成興趣點的檢索，避免Skyline查詢檢索整個興趣點集。針對圖1（b）興趣點建立的倒排索引如圖2所示。

剪枝策略。針對不同維度上的檢索，使用Ni變量表示維度i上已檢索興趣點的數(shù)量，p.num變量表示興趣點p被檢索的次數(shù)，Ri變量表示維度i的查詢結果集。依次檢索Ni最小維度i上的興趣點得到候選點集C，計算C中興趣點的聚合距離（僅針對num=0且為興趣點自身屬性維度檢索到的興趣點），然后與C、Ri中的興趣點進行支配判定，將num=1且不被支配的興趣點插入Ri。重復以上操作，直到存在一個興趣點在所有屬性維度都被檢索過一次，檢索結束。

定理1 當一個興趣點pi在所有屬性維度中都被檢索過一次，則對于從未被檢索過的興趣點pj，pj一定被pi支配。

證明 由支配定義可知，若pj不被pi支配，則k∈［0，n+1］，使得pj［k］優(yōu)于pi［k］。然而對于由優(yōu)到劣排序的興趣點，pi被檢索的順序先于pj，則不存在pj［k］優(yōu)于pi［k］。得證。

定理2 對于維度m檢索到的興趣點pi，若pi不被查詢結果集Rm中的興趣點支配，則將pi插入維度m的查詢結果集Rm。

證明 若存在pj支配pi，根據(jù)支配的定義，存在k∈［0，n+1］，使得pj［k］不差于pi［k］。然而，給定條件中pi在維度m上先于pj被檢索，即存在pi［m］優(yōu)于pj［m］，與pj支配pi的定義矛盾。得證。

3.2 基于最小聚合距離的倒排索引Skyline查詢算法

圖3描述了基于最小聚合距離的倒排索引Skyline查詢算法的主要流程。首先對興趣點集建立倒排索引結構，對道路網(wǎng)建立QG-tree索引。根據(jù)剪枝策略檢索Ni最小維度中的興趣點，直到存在一個興趣點在所有屬性維度上都被檢索過一次，最終查詢結果集為各維度上的查詢結果集C的并集。

圖3重點描述了IMA算法的主要流程，省略了一些細節(jié)。以下將介紹該算法使用的主要函數(shù)，即最小聚合距離興趣點的計算和興趣點聚合距離的計算。

3.3 最小聚合距離興趣點的計算

本文采用QG-tree索引來加快道路網(wǎng)上興趣點的聚合距離計算，QG-tree索引是G-tree［22，23］與查詢距離矩陣的結合。G-tree是一種高效的路網(wǎng)索引，通過G-tree可以快速計算點對點的最短距離。對于查詢點集Q和興趣點集P，可以調(diào)用|Q|×|P|次G-tree查詢來計算每個興趣點到Q的聚合距離。但是當|P|很大時，|Q|×|P|次G-tree查詢的開銷不可忽略。本文采用最小聚合距離優(yōu)先的剪枝策略［25］進行剪枝。

G-tree的構造分為兩個階段：a）自頂向下階段，采用多級分區(qū)算法［26］將道路網(wǎng)G遞歸地劃分為子網(wǎng)絡Gi，建立G-tree，每個子網(wǎng)絡對應G-tree中的一個樹節(jié)點（Gi可以表示為子網(wǎng)絡或樹節(jié)點），針對圖1（a）道路網(wǎng)進行遞歸劃分處理后的道路網(wǎng)如圖4（a）所示，建立的G-tree如圖4（b）所示；b）自底向上階段，以自下而上的方式計算每個樹節(jié)點的邊界點和距離矩陣。

對于道路網(wǎng)上任意兩個頂點a、b之間的最短路徑距離dist（a，b），可以在預處理距離矩陣的基礎上使用基于裝配的方法計算。許多道路頂點間的最短路徑存在共同子路徑，例如圖4（a）中頂點v7到v3的最短路徑為v7v6v3，v9到v3的最短路徑為v9v6v3。這兩條路徑存在一個公共子路徑v6v3，是邊界點v6到邊界點v3的最短路徑。因此，可以通過距離矩陣存儲預處理的頂點對的最短路徑距離，然后進行動態(tài)裝配，實現(xiàn)最短路徑距離的計算，減少重復的路網(wǎng)距離計算。

例2采用基于裝配的方法計算圖4（a）中頂點v15與v13之間的最短路徑距離dist（v15，v13），基于裝配方法的計算過程示例如圖5所示。首先確定v15、v13所在的葉子節(jié)點分別為G3和G5，v15到v13經(jīng)過的樹節(jié)點路徑為G3—G1—G2—G5，根據(jù)樹節(jié)點對應的距離矩陣，依次計算v15與樹節(jié)點G3、G1、G2、G5中邊界點的最短路徑距離：由MG3計算v15與B（G3）的最短路徑距離dist（v15，v14），加入由MG1計算v14與B（G1）的最短路徑距離dist（v14，v14），再加入由MG0計算v14與B（G2）的最短路徑距離dist（v14，v12），然后加入由MG2計算v12與B（G5）的最短路徑距離dist（v12，v12），最后加入由MG5計算的dist（v12，v13），最終動態(tài)裝配得到dist（v15，v13）。

定義6 查詢路徑。給定一個查詢點集Q，對于每個查詢點q∈Q，定義查詢路徑QP（q）為查詢點q所在的葉子節(jié)點Gi到根節(jié)點G0所經(jīng)過的樹節(jié)點集合。例如，查詢點q1的查詢路徑QP（q）=G4—G1—G0。

定義7 查詢距離矩陣。對于每一個樹節(jié)點Gi，維護一個二維矩陣QMQGi，用于存儲每個查詢點與樹節(jié)點Gi內(nèi)邊界點間的最短路徑距離，對于每個查詢點q∈Q，有：

QMQGi（q，b）=dist（q，b） b∈B（Gi）（2）

查詢距離矩陣QMQGi的計算，給定一個查詢點q∈Q，最初只計算QP（q）中樹節(jié)點Gi的初始查詢距離矩陣，即只計算樹節(jié)點Gi內(nèi)查詢點與邊界點之間的最短路徑距離。對于樹節(jié)點Gi外部的查詢點，只有當查詢點訪問到樹節(jié)點Gi時再進行計算，避免重復地計算距離開銷。例如，圖4（a）中的查詢點q1，其查詢路徑為G4—G1—G0，對應的初始查詢距離矩陣如圖6所示。

定義8 樹節(jié)點的聚合距離。給定一個樹節(jié)點Gi和一個查詢點q∈Q，定義查詢點q與樹節(jié)點Gi間的最短路徑距離dist（Gi，q），則樹節(jié)點Gi的聚合距離定義為

對于最小聚合距離興趣點的計算，首先計算初始查詢距離矩陣，接著自頂向下地遍歷G-tree，迭代地訪問dA（Gi，Q）最小的樹節(jié)點，利用優(yōu)先隊列存儲樹節(jié)點的聚合距離信息（以“Gi，dA（Gi，Q）”的形式存儲）并以dA（Gi，Q）升序排列，保證聚合距離最小的樹節(jié)點先被訪問。直到找到最小聚合距離興趣點PA和最小聚合距離DA。算法1給出了最小聚合距離興趣點計算的詳細過程。

算法1 最小聚合距離興趣點的計算

輸入：道路網(wǎng)G=（V，E，W）；興趣點集P；查詢點集Q。

輸出：具有最小聚合距離的興趣點PA；最小聚合距離DA。

1 初始化PA←-1，DA←∞；

2 for each q∈Q

3 確定查詢點q所在的葉子節(jié)點Gi；

4 for each v∈B（Gi）

5 QMQGi（q，v）=dist（q，v）；

6 while Gi≠G0

7 Gt←Gi，Gi←QP（q）中Gi的后驅樹節(jié)點；

8 for each vi∈B（Gi）

9 min=∞；

10 for each vj∈B（Gt）

11 temp=QMQGt（q，vj）+dist（vj，vi）；

12 if templt;min then min=temp；

13 QMQGi（q，vi）=min；

14 初始化優(yōu)先隊列PQ←“G0，0”；

15 while PQ≠

16 取隊首元素“Gi，dA（Gi，Q）”并出隊；

17 if dA（Gi，Q）≥DA

18 break；

19 if Gi為非葉子節(jié)點

20 for each Gi的孩子樹節(jié)點Gc

21 計算dA（Gc，Q）；

22 if dA（Gc，Q）lt;DA

23 將“Gc，dA（Gc，Q）”插入PQ；

24 else

25 for each p∈Gi

26 for each q∈Q

27 min=∞；

28 for each v∈B（Gi）

29 temp=dist（p，v）+dist（v，q）；

30 if templt;min then min=temp；

31 dist（p，q）=min；

32 dagg（p，Q）=∑q∈Qdist（p，q）；

33 if dagg（p，Q）lt;DA

34 PA=p，DA=dagg（p，Q）；

35 return PA，DA；

第2～13行計算初始查詢距離矩陣QMQGi，用于加快聚合距離的計算；第2～5行首先確定查詢點所在的葉子節(jié)點Gi，并根據(jù)MGi計算查詢點與Gi內(nèi)邊界點間的最短距離；第6～13行依次計算查詢路徑Q中各樹節(jié)點Gi的初始查詢距離矩陣QMQGi，可結合距離矩陣MGi和查詢距離矩陣QMQGi使用基于裝配的方法計算；第14行初始化優(yōu)先隊列PQ，將根節(jié)點G0入隊；第15～18行依次檢索PQ隊首的樹節(jié)點Gi，如果Gi的聚合距離dA（Gi，Q）≥DA，算法結束，返回最小聚合距離DA和最小距離興趣點PA；第19～23行表示如果Gi為非葉子節(jié)點，則對Gi的孩子樹節(jié)點進行擴展，利用式（3）計算孩子樹節(jié)點的聚合距離dA（Gc，Q），將dA（Gc，Q）lt;DA的樹節(jié)點插入優(yōu)先隊列PQ；第24～31行表示如果Gi為葉子節(jié)點，檢索葉子節(jié)點內(nèi)的興趣點，利用距離矩陣MGi計算dist（v，p）和查詢距離矩陣QMQGi計算dist（q，v），最后得到dist（p，q）；第32～34行根據(jù)式（1）計算興趣點的聚合距離，更新最小聚合距離DA和最小聚合距離興趣點PA。

3.4 興趣點聚合距離的計算

為了解決道路網(wǎng)中興趣點聚合距離的計算問題，可以利用預處理的距離矩陣MGi和初始查詢距離矩陣QMQGi，并基于裝配的方法計算興趣點的聚合距離。給定一個興趣點p和一個查詢點集Q，算法2給出了興趣點p的聚合距離dagg（p，Q）計算的全過程。

算法2 興趣點的聚合距離計算

輸入：道路網(wǎng)G=（V，E，W）；查詢點集Q；興趣點p。

輸出：興趣點p的聚合距離dagg（p，Q）。

1 確定興趣點p所在的葉子節(jié)點Gp；

2 for each q∈Q

3 確定查詢點所在的葉子節(jié)點Gq；

4 if Gp==Gq

5 min=∞；

6 for each v∈B（Gp）

7 temp=dist（p，v）+dist（v，q）；

8 if templt;min then min=temp；

9 dist（p，q）=min；

10 else

11 確定Gp和Gq的公共樹節(jié)點Gt；

12 do

13 Gc=Gp ，Gp=Gf ； // Gf是Gp的父親節(jié)點

14 for each vi∈B（Gp）

15 min=∞；

16 for each vj∈B（Gc）

17 temp=dist（p，vj）+dist（vj，vi）；

18 if templt;min then min=temp；

19 dist（p，vi）=min；

20 while （Gp≠Gt）

21 min=∞；

22 for each v∈B（Gt）

23 temp=dist（p，v）+dist（v，q）；

24 if templt;min then min=temp；

25 dist（p，q）=min；

26 dagg（p，Q）=∑q∈Qdist（p，q）；

第1～3行確定興趣點p和查詢點q所在的葉子節(jié)點；第4～9行表示如果p、q位于同一葉子節(jié)點內(nèi)，可利用葉子節(jié)點的距離矩陣和查詢距離矩陣計算dist（p，q）；第10～20行表示如果p、q位于不同的葉子節(jié)點內(nèi)，找到p、q的公共樹節(jié)點Gt，先利用基于裝配的方法在距離矩陣的基礎上計算興趣點p到Gt內(nèi)邊界點的最短距離dist（p，v）；第21～26行表示根據(jù)初始查詢距離矩陣QMQGt計算查詢點q到Gt內(nèi)邊界點的最短路徑距離dist（v，q），結合dist（p，v）得到dist（p，q）。最后，根據(jù)式（1）計算興趣點p的聚合距離。

QG-tree索引的建立需要進行邊界點、距離矩陣和初始查詢距離矩陣的預處理，所需要的空間復雜度為

其中：f為樹節(jié)點的分支數(shù)量；τ為葉子樹節(jié)點內(nèi)頂點數(shù)量。

例3 對圖4（a）道路網(wǎng)進行多源Skyline查詢，圖7給出了查詢的詳細過程。首先將價格、評分和聚合距離維度Ni及每個興趣點的num初始化為0；第一次檢索聚合距離維度，計算得出最小聚合興趣點為p3，更新Ni、num，p3插入聚合距離維度結果集；第二次檢索價格維度，檢索到p3、p5，更新Ni、num，支配判定（p3支配p5），p3為聚合距離維度的Skyline點，不插入價格維度結果集；第三次檢索評分維度，檢索到p7、p9、p11，更新Ni、num，p7支配p9，p7和p11插入評分維度結果集；第四次檢索聚合距離維度，計算得出最小聚合興趣點為p12，更新Ni、num，p12插入聚合距離維度結果集；第五次檢索價格維度，檢索到p4、p6、p12，更新Ni、num，p12支配p4、p6，p12為聚合距離維度的Skyline點，不插入價格維度結果集；第六次檢索聚合距離維度，計算得出最小聚合興趣點為p2，更新Ni、num，p12支配p2，不插入聚合距離結果集；第七次檢索評分維度，檢索到p12，p12為聚合維度的Skyline點，不插入聚合距離維度結果集。此時p12，num=3，算法結束。最終得到查詢結果集為R={p3，p7，p11，p12}。

可以發(fā)現(xiàn)，查詢結果集R與例1中R2相比，R的尺寸更小。因此，使用一個聚合距離代替興趣點與查詢點間的多個路網(wǎng)距離的策略可以有效地減小查詢結果集的尺寸，為用戶提供更加精簡有效的查詢結果。同時，基于最小聚合距離的倒排索引Skyline查詢方法只需檢索部分的興趣點即可得到最終查詢結果，減少了聚合距離計算和支配判定的開銷，從而提高了查詢效率。

4 實驗結果與分析

為了驗證基于最小聚合距離的倒排索引Skyline查詢算法的有效性，實驗采用三個不同規(guī)模的真實道路網(wǎng)數(shù)據(jù)集進行驗證，表1列出了道路網(wǎng)數(shù)據(jù)集的詳細信息。興趣點集和查詢點集都是在道路網(wǎng)頂點中隨機選取，每個興趣點的自身屬性值在［0，1 000］隨機生成。對于QG-tree索引的建立，設定τ =32，f=4。

本文將基于最小聚合距離的倒排索引Skyline查詢算法（IMA）與N3S算法［9］、DSR算法［24］進行實驗對比。由于DSR算法是道路網(wǎng)環(huán)境下單源Skyline查詢，所以對DSR算法進行適當修改使其適用于多源Skyline查詢：分別計算興趣點到每個查詢點的路網(wǎng)距離，均作為支配判定需要考慮的一個屬性維度。為了評估不同參數(shù)下的算法性能，表2列出了影響算法性能的三個參數(shù)，即興趣點的密度、興趣點自身屬性維度、查詢點數(shù)量。每組實驗只改變一個參數(shù)，其他參數(shù)為默認值，分別在三種不同規(guī)模道路網(wǎng)中進行實驗。實驗采用查詢時間作為評價指標來反映算法的查詢性能。

所有的算法均采用C++語言編寫，實驗環(huán)境為3.60 GHz CPU，RAM 32.0 GB，在Windows 10操作系統(tǒng)上的Microsoft Visual Studio 2017實現(xiàn)。

4.1 興趣點密度對算法性能的影響

本實驗將興趣點密度從0.05%改變到5.5%，其他參數(shù)設為默認值，分別在三種不同規(guī)模道路網(wǎng)中研究興趣點密度對算法性能的影響。興趣點密度表示道路網(wǎng)中興趣點的數(shù)量。如圖8所示，當興趣點密度增大時，IMA和DSR算法的查詢時間不斷增加，同時三種算法的查詢時間都隨著道路網(wǎng)規(guī)模的擴大而增加。綜合算法在三種不同規(guī)模道路網(wǎng)中的表現(xiàn)，IMA算法的查詢時間都遠小于DSR和N3S算法。隨著興趣點密度的增加，三種算法都需要檢索更多的興趣點得到查詢結果，IMA算法得益于高效的QG-tree索引，提高了聚合距離的計算效率，使得查詢性能遠優(yōu)于DSR、N3S算法。

4.2 興趣點自身屬性維度對算法性能的影響

為了研究興趣點自身屬性維度對算法性能的影響，實驗將興趣點自身屬性維度從2變化到6，其他參數(shù)為默認值。由圖9所示，當興趣點自身屬性維度增加時，三種算法的查詢時間都相應增加，并且隨著道路網(wǎng)規(guī)模的擴大，算法的查詢時間也相應增加。由于興趣點自身屬性維度的增加，IMA、DSR算法要檢索更多的興趣點找到一個被所有維度檢索過的興趣點，增加了聚合距離計算和支配判定的開銷，但IMA算法得益于高效的QG-tree索引，提高了聚合距離的計算效率。綜合算法在三種不同規(guī)模道路網(wǎng)上的表現(xiàn)，IMA算法的查詢性能優(yōu)于DSR和N3S算法。

4.3 查詢點數(shù)量對算法性能的影響

本實驗研究查詢點數(shù)量對算法性能的影響，將查詢點數(shù)量從2變化到8，其他參數(shù)為默認值，在三種不同規(guī)模道路網(wǎng)上進行實驗。如圖10所示，N3S和DSR算法的查詢時間都隨著查詢點數(shù)量的增加而增加，這是因為查詢點的增加使得N3S算法需要計算更多的最近鄰點才能找到第一個共同最近鄰點，而DSR算法需要檢索更多的興趣點才能找到掃描結束點，大大增加了路網(wǎng)距離計算和支配判定的開銷。然而IMA 算法使用一個聚合距離代替興趣點與查詢點之間的多個路網(wǎng)距離，聚合距離維度不受查詢點數(shù)量變化的影響，查詢時間的變化幅度較小。結合算法在三種不同規(guī)模道路網(wǎng)上的表現(xiàn)，IMA算法的查詢性能明顯優(yōu)于DSR和N3S算法。

總體而言，IMA算法的查詢性能優(yōu)于DSR和N3S，主要由于IMA算法采用一個聚合距離代替興趣點與查詢點之間的多個路網(wǎng)距離，解決了由查詢點增加帶來的問題，降低查詢點數(shù)量的變化對IMA算法的影響。并且采用高效的QG-tree索引對道路網(wǎng)劃分建模，提高興趣點聚合距離的計算效率；采用倒排索引管理興趣點集，結合剪枝策略，實現(xiàn)了檢索部分興趣點即可得到查詢結果。而N3S和DSR算法需要大量的路網(wǎng)距離計算和支配判定。

5 結束語

本文針對道路網(wǎng)環(huán)境下多源Skyline查詢存在聚合距離計算效率較低、無法為查詢用戶提供精簡有效的查詢結果的問題進行了研究，提出一種道路網(wǎng)環(huán)境下基于最小聚合距離的倒排索引Skyline查詢算法（IMA）。采用高效的QG-tree索引對道路網(wǎng)進行劃分建模，通過預處理的查詢距離聚合和距離矩陣提高了聚合距離的計算效率，并且采用倒排索引對興趣點集進行管理，結合剪枝策略對興趣點進行檢索剪枝，實現(xiàn)檢索部分興趣點即得到查詢結果。實驗結果證明了IMA算法可以有效地處理道路網(wǎng)環(huán)境下多源Skyline查詢問題。

參考文獻：

［1］Borzsony S，Kossmann D，Stocker K.The Skyline operator［C］//Proc of the 17th International Conference on Data Engineering.Piscataway，NJ：IEEE Press，2001：421-430.

［2］Zhang Songnian，Ray S，Lu Rongxing，et al.Toward privacy-preserving aggregate reverse Skyline query with strong security［J］.IEEE Trans on Information Forensics and Security，2022，17（7）：2538-2552.

［3］Ding Linlin，Wang Shu，Song Baoyan.Efficient k-dominant Skyline query over incomplete data using MapReduce［J］.Frontiers of Computer Science，2021，15（4）：154611.

［4］He Jingxuan，Han Xixian.Efficient Skyline computation on massive incomplete data［J］.Data Science and Engineering，2022，7（2）：102-119.

［5］Sharifzadeh M，Shahabi C.The spatial Skyline queries［C］//Proc of the 32nd International Conference on Very Large Data Bases.New York：ACM Press，2006：751-762.

［6］Li Qiyan，Zhu Yuanyuan，Yu J X.Skyline cohesive group queries in large road-social networks［C］//Proc of the 36th International Confe-rence on Data Engineering.Piscataway，NJ：IEEE Press，2020：397-408.

［7］李松，李爽，張麗平，等.障礙空間中基于R+樹的空間Skyline查詢方法［J］.計算機科學與探索，2017，11（12）：1886-1896.（Li Song，Li Shuang，Zhang Liping，et al.Spatial Skyline query method based on R+-tree for obstructed spaces［J］.Frontiers of Computer Science and Technology，2017，11（12）：1886-1896.）

［8］Deng Ke，Zhou Xiaofang，Shen Hengtao.Multi-source Skyline query processing in road networks［C］//Proc of the 23rd International Conference on Data Engineering.Piscataway，NJ：IEEE Press，2007：796-805.

［9］Safar M，El-Amin D，Taniar D.Optimized Skyline queries on road networks using nearest neighbors［J］.Personal and Ubiquitous Computing，2011，15（8）：845-856.

［10］Cai Zhi，Cui Xuerui，Su Xing，et al.Continuous road network-based Skyline query for moving objects［J］.IEEE Trans on Intelligent Transportation Systems，2021，22（12）：7383-7394.

［11］Hidayat A，Cheema M A，Lin Xuemin，et al.Continuous monitoring of moving Skyline and top-k queries［J］.The VLDB Journal，2022，31（3）：459-482.

［12］Xu Bin，F(xiàn)eng Jun，Lu Jiamin.Continuous Skyline queries for moving objects in road network based on MSO［C］//Proc of the 12th International Conference on Ubiquitous Information Management and Communication.New York：ACM Press，2018：1-6.

［13］周劍剛，秦小麟，張珂珩，等.基于道路網(wǎng)多移動用戶動態(tài) Skyline 查詢［J］.計算機科學，2019，46（9）：73-78.（Zhou Jiangang，Qin Xiaolin，Zhang Keheng，et al.Dynamic Skyline query for multiple mobile users based on road network［J］.Computer Science，2019，46（9）：73-78.）

［14］Cai Zhi，Cui Xuerui，Su Xing，et al.Speed and direction aware Skyline query for moving objects［J］.IEEE Trans on Intelligent Transportation Systems，2022，23（4）：3000-3011.

［15］Li Ronghua，Qin Lu，Ye Fanghua，et al.Finding Skyline communities in multi-valued networks［J］.International Journal on Very Large Data Bases，2020，29（6）：1407-1432.

［16］Huang Y K.Within Skyline query processing in dynamic road networks［J］.ISPRS International Journal of Geo-Information，2017，6（5）：137.

［17］Attique M，Afzal M，Ali F，et al.Geo-social top-k and Skyline keyword queries on road network［J］.Sensors，2020，20（3）：798.

［18］李松，竇雅男，郝曉紅，等.道路網(wǎng)環(huán)境下K-支配空間Skyline查詢方法［J］.計算機研究與發(fā)展，2020，57（1）：227-239.（Li Song，Dou Yanan，Hao Xiaohong，et al.The method of the K-dominant space Skyline query in road network［J］.Journal of Computer Research and Development，2020，57（1）：227-239.）

［19］Shen Bilong，Zhao Ying，Li Guoliang，et al.V-Tree：efficient KNN search on moving objects with road-network constraints［C］//Proc of the 33rd IEEE International Conference on Data Engineering.Pisca-taway，NJ：IEEE Press，2017：609-620.

［20］Huang Y K，Lee C P，Tsai C Y.Evaluating KNN-Skyline queries in dynamic road networks［C］//Proc of the 27th Wireless and Optical Communication Conference.Piscataway，NJ：IEEE Press，2018：1-2.

［21］Shekhar S，Xiong Hui.Voronoi-based query processing in road network databases［M］//Shekhar S，Xiong Hui.

Encyclopedia of GIS.Boston，MA：Springer，2017：1241.

［22］Zhong Ruicheng，Li Guoliang，Tan K L，et al.G-Tree：an efficient index for KNN search on road networks［C］//Proc of the 22nd ACM International Conference on Information and Knowledge Management.New York：ACM Press，2013：39-48.

［23］Zhong Ruicheng，Li Guoliang，Tan K L，et al.G-tree：an efficient and scalable index for spatial search on road networks［J］.IEEE Trans on Knowledge and Data Engineering，2015，27（8）：2175-2189.

［24］白梅，萇仕涵，王習特.基于位置的路網(wǎng)Skyline查詢處理研究［J］.計算機工程，2022，48（1）：127-134.（Bai Mei，Chang Shihan，Wang Xite.Research on location-based Skyline queries proces-sing in road network［J］.Computer Engineering，2022，48（1）：127-134.）

［25］Zhang Pengfei，Lin Huaizhong，Gao Yunjun，et al.Aggregate keyword nearest neighbor queries on road networks［J］.GeoInformatica，2018，22（4）：237-268.

［26］Karypis G，Kumar V.Analysis of multilevel graph partitioning［C］//Proc of ACM/IEEE Conference on Supercomputing.New York：ACM Press，1995：29-es.

收稿日期：2022-06-30；修回日期：2022-08-31 基金項目：廣東省重點領域研發(fā)計劃資助項目（2021B0101200002）；深圳職業(yè)技術學院科研項目（6022312044K，6021271004K）

作者簡介：宋志遠（1997-），男，江西贛州人，碩士研究生，主要研究方向為大規(guī)模圖查詢；馬慧（1981-），女（通信作者），廣東中山人，副教授，博士，主要研究方向為大規(guī)模圖查詢（zsmahui@163.com）；柳毅（1976-），男，江蘇連云港人，教授，博士，主要研究方向為網(wǎng)絡與信息安全．