一種基于群組的反向k排名查詢算法

周楊淏，秦小麟，謝小軍，郭成蓋

(南京航空航天大學 計算機技術與科學學院，南京 211106)

1 引 言

隨著數據庫技術在商業、軍事等領域的廣泛應用，排名感知類的查詢處理被越來越多的研究者所關注[1]，其主要原因在于這類查詢可以根據實際的需要，從規模龐大的數據庫中檢索出少數“最優”的數據點.最初的排名感知查詢以Top-k查詢[2，3]為代表，基于給定的用戶偏好函數計算得分最小的k個元組.該類查詢模型僅是從用戶的角度來查找與其偏好函數所匹配的產品.然而在許多場景下，產品生產商或者銷售商也希望知道某些產品對哪些潛在用戶有吸引力.這種從產品生產商的角度來分析用戶的查詢模型其應用范圍不僅僅局限于電子商務中的產品(用戶)推薦，還可以被拓展到更為寬泛的領域，比如商業評估、企業招聘等.

反向排名查詢是從產品的角度出發，基于給定的產品檢索滿足需求的用戶[4].其中，反向Top-k查詢[4]和反向k排名查詢就是反向排名查詢中最為典型的兩種查詢模型.設查詢點為q，用戶偏好集合為W，反向Top-k查詢返回了一個偏好集合W′，對于W′中的任意用戶偏好，q都屬于其Top-k查詢的結果集.因此，反向Top-k查詢主要用于評估產品對用戶潛在的吸引力，以及產品能夠吸引哪些用戶或者在不同的偏好下是否擁有很好的排名.但是，該類查詢無法控制結果集的數目，因為對于某些很受歡迎的產品，其反向Top-k查詢會匹配到大量的用戶偏好，然而對于某些不受歡迎的商品，其查詢結果集中可能沒有任何的用戶偏好.Zhang等人提出的反向k排名查詢[5]很好的解決了這一問題.與反向Top-k查詢不同，反向k排名查詢為查詢點返回了大小為k的用戶偏好集，且在這k個用戶偏好下該商品的排名比在其他用戶偏好下的排名都要小.這就為每一個需要查詢的產品檢索到了對它而言最優的k個用戶.

當查詢點數目不再局限于單個而是擴展為集合時，可以迭代計算每一個查詢點的反向k排名，但這樣不僅耗費了大量的查詢時間，還會導致結果集非常龐大，為此Dong等人提出了聚集反向排名查詢[6]，將查詢點集合作為一個整體，一次計算某用戶偏好下該集合的排名之和，作為最終偏好遴選的依據.但是，該方法對于基數比較大的查詢點集合仍然存在以下問題：

1)結果集失真.由于產品在某用戶偏好下的得分排名是根據產品各個維度的屬性計算而來，所以不同的產品在不同的用戶偏好下會有不同的排名，換言之，隨著查詢點集基數的增加，不同的產品可能會有不同的反向k排名結果集，當查詢點集合的集群相似度很低時，其反向k排名的查詢結果之間會有很小的相似性，現有的整體求解的方法得到的結果集與單個查詢點得到的結果集差距很大，導致結果集質量很差；

2)算法性能退化.由于算法在執行時對查詢點集合中所有點的外包矩形框和產品集中的點(或R樹節點)進行過濾判定，所以當查詢點分布較為分散時其外包矩形框會很大，算法無法根據矩形框的邊界點有效的進行批量過濾，只能將矩形框中的點一一與產品集中的點或R樹節點進行比較，這導致了算法性能的急劇退化.在最壞情況下，算法退化為一一配對的蠻力搜索.

圖1 反向k排名查詢實例Fig.1 An example of reverse k ranks query

圖1給出了一個包含五個產品和三個用戶的查詢實例.(a)中給出了5個商品在兩個維度上的屬性值和其反向Top-2的查詢結果，可以看到P1和P5不屬于任何用戶偏好的Top-2結果；(b)給出了3個用戶的不同偏好及在每個用戶偏好下的Top-2查詢結果；(c)中給出了五個產品在不同用戶偏好下的排名及每個產品的反向1排名的查詢結果.若查詢點集合為{P3，P4，P5}，采用現有的聚集反向排名計算方法得到的反向1-rank的結果為Jack，計算過程如圖(d)所示，可以發現對P3而言，Jack是其排名最差的點，顯然不是一個合理的結果.這說明現有的查詢策略是不公平的，在某些情況下會導致結果集的準確性較差.

