邵路伊，秦小麟，王瀟逸，郭成蓋，鄧丹萍

南京航空航天大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，南京 210016

1 引言

隨著數(shù)據(jù)庫技術(shù)的發(fā)展，數(shù)據(jù)庫中存儲的數(shù)據(jù)量急劇增加，如何從海量數(shù)據(jù)中找到人們最感興趣的信息，為人們做出有效的決策，成為一個重要的研究課題。因此，Skyline查詢在2001年作為一種新的數(shù)據(jù)庫操作符被提出來[1]，從此得到了數(shù)據(jù)庫領(lǐng)域眾多研究者的大量關(guān)注。Skyline查詢在很多應(yīng)用中都有著非常重要的作用，例如多目標(biāo)決策、數(shù)據(jù)挖掘及可視化，以及用戶偏好查詢等[2]。數(shù)據(jù)庫領(lǐng)域最初的Skyline查詢是由單用戶發(fā)起的，例如，一個用戶發(fā)出查詢“查找一家價格便宜同時距離海邊近的酒店”。然而，在數(shù)據(jù)管理領(lǐng)域，隨著計算環(huán)境的不斷變化、信息技術(shù)的發(fā)展和應(yīng)用新需求的出現(xiàn)，越來越多的數(shù)據(jù)庫應(yīng)用會涉及到由多個用戶共同完成一個查詢，例如：

查詢1一群游客共同商定一個旅游城市，每位游客針對城市的氣候、地理位置、景點以及消費水平等提出不同要求的查詢。

查詢2一個家庭共同選擇一個寬帶方案，每位家庭成員針對方案的帶寬、價格、合約期限等提出不同要求的查詢。

查詢3一組同事共同預(yù)定一家聚餐餐廳，每位同事針對餐廳的口味、環(huán)境、服務(wù)以及人均價格等提出不同要求的查詢。

上述查詢事例可以抽象為：對于某數(shù)據(jù)集，多個用戶發(fā)起不同維度組合上的子空間Skyline查詢，系統(tǒng)對同時存在的子結(jié)果集進(jìn)行整合，最終返回一個結(jié)果集。此類查詢可概括為MUSQ（multi-user Skyline query）問題，即多用戶Skyline查詢問題。在此類查詢中，發(fā)起查詢操作的主體由單用戶轉(zhuǎn)變?yōu)槎嘤脩?，并且多?shù)情況下，用戶只對數(shù)據(jù)集的某幾個維度感興趣，并非全部維度。由于用戶之間關(guān)注的維度不同，在某些數(shù)據(jù)集上可能會發(fā)生查詢條件沖突的現(xiàn)象。

研究者對子空間Skyline查詢算法已經(jīng)有了較為深入的研究，包括對某一特定子空間的查詢[3]和對全部子空間[4-5]的查詢。目前已有的算法均是在單用戶場景下設(shè)計的，可以得到符合單個用戶需求的子Skyline結(jié)果集，但是在涉及多用戶參與的Skyline查詢中無法對同時得到的多個子Skyline結(jié)果集進(jìn)行有效整合。

同時，傳統(tǒng)的Skyline算法缺乏交互性。對于用戶提出的查詢要求，已有的算法通過單次Skyline計算得到查詢結(jié)果并返回給用戶。然而，在實際應(yīng)用場景中，由于用戶的數(shù)量增加，且不同用戶關(guān)注的數(shù)據(jù)維度不同，用戶之間的查詢條件存在差異性，單次Skyline計算得到的結(jié)果可能無法令所有用戶滿意。此時，用戶與查詢結(jié)果之間需要交互，用戶與用戶之間更需要交互，用戶根據(jù)系統(tǒng)返回結(jié)果和其他用戶的選擇結(jié)果來調(diào)整自己的需求，使得結(jié)果更快地趨向于統(tǒng)一。通過交互，可以使系統(tǒng)返回更符合用戶需求的候選集，令用戶更好地做出決策。

此外，出于經(jīng)驗、社會地位等因素的考慮，不同用戶在決策過程中的地位不同，當(dāng)某個用戶給出的意見更具有專業(yè)性，其查詢需求則更具有決定性作用。例如，在餐廳選擇的例子中，用戶A在外就餐的次數(shù)多，對餐廳的選擇相比其他用戶更有經(jīng)驗，因此他的查詢意見在最終決定中應(yīng)賦予更大的權(quán)重。而傳統(tǒng)的Skyline算法對用戶本身的權(quán)重沒有考慮。在此基礎(chǔ)上，本文提出一種基于權(quán)重的交互式多用戶Skyline查詢（weight-based interactive multi-user Skyline query，MUSW）算法，有效處理多用戶Skyline查詢問題。

