李 松 賓婷亮 郝曉紅 張麗平 郝忠孝

（哈爾濱理工大學計算機科學與技術(shù)學院 哈爾濱 150080）

天際線（Skyline）查詢[1]作為多目標決策、興趣點發(fā)現(xiàn)、推薦系統(tǒng)等領(lǐng)域關(guān)鍵問題的一種解決途徑，在2001 年被提出，自此受到研究學者的廣泛關(guān)注與研究.近些年，Skyline 查詢研究拓展到不確定數(shù)據(jù)Skyline 查詢[2]﹑數(shù)據(jù)流Skyline 查詢[3]﹑動態(tài)Skyline 查詢[4]﹑反Skyline 查詢[5]、偏好Skyline 查詢等方面，其中偏好Skyline 查詢可以返回滿足用戶偏好需求的結(jié)果集.針對因用戶偏好不同導(dǎo)致屬性的重要性不同問題，研究者們提出了新的支配關(guān)系與算法.但已有研究主要集中在非道路網(wǎng)的用戶偏好Skyline 查詢或者道路網(wǎng)單用戶偏好Skyline 查詢方面，沒有考慮道路網(wǎng)多用戶偏好和權(quán)重的Top-kSkyline 查詢.

傳統(tǒng)偏好Skyline 查詢算法主要存在3 點局限性：1）偏好Skyline 查詢需要確定屬性的重要程度，由于不同用戶權(quán)重與偏好不同，因此不同屬性的重要程度也不一致，而已有研究中較少有提出將用戶偏好和權(quán)重綜合考慮，得到對用戶群統(tǒng)一的屬性重要程度次序處理方法；2）傳統(tǒng)偏好Skyline 查詢算法大多未考慮道路網(wǎng)環(huán)境下的距離維度，只考慮靜態(tài)維度；3）傳統(tǒng)偏好Skyline 查詢算法返回的結(jié)果集過大、無序，不能給用戶提供有效的決策支持.

因此，針對道路網(wǎng)多用戶偏好Top-kSkyline 查詢問題，本文提出滿足多用戶不同權(quán)重和偏好需求的查詢方法.

本文的主要貢獻有3 點：

1）針對道路網(wǎng)存在大量數(shù)據(jù)點以及多查詢用戶場景，需要計算數(shù)據(jù)點到各個查詢用戶的道路網(wǎng)距離，從而產(chǎn)生的很大距離計算開銷，為了提升距離計算效率，本文根據(jù)所提的Vor-R*-DHash 索引結(jié)構(gòu)以及數(shù)據(jù)點與查詢用戶群的空間位置關(guān)系，提前剪枝在距離維度被支配的大量數(shù)據(jù)點.

2）針對在道路網(wǎng)Top-kSkyline 查詢處理時未綜合考慮多用戶不同權(quán)重和偏好以及返回的結(jié)果集數(shù)量不可控的問題，本文首先提出整體屬性權(quán)重值的概念，綜合考慮用戶權(quán)重和偏好；并進一步提出用戶群權(quán)重偏好次序，并基于此次序提出一種新的支配，即K-準放松支配；接著根據(jù)偏好次序進行逐次放松支配，使返回結(jié)果集大小可控；同時當k值改變時，動態(tài)調(diào)整放松輪次即可獲取候選結(jié)果集CS，而無需重新計算距離、偏好次序等，減少了查詢計算開銷.

3）針對Skyline 查詢返回結(jié)果集無序的問題，本文基于z-整體屬性權(quán)重值，提出了選取Top-k個結(jié)果集的打分函數(shù)，對候選結(jié)果集CS打分排序，返回有序結(jié)果集.

1 相關(guān)工作

Skyline 查詢主要分為集中式查詢和分布式查詢.其中集中式查詢主要分為使用索引結(jié)構(gòu)和不使用索引結(jié)構(gòu).使用索引結(jié)構(gòu)的算法常用R-tree 等索引結(jié)構(gòu)，例如文獻[6]利用最近鄰（nearest neighbor，NN）算法和R-tree 索引查找Skyline 點，基于R-tree 可以快速判斷數(shù)據(jù)點是否為Skyline 點，接著利用數(shù)據(jù)點進行子集合的劃分，遞歸查找Skyline 點.不使用索引結(jié)構(gòu)的Skyline 查詢算法主要有基于排序的SFS（sort-filter Skyline）算法[7].而Skyline 查詢在不斷發(fā)展過程中又產(chǎn)生了許多變種問題，例如K-支配空間Skyline 查詢[8]﹑連續(xù)Skyline 查詢[9]﹑針對推薦系統(tǒng)的范圍障礙空間連續(xù)Skyline 查詢[10]﹑概率Skyline 查詢[11]以及Top-kSkyline 查詢等[12-13].