基于此，本文給出了一種新型的基于群組的反向k排名查詢方法.本文貢獻點如下：

1)針對反向k排名查詢中多查詢點存在的問題提出了一種基于群組劃分的查詢方法，該方法通過動態閾值調整，有效的提高了結果集質量，并解決了算法性能退化的問題；

2)在現有的支配圖結構的基礎上，提出了一種基于層次網格的索引結構LG-Index，該結構將層次索引方法和概要索引方法相結合；并基于此索引結構采用層次漸進式的求解策略，可以更加高效的解決上述問題；

3)在人造數據和真實數據集上進行了實驗，實驗結果表明，本文提出的查詢方法能夠有效解決多查詢點的反向k排名查詢問題，并且基于層次網格索引的查詢策略更為高效.

本文結構如下：第2節介紹反向k排名查詢的基礎知識和相關工作，并分析現有反向k排名查詢方法在解決多查詢點問題時的不足；第3節提出基于群組的反向k排名查詢算法，并利用層次網格索引結構對算法進行了優化；第4節對提出的查詢算法進行了實驗評估，并與現有算法進行性能對比；最后在第5節對本文工作進行了總結.

2 背景知識

2.1 相關工作

排名是對象評估過程中一個非常重要的指標.近年來，支持排名感知的查詢在數據庫領域得到了廣泛的關注.其中最基本的基于偏好的查詢為Top-k查詢和Skyline查詢[7，8].

Top-k查詢是根據給定的一個用戶偏好和得分函數計算返回得分最小的k個對象.這一問題的求解算法大致可以分為三類：1)Sort-list方法2)層次式方法3)基于視圖的方法.Sort-list方法[2]中最著名的算法為TA算法，算法為每一個需要計算的維度獨立排序然后順序的訪問每一個已經排好序的列表元組，逐步找到所有大于給定閾值的元組.基于層次的方法[9，10]考慮了全部元組的每一個屬性值然后構建了一個全局索引，將數據集中的元組按給定的層次規則分層.基于視圖的方法[11]是預先根據某些得分函數對對象集進行計算排序，構成“預排序視圖”，在查詢時用查詢函數在預排序視圖中查找結果，兩個函數越接近查詢速度越快.

Skyline查詢屬于多目標優化的范疇，它根據原始數據集間固有的支配關系得到所有的非劣點，不受用戶偏好的影響.對于Skyline的計算方法主要包括塊嵌套環算法(BNL)、排序過濾算法(SFS)、分治算法(D&C)、位圖算法(Bitmap)、索引算法(Index)、最近鄰算法(NN)、分支界限算法(BBS)等[7].

Vlachou等人[4]在Top-k查詢和Skyline查詢的基礎上提出了反向Top-k查詢，主要用于分析市場中潛在的商品是哪些用戶偏好的反向Top-k結果，其求解方法主要包括基于閾值的方法(RTA)，基于網格的方法(GRTA)和分支界限方法(BBR).

由于反向Top-k查詢的結果集分布的不均勻性和結果集數量的不確定性，在實際分析時需要根據返回的結果集數量進一步調整k值進行迭代.Zhang等人提出了反向k排名查詢[5](Rkr)來解決反向Top-k查詢的局限性.Rkr查詢與反向Top-k查詢的不同點在于Rkr查詢為每一個潛在的商品返回了k個用戶偏好，使得在這k個用戶偏好下該商品擁有最佳的排名.文中提出了解決該問題的三個算法：TPA，BPA，MPA，這三個算法都是基于R樹索引的方法.Dong等人為解決上述R樹索引方法在多維空間下效率退化的問題，提出了基于二維網格視圖的GIRk-Rank算法[12]，該算法通過將“預計算”的結果緩存到視圖中，節省了CPU的計算開銷.