本文主要貢獻(xiàn)如下：

（1）深入多用戶Skyline查詢問題，分析傳統(tǒng)算法在多用戶參與下的不足，提出基于用戶權(quán)重的MUSW算法，考慮用戶在查詢選擇過程中的權(quán)重比例，有效解決了多用戶Skyline查詢結(jié)果的整合問題。

（2）定義了一種滿意度度量方法，對子空間Skyline查詢后得到的結(jié)果進(jìn)行滿意度計算，再利用top-k選取k個滿意度高的結(jié)果，可以有效控制輸出結(jié)果的個數(shù)。

（3）設(shè)計了一套交互查詢的機(jī)制，通過用戶與返回結(jié)果以及用戶與用戶之間的交互，使得結(jié)果更符合用戶的要求。

本文組織結(jié)構(gòu)如下：第2章介紹Skyline查詢的基礎(chǔ)知識及相關(guān)工作，并分析現(xiàn)有方法在解決多用戶Skyline查詢時的不足；第3章提出MUSW算法，并對算法進(jìn)行詳盡的解析；第4章對MUSW算法進(jìn)行實驗評估，驗證其可行性并檢驗其性能；最后對本文工作進(jìn)行總結(jié)。

2 基礎(chǔ)知識

2.1 Skyline查詢概述

首先，介紹Skyline查詢中的相關(guān)概念。

定義1（支配[1]）給定一個d維數(shù)據(jù)集S，D為d個維度的集合。對于S上的兩個數(shù)據(jù)點p和q，p支配q當(dāng)且僅當(dāng)p在任一維度上的取值都不比q差，且至少在一個維度上比q好，記為p?q。

值得注意的是，不同維度的評判標(biāo)準(zhǔn)不同，由數(shù)據(jù)集本身的屬性定義。

定義2（全空間Skyline）給定一個d維數(shù)據(jù)集S，以及維度組合U，如果U=D，則稱U上所有不被任何其他點支配的數(shù)據(jù)點的集合為全空間Skyline結(jié)果集，記為skyD(S)。

表1為餐廳數(shù)據(jù)集示例，該數(shù)據(jù)集有5個數(shù)據(jù)點，4個維度，其中前3個維度的取值越大越優(yōu)，第4個維度則相反。根據(jù)定義2，當(dāng)一個用戶發(fā)出查詢“查找口味佳、環(huán)境好、服務(wù)水平高并且人均價格低的餐廳”，則為全空間Skyline查詢，其查詢結(jié)果為skyD(S)={O1,O2,O3,O4,O5}。

定義3（子空間Skyline）給定一個d維數(shù)據(jù)集S，以及維度組合U，如果U?D，則稱U上所有不被任何其他點支配的數(shù)據(jù)點的集合為子空間Skyline結(jié)果集，記為skyU(S)。

同樣以表1的數(shù)據(jù)集為例，此時有3位用戶A、B、C分別根據(jù)自己感興趣的數(shù)據(jù)維度提出了不同的查詢。

用戶A：查詢口味佳且服務(wù)好的餐廳。

用戶B：查詢?nèi)司鶅r格低且口味佳的餐廳。

用戶C：查詢環(huán)境評分高的餐廳。

以上3個查詢均為子空間Skyline查詢，將得到3個維度組合下的子空間Skyline查詢結(jié)果，分別為skyA(S)={O1,O3}、skyB(S)={O4,O5}、skyC(S)={O2,O5}。

Table 1 Restaurant information data set表1 餐廳數(shù)據(jù)集示例

2.2 相關(guān)工作

傳統(tǒng)Skyline查詢的研究主要分為全空間Skyline查詢和子空間Skyline查詢。全空間Skyline查詢算法主要包括 BNL（block-nested-loops）算法[1]、SFS（sort first skyline）算法[6]、D&C（divide and conquer）算法[1]，以及基于R樹索引提出的NN（nearest neighbor）算法[7]和BBS（branch and bound skyline）算法[8]，其中BBS算法具有很強(qiáng)的剪枝能力。全空間Skyline的查詢結(jié)果會隨著數(shù)據(jù)量和數(shù)據(jù)維度的增加而劇增，意義不大，因此Pei等人[5,9]提出了子空間Skyline查詢的概念。研究者對子空間Skyline查詢的研究主要包括：Xia等人[10]提出了一種數(shù)據(jù)結(jié)構(gòu)CSC（compressed SkyCube），對Skyline進(jìn)行壓縮分組，并基于CSC結(jié)構(gòu)給出一個Skyline結(jié)果集計算方法QueryCSC；Huang等人[11]提出了SkyCube立方體的概念，他們將Skyline計算的所有子空間建立成一個SkyCube結(jié)構(gòu)，并在此基礎(chǔ)上提出了IMASCIR（incremental maintenance algorithm of SkyCube）算法；Tao等人[3,12]首次研究任意單個子空間上的Skyline查詢，并給出一種計算任意子空間上Skyline對象的算法SUBSKY。以上傳統(tǒng)的Skyline查詢算法均針對單用戶進(jìn)行研究，未考慮多用戶參與下查詢要求的差異性，也沒有對各子結(jié)果集的整理和融合進(jìn)行進(jìn)一步的研究。