在集中式計算環(huán)境下，文獻[14]根據(jù)用戶不同偏好提出了維度不確定的定義，根據(jù)維度特征劃分數(shù)據(jù)，進行Skyline 概率支配測試，同時利用閾值處理大規(guī)模數(shù)據(jù)集Skyline 查詢問題.文獻[15]提出一種高效偏序域Skyline 查詢處理方法，利用倒排索引進行Skyline 查詢.在并行計算環(huán)境下，文獻[16]提出了不完全數(shù)據(jù)集的偏好Skyline 查詢算法SPQ（Skyline preference query）.文獻[17]根據(jù)用戶的偏好，基于Voronoi 圖將數(shù)據(jù)對象劃分到不同網(wǎng)格中，并行計算所有對象組合，獲取動態(tài)Skyline 結(jié)果.文獻[18]提出了MapReduce 下Top-kSkyline 偏好查詢.

道路網(wǎng)Skyline 查詢近些年來也受到越來越多的關(guān)注.道路網(wǎng)Skyline 查詢既考慮數(shù)據(jù)點的路網(wǎng)空間屬性，又考慮非空間屬性.文獻[19]提出了基于范圍的移動對象連續(xù)Skyline 查詢處理方法，利用Voronoi圖組織道路網(wǎng)中的數(shù)據(jù)點，通過所提的3 種算法減少道路網(wǎng)產(chǎn)生的相交節(jié)點數(shù)和距離計算開銷.文獻[20]提出了道路網(wǎng)環(huán)境下綜合考慮空間距離和社交距離的Skyline 組用戶查詢方法.

Top-kSkyline 查詢在多目標決策中往往更具優(yōu)勢，因為它可以控制返回的結(jié)果集數(shù)量.文獻[21]提出基于安全區(qū)域技術(shù)解決連續(xù)Top-kSkyline 查詢結(jié)果更新問題，提出了結(jié)合Top-k查詢和Skyline 查詢的安全區(qū)域構(gòu)建算法.文獻[22]提出了MapReduce環(huán)境下Top-kSkyline 處理方法.文獻[23]將K-Skyband查詢與Top-kSkyline 查詢結(jié)合處理大數(shù)據(jù)集的Top-kSkyline 查詢.

目前道路網(wǎng)環(huán)境下Top-kSkyline 查詢研究大多集中在單用戶場景，較少考慮多用戶偏好和權(quán)重不同的場景.針對已有方法的不足，本文利用查詢點與數(shù)據(jù)點的位置關(guān)系剪枝數(shù)據(jù)集，利用所提的K-準放松支配控制結(jié)果集數(shù)量；利用所提的打分函數(shù)返回有序結(jié)果集，在理論論證和分析基礎(chǔ)上提出了道路網(wǎng)多用戶偏好Top-kSkyline 查詢方法.

2 主要定義

設(shè)道路網(wǎng)環(huán)境下數(shù)據(jù)集P={p1,p2,…,pn}，查詢用戶群G={q1,q2,…,qm}.

定義1.道路網(wǎng)距離支配.給定查詢用戶群G、數(shù)據(jù)點p1、數(shù)據(jù)點p2，數(shù)據(jù)點之間的距離為Dist，當且僅當Dist（p1,qi）≤Dist（p2,qi），1≤i≤m；且存在Dist（p1,qi）＜Dist（p2,qi），1≤i≤m，稱p1道路網(wǎng)距離支配p2，記作p1?p2.本文距離如不特殊說明，則為道路網(wǎng)距離.

定義2.整體屬性權(quán)重.給定查詢用戶群G，用戶權(quán)重w={w1,w2,…,wm}，用戶qi的查詢關(guān)鍵字keys={C1，C2}，C1為優(yōu)先考慮的屬性集合，C2為一般偏好的屬性集合，任意維度dj的整體屬性權(quán)重Wj如式（1）：

其中si代表屬性dj對于用戶qi的重要性得分.

在屬性的重要性程度計分時，將屬性偏好分為3 類：優(yōu)先考慮﹑一般偏好和未考慮.不同類別分數(shù)不同，例如C1中的屬性被賦予2 分，C2中的屬性被賦予1 分，未考慮的屬性被賦予0 分.

定義3.用戶群權(quán)重偏好次序.指針對查詢用戶群屬性的有序集合GP={d1,d2,…,di},其中di代表任意屬性，GP中屬性對用戶群的重要性程度呈非遞增排列.用戶群權(quán)重偏好次序綜合考慮用戶的偏好和權(quán)重.

定義4.K-準放松支配（KPRD）.設(shè)P為數(shù)據(jù)集，數(shù)據(jù)維度空間為D，dj為任意維度，總維度數(shù)為r，θ=（θ1,θ2,…,θK）是D上K個維度的無差異閾值.數(shù)據(jù)點pi，pt∈P，piK-準放松支配pt，記作pi?pt，當且僅當：其中1≤j≤K.