文獻[6]中提出了針對多個產品的反向k排名查詢，該查詢將查詢點的規模從單個擴展到集合，并將所有查詢點視作一個對象進行排名的計算，避免了對每個查詢點進行一一計算，有較高的查詢效率.該算法仍然采用了基于樹結構索引的過濾策略.

Kyriakos等人提出了最大排名查詢[13]，該查詢計算了給定的數據點在任意可能的偏好下該點所能達到的最大排名，并且得到了對于查詢向量而言其不同排名所能覆蓋的區域，為市場分析和數據可視化提供了一個有效的手段.

最近，Li等人提出了反向空間偏好top-k 查詢[14]，從空間對象角度出發并考慮了主體對象與周圍設施的位置關系，將對象的屬性值與其所處的空間位置所關聯.

雖然上述工作中已有基于查詢點集合的反向k排名查詢，但現有的查詢方法并未考慮查詢點集合上不同查詢點分布情況對結果集質量的影響.當查詢點分布相對分散時，結果集會明顯失真.為此，我們研究了兼顧查詢效率和結果集準確性的查詢算法.

2.2 反向k排名查詢相關定義

本節介紹反向k排名查詢的相關知識.文中所用到的符號及含義如表1所示.

表1 符號定義解釋表Table 1 Interpretation of defined symbol

定義1.(rank(w，q)[5]) 給定數據點集合P，用戶偏好w，查詢點q，rank(w，q)=S，S?P且?pi∈S，f(w，pi)

在反向k排名查詢類問題中，我們關心的實際是查詢點在每個用戶偏好下的排名，而非其具體的得分.在已知排名的基礎上，從中選取k個排名最為靠前的用戶偏好.

定義2. (反向k-ranks查詢Rkr[5]) 給定數據點集合P，用戶偏好集合W，正整數k，查詢點q，反向k排名查詢返回一個集合S，S?W，S=k，且滿足?wi∈S，?wj∈W-S，rank(wi，q)≤rank(wj，q).

由上述定義可知，反向k排名查詢將結果集基數嚴格限定為k，即為查詢點求解了k個用戶偏好，使得在這些用戶偏好下該查詢點的排名比剩余用戶偏好下的排名要好.

3 基于層次網格索引的方法GP-Rkr

針對反向k排名查詢中多查詢點的問題，在本節中給出了基于群組的查詢方法.該方法包含群組劃分和查詢過濾兩個階段.需要說明的是，當查詢點為集合時，其排名為集合內各個查詢點的排名之和.3.1節給出了群組劃分的算法，采用聚類方法對查詢點集合Q中的數據點進行分組聚類，通過動態的閾值調整，將查詢點分割成多個互不相交的子集，各子集之間相互獨立；3.2節給出了查詢過濾階段的算法框架，對各個獨立的子集進行組的反向k排名查詢，為每個查詢點子集求解最優的k個用戶偏好；3.3節針對過濾階段的算法框架提出了一種新的索引結構，并基于該結構給出查詢算法，以提高查詢效率.

3.1 群組劃分

由于查詢點集合Q的基數不會很大，且群組劃分的數目受數據分布情況的影響難以預先確定，所以在分析現有的聚類模型的基礎上，本文采用凝聚式層次聚類方法[15，16]，自底向上的對原子簇進行合并，直到終止條件滿足.為了適應多種數據分布，需要預先給定最大分組數目mmax，以限制群組劃分的數量.為保證分組質量的同時加快算法的收斂，我們采用動態設置類別間距離閾值的方法來控制算法迭代次數.閾值采用“二進制步長法”動態增長，直到得到的分組數目小于預先設定的最大分組數目.其中，距離度量采用歐式距離，簇的臨近準則采用組平均準則.算法結束時，可以將查詢集合Q分成m個子集(m≤mmax)，算法如下：

算法1.群組劃分方法Group Partition

輸入：查詢點集合Q，最大分組數目mmax

輸出：劃分后的m個查詢子集Qi，1 ≤i≤mmax

1.i←0;m←|Q|;

2.Whilem>mmaxdo/*控制終止條件*/

3.t←2i·t0;/*二進制步長法動態閾值調整*/

4.m←|Q|;

5.Whilem>1 do

6. Find two cluster with minimal distancedistancemin

/*查找距離最小的兩個簇*/

7.Ifdistancemin>tbreak;

