道路網(wǎng)多用戶偏好Top-k 天際線查詢方法

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

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

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

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

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

本文的主要貢獻(xiàn)有3 點(diǎn)：

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

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

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

1 相關(guān)工作

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

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

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

Top-kSkyline 查詢?cè)诙嗄繕?biāo)決策中往往更具優(yōu)勢(shì)，因?yàn)樗梢钥刂品祷氐慕Y(jié)果集數(shù)量.文獻(xiàn)[21]提出基于安全區(qū)域技術(shù)解決連續(xù)Top-kSkyline 查詢結(jié)果更新問(wèn)題，提出了結(jié)合Top-k查詢和Skyline 查詢的安全區(qū)域構(gòu)建算法.文獻(xiàn)[22]提出了MapReduce環(huán)境下Top-kSkyline 處理方法.文獻(xiàn)[23]將K-Skyband查詢與Top-kSkyline 查詢結(jié)合處理大數(shù)據(jù)集的Top-kSkyline 查詢.

目前道路網(wǎng)環(huán)境下Top-kSkyline 查詢研究大多集中在單用戶場(chǎng)景，較少考慮多用戶偏好和權(quán)重不同的場(chǎng)景.針對(duì)已有方法的不足，本文利用查詢點(diǎn)與數(shù)據(jù)點(diǎn)的位置關(guān)系剪枝數(shù)據(jù)集，利用所提的K-準(zhǔn)放松支配控制結(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ù)點(diǎn)p1、數(shù)據(jù)點(diǎn)p2，數(shù)據(jù)點(diǎn)之間的距離為Dist，當(dāng)且僅當(dāng)Dist（p1,qi）≤Dist（p2,qi），1≤i≤m；且存在Dist（p1,qi）＜Dist（p2,qi），1≤i≤m，稱p1道路網(wǎng)距離支配p2，記作p1?p2.本文距離如不特殊說(shuō)明，則為道路網(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對(duì)于用戶qi的重要性得分.

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

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

定義4.K-準(zhǔn)放松支配（KPRD）.設(shè)P為數(shù)據(jù)集，數(shù)據(jù)維度空間為D，dj為任意維度，總維度數(shù)為r，θ=（θ1,θ2,…,θK）是D上K個(gè)維度的無(wú)差異閾值.數(shù)據(jù)點(diǎn)pi，pt∈P，piK-準(zhǔn)放松支配pt，記作pi?pt，當(dāng)且僅當(dāng)：其中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的一個(gè)子集.該子集中數(shù)據(jù)點(diǎn)在道路網(wǎng)的距離維度和靜態(tài)維度都不能被P中任意其他數(shù)據(jù)點(diǎn)支配，并且是根據(jù)用戶群偏好和權(quán)重排序的Top-k個(gè)數(shù)據(jù)點(diǎn).本文將道路網(wǎng)多用戶偏好Top-kSkyline 查詢方法記作MUP-TKS.

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

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

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

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

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

定義8.Ndist 距離.設(shè)查詢用戶群的MBR 為Q，數(shù)據(jù)點(diǎn)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ù)點(diǎn)，Ndist（p,Q）為p到Q的網(wǎng)絡(luò)距離.

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

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

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

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

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

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

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

如圖1 所示，數(shù)據(jù)點(diǎn)p1，p2到查詢用戶群{q1,q2,q3}的最大網(wǎng)絡(luò)距離分別為DN1，DN2，有DN1＞DN2，則DN_MaxMin=DN2.數(shù)據(jù)點(diǎn){p3,p4,p5,p6,p7,p8}構(gòu)成的MBR為N1；若Edistmin（Q,N1）＞DN_MaxMin，可得N1中數(shù)據(jù)點(diǎn)到各查詢用戶的網(wǎng)絡(luò)距離大于DN_MaxMin，因?yàn)镋distmin（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ù)點(diǎn)pi到查詢用戶qj的歐氏距離，若min{DE（pi,qj）}＞DN_MaxMin（1≤j≤m），則pi被剪枝.

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

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