考慮到傳統(tǒng)Skyline查詢在解決問題上的缺陷，研究者對Skyline查詢的變種進(jìn)行研究，其中包括多用戶Skyline查詢和交互Skyline查詢。對多用戶Skyline查詢的研究如下：對于在分類屬性上定義的目標(biāo)選項和用戶偏好，Benouaret等人[13]利用匹配度來計算支配關(guān)系，并提出了collective Skyline的概念，將Skyline中數(shù)據(jù)點的支配要求放松，對一半以上的用戶成立即可，從而減少了Skyline結(jié)果集的規(guī)模；Bikakis等人[14]也利用匹配度，并給出了一種雙重基于Pareto的策略，依次在單用戶下和所有用戶下對目標(biāo)進(jìn)行偏序排序；Ali等人[15]基于評價函數(shù)提出一種針對組用戶查詢的策略，致力于找到對一個子用戶組而言評價函數(shù)最高的結(jié)果，且要求子用戶組中用戶的數(shù)量盡可能大；Sato等人[16]給出了一種解決空間數(shù)據(jù)集上多查詢點問題的AMUSE算法，先找到一個子查詢組的最優(yōu)點，再通過k-NN查詢找到更優(yōu)的數(shù)據(jù)點。這些解決多用戶參與的算法中，均沒有對用戶的重要程度進(jìn)行劃分，同時也沒有考慮查詢過程中的交互問題。同時，也有研究者對交互式的Skyline查詢進(jìn)行研究。Lee等人[17]提出了一種交互引導(dǎo)框架，針對用戶提出的查詢，系統(tǒng)分析現(xiàn)有的Skyline結(jié)果，推出一些能更新支配關(guān)系的重要問題反饋給用戶，從而減小Skyline結(jié)果集的規(guī)模；Chester等人[18]通過增量式地修改Skyline查詢要求，動態(tài)地調(diào)整Skyline的結(jié)果，以獲得更符合用戶真實需求的結(jié)果集。但以上的交互查詢僅考慮單用戶與系統(tǒng)之間的交互性，沒有考慮多用戶之間的交互對Skyline查詢的影響。

綜上，現(xiàn)有算法在解決多用戶Skyline查詢上的研究還很不成熟，在涉及多用戶的Skyline查詢過程中無法有效整合子Skyline結(jié)果集。此外現(xiàn)有的Skyline查詢?nèi)狈τ脩糁g的交互性，無法最大程度上滿足所有用戶的需求。為解決以上問題，本文提出了MUSW算法。

3 基于權(quán)重的交互式多用戶Skyline查詢

3.1 算法的基本思路

為解決多用戶Skyline查詢問題，本文提出了一種滿意度度量方法，由用戶權(quán)重決定每個數(shù)據(jù)點的滿意度大小。首先給出滿意度的定義。

定義4（滿意度）對于d維數(shù)據(jù)集S中的一點oi，滿意度W為用戶群U對該數(shù)據(jù)點的總體滿意程度，其計算公式為WOi=∑lj(j|oi∈SKYj)，其中SKYj為用戶uj的子空間Skyline結(jié)果集，lj為用戶uj對應(yīng)的權(quán)重大小。

由定義可知，滿意度由用戶的權(quán)值決定，當(dāng)其中一個用戶的權(quán)重增大，那該點的滿意度也增加。本文利用滿意度來衡量目標(biāo)選項的優(yōu)劣性，滿意度越高的目標(biāo)選擇越有可能返回給用戶選擇。因此，算法的基本思路為，在迭代過程中通過交互來動態(tài)調(diào)整用戶的權(quán)值，使權(quán)值的比例更符合用戶在用戶群中的地位體現(xiàn)，從而使得返回的結(jié)果集更趨向于用戶群的需求。