/*距離大于閾值則結束迭代過程*/

8. Merge two cluster;

/*對兩個簇進行合并操作*/

9.m←m-1;

10.Endwhile

11.i++;

12.Endwhile

13.Returnmclusters

算法1第1行設置初始原子簇數目為查詢點數目，2-12行對不同的類別間閾值迭代計算其分組數目，其中第3行為閾值擴張，5-10行為簇合并操作.由上述算法可知，該算法迭代次數受數據點分布的影響，但至多迭代log2mmax次.

3.2 查詢過濾

通過群組劃分，已經將查詢點集合分成了互不相交的子集，這樣一來，大大減少了最終結果集的數目；同時每一個群組均是根據空間相似性劃分，具有相似的得分和排名，可以提高結果集的準確性.在查詢過濾階段，要做的任務是對每一個子集Qi求解排名最小的k個用戶偏好，由于第一階段工作提高了查詢點子集邊界矩形框的有效覆蓋率，所以進行組過濾效率更高.這一問題最基本的求解方法為計算所有對偶點的NA算法和基于R樹過濾的方法.本文給出如下算法框架：

算法2.查詢過濾方法

輸入：產品集P，用戶偏好集W，查詢點子集Qi

輸出：Qi的Rkr結果集

1.ForeachwiinWdo/*遍歷權重集中的每一個權重向量*/

2.A[wi]← 0;

3.ForeachpinPdo

/*對產品集中的點進行遍歷*/