定義5.道路網(wǎng)多用戶偏好Top-kSkyline 查詢.給定道路網(wǎng)路段集R、查詢用戶群G、數(shù)據(jù)集P、用戶的查詢關(guān)鍵字集合keys和用戶權(quán)重集合w，道路網(wǎng)多用戶偏好Top-kSkyline 查詢返回P的一個子集.該子集中數(shù)據(jù)點在道路網(wǎng)的距離維度和靜態(tài)維度都不能被P中任意其他數(shù)據(jù)點支配，并且是根據(jù)用戶群偏好和權(quán)重排序的Top-k個數(shù)據(jù)點.本文將道路網(wǎng)多用戶偏好Top-kSkyline 查詢方法記作MUP-TKS.

3 道路網(wǎng)多用戶偏好Top-k Skyline 查詢

本文提出的道路網(wǎng)多用戶偏好Top-kSkyline 查詢方法主要分為3 個部分：距離較優(yōu)集選取﹑K-準放松支配和Top-k個數(shù)據(jù)點選取.

3.1 道路網(wǎng)距離較優(yōu)集選取方法

定義6.Mindist 距離[24].r維歐氏空間中，點p到同一空間內(nèi)某矩形N的最小距離為Mindist（N,p）.

定義7.Edist 距離.設(shè)查詢用戶群的最小外接矩形（minimum bounding rectangle，MBR）為Q，數(shù)據(jù)點p的MBR 為N，則min{Mindist（p,Q）}為（Q,N）最小歐氏距離，記作Edistmin；max{Mindist（p,Q）}為（Q,N）最大歐氏距離，記作Edistmax.

定義8.Ndist 距離.設(shè)查詢用戶群的MBR 為Q，數(shù)據(jù)點p的MBR 為N，有min{Ndist（p,Q）}為（Q,N）最小網(wǎng)絡(luò)距離，記作Ndistmin；max{Ndist（p,Q）}為（Q,N）最大網(wǎng)絡(luò)距離，記作Ndistmax，其中p為N中的任意數(shù)據(jù)點，Ndist（p,Q）為p到Q的網(wǎng)絡(luò)距離.

定理1.設(shè)查詢用戶群的MBR 為Q，道路網(wǎng)中數(shù)據(jù)點構(gòu)成的2 個中間節(jié)點分別為N1，N2，若DE1=Edistmin（Q,N2），DE2=Edistmax（Q,N1），DN1=Ndistmax（Q,N1），并且DE1＞DE2，DE1＞DN1，則N1?N2，且N2中任意數(shù)據(jù)點都被N1中數(shù)據(jù)點距離支配.

證明.假設(shè)DN2=Ndistmin（Q,N2），因為歐氏距離值一定小于等于道路網(wǎng)距離值，所以當DE1＞DE2且DE1＞DN1時一定有DN2≥DE1，可得DN2＞DN1，即N2中數(shù)據(jù)點到Q的最小網(wǎng)絡(luò)距離大于N1中數(shù)據(jù)點到Q的最大網(wǎng)絡(luò)距離，進而可得N2中任意數(shù)據(jù)點到Q的網(wǎng)絡(luò)距離都大于N1中任意數(shù)據(jù)點到Q的網(wǎng)絡(luò)距離.因此N1?N2，且N2中任意數(shù)據(jù)點被N1中任意數(shù)據(jù)點道路網(wǎng)距離支配.證畢.

剪枝規(guī)則1.設(shè)數(shù)據(jù)點構(gòu)成的MBR 分別為N1，N2，查詢用戶群的MBR 為Q，如果滿足：Edistmax（Q,N1）≤Edistmin（Q,N2），并且Ndistmax（Q,N1）＜Edistmin（Q,N2），則節(jié)點N2可被剪枝.

定義9.道路網(wǎng)最大距離的最小值.給定數(shù)據(jù)點p1，p2，查詢用戶群G，數(shù)據(jù)點p到查詢點q的道路網(wǎng)距離為Ndist（p,q）.若有DN1=max{Ndist（p1,qi）}，DN2=max{Ndist（p2,qi）}（1≤i≤m），并且DN1＜DN2，則當前道路網(wǎng)最大距離的最小值為DN1，記作DN_MaxMin.對應(yīng)的數(shù)據(jù)點為p1.

定理2.若節(jié)點N的Edistmin（Q,N）＞DN_MaxMin，則節(jié)點N可被剪枝.

證明.因為Edistmin（Q,N）＞max{Ndist（p,qi）}（1≤i≤m），所以Ndistmin（Q,N）＞max{Ndist（p,qi）}，即p?N，且N中數(shù)據(jù)點也被p距離支配.證畢.

剪枝規(guī)則2.若Edistmin（Q,N）≥DN_MaxMin，則節(jié)點N被支配，即N和N中數(shù)據(jù)點{p1,p2,···,pi}被剪枝.