在多用戶Skyline查詢問題中，對于初始數(shù)據(jù)集D={o1,o2,…,om}，用戶群U={u1,u2,…,un},提出基于各自偏好的查詢Q={q1,q2,…,qn}。MUSW算法的解決方案為，通過子空間Skyline查詢得到每個用戶ui對應(yīng)的SKYi(SKYi?D)，接著進(jìn)行多輪迭代交互，根據(jù)用戶的權(quán)值計算每個數(shù)據(jù)點oi在第t輪迭代中的滿意度，再將本輪的候選集結(jié)果返回給用戶，系統(tǒng)通過用戶的反饋對權(quán)重進(jìn)行動態(tài)調(diào)整，從而在下輪迭代中對數(shù)據(jù)點的滿意度進(jìn)行更新，直至交互過程終止。在權(quán)重更新過程中，系統(tǒng)對用戶投票結(jié)果進(jìn)行分析。在目標(biāo)決策中，一個專業(yè)的決策者會影響其他決策者的選擇[19]，因此當(dāng)用戶u1參照另一個用戶u2的選擇時，則說明用戶u2更加專業(yè)，即u2在用戶群中的地位更高。權(quán)重是用戶地位的體現(xiàn)，因此u2的權(quán)重將增大。

以2.1節(jié)中表1的數(shù)據(jù)集為例，A、B、C用戶分別提出查詢條件，且用戶設(shè)定返回結(jié)果集大小為3。首先，分別對A、B、C用戶作子空間上的Skyline查詢操作，得到skyA(S)={O1,O3}、skyB(S)={O4,O5}、skyC(S)={O2,O5}。首先考慮3位用戶擁有平等的地位，即權(quán)值lA=lB=lC=1，根據(jù)定義4計算用戶對目標(biāo)Oi的滿意度可得而因此將返回滿意度W最高的3個目標(biāo){O5,O1,O2}作為結(jié)果。在后續(xù)投票過程中，用戶A選擇o1,用戶B選擇o5，而用戶C參照A選擇了o1。當(dāng)系統(tǒng)對投票結(jié)果進(jìn)行分析，發(fā)現(xiàn)C參照了A的選擇，可知A的地位比C更高，因此A的權(quán)重將增大，而C的權(quán)重相應(yīng)減小。根據(jù)權(quán)值變化函數(shù)（詳見3.5節(jié)），系統(tǒng)預(yù)定義的常數(shù)A取0.5，則在第1輪交互過程中，權(quán)值變化值Δl(t)=0.5。因此A相應(yīng)權(quán)值增加為1.5，C的權(quán)值減小為0.5，而B的權(quán)值保持為1。此時因此將返回{O1,O3,O5}作為結(jié)果。隨著后續(xù)交互的進(jìn)行，用戶的權(quán)值越來越趨向于用戶真實的需求，而目標(biāo)選項的滿意度由用戶的權(quán)值決定，那么返回的結(jié)果則越來越符合用戶的要求。

3.2 MUSW算法

MUSW算法的輸入為初始數(shù)據(jù)集合S、用戶集合U和用戶理想結(jié)果集大小k，輸出為更大程度符合用戶需求的Skyline結(jié)果集SKYk。MUSW算法將查詢處理過程分為3個步驟：首先，針對多用戶的不同需求，通過SUBSKY算法對原始數(shù)據(jù)集S進(jìn)行子空間Skyline查詢處理，得到各用戶uj對應(yīng)的子Skyline結(jié)果集SKYj組成的集合SUBSKYS；其次，對該結(jié)果建立一個基于Map的結(jié)果集索引；最后，實現(xiàn)交互流程，通過多輪迭代，最終返回大小為k的最終結(jié)果集給用戶，對應(yīng)算法1的第4～5行，具體的交互過程將在3.4節(jié)和3.5節(jié)中詳細(xì)介紹。子空間Skyline查詢的時間復(fù)雜度為O(nlbn)，建立Map索引結(jié)構(gòu)的時間復(fù)雜度為O(count(subskys))，交互過程的時間復(fù)雜度為O[t(count(subskys)+m)]（詳見算法2）。綜上，算法1的時間復(fù)雜度為O[nlbn+t(count(subskys)+m)]，其中n為數(shù)據(jù)點個數(shù)，count(subskys)為子空間候選集中的數(shù)據(jù)點個數(shù)，m為用戶的數(shù)量，t為迭代的次數(shù)。

算法1MUSW算法

輸入：原始數(shù)據(jù)集合S、用戶集合U和用戶理想結(jié)果集大小k。

輸出：交互后大小為k的Skyline結(jié)果集SKYk。

3.3 建立基于Map的索引