4.If(f(wi，p)

/*得分小于Qi中的最小值，則該點排名小于Qi所有點排名*/

5. A[wi]←A[wi] + |Qi|;

6.IfA[wi]≥maxrankthenreturn-1

7.Elseif(f(wi，Qi.up)

/*得分大于Qi中的最大值，則過濾*/

8.ElseCalculaterank(wi，q) for eachqinQand UpdateA[wi]/*依次計算當前查詢點子集中每個查詢點在當前用戶偏好下的排名*/

9.Endif

10.Endfor

11.Endfor

12.Returnksmallest entries inA

算法2依次求解了查詢點子集在不同用戶偏好下的排名，第4-8行對遍歷的產品點和查詢點子集進行得分判斷，若產品點得分小于查詢點子集中最小得分，則該產品點的排名位于查詢點子集中所有點之前，所以排名增加子集基數；反之，當查詢點子集最大得分小于產品點得分時，該產品點排名位列所有查詢點之后，可以直接過濾；當無法通過最大點最小點進行快速判斷時，就需要對查詢點子集中的點依次進行判斷，見算法第8行.算法結束時，排名最小的k個用戶偏好即為所求.

3.3 基于層次網格索引的方法GP-Rkr

在上述的查詢過濾階段，可以采用R樹來索引數據點并且通過MBR(邊界矩形框)來進行過濾，然而，當數據集的維度很大時，R樹的性能會急劇退化，甚至還不如線性掃描[17，18].這主要是由于在高維度的情況下，R樹方法無法對數據點進行很好的分割，造成大多數的MBR之間相互重疊，且由于每一次查詢過程都是從樹根進行自頂向下進行過濾，所以效率較低.針對上述問題，我們提出了層次網格索引結構.

3.3.1 支配圖與網格索引

定義3. (支配圖)給定一個多維數據集S，S包含n個非空的最大層Li，i=1…n，第i層中的數據點R和第i+1層中的數據點R′形成二分圖gi，i=1…n-1.在gi中存在從R到R′的有向邊當且僅當R支配R′.所有的二分圖gi構成了支配圖，第i層Li叫做支配圖的第i層.

由于數據點集合P中的每一個對象p的各個維度的屬性值具有不同的實際意義，比如p[1]表示價格，p[2]表示產品供應商的距離，顯然，對象p在這兩個屬性上的取值范圍不同，但是為了數據處理和計算的方便，同時消除量綱的影響，首先對原始數據的各個維度進行歸一化操作，本文中采用min-max標準歸一化方法，通過離差標準化，對數據集P中的每個對象的各個維度進行線性變換，將其映射到區間[0，1].顯然，線性變換后每一個對象的得分排名都不會發生變化.這樣，對于d維數據集中的每一個對象，都會映射為d維空間中的一個點.由于許多數據點在d維空間中彼此相鄰，所以為了提高過濾效率，采用網格索引結構對數據點進行劃分，即將每一個維度劃分為許多等寬的區間，這樣每一個數據點都屬于一個d維的網格單元，以2維數據點為例，設每個對象p可以表示為，網格在兩個維度上的寬度分別為δ1、δ2，則網格單元Celli，j包含了滿足i·δ1

3.3.2 層次網格索引LG-Index

基于上述的支配圖結構和網格索引結構，我們提出了一種新的索引結構——層次網格索引LG-Index，結構如圖2所示.

該索引由兩部分組成：描述數據點層次支配關系的支配圖DG和描述網格——數據點映射關系的網格索引表GridLink.其中DG描述了不同層次數據點之間的支配關系，同一層上屬于同一網格的數據點存放在一起，分屬不同網格的數據點按照近鄰優先的原則依次存放.為了進一步提高Cache利用率，在本文中采用了“冷數據”和“熱數據”分離的策略，只將頻繁訪問的“熱數據”作為DG中的基本單元，而將“冷數據”作為“熱數據”的指針指向單元.對于同一層上屬于同一網格的數據點，只選取其中的一個數據點作為該網格的代表元，然后設置一個指針指向與該數據點屬于同一網格的其他數據點.

圖2 支配圖結構Fig.2 Structure of dominant graph

DG中的每一節點結構為，其中pid是數據點唯一標識，cid指示所屬網格號，clink是孩子集指針，指向由該節點的所有孩子節點構成的集合，blink是兄弟節點集指針，指向與該節點所屬同一網格單元且同一skyline層的節點所構成的集合，slink指向同層的后繼節點.

網格索引表GridLink描述了網格和數據點之間的連接關系.GridLink結構如圖3所示.

圖3 GridLink結構Fig.3 Structure of GridLink

GridLink是一張存儲了每個非空網格的索引表，表中的每個條目由一個三元組構成.其中cid是網格單元唯一標識，Info包含了該網格的左下角信息cell.L、右上角信息cell.U和網格所包含的數據點數目count.DGLink指針指向一張記錄網格與數據點鏈接信息的表，在該表中維護了cell與DG的連接信息，記錄了cell中數據點的DG層次信息，如果此網格在Layer-i層中存在數據點，則將產生一個對象Layer-i，在該對象中存儲了在DG的Layer-i中此網格第一個數據點的id，指向DG中該數據點的指針，以及該層數據點的總數cnt.這樣，可以很方便的找到該網格在Layer-i中其他的數據點.

將DG和GridLink整合后得到的層次化網格索引LG-Index，其總體結構如圖4所示：每一個cell可以通過link指針迅速定位到網格數據點，對DG中的數據點而言，也可以根據cid迅速找到對應的網格，基于此，我們就建立了完整的索引結構.

圖4 LG-Index結構Fig.4 Structure of LG-Index

LG-Index構建算法分為3步，首先是將數據點根據網格進行劃分，剔除空網格；其次是在原始數據點上構建DG索引，存儲各數據點之間的支配關系；最后是建立網格單元和支配圖之間的鏈接關系，回填網格單元和支配圖相應的屬性域.由于上述索引結構只依賴于數據庫中的產品集，所以可以根據產品數據集離線的構建LG-Index，然后將其存儲在磁盤上，得到查詢請求后再將索引讀入內存.

算法3.LG-Index構建算法

輸入：數據集P

輸出：LG-Index

/*先構建網格索引，并計算每個網格單元中的數據點數目*/

1.Foreachpin P do

2. Calculate whichCellpbelongs to

3.Cell.count←Cell.count+ 1;

4.Endfor

5. Construct DG forpin P /*構建支配圖*/

6.Foreach Cell which is not empty

7. Find the firstpin each layer，logp′ id and count the amount of each cell and layer

/*建立支配圖和網格索引之間的關聯關系*/

8.Endfor

9.ReturnLG

3.3.3 基于層次網格索引的反向k排名求解算法

上述層次網格索引構建完成后，在查詢過濾階段不需要對每個產品數據進行迭代，而是利用索引結構中的支配關系和概要信息提高查詢效率.

定義4. (函數支配)對于給定的數據點p、q，若有f(p，w)

性質1. 函數支配具有傳遞性，且若有pq，則?w∈W，pwq.

性質2. ?p∈P，若qp，則p及p所支配的點都可以過濾.

性質3. 若qwp，則對于用戶偏好w，p及p所支配的點都可以過濾.

定理1. 對于偏好函數w，若rank(w，p)=k且?p′p(或則rank(w，p′)≤k-1

證明：

2)當p′p時，對于?i，1≤i≤d，p′[i]≤p[i]，且?i，1≤i≤d，p′[i]

定理2.對于一個查詢點子集Qi和給定的用戶偏好w，滿足：α≤rank(w，Qi)≤β.其中，α=rank(w，Qi.min)·|Qi|，β=rank(w，Qi.max)·|Qi|

證明：對于?q∈Qi，q≠Qi.min，因為Qi.min為Qi邊界矩形框最左下角點，所以Qi.minq，rank(w，Qi.min)≤rank(w，q)，所以rank(w，Qi.min)·|Qi|≤∑q∈Qirank(w，q)，即rank(w，Qi.min)·|Qi|≤rank(w，Qi).同理，可以證得，rank(w，Qi.max)·|Qi|≥rank(w，Qi)

基于上述性質和定理，我們可以采用如下的過濾策略：初始時設定一個排名閾值，為所有產品點的數目與查詢點數目之積，然后對每一用戶偏好進行檢查，若查詢點子集的最小排名大于閾值，則不必繼續計算，直接進行剪枝，進行下一個用戶偏好的檢查.同時維護一個大小為k的大根堆，該堆存儲了k個最小的排名，每次對閾值更新時將閾值設定為堆的最大值.按照此過程進行迭代，閾值會逐漸收斂.給出算法如下：

算法4.GP-Rkr算法

輸入：產品集P，用戶偏好集W，LG索引，查詢點集合Q，最大分組數目mmax

輸出：群組劃分數目m，每一群組Qi的反向k排名查詢結果集Si/*先進行群組劃分，再進行計算*/

1. Group Partition(Q，mmax);

2.ForeachQido

3.Si←{ };threshold←|P|·|Qi|;/*查詢初始化*/

4.ForeachwinWdo

5.rank←CalculateRank(w，Qi，P，LGIndex，threshold);

6.If|Si|

/*若檢查過的用戶偏好數目不足k，則直接加入*/

7.Elseifrank> 0then

8.IfSi.maxrank>rankthen

/*淘汰排名最大的偏好，加入新偏好*/

9.Si←Si-Si.max;

10.Si←Si∪w;

11.EndIf

12. threshold ←Si.maxrank;/*閾值更新*/

13.EndIf

14.Endfor

15.Endfor

16.ReturnS

算法4第1行調用了群組劃分方法；第2-15行對劃分后的群組調用CalculateRank方法計算排名，并利用堆的性質維護了前k個排名的用戶偏好信息.

算法5.CalculateRank

輸入：產品集P，用戶偏好w，LG索引，當前的查詢點集合Qi，閾值threshold

輸出：在當前用戶偏好下的排名rank

1.Candidate←{ }; rank ←0;

2.Candidate←Candidate∪LG-Index′ 1st layer ;

/*將第一層中的點加入候選集*/

3.While(Candidate!= NULL) do

/*候選集為空時算法終止*/

4. GetpinCandidate;

5.Candidate←Candidate-{p};

6.cid←p.cid

7.Ifthe grid ofcidhas been visited or invalid then continue;

/*若網格已被訪問處理過或已判定無效則直接過濾*/

8.Ifgrid.upQi.min‖grid.upwQi.minthen

/*采用支配關系和函數支配關系進行過濾*/

9.rank←rank+grid.count·Qi.size;

/*網格中所有點的排名均在查詢點排名之前*/

10.Ifrank>thresholdreturn-1

11.Foreachchildrencofgrid′s item

12.Ifchas at least one parent which has not been adopted

thencontinue;

/*對孩子節點進行判定，若其父節點均滿足要求，則將其加入候選集*/

13.Candidate←Candidate∪c;

14.Endfor

15.ElseifQi.maxgrid.downthenthegridis invalid

/*無效性判定*/

16.Elserefine and calculate withQiandgridpairwise，updaterank

/*無法根據近似值進行判定則進一步提煉*/

17.Endif

18.Endwhile

19.Returnrank

算法5計算了某一用戶偏好下查詢點子集的排名.算法第2行將索引第一層中的點加入候選集.3-18行對候選集中的每一個點進行判斷，因為索引中存儲了數據點所在網格的信息，所以可以據此對該點所處的網格進行整體判斷.當且僅當某一數據點排名位于查詢點之前時(7-10行)，才會對該點的孩子節點進行判定.若某一孩子節點的所有父節點的排名都在查詢點之前時，才會將該點加入候選集(12-14行).算法15行對網格進行了有效性判定.當無法根據“預計算”的概要信息進行快速判斷時，就要進行查詢點和網格點的一一計算(16行).

4 實驗及分析

為了驗證本文提出的基于群組的反向k排名查詢算法和LG索引的有效性，在本節中設計實驗對其進行了測試.實驗中對計算所有對偶點的NA算法、基于R樹過濾的RT算法和基于層次網格索引的GP-Rkr算法進行了比較，并對查詢點集分割的有效性進行了實驗驗證.為避免隨機性，算法查詢性能以10次測試的平均值作為最終指標，不同算法在相同的數據集上進行測試.

實驗的相關算法采用Java語言實現，編譯器為Eclipse.實驗環境為：Window10操作系統，Intel Core i7 3.3GHz處理器，6GB內存，<256KB，64B，8>(緩存容量，緩存塊大小，路數)L2 Cache，<3MB，64k，12>L3 Cache，500G硬盤.

4.1 數據集設置

實驗中共使用了三類數據集，包括產品集(對象集)P，用戶偏好集W和查詢點集Q.

產品集D：實驗采用了人造數據集和真實數據集.其中，人造數據集包括均勻分布、正相關、反相關三種，具體的生成方法在文獻[19]中有相關介紹.真實數據集取自NBA 1949年至2009年的球員得分，該數據集共包含20960條記錄，我們從中提取了五個維度構成一個5維的數據集.

用戶偏好集W：我們人工產生了兩種不同分布的數據集[20]：均勻分布和集群分布.其中，集群分布的數據集通過兩個參數來創建ρ和σ2，首先隨機生成ρ個獨立的用戶偏好，并以他們為聚簇中心生成方差為σ2的用戶權重.

查詢點集Q：因為已經產生的產品集D，所以實驗時從D中隨機選取m個產品點構成查詢點集Q，以模擬真實的查詢情況.

4.2 數據量對算法性能的影響

為分析不同數據量下算法的性能，本實驗采用了相關、獨立、反相關三種人造數據集進行測試，數據量分別為(P：50k，W：2k)、(P：80k，W：10k)、(P：100k，W：30k)、(P：150k，W：50k)、(P：200k，W：100k)，其中數據集維度統一為5維，查詢點分組參數設置為5.實驗采用查詢時的CPU時間作為評價指標衡量算法效率，其中CPU時間為對m個查詢點子集計算反向k排名的執行時間之和.

圖5 數據量對算法性能的影響Fig.5 Performances with scalability of dataset

圖5為不同數據量及數據分布下三個算法的性能測試結果.由圖中可以看出，隨著數據規模的增大，三個算法的執行時間均有所上升，但NA算法要明顯劣于RT算法和GP-Rkr算法，且數據規模越大，GP-Rkr算法優勢越發明顯.這主要是由于基于R樹索引的RT算法可以在查詢時根據邊界矩形框(MBR)自頂向下的過濾掉了大量的產品點，從而減少了對偶點的計算次數；而GP-Rkr算法則通過Skyline計算將數據點根據支配關系進行分層，并對數據點進行網格劃分，使數據點訪問在層次間有序且在訪問時更早的剪枝，從Skyline支配關系和函數支配關系兩個層面對數據點進行高效過濾，從而大大減少了對無效點的訪問次數和計算次數.從數據分布的角度來看，相關分布和獨立分布時GP-Rkr算法和RT算法的效率較高，特別是在相關分布的情況下，而反相關分布時二者效率有明顯的下降，但仍大大優于NA算法.而NA算法對數據集分布不敏感，效率相對穩定.這主要是由于RT算法和GP-Rkr算法是基于支配關系進行過濾，當數據集中的支配較多時，過濾性能更為高效，而反相關分布破壞了這種支配關系，使得查詢時可以根據固有支配關系進行裁剪的數據量明顯下降，導致了GP-Rkr算法和RT算法的性能退化.

4.3 數據維度對算法性能的影響

從5.2節可知GP-Rkr算法和RT算法具有較高的計算效率，特別是在正相關分布和獨立分布的情況下.本節設計實驗驗證不同數據集維度對算法執行效率的影響，產品集D統一設置為200K均勻分布，用戶偏好集統一設置為100K均勻分布，查詢點分組參數設置為5，數據集的維度從2維到10維變化，實驗以執行時間作為評價指標.

圖6給出了測試結果，可以發現隨著數據維度的提高，GP-Rkr算法和RT算法性能發生退化，NA算法基本不受維度的影響.其中，在2維、4維時RT算法的性能略優于GP-Rkr算法，當維度大于4維時RT算法性能開始急劇退化，維度為10時計算所用的時間約為GP-Rkr算法的2倍.產生上述結果的原因主要是隨著維度的增加，R樹方法無法將數據進行準確的分割，導致大多數的MBR相互重疊，因此不得不對MBR中的點依次進行計算，從而導致RT算法的效率急劇退化.GP-Rkr算法在支配圖的基礎上進行了網格劃分，各網格之間不會產生重疊，維度增加僅導致了支配關系的減少，所以對維度變化產生的性能退化沒有RT算法明顯.

4.4 查詢點子集數目對結果集質量的影響

本部分實驗驗證不同的查詢點子集數目對結果集質量的影響.實驗數據規模為P：100KW：30K，包括獨立分布、相關分布和反相關分布.查詢點集合大小為500，子集數目設置為從10到50變化.結果集質量的評價函數為：

(1)

(2)

圖7給出了實驗結果.從圖中可知，隨著子集分割數目的增多，查詢結果越來越準確，但結果集質量的提高也愈發緩慢.當子集分割數等于查詢點數的時候，算法相當于對每一個查詢點進行了一次反向k排名查詢，雖然得到了準確的結果集，但是時間開銷和結果集數量都是巨大的，適當的對查詢點集進行分割能得到效率和結果集質量都可以接受的結果.

4.5 真實數據集下的算法性能

為進一步驗證GP-Rkr算法的有效性，我們在真實數據下進行了實驗.產品集為NBA球員得分數據集，包括20960條記錄，用戶偏好集為人工產生的均勻分布的數據集，數據規模為50000，數據集維度都為5維.查詢點集大小設置為100，k從5到30變化.為了方便與人造數據的結果進行對比，我們對真實數據集進行標準歸一化，在算法執行之前將每一個維度的得分映射到區間[0，1].

圖6 維度對查詢性能影響Fig.6 Performances with dimensions

圖7 查詢點子集數目對結果集質量的影響Fig.7 Effects of quantity of subsetson the quality of the result

圖8 真實數據集下的算法性能Fig.8 Performances with real-life dataset

圖8展示了在均勻分布偏好集下算法的執行效率.在圖中可以看出測試結果與人造數據下的保持一致.隨著k的增大，查詢時間略微有所增加.在該數據分布下GP-Rkr算法和RT算法效率更高.

5 結束語

本文從產品的視角出發，針對反向k排名查詢應用于多查詢點時產生的結果集質量較差和查詢效率退化問題，提出了一種針對群組反向k排名查詢問題的解決方案.首先，基于凝聚式層次聚類方法和動態閾值調整，對查詢點集合進行分割.其次，在支配圖結構的基礎上，提出了一種層次網格索引結構，對數據點進行分層索引；并基于該結構，給出了完整的群組反向k排名查詢求解算法.最后，設計實驗在人造數據和真實數據集上進行了測試.實驗結果顯示，本文提出的方法可以有效解決群組反向k排名查詢問題，并且具有更為優良的查詢性能.