如圖1 所示，數(shù)據(jù)點p1，p2到查詢用戶群{q1,q2,q3}的最大網(wǎng)絡(luò)距離分別為DN1，DN2，有DN1＞DN2，則DN_MaxMin=DN2.數(shù)據(jù)點{p3,p4,p5,p6,p7,p8}構(gòu)成的MBR為N1；若Edistmin（Q,N1）＞DN_MaxMin，可得N1中數(shù)據(jù)點到各查詢用戶的網(wǎng)絡(luò)距離大于DN_MaxMin，因為Edistmin（Q,N1）＞DN_MaxMin，且有min{Ndist（p2,qi）}≥Edistmin（Q,N1）（1≤i≤3），所以p2?N1，N1可被剪枝.

Fig.1 Example of pruning rule 2圖1 剪枝規(guī)則2 示例

定理3.設(shè)DE為數(shù)據(jù)點pi到查詢用戶qj的歐氏距離，若min{DE（pi,qj）}＞DN_MaxMin（1≤j≤m），則pi被剪枝.

證明.假設(shè)p1為DN_MaxMin對應(yīng)的數(shù)據(jù)點，若min{DE（pi,qj）}＞DN_MaxMin，則有Ndist（p,qj）＞DN_MaxMin（1≤j≤m），即數(shù)據(jù)點p1?p，p可被剪枝.證畢.

剪枝規(guī)則3.假設(shè)數(shù)據(jù)點p1為DN_MaxMin對應(yīng)的數(shù)據(jù)點，若存在DN_MaxMin＜min{DE（pi,qj）}（1≤j≤m），則p1?pi，可將pi從候選集中刪除，其中pi為任意不為p1的數(shù)據(jù)點.

為了減少計算，在剪枝前基于路網(wǎng)數(shù)據(jù)點的網(wǎng)絡(luò)Voronoi 圖構(gòu)建Vor-R*-DHash 索引結(jié)構(gòu)，如圖2 所示.

Fig.2 Index structure of Vor-R*-DHash圖2 Vor-R*-DHash 索引結(jié)構(gòu)

Vor-R*-DHash 索引結(jié)構(gòu)構(gòu)造過程有3 步：

1）構(gòu)建路網(wǎng)所有數(shù)據(jù)點的網(wǎng)絡(luò)Voronoi 圖.

2）創(chuàng)建R*-tree.從R*-tree 的根部開始，從上至下、從左至右給每個節(jié)點編號，從0 開始編號.

3）構(gòu)建2 級HashMap 結(jié)構(gòu)，第1 級HashMap 為first_hash、key為R*-tree 中每個節(jié)點編號；第2 級HashMap為sec_hash、key為后續(xù)剪枝處理需要的值，包括isNode（非數(shù)據(jù)點的節(jié)點）、MinE（節(jié)點到Q的最小歐氏距離值）、MaxE（節(jié)點到Q的最大歐氏距離值 ）、MinN（節(jié)點到Q的最小網(wǎng)絡(luò)距離值）、MaxN（節(jié)點到Q的最大網(wǎng)絡(luò)距離值）、{DN1,DN2,…,DNi}（數(shù)據(jù)點到各查詢用戶的網(wǎng)絡(luò)距離）、{DE1,DE2,…,DEi}（數(shù)據(jù)點到各查詢用戶的歐氏距離）.

2 級key對應(yīng)的value值初始都為空，若數(shù)據(jù)點根據(jù)剪枝規(guī)則提前被剪枝，則這些值無需計算.DEi，DNi的值也是后續(xù)需要使用才被計算，并存入sec_hash.

基于剪枝規(guī)則1～3 和Vor-R*-DHash 索引結(jié)構(gòu)，進一步給出距離較優(yōu)集選取方法，如算法1 所示.

算法1.距離較優(yōu)集選取方法 G_DBC.

輸入：查詢用戶群G，道路網(wǎng)路段集R，數(shù)據(jù)集P；

輸出：距離維度不被支配的距離較優(yōu)集DBC.

算法1 首先構(gòu)建Vor-R*-DHash 索引和查詢用戶群最小外接矩形Q，可快速得到距離查詢點最近的數(shù)據(jù)點point，計算并保存sec_hash所需數(shù)據(jù).將point加入距離較優(yōu)集DBC，并初始化DN_MaxMin.接著將point父節(jié)點加入隊列queue中，計算并保存sec_hash所需數(shù)據(jù)，并初始化N1.每次取出隊頭節(jié)點處理，依據(jù)剪枝規(guī)則1～3 進行節(jié)點的剪枝或者將節(jié)點加入DBC，并判斷是否需要更新N1，DN_MaxMin等值，直至隊列為空，循環(huán)結(jié)束.最后返回距離較優(yōu)集DBC.

3.2 數(shù)據(jù)集的放松支配過程

3.2.1 獲取用戶群權(quán)重偏好次序