MUSW算法的第一步是通過SUBSKY算法得到n個用戶對應(yīng)的n個子Skyline結(jié)果集集合SubSKYS，在后續(xù)的迭代過程中，系統(tǒng)會多次計算子Skyline結(jié)果集中數(shù)據(jù)點的滿意度大小，需要對結(jié)果集進(jìn)行多次遍歷查詢，因此需要對其建立索引減少遍歷時間。本文采用基于Map的索引結(jié)構(gòu)，將SKYj中的目標(biāo)選項oi作為關(guān)鍵字建立索引，并以升序排列，每個關(guān)鍵字映射的內(nèi)容為所有包含oi的子空間對應(yīng)的用戶群。

以表1中的數(shù)據(jù)為例，對A、B、C用戶做子空間上的Skyline查詢操作后得到skyA(S)={O1,O3}、skyB(S)={O4,O5}、skyC(S)={O2,O5}，以上3個子結(jié)果集組成SubSKYS={O1,O2,O3,O4,O5}，對其建立的索引如圖1所示。

Fig.1 Map-based index graph圖1 基于Map的索引圖

3.4 用戶交互過程

查詢過程中，需求的改變會影響Skyline的結(jié)果集[19]，特別對于多用戶參與的查詢，用戶可以根據(jù)查詢結(jié)果對自己的查詢需求進(jìn)行微調(diào)，交互的引入可使用戶獲得更準(zhǔn)確的結(jié)果。因此，在得到子空間Skyline結(jié)果集的索引后，MUSW算法將通過用戶與返回結(jié)果的交互，以及用戶之間的交互，對用戶的權(quán)重進(jìn)行動態(tài)調(diào)整，使結(jié)果趨向于用戶的需求，迭代交互過程是核心部分。

算法2用戶交互算法Interact

輸入：用戶理想結(jié)果集大小k，子結(jié)果集索引IndexOf-SubSky。

輸出：交互結(jié)果SKYk。

算法2的第1行分別對用戶權(quán)重和迭代輪次等進(jìn)行了初始化。其中，在交互之前用戶的地位是平等的，因此系統(tǒng)將每個用戶的權(quán)重初始值設(shè)為1。首先，系統(tǒng)通過用戶的權(quán)重值和滿意度計算公式得到子Skyline結(jié)果集中所有目標(biāo)選項的滿意度，然后選取滿意度最高的k個結(jié)果返回，同時將結(jié)果顯示在交互界面上供用戶選擇，對應(yīng)算法2的第3～4行。此時，每個用戶選擇k個結(jié)果中最符合自己需求的1個目標(biāo)選項返回給系統(tǒng)，系統(tǒng)記錄下用戶的選擇以便之后的分析。根據(jù)用戶的選擇，系統(tǒng)將判斷交互是否達(dá)到終止條件，一旦條件滿足，將終止交互并將當(dāng)前輪次產(chǎn)生的k個目標(biāo)選項作為SKYk返回。終止的條件具體為：（1）所有用戶均選擇同一個目標(biāo)，則返回以該目標(biāo)為首的SKYk。（2）該輪迭代后，用戶當(dāng)前輪次的投票結(jié)果與上一輪的投票結(jié)果相同。若終止條件不滿足，將對用戶的投票結(jié)果進(jìn)行分析，并根據(jù)分析結(jié)果相應(yīng)地更新權(quán)重，具體算法見算法3。一輪交互結(jié)束后，用戶的權(quán)重會根據(jù)本輪用戶的投票選擇做出動態(tài)調(diào)整。由此可知，算法2的時間復(fù)雜度為O[t(count(subskys)+m)]，其中count(subskys)為子空間候選集索引的數(shù)據(jù)點個數(shù)，m為用戶的數(shù)量，t為迭代的次數(shù)，值得注意的是，由于算法快速收斂，因此t一般很小。

3.5 分析更新算法

權(quán)重的變化是根據(jù)用戶該輪投票結(jié)果來進(jìn)行動態(tài)調(diào)整的。在目標(biāo)決策中，一個專業(yè)的決策者會影響其他決策者的選擇[19]，即用戶的投票結(jié)果會相互影響。而專業(yè)的用戶，他在用戶群里的權(quán)重比例更大。因此，算法3對所有用戶做以下操作：當(dāng)用戶uj選擇的是自身子結(jié)果集上SKYj的點，那么其權(quán)重值保持不變，對應(yīng)算法3的第2～3行；當(dāng)用戶uj選擇其他用戶up的子結(jié)果集SKYp的點，那么用戶uj的權(quán)重會減少Δl(t)，用戶up的權(quán)重值會相應(yīng)增加Δl(t)，保證了所有用戶的權(quán)重值總和維持在n，對應(yīng)算法3的第5～8行。其中，每輪交互迭代過程的權(quán)重的變化率Δl(t)是有關(guān)迭代輪次t的函數(shù)f(t)=A/t2，其中A為系統(tǒng)預(yù)定義的常數(shù)，用戶可以根據(jù)需求進(jìn)行調(diào)整。綜上，哈希技術(shù)下Map索引的查詢時間復(fù)雜度為O(1)，因此算法3的時間復(fù)雜度為O(m)，其中m為用戶的數(shù)量。