為了減少計(jì)算，在剪枝前基于路網(wǎng)數(shù)據(jù)點(diǎn)的網(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)造過(guò)程有3 步：

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

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

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

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

基于剪枝規(guī)則1～3 和Vor-R*-DHash 索引結(jié)構(gòu)，進(jìn)一步給出距離較優(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，可快速得到距離查詢點(diǎn)最近的數(shù)據(jù)點(diǎn)point，計(jì)算并保存sec_hash所需數(shù)據(jù).將point加入距離較優(yōu)集DBC，并初始化DN_MaxMin.接著將point父節(jié)點(diǎn)加入隊(duì)列queue中，計(jì)算并保存sec_hash所需數(shù)據(jù)，并初始化N1.每次取出隊(duì)頭節(jié)點(diǎn)處理，依據(jù)剪枝規(guī)則1～3 進(jìn)行節(jié)點(diǎn)的剪枝或者將節(jié)點(diǎn)加入DBC，并判斷是否需要更新N1，DN_MaxMin等值，直至隊(duì)列為空，循環(huán)結(jié)束.最后返回距離較優(yōu)集DBC.

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

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

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

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

進(jìn)一步給出獲取用戶群權(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-準(zhǔn)放松支配

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

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

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

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

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

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

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

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

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

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

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

3.3 Top-k 個(gè)數(shù)據(jù)點(diǎn)選取方法

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

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

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

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

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

證明.以反證法進(jìn)行證明.假設(shè)存在2 個(gè)數(shù)據(jù)點(diǎn)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（這兩者是等價(jià)的，會(huì)根據(jù)屬性的映射關(guān)系排序），或者p1和p2之間不具備支配關(guān)系.因此依據(jù)打分函數(shù)F所得數(shù)據(jù)點(diǎn)順序是按照Skyline支配關(guān)系的一個(gè)拓?fù)漤樞?證畢.

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

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

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

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

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

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

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

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

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

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

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

① forpi∈CSdo

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

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

④ end for

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

⑥ return Top-k個(gè)數(shù)據(jù)點(diǎn).

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

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)比較與分析

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

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

實(shí)驗(yà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個(gè)節(jié)點(diǎn)和179 179 條邊.興趣點(diǎn)數(shù)據(jù)集②https://www.ahla.com/來(lái)自北美酒店及登記信息.查詢用戶采用隨機(jī)生成的方式.本文使用Vor-R*-DHash 索引結(jié)構(gòu)組織數(shù)據(jù)集.實(shí)驗(yàn)參數(shù)取值范圍如表1 所示，每個(gè)用戶最大關(guān)注維度為4.每個(gè)實(shí)驗(yàn)采取單一變量原則，其余變量為默認(rèn)值，實(shí)驗(yàn)結(jié)果取30 次實(shí)驗(yàn)運(yùn)行的平均值.

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

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

4.2 算法對(duì)比實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

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

3）k值對(duì)算法性能的影響

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

Fig.6 Effect of k value on CPU execution time圖6 k 值對(duì)CPU 運(yùn)行時(shí)間的影響

圖7 展示了4 種算法隨著k值變化元組比較次數(shù)的變化情況.可以發(fā)現(xiàn)MUP-TKS 隨著k值增大，元組比較次數(shù)減少，因?yàn)楫?dāng)k值增大時(shí)，放松支配的輪次減少.而隨著k值增大，EKSJQ，EUP-BPA 算法的元組比較次數(shù)增多，因?yàn)樾枰M(jìn)行更多的支配比較找到Topk個(gè)數(shù)據(jù)點(diǎn).隨著k值增大，EDSAS 算法的元組比較次數(shù)基本沒(méi)有變化.

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

4）無(wú)差異閾值對(duì)算法性能的影響

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

Fig.8 Effect of θ on CPU execution time圖8 θ 對(duì)CPU 運(yùn)行時(shí)間的影響

5 總結(jié)

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

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