首先初始化整體屬性權(quán)重集合.W={W1,W2,…,Wi}={0,0,…,0}；接著計算每個屬性的整體屬性權(quán)重值得到W；最后對整體屬性權(quán)重值不為0 的屬性降序排列，得到屬性的重要性次序，即用戶群權(quán)重偏好次序.

在獲取用戶群權(quán)重偏好次序時，為了減小計算開銷，利用HMap1，HMap2分別保存優(yōu)先考慮的屬性和一般偏好的屬性.當用戶發(fā)起查詢時，將C1中屬性作為鍵，對應(yīng)的用戶權(quán)重作為值保存到HMap1；將C2中屬性作為鍵，對應(yīng)的用戶權(quán)重作為值保存到HMap2.

進一步給出獲取用戶群權(quán)重偏好次序算法CDW，如算法2 所示.

算法2.獲取用戶群權(quán)重偏好次序算法 CDW.

輸入：用戶群G，用戶查詢關(guān)鍵字keys，用戶權(quán)重w，維度空間D；

輸出：用戶群權(quán)重偏好次序GP.

① 初始化W為0；/*大小為數(shù)據(jù)集維度數(shù)*/

② 根據(jù)keys，w創(chuàng)建HMap1，HMap2；

③ fordj∈Ddo

④ 基于HMap1、HMap2和式（1）得到Wj；

⑤ end for

⑥ 根據(jù)W降序得到用戶群權(quán)重偏好次序GP；

⑦ returnGP./*返回用戶群權(quán)重偏好次序*/

3.2.2 基于用戶群權(quán)重偏好次序的K-準放松支配

獲取用戶群偏好次序后，基于該次序進行放松支配處理.本文中K為整體屬性權(quán)重值不為0 的維度數(shù).放松支配過程的處理對象為DBC與靜態(tài)Skyline集取并集后的集合S.經(jīng)K-準放松支配后得到數(shù)量可控的候選結(jié)果集CS.

定理4.任意2 個數(shù)據(jù)點pi，pj∈P，若第i（i＞0）輪在K個維度上pi?pj，則數(shù)據(jù)點pi必定在前K-i維支配數(shù)據(jù)點pj.

證明.若在第i輪pi?pj，可知該輪的無差異閾值為（0,0,…,0,θK-i+1,…,θK），進而可得前K-i維使用的無差異閾值為（0,0,…,0），所以前K-i維為嚴格支配比較，即數(shù)據(jù)點pi必定在前K-i維支配數(shù)據(jù)點pj.證畢.

定理5.數(shù)據(jù)集P經(jīng)過第i（i＞1）輪放松支配后所得結(jié)果集Si一定是第i-1 輪放松支配后所得結(jié)果集Si-1的子集.

證明.設(shè)第i輪放松的維度為第（K-i+1）～K維，第i-1 輪放松的維度為第（K-i+2）～K維，其余維度使用嚴格支配.可知第i輪的無差異閾值為（0,0,…,0,θK-i+1,θK-i+2,…,θK），第i-1 輪的無差異閾值為（0,0,…,0,θK-i+2,…,θK），進而可知第i-1 輪在前K-i+1 個維度為嚴格支配比較，即在前K-i+1 個維度的無差異閾值為（0,0,…,0）.第i輪不同于第i-1 輪之處在于對第K-i+1 維進行了放松支配，即在前K-i+1 個維度無差異閾值為（0,0,…,0,θK-i+1），所以有Si?Si-1.證畢.由定理4、定理5 可直接得出定理6.

定理6.給定數(shù)據(jù)集S，結(jié)果集數(shù)量隨著每一輪放松而呈單調(diào)非遞增趨勢，即

為使返回的結(jié)果集更符合用戶群偏好，并保證數(shù)量可控，基于定理4～6 進行逐次放松支配.逐次放松支配過程中，θ是D上K個維度的無差異閾值，θ=（θ1,θ2,…,θK）.假定當前放松輪次為第i輪（1≤i≤K），無差異閾值θ=（0,0,…,0,θK-i+1,…,θK）.位于di前面的維度重要性都要高于di，因此該輪放松支配維度d1～di-1都使用嚴格支配比較.放松支配從對用戶群而言最不重要的屬性開始，并預(yù)先將數(shù)據(jù)點按照用戶群權(quán)重偏好次序非遞增排序，距離維度值用數(shù)據(jù)點到查詢用戶群網(wǎng)絡(luò)距離的最大值表示.

基于以上討論，進一步給出基于用戶群權(quán)重偏好次序的K-準放松支配算法KPRD，如算法3 所示.

算法3.基于用戶群權(quán)重偏好次序的K-準放松支配算法KPRD.

輸入：用戶群G，無差異閾值θ，并集S，數(shù)據(jù)維度空間D，k值，用戶查詢關(guān)鍵字keys，用戶權(quán)重w；