定理1對于給定的數(shù)據(jù)集D和用戶集U，權(quán)重更新算法快速收斂，因此MUSW算法的交互迭代過程具有收斂性。

證明在權(quán)重更新的過程中，用戶權(quán)值組的各個元素隨迭代輪次發(fā)生動態(tài)變化。第t輪的權(quán)值變化增量為f(t)=A/t2，對?t0，在t0之后，權(quán)值增量總量為而由于權(quán)值不完全總在權(quán)值組的同一元素中，因此對?t0，在t0之后，權(quán)值組任意元素的增量都將A/(t0-1)。同時，令g(t0)=A/(t0-1),則g′(t0)=-A/(t0-1)2，則在t0足夠小時，g(t0)就能夠快速收斂，并隨著t0的增大快速收斂至0。因此f(t)將隨著t0的增大快速收斂至0，即用戶的權(quán)值組快速收斂至穩(wěn)定。由定義4可知，滿意度由用戶的權(quán)重決定，則數(shù)據(jù)點的滿意度W也趨向于不變，從而使得返回的結(jié)果趨向于不變，因此MUSW算法迭代過程收斂。 □

算法3分析更新算法Analyze

輸入：投票結(jié)果SelectArray，用戶權(quán)重LevelArray，迭代輪次t。

輸出：更新后的用戶權(quán)重LevelArray。

4 實驗及分析

以下驗證MUSW算法的有效性和交互性能，其中驗證交互性能的必要性在于，在多用戶參與的交互過程中，若系統(tǒng)無法在特定間隔內(nèi)提供反饋信息將影響用戶的交互體驗。由于目前尚未有其他專門針對交互式多用戶Skyline查詢的算法可供比較，本實驗中作為對比的Baseline算法為傳統(tǒng)單用戶下的Subsky算法[13-14]的兩種擴(kuò)展。首先通過Subsky算法獲取多個子空間上的子Skyline結(jié)果集，然后對所有子結(jié)果集分別進(jìn)行以下兩種方式的整合：對所有子結(jié)果集做交集處理，對所有子結(jié)果集做并集處理，分別記為Baseline-intersection算法和Baseline-union算法。

MUSW算法的有效性將從兩方面得到證明：首先，對算法的可行性進(jìn)行驗證，實驗過程中，MUSW算法可以得到用戶預(yù)定義大小的結(jié)果集，因此MUSW算法具備可行性；其次，對結(jié)果集大小這一指標(biāo)進(jìn)行衡量，并與Baseline-intersection算法、Baselineunion算法的執(zhí)行結(jié)果進(jìn)行對比。

算法的交互性能采用迭代輪次和系統(tǒng)自適應(yīng)間隔兩個指標(biāo)（見表2）進(jìn)行衡量。其中迭代輪次為系統(tǒng)與用戶之間進(jìn)行的交互次數(shù)，從系統(tǒng)返回候選集、用戶投票、系統(tǒng)分析投票結(jié)果到更新用戶權(quán)重值這整個過程為一個迭代輪次。系統(tǒng)自適應(yīng)間隔，指用戶通過交互進(jìn)行投票后，系統(tǒng)通過分析更新用戶權(quán)值從而調(diào)整目標(biāo)選項的滿意度到可支持下一輪交互的間隔。

Table 2 Experimental indicators表2 實驗指標(biāo)

實驗分別采用模擬數(shù)據(jù)集和真實數(shù)據(jù)集進(jìn)行測試，如表3所示。其中，模擬數(shù)據(jù)集參照文獻(xiàn)[1]中提到的數(shù)據(jù)生成器產(chǎn)生，默認(rèn)屬性值越小越優(yōu)。模擬數(shù)據(jù)集根據(jù)數(shù)據(jù)點維度間關(guān)系分為3種[1]：（1）相關(guān)數(shù)據(jù)集，一個數(shù)據(jù)點在某個維度上相對較優(yōu)，那么在其他維度上也較優(yōu)；（2）獨立數(shù)據(jù)集，數(shù)據(jù)集中所有維度上的數(shù)值都是獨立分布的，即各維度直接沒有相關(guān)關(guān)系；（3）反相關(guān)數(shù)據(jù)集，數(shù)據(jù)點在某個維度上較優(yōu)，則在其他維度上相對較差。實驗中，3種數(shù)據(jù)集的全空間維度均為6維。真實數(shù)據(jù)集參照文獻(xiàn)[5]中的NBA球員技術(shù)統(tǒng)計數(shù)據(jù)集(www.nba.com)。由于實驗需要多用戶同時參與，在學(xué)校范圍內(nèi)選取了30名志愿者，在實驗過程中作為用戶提出不同的需求。為避免隨機(jī)性對實驗結(jié)果產(chǎn)生的影響，所有的結(jié)果均為10次實驗運(yùn)行結(jié)果的平均值。

