道路網多用戶偏好Top-k 天際線查詢方法

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

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

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

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

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

本文的主要貢獻有3 點：

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

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

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

1 相關工作

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

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

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

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

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

2 主要定義

設道路網環境下數據集P={p1,p2,…,pn}，查詢用戶群G={q1,q2,…,qm}.

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

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

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

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

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

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

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

3 道路網多用戶偏好Top-k Skyline 查詢

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

3.1 道路網距離較優集選取方法

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

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

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

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

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

剪枝規則1.設數據點構成的MBR 分別為N1，N2，查詢用戶群的MBR 為Q，如果滿足：Edistmax（Q,N1）≤Edistmin（Q,N2），并且Ndistmax（Q,N1）＜Edistmin（Q,N2），則節點N2可被剪枝.

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

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

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

剪枝規則2.若Edistmin（Q,N）≥DN_MaxMin，則節點N被支配，即N和N中數據點{p1,p2,···,pi}被剪枝.

如圖1 所示，數據點p1，p2到查詢用戶群{q1,q2,q3}的最大網絡距離分別為DN1，DN2，有DN1＞DN2，則DN_MaxMin=DN2.數據點{p3,p4,p5,p6,p7,p8}構成的MBR為N1；若Edistmin（Q,N1）＞DN_MaxMin，可得N1中數據點到各查詢用戶的網絡距離大于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 剪枝規則2 示例

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

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

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

為了減少計算，在剪枝前基于路網數據點的網絡Voronoi 圖構建Vor-R*-DHash 索引結構，如圖2 所示.

Fig.2 Index structure of Vor-R*-DHash圖2 Vor-R*-DHash 索引結構

Vor-R*-DHash 索引結構構造過程有3 步：

1）構建路網所有數據點的網絡Voronoi 圖.

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

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

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

基于剪枝規則1～3 和Vor-R*-DHash 索引結構，進一步給出距離較優集選取方法，如算法1 所示.

算法1.距離較優集選取方法 G_DBC.

輸入：查詢用戶群G，道路網路段集R，數據集P；

輸出：距離維度不被支配的距離較優集DBC.

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

3.2 數據集的放松支配過程

3.2.1 獲取用戶群權重偏好次序

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

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

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

算法2.獲取用戶群權重偏好次序算法 CDW.

輸入：用戶群G，用戶查詢關鍵字keys，用戶權重w，維度空間D；

輸出：用戶群權重偏好次序GP.

① 初始化W為0；/*大小為數據集維度數*/

② 根據keys，w創建HMap1，HMap2；

③ fordj∈Ddo

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

⑤ end for

⑥ 根據W降序得到用戶群權重偏好次序GP；

⑦ returnGP./*返回用戶群權重偏好次序*/

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

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

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

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

定理5.數據集P經過第i（i＞1）輪放松支配后所得結果集Si一定是第i-1 輪放松支配后所得結果集Si-1的子集.

證明.設第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.給定數據集S，結果集數量隨著每一輪放松而呈單調非遞增趨勢，即

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

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

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

輸入：用戶群G，無差異閾值θ，并集S，數據維度空間D，k值，用戶查詢關鍵字keys，用戶權重w；

輸出：候選結果集CS.

3.3 Top-k 個數據點選取方法

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

定義10.單調打分函數F[25].數據集中數據點作為輸入域將數據點映射到實數范圍.F由r個單調函數構成，F={f1,f2,…,fr}.對于數據集中任意數據點，有，其中fj（p[dj]）為數據點在dj維度的單調函數.

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

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

定理8.數據集P根據任意單調打分函數所得數據點順序是Skyline 支配的拓撲順序.

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

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

定義12.z-整體屬性權重值.給定數據集P，數據點pi∈P，pi在dj維度的z-整體屬性權重值為

定理9.數據點任意維度的fj（p[dj]）是單調的.

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

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

定理10.F（pi）是單調打分函數.

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

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

算法4.Top-k個數據點選取方法TK_DC.

輸入：候選結果集CS，整體屬性權重集合W，維度優劣集合ζ；

輸出：Top-kSkyline 結果集.

① forpi∈CSdo

② 計算數據點的z-整體屬性權重值；/*根據式（4）*/

③ 計算數據點得分；/*根據式（5）*/

④ end for

⑤ 根據F（pi）降序排序；

⑥ return Top-k個數據點.

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

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

算法5.道路網多用戶偏好Top-kSkyline 查詢算法MUP-TKS.

輸入：數據集P，道路網路段集R，用戶群G，用戶查詢關鍵字keys，用戶權重w，無差異閾值θ，k，維度優劣集合ζ；

輸出：Top-kSkyline 結果集.

① 預先計算保存數據集的靜態Skyline 集；

② 距離較優集選取方法G_DBC；/*調用算法1*/

③ 對距離較優集與靜態Skyline 集求并集S；

④K-準放松支配算法KPRD；/*調用算法 3*/

⑤ Top-k個數據點選取方法TK_DC./*調用算法4*/

4 實驗比較與分析

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

4.1 數據集及實驗環境設置

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

Table 1 Experimental Parameter Setting表1 實驗參數設置

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

4.2 算法對比實驗

1）用戶數量對算法性能的影響

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

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

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

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

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

2）數據規模對算法性能的影響

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

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

Fig.5 Effect of data size on CPU execution time圖5 數據規模對CPU 運行時間的影響

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

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

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

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

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

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

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

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

5 總結

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

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