輸出：候選結(jié)果集CS.

3.3 Top-k 個數(shù)據(jù)點選取方法

通過放松支配處理后可有效控制返回用戶群的結(jié)果集大小，本節(jié)進一步給出Top-k個數(shù)據(jù)點選取策略，使返回結(jié)果集有序.利用z-整體屬性權(quán)重值的打分函數(shù)選取Top-k個數(shù)據(jù)點，處理對象為候選結(jié)果集CS.

定義10.單調(diào)打分函數(shù)F[25].數(shù)據(jù)集中數(shù)據(jù)點作為輸入域?qū)?shù)據(jù)點映射到實數(shù)范圍.F由r個單調(diào)函數(shù)構(gòu)成，F(xiàn)={f1,f2,…,fr}.對于數(shù)據(jù)集中任意數(shù)據(jù)點，有，其中fj（p[dj]）為數(shù)據(jù)點在dj維度的單調(diào)函數(shù).

定理7.假設(shè)數(shù)據(jù)集P的單調(diào)打分函數(shù)為F，若數(shù)據(jù)集中任意一個元組有最高的分數(shù)，那么它一定是Skyline 點.

證明.以反證法進行證明.假設(shè)有p1，p2∈P，p1的得分F（p1）為數(shù)據(jù)集的最高得分，F(xiàn)（p1）＞F（p2），p1不是Skyline 點，p2支配p1，p1[dj]≤p2[dj]（1≤j≤r），則可得，即F（p1）≤F（p2），與假設(shè)矛盾.證畢.

定理8.數(shù)據(jù)集P根據(jù)任意單調(diào)打分函數(shù)所得數(shù)據(jù)點順序是Skyline 支配的拓撲順序.

證明.以反證法進行證明.假設(shè)存在2 個數(shù)據(jù)點p1，p2∈P，單調(diào)打分函數(shù)為F，p1支配p2，F(xiàn)（p1）＜F（p2），根據(jù)定理7 可知，p1支配p2，則有F（p1）≥F（p2）,與假設(shè)矛盾.所以如果F（p2）＞F（p1），可能有p2支配p1，但可以確定p1不可能支配p2.如果F（p1）=F（p2），則p1支配p2或p2支配p1（這兩者是等價的，會根據(jù)屬性的映射關(guān)系排序），或者p1和p2之間不具備支配關(guān)系.因此依據(jù)打分函數(shù)F所得數(shù)據(jù)點順序是按照Skyline支配關(guān)系的一個拓撲順序.證畢.

定義11.線性打分函數(shù)[25].給定線性打分函數(shù)L，一般化形式為，其中ωj為實常數(shù)，p[dj]為數(shù)據(jù)點在dj維度的取值.

定義12.z-整體屬性權(quán)重值.給定數(shù)據(jù)集P，數(shù)據(jù)點pi∈P，pi在dj維度的z-整體屬性權(quán)重值為

定理9.數(shù)據(jù)點任意維度的fj（p[dj]）是單調(diào)的.

證明.因為ωj=Wjζj，在打分階段Wj為實常數(shù)，所以可得ωj為實常數(shù)，且隨著數(shù)據(jù)點維度值變大，它的z值也變大，因此數(shù)據(jù)點的任意維度fj（p[dj]）是單調(diào)的.證畢.

定義13.基于z-整體屬性權(quán)重值的打分函數(shù).數(shù)據(jù)點pi各維度z-整體屬性值之和為它的得分，記作F（pi）:

定理10.F（pi）是單調(diào)打分函數(shù).

證明.因為有F(pi)=fj(p[dj])，根據(jù)定理9 可知數(shù)據(jù)點的任意維度fj（p[dj]）隨著維度值變大單調(diào)遞增，它們具備相同的單調(diào)性，因此F（pi）也是單調(diào)的.證畢.

進一步給出Top-k個數(shù)據(jù)點選取方法，如算法4所示.

算法4.Top-k個數(shù)據(jù)點選取方法TK_DC.

輸入：候選結(jié)果集CS，整體屬性權(quán)重集合W，維度優(yōu)劣集合ζ；

輸出：Top-kSkyline 結(jié)果集.

① forpi∈CSdo

② 計算數(shù)據(jù)點的z-整體屬性權(quán)重值；/*根據(jù)式（4）*/

③ 計算數(shù)據(jù)點得分；/*根據(jù)式（5）*/

④ end for

⑤ 根據(jù)F（pi）降序排序；

⑥ return Top-k個數(shù)據(jù)點.

算法4 主要對經(jīng)過算法3 處理后的候選結(jié)果集CS打分，并對行②③計算CS中各個數(shù)據(jù)點的得分，基于行⑤⑥數(shù)據(jù)點的得分排序，輸出Top-kSkyline 結(jié)果集給用戶群.