Table 3 Experimental datasets表3 實驗數(shù)據(jù)集

實驗所用計算機(jī)的操作系統(tǒng)為Windows 10，CPU主頻為3.3 GHz，內(nèi)存為4 GB。所有算法均用C++語言實現(xiàn)，編譯器為Visual Studio2010。

4.1 數(shù)據(jù)量對算法性能的影響

為分析數(shù)據(jù)量對MUSW算法性能的影響，本實驗采用相關(guān)、獨立和反相關(guān)3種人造數(shù)據(jù)集進(jìn)行測試。數(shù)據(jù)點個數(shù)n從1×104到5×104變化。實驗隨機(jī)挑選10組測試用戶組合，設(shè)定每組測試中參與的用戶數(shù)為5，每個用戶關(guān)注的最大維度為4，所求結(jié)果集大小、迭代輪次和系統(tǒng)自適應(yīng)間隔為10組實驗結(jié)果的平均值。

圖2（a）、（b）、（c）分別展示了不同類型數(shù)據(jù)集下3種算法的結(jié)果集大小對比，從實驗結(jié)果可以發(fā)現(xiàn)：Baseline算法得到的結(jié)果集大小隨著數(shù)據(jù)集增大而增加，其中Baseline-union算法的結(jié)果集規(guī)模較其他兩種算法很大，在圖2（c）中尤為明顯；Baseline-intersection算法在反相關(guān)數(shù)據(jù)集下的結(jié)果集規(guī)模比在相關(guān)數(shù)據(jù)集下小，這是因為前者各子Skyline結(jié)果集的數(shù)據(jù)點之間的共性??；而MUSW算法的結(jié)果集大小在不同的數(shù)據(jù)集下均穩(wěn)定于較小的常量，保證了結(jié)果的有效性，該常量根據(jù)用戶的需求由系統(tǒng)提前設(shè)定，故不受結(jié)果集基數(shù)大小以及數(shù)據(jù)集類型的影響。

考慮到Baseline算法均沒有交互過程，因此對其不做交互性能的對比。圖3為MUSW算法在相關(guān)、獨立和反相關(guān)3種數(shù)據(jù)集下的迭代輪次結(jié)果。由于正相關(guān)數(shù)據(jù)集下各子空間Skyline結(jié)果集包含的數(shù)據(jù)點較少，且各子結(jié)果之間的交集較多，用戶更容易達(dá)成共識，從而交互迭代的次數(shù)較其他兩個數(shù)據(jù)集少。從實驗結(jié)果看，迭代輪次整體上與數(shù)據(jù)量成正比，但變化幅度不大，且能有效控制在10次以內(nèi)，這是因為MUSW算法中的權(quán)值變化函數(shù)具有收斂性，從而使得交互過程可收斂。

Fig.2 Effect of cardinality on result size圖2 數(shù)據(jù)點基數(shù)對結(jié)果集大小的影響

Fig.3 Effect of cardinality on iteration rounds圖3 數(shù)據(jù)點基數(shù)對迭代輪次的影響

圖4展示了3種數(shù)據(jù)集下系統(tǒng)自適應(yīng)間隔的對比，該時間主要包括MUSW算法中的用戶投票結(jié)果分析和滿意度計算的運(yùn)行時間。由于滿意度計算與子Skyline結(jié)果的規(guī)模相關(guān)，從而隨著數(shù)據(jù)集的增加，滿意度計算消耗的時間緩慢遞增。實驗中系統(tǒng)交互間隔均在10 ms以內(nèi)，算法中索引的建立使其可高效支持查詢中用戶權(quán)重的動態(tài)變化。

Fig.4 Effect of cardinality on adaptive interval圖4 數(shù)據(jù)點基數(shù)對系統(tǒng)自適應(yīng)間隔的影響

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