綜合距離較優(yōu)集選取﹑K-準放松支配和Top-k個數(shù)據(jù)點選取的處理過程，進一步給出算法5 MUPTKS 的算法.

算法5.道路網(wǎng)多用戶偏好Top-kSkyline 查詢算法MUP-TKS.

輸入：數(shù)據(jù)集P，道路網(wǎng)路段集R，用戶群G，用戶查詢關(guān)鍵字keys，用戶權(quán)重w，無差異閾值θ，k，維度優(yōu)劣集合ζ；

輸出：Top-kSkyline 結(jié)果集.

① 預(yù)先計算保存數(shù)據(jù)集的靜態(tài)Skyline 集；

② 距離較優(yōu)集選取方法G_DBC；/*調(diào)用算法1*/

③ 對距離較優(yōu)集與靜態(tài)Skyline 集求并集S；

④K-準放松支配算法KPRD；/*調(diào)用算法 3*/

⑤ Top-k個數(shù)據(jù)點選取方法TK_DC./*調(diào)用算法4*/

4 實驗比較與分析

本節(jié)主要對MUP-TKS 進行實驗以及性能評估.實驗對比算法為道路網(wǎng)單用戶偏好Skyline 算法UPBPA[26]、K支配空間偏好Skyline 算法KSJQ[23]以及基于時間道路網(wǎng)多用戶偏好Skyline 算法DSAS[27].UPBPA 算法適用于道路網(wǎng)單用戶，為了更好地與本文所提MUP-TKS 進行對比，將其擴展，對查詢用戶群的每個用戶分別運行該算法；再對子結(jié)果集取并集，得到候選結(jié)果集CS；最后對候選結(jié)果集基于z-值的打分函數(shù)打分，得到Top-k個數(shù)據(jù)點，擴展后的算法稱為EUP-BPA.將KSJQ 算法擴展，對每個用戶單獨執(zhí)行該算法，用戶偏好對應(yīng)它的K個子空間；對每個用戶的結(jié)果集取并集后得到候選結(jié)果集；對候選結(jié)果集CS基于z-值的打分函數(shù)打分，得到Top-k個Skyline結(jié)果集，擴展后的算法稱為EKSJQ.將DSAS 算法擴展，對滿足不同用戶需求的數(shù)據(jù)點基于z-值打分函數(shù)打分，按照數(shù)據(jù)點得分從高至低返回Top-k個Skyline結(jié)果集，擴展后的算法稱為EDSAS.

4.1 數(shù)據(jù)集及實驗環(huán)境設(shè)置

實驗使用真實道路網(wǎng)數(shù)據(jù)集.道路網(wǎng)數(shù)據(jù)集①http://www.cs.utah.edu/～lifeifei/SpatialDataset.htm是北美2.5×107km2范圍內(nèi)的路段信息，它包含175 813個節(jié)點和179 179 條邊.興趣點數(shù)據(jù)集②https://www.ahla.com/來自北美酒店及登記信息.查詢用戶采用隨機生成的方式.本文使用Vor-R*-DHash 索引結(jié)構(gòu)組織數(shù)據(jù)集.實驗參數(shù)取值范圍如表1 所示，每個用戶最大關(guān)注維度為4.每個實驗采取單一變量原則，其余變量為默認值，實驗結(jié)果取30 次實驗運行的平均值.

Table 1 Experimental Parameter Setting表1 實驗參數(shù)設(shè)置

實驗環(huán)境為：Windows 10（64b），CoreTMi6-5200U CPU @2.20 GHz 2.19 GHz 處理器，12 GB 運行內(nèi)存.在IntelliJ IDEA 開發(fā)平臺上使用Java 實現(xiàn)本文所提的算法MUP-TKS 和對比算法EUP-BPA，EKSJQ，EDSAS.

4.2 算法對比實驗

1）用戶數(shù)量對算法性能的影響

為了分析用戶數(shù)量對算法性能的影響，本實驗對不同用戶數(shù)量下的MUP-TKS，EKSJQ，EDSAS，EUPBPA 算法進行測試，觀察算法在不同用戶數(shù)量下的CPU 運行時間、候選結(jié)果集CS數(shù)量的變化情況.

圖3 展示了4 種算法在不同用戶數(shù)量下CPU 運行時間變化情況.由圖3 可知，隨著用戶數(shù)量的增加，4 種算法的CPU運行時間都在增加.因為用戶數(shù)量增加導(dǎo)致不同用戶的偏好情況增加，從而需要更多時間處理用戶偏好.MUP-TKS 的CPU 運行時間增長趨勢沒有其他3 種算法的增長趨勢大，主要原因是MUP-TKS 將多用戶的偏好轉(zhuǎn)換成用戶群權(quán)重偏好次序，對數(shù)據(jù)集按照該次序預(yù)排序，再進行K-準放松支配，使用戶數(shù)量增加對CPU 運行時間的影響減小.

Fig.3 Effect of user number on CPU execution time圖3 用戶數(shù)量對CPU 運行時間的影響

圖4 展示了4 種算法隨著用戶數(shù)量的變化，候選結(jié)果集CS數(shù)量的變化情況.由圖4 可知隨著用戶數(shù)量的增加，CS的數(shù)量變大.但MUP-TKS，EKSJQ，EDSAS 算法的變化趨勢遠沒有EUP-BPA 算法的變化趨勢大，主要因為EUP-BPA 算法需要對每個用戶進行偏好Skyline 查詢，再合并各用戶的偏好Skyline結(jié)果集.

Fig.4 Effect of user number on CS number圖4 用戶數(shù)量對CS 數(shù)量的影響

2）數(shù)據(jù)規(guī)模對算法性能的影響

為了分析數(shù)據(jù)規(guī)模對MUP-TKS 性能的影響，本實驗對不同數(shù)據(jù)規(guī)模下的MUP-TKS，EKSJQ，EDSAS，EUP-BPA 算法進行測試，觀察4 種算法在不同數(shù)據(jù)規(guī)模下CPU 運行時間、CS數(shù)量的對比情況.

由圖5 可知，隨著數(shù)據(jù)集規(guī)模變大，CPU 運行時間不斷增加，因為當數(shù)據(jù)集規(guī)模變大時，需要比較的元組數(shù)量增加.而MUP-TKS 的增長趨勢比其他3 種算法小，主要因為MUP-TKS 利用剪枝策略和Vor-R*-DHash索引提前剪枝大量不可能成為Skyline 的數(shù)據(jù)點，減少了元組比較次數(shù).

Fig.5 Effect of data size on CPU execution time圖5 數(shù)據(jù)規(guī)模對CPU 運行時間的影響

3）k值對算法性能的影響

圖6 展示了4 種算法隨著k值變化CPU 運行時間變化的情況.隨著k值變化，MUP-TKS 的CPU 運行時間沒有太大變化，因為MUP-TKS 在每一輪放松支配后會保存結(jié)果集，當k值變化時，可直接找到對應(yīng)符合大小要求輪次的CS打分，即可得到Top-kSkyline結(jié)果集，該過程時間消耗很小.而EKSJQ，EUP-BPA算法都需要重新計算，時間消耗較大.

Fig.6 Effect of k value on CPU execution time圖6 k 值對CPU 運行時間的影響

圖7 展示了4 種算法隨著k值變化元組比較次數(shù)的變化情況.可以發(fā)現(xiàn)MUP-TKS 隨著k值增大，元組比較次數(shù)減少，因為當k值增大時，放松支配的輪次減少.而隨著k值增大，EKSJQ，EUP-BPA 算法的元組比較次數(shù)增多，因為需要進行更多的支配比較找到Topk個數(shù)據(jù)點.隨著k值增大，EDSAS 算法的元組比較次數(shù)基本沒有變化.

Fig.7 Effect of k value on the number of tuple comparison圖7 k 值對元組比較次數(shù)的影響

4）無差異閾值對算法性能的影響

本實驗分析無差異閾值對MUP-TKS 性能的影響.圖8 展示了MUP-TKS 在不同無差異閾值下CPU運行時間的變化情況.由圖8 可知，若只考慮第1 輪放松時間，無差異閾值變化對第1 輪放松的CPU 響應(yīng)時間影響不大，因為不同無差異閾值的初始數(shù)據(jù)集大小都是相同的，處理相同數(shù)據(jù)集規(guī)模的時間差異不大.而算法總運行時間隨著閾值增大而減小，因為無差異閾值增大后，放松支配時會刪減更多被支配的元組.

Fig.8 Effect of θ on CPU execution time圖8 θ 對CPU 運行時間的影響

5 總結(jié)

本文針對現(xiàn)實生活中道路網(wǎng)多用戶場景的偏好Top-kSkyline 查詢問題，進行深入分析與研究.作為道路網(wǎng)上單用戶偏好Skyline 查詢問題的補充，提出了一種基于道路網(wǎng)環(huán)境下多用戶偏好Top-kSkyline查詢方法.該方法利用剪枝規(guī)則和索引減少了距離計算開銷，并利用用戶群權(quán)重偏好次序進行放松支配，使結(jié)果集可控.實驗結(jié)果表明，本文方法能有效解決道路網(wǎng)多用戶偏好查詢問題，返回的結(jié)果集可以滿足多用戶偏好與權(quán)重需求，可以提供有效參考價值.下一步研究重點主要集中在對多查詢用戶移動情況下偏好 Top-kSkyline 查詢問題的處理.

作者貢獻聲明：李松提出了方法思路和技術(shù)方案；賓婷亮和郝曉紅負責算法優(yōu)化、完成部分實驗并撰寫論文；張麗平完成部分實驗；郝忠孝提出指導(dǎo)意見并修改論文.