本實驗主要考察用戶數(shù)量對MUSW算法性能的影響。由上節(jié)實驗可知，正相關(guān)數(shù)據(jù)集下產(chǎn)生的子Skyline結(jié)果集的數(shù)據(jù)點較少，算法性能均較好，因此實驗采用獨立數(shù)據(jù)集和反相關(guān)數(shù)據(jù)集進(jìn)行測試，數(shù)據(jù)點個數(shù)均為1×104。實驗隨機(jī)從30名志愿者中選取不同數(shù)量的用戶組合，每組用戶的數(shù)量從2到6變化，每個用戶關(guān)注的維度最大為4，每組所求結(jié)果集大小、迭代輪次和系統(tǒng)自適應(yīng)間隔為10次實驗結(jié)果的平均值。

圖5（a）、（b）分別為獨立數(shù)據(jù)集和反相關(guān)數(shù)據(jù)集下結(jié)果集大小的測試結(jié)果，可以看出隨著用戶數(shù)量的增加，即子空間個數(shù)增長時，Baseline-union算法得到的結(jié)果集大小呈正比增長，而Baseline-intersection算法的結(jié)果集大小反而會減少。這是因為用戶數(shù)量增加，即子空間個數(shù)增加，同時滿足所有用戶需求的交集變小。而MUSW算法優(yōu)于以上兩種算法，不受用戶數(shù)量的影響，能穩(wěn)定得到固定大小的候選集，有效地輸出結(jié)果。

Fig.5 Effect of user number on result size圖5 用戶數(shù)量對結(jié)果集大小的影響

MUSW算法在獨立和反相關(guān)數(shù)據(jù)集下的迭代輪次結(jié)果如圖6所示，當(dāng)參與的用戶增多，多用戶之間統(tǒng)一結(jié)果的難度增加，因此迭代輪次隨之增加，但是均在10次以內(nèi)，在用戶可接受范圍內(nèi)。圖7為系統(tǒng)自適應(yīng)間隔的實驗結(jié)果，當(dāng)用戶數(shù)量增加，子空間Skyline結(jié)果集個數(shù)增加，對目標(biāo)選項滿意度的計算耗時增加，因此系統(tǒng)自適應(yīng)間隔與用戶數(shù)量呈正比緩慢增長，且時間在10 ms以內(nèi)，給用戶提供良好的交互體驗。

Fig.6 Effect of user number on iteration rounds圖6 用戶數(shù)量對迭代輪次的影響

Fig.7 Effect of user number on adaptive interval圖7 用戶數(shù)量對系統(tǒng)自適應(yīng)間隔的影響

4.3 真實數(shù)據(jù)集下的算法性能

本實驗采用NBA球員技術(shù)統(tǒng)計數(shù)據(jù)集對算法的性能進(jìn)行驗證。該數(shù)據(jù)集共有17 265條數(shù)據(jù)，全空間維數(shù)為8維。為便于同人造數(shù)據(jù)下的實驗比較，對原始數(shù)據(jù)進(jìn)行預(yù)處理，將各維度數(shù)值映射到區(qū)間[1,100]之間，相應(yīng)轉(zhuǎn)換函數(shù)如下：

其中，p(ai)為數(shù)據(jù)在維度ai上的取值；maxai和minai分別為所有數(shù)據(jù)點在該維度上的最大值和最小值。

圖8展示了真實數(shù)據(jù)集下用戶數(shù)量對MUSW算法性能的影響。圖8（a）、（b）分別為迭代次數(shù)和系統(tǒng)自適應(yīng)間隔的實驗結(jié)果，可以發(fā)現(xiàn)其結(jié)果與人造標(biāo)準(zhǔn)數(shù)據(jù)下的結(jié)果一致，驗證了MUSW算法的收斂性，以及可高效地支持用戶進(jìn)行交互式查詢。

Fig.8 Effect of user number on algorithm performance under real data set圖8 真實數(shù)據(jù)集下用戶數(shù)量對算法性能的影響

5 結(jié)束語

本文針對多用戶場景下的Skyline查詢問題，進(jìn)行深入分析和研究，提出了一種基于權(quán)重的交互式多用戶Skyline查詢算法MUSW。算法定義了一種滿意度度量方法，由用戶權(quán)重決定每個數(shù)據(jù)點的滿意度大小。算法實施過程中，通過用戶與結(jié)果以及用戶之間的交互不斷動態(tài)調(diào)整用戶權(quán)重，當(dāng)系統(tǒng)根據(jù)用戶的反饋判斷查詢終止時，算法將返回滿意度最大的K個點，從而使返回結(jié)果更符合用戶的真實需求。實驗證明MUSW算法可有效解決多用戶Skyline查詢問題，且具有良好的交互性能。