白梅 王京徽 王習特 朱斌 李冠宇

摘? ?要：為解決偏序域上的skyline查詢問題，本文提出一種高效的偏序域上的skyline查詢處理方法，來滿足人們對查詢效率日益增長的需求. 首先，為提高偏序域上skyline的查詢效率，將倒排索引引入skyline查詢，提出一種基于倒排的索引結構. 其次，提出基礎算法 （Basic Partially-ordered Skyline Processing based on inverted index，PSP_B），PSP_B包含兩個階段：第一階段，能夠通過映射將偏序域轉化成全序域，并建立倒排索引;第二階段，通過倒排索引提前找到掃描結束點，得到最終的skyline結果. 再次，在PSP_B的基礎上，進一步提出優(yōu)化算法 （Improved Partially-ordered Skyline Processing based on inverted index，PSP_I）. PSP_I通過先分組再建索引的方法能夠進一步提高計算效率. 最后，用大量的實驗證明本文所提算法的正確性和高效性.

關鍵詞：skyline查詢;倒排索引;偏序域;查詢優(yōu)化;算法

中圖分類號：TP391 ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻標志碼：A? ? ? ? ? 文章編號：1674—2974（2020）08—0009—12

Abstract：In order to solve the skyline query problem in partial order domain， this paper proposes an efficient query processing method for the skyline query in the partial order domain to meet people's increasing demand for query efficiency. Firstly， in order to improve the query efficiency of skyline on partially ordered domains， this paper introduces the inverted index into the skyline query and proposes an index structure based on the inverted index. Secondly， the basic algorithm PSP_B （Basic Partially-ordered Skyline Processing based on inverted index， PSP_B） is proposed. The PSP_B consists of two phases： in the first step， each partially ordered domain is converted into two fully ordered domains through mapping function， and then each fully ordered dimension is managed through the inverted index; in the second step， the scan end point is found through scanning the inverted index and the result set is obtained. Thirdly， based on the PSP_B， this paper further proposes an optimization algorithm PSP_I （Improved Partially-ordered Skyline Processing based on inverted index， PSP_I）. The PSP_I can further improve the computational efficiency by grouping the data in advance and then indexing them. Finally， a large number of experiments prove the correctness and efficiency of the proposed algorithm.

Key words：skyline query;inverted index;partial order domain;query optimization;algorithm

近年來，隨著互聯(lián)網(wǎng)技術的發(fā)展以及信息獲取設備的進步，數(shù)據(jù)庫收集處理的數(shù)據(jù)量增多，進一步，數(shù)據(jù)庫中存儲的數(shù)據(jù)量也急劇增加. 但是，人們卻很難從這些海量、龐雜的信息中挖掘出自己最想要的有價值的信息. 因此，如何快速高效地從海量數(shù)據(jù)中返回給用戶最為關心的數(shù)據(jù)，成為學術界的研究熱點.

skyline查詢根據(jù)用戶在各個維度的偏好，利用“支配”的概念，將數(shù)值間的大小比例作為“好壞”的評價標準，直觀而準確地返回給用戶最為關心的結果集. 具體地，給定兩個點p1和p2，p1支配p2指的是在所有維度上p1都不比p2差，并且至少在一個維度上p1要嚴格好于p2. 如圖1所示，共有20條圖書信息記錄{p1，p2，…，p20}，每一條圖書信息包括了兩個維度信息：圖書價格和評分，評分維度利用倒數(shù)映射到[0，1]區(qū)間內(nèi)，使兩個維度均以小值為“優(yōu)”. 例如圖1中p8在每一維都比p15小，說明p8價格和評分都比p15要好，即p8支配p15. 經(jīng)過skyline查詢后，圖中最終skyline集合為{p8，p12，p16，p17}，其他圖書記錄都可以被這個集合中的點支配.

偏序域上的skyline第一次被考慮到是在2005年，Chan等[1]討論了具有偏序域屬性的數(shù)據(jù)集上的skyline查詢，他們將一個偏序域映射到兩個全序域上，來適應自己提出的skyline算法，并針對這種映射提出了SDC+和BBS+算法. 但這種方法映射時成本太高，且不具有可擴展性. Sacharidis等[2]在2009年提出了一種基于拓撲排序的skyline查詢方法可以用來處理動態(tài)skyline查詢. Liu等[3]提出了ZINC（Z-order Indexing with Nested Codes）算法，通過降維等方法來處理偏序維度，但當偏好關系復雜時，偏序維度降維成本將會很高. 文獻[4]提出了一種PSLP（Parallel Skylines with Logical Partitioning）框架，通過過濾不含skyline點的邏輯分區(qū)提高計算效率，但分區(qū)成本較高且過濾效率提高效果不明顯.

綜上所述，為了避免查詢成本過高，本文將在映射的基礎上引入倒排索引，提前對數(shù)據(jù)集進行過濾剪枝，通過減少對整個數(shù)據(jù)集的掃描來達到提高計算效率的目的.

偏序域上的skyline查詢處理，在現(xiàn)實生活中是一個非常有意義的議題. 例如，在為用戶進行圖書推薦時，用戶往往希望得到評分高且價格低的圖書推薦，并且不同用戶對不同種類圖書的偏好不同，如圖2所示，需要將全序域與偏序域結合起來進行skyline查詢，高效地針對不同用戶進行個性化推薦. 因此，在偏序域上進行高效skyline查詢具有極大的實際應用價值.

為了更有效地減少開銷，提高輪廓查詢效率，本文將倒排索引應用到查詢中，首先提出了一種高效的偏序域上skyline查詢處理方法（Basic? Partially-ordered Skyline Processing based on inverted index，PSP_B）. 之后，在此算法的基礎上，通過提前對數(shù)據(jù)點進行分組，提出了改進的優(yōu)化算法 （Improved Partially-ordered Skyline Processing based on inverted index，PSP_I），利用優(yōu)化算法在極大程度上對冗余點進行過濾. 實驗證明，該算法能更高效地處理偏序域上的輪廓查詢.

總的來說，本文的主要貢獻如下：

1）提出將倒排索引引入skyline查詢領域，倒排索引將每個偏好維度上的屬性按從優(yōu)至劣進行排序，減少大量的冗余計算，從而提高計算效率.

2）提出了PSP_B算法，解決了傳統(tǒng)算法中每次計算都對整個數(shù)據(jù)集進行掃描的問題. 算法對數(shù)據(jù)集在每個維度上建立倒排索引，通過循環(huán)掃描策略快速找到掃描結束點來結束算法，達到了對數(shù)據(jù)集過濾剪枝的目的，提高了計算效率.

3）在PSP_B算法的基礎上，提出了PSP_I算法，在將偏序域映射到全序域之后，建立倒排索引之前，對整個數(shù)據(jù)集按文中提出的分組策略進行分組，在組內(nèi)建立倒排索引. 并提出整組過濾策略，對不含skyline結果點的分組進行整組過濾，在基礎算法的基礎上進一步提高了剪枝效率.

4）設計了詳細的性能比較實驗，通過實驗證明了本文提出的PSP_B和PSP_I算法可以有效地處理偏序域上的skyline查詢問題，并且PSP_I算法在查詢效率上要更優(yōu)于PSP_B算法.

1? ?相關工作

1.1? ?傳統(tǒng)skyline查詢

早期，人們主要關注于全序域上的skyline查詢. Borzsonyi等[5]第一次將skyline查詢的概念引入數(shù)據(jù)庫領域，并提出了BNL（Block Nested Loops）和D&C（Divide and Conquer）算法，BNL算法對待測元組建立臨時表，通過將每個待測元組與表內(nèi)元組比較來進行輪廓查詢，因此BNL算法性能受主內(nèi)存大小的限制;D&C算法是將數(shù)據(jù)集劃分為多個分區(qū)，在每個分區(qū)內(nèi)進行查詢，計算出局部的skyline點，再將得到的結果進行合并，然后對合并的結果再進行查詢來得到最終結果. 這兩種算法都會產(chǎn)生多次迭代，查詢效率較低.

之后，Chomicki 等[6]提出了SFS算法，該算法是在BNL的基礎上對數(shù)據(jù)按單調(diào)函數(shù)進行預排序，然后再進行skyline查詢，減少了開銷. Tan等[7]提出的Bitmap算法先將每個元組映射成一個m位矢量，然后通過矢量間的計算得到最后的skyline集合. 之后，NN（Neural Network）算法[8]利用R樹索引數(shù)據(jù)集，并利用K近鄰算法來進行skyline查詢，通過不斷循環(huán)刪除skyline點支配的區(qū)域來找到結果，因此在對高維數(shù)據(jù)進行查詢時會有大量的重復查詢，導致效率低.

2005年Chan等提出BBS算法[1]，基于最近鄰搜索策略，用R-Tree對待測數(shù)據(jù)集建立索引，將所有待測元組劃在一個個最小邊界矩形上. 通過對最小邊界矩形左下角元組的比較來過濾冗余元組，又進一步節(jié)省了開銷.

此外，還有許多針對特定數(shù)據(jù)環(huán)境下的skyline查詢算法，如P2P網(wǎng)絡[9]、分布式環(huán)境[10]和不確定數(shù)據(jù)環(huán)境[11]等.

1.2? ?偏序域上的skyline查詢

在實際應用中，有許多維度是無法直接通過數(shù)值間的大小比例來判斷好壞的，因此，偏序域上的skyline查詢在現(xiàn)實生活中是一個非常有意義的議題. Chan等在2005年第一次討論了具有偏序域屬性的數(shù)據(jù)集上的輪廓查詢[1]，由于引入偏序域后，傳統(tǒng)的輪廓查詢算法將不能再有效地修剪空間，因此，他們提出將每個偏序域映射到兩個全序域上來解決這一問題，并且提出了BBS+、SDC和SDC+三種算法. BBS+是進行投影空間轉換后直接適應BBS;SDC和SDC+都利用支配關系將數(shù)據(jù)進行分層，雖然減少了不必要的比較，但分層時的開銷卻很大.

2009年，Sacharidis等[2]提出了一種基于拓撲排序的skyline查詢方法TSS（Topologically Sorted Skylines for Partially Ordered Domains），利用拓撲排序將偏序域映射成全序域上的間隔，并且，TSS算法可以用來處理動態(tài)skyline查詢. 2010年，Liu等[3]提出了ZINC算法，通過降維來簡化用戶偏好情況，并使用嵌套碼將其轉化為部分階映射到總階數(shù). 最后用ZB樹來索引編碼值，然而，當用戶偏好復雜時，偏序降維成本將會很高.

Hsueh等在2017年提出e-DFS（extended Depth-First Search）算法[12]，通過緩存之前的查詢結果，將這些結果作為索引，對相似查詢直接在緩存區(qū)中進行查詢，該算法在相似性比較上開銷大，且針對性不強，在緩存區(qū)沒有相似查詢時仍要訪問整個數(shù)據(jù)集.

綜上所述，雖然在全序域上的skyline查詢已經(jīng)取得了豐碩的成果，但在處理偏序域上的數(shù)據(jù)時仍缺少一種有效率的方法. 因此，本文將針對偏序域上的數(shù)據(jù)集，將偏序與全序結合起來，引入倒排索引的概念，在進行skyline計算之前對數(shù)據(jù)集進行過濾剪枝，將明顯提高計算效率，有較高的實用價值.

2? ?問題描述

本文關注的是偏序域上的skyline查詢問題，以小值為優(yōu)舉例，遇到大值為優(yōu)的維度需要經(jīng)過預處理變成倒數(shù)后再進行計算. 為了描述方便，表1給出了本文的符號定義.

傳統(tǒng)的支配關系和skyline的相關概念分別如定義1和定義2所示.

定義1? ?（支配[5]）給定d維數(shù)據(jù)集P，其中兩個元組p1和p2，p1支配p2（記作p1 < p2）滿足下列條件：（i，j指不同的屬性維度）

偏序域由多個二元關系組成，表明對于集合中的某些元素對，其中一個元素要優(yōu)于另一個元素.? 偏序一詞用于表示不是每對元素都需要具有可比性. 引入偏序域后，原有的支配定義將不再適應現(xiàn)有的數(shù)據(jù)集，因此給出新的支配關系.

定義3? ?（偏序-支配[1]）給定d維數(shù)據(jù)集P，對兩個元組p1和p2，p1支配p2（記作p1 < p2）滿足下列條件：（其中i∈TO，j∈PO，m∈d）

利用圖2（a）的數(shù)據(jù)集舉例說明，圖1是對該數(shù)據(jù)集僅考慮價格和評分兩個全序域，直接在全序域上求skyline的結果，最終計算得到的skyline集合為{ p8，p12，p16，p17}，但在圖2（b）中，加入了偏序域上不同用戶對不同種類圖書的偏好，對3個不同用戶分別求得的skyline集合分別為{p4，p6，p8，p9，p11，p12，p14，p15，p16，p17}、{p5，p8，p9，p11，p12，p16，p17}、{p8，p12，p16，p17}.

3? ?基于倒排索引的高效處理方法

本章首先介紹了文中的數(shù)據(jù)索引（倒排索引）;然后，介紹了利用倒排索引的過濾方法;最后，介紹了基于倒排索引的基礎算法PSP_B. 算法利用倒排索引對數(shù)據(jù)提前進行處理，對數(shù)據(jù)集進行過濾剪枝，使得進行skyline查詢時不必掃描整個數(shù)據(jù)集.

3.1? ?倒排索引

對于具有偏序域的數(shù)據(jù)集，在建立倒排索引前，為了方便計算，需要將偏序維度映射到全序維度.

映射規(guī)則[2]：算法采用將偏序域屬性映射到兩個全序域的方式來處理偏序域屬性. 如圖3所示，對于偏好哈斯圖[13]進行深度優(yōu)先遍歷，并用間隔[po-to1，po-to2]進行標記，其中po-to1表示節(jié)點在深度優(yōu)先遍歷時第一次被掃描到的時刻，po-to2表示節(jié)點結束掃描的時刻，即該點的子節(jié)點全部遍歷結束. 偏序域上的偏好關系就可以用間隔間的覆蓋來表示.

如用戶u2所示的偏好圖，在進行映射前事先為偏好圖加一個虛節(jié)點，方便對偏好屬性進行映射;并且對于映射出不止一個間隔的情況，按所有間隔的并集處理，如用戶u3所示，由于屬性D優(yōu)于屬性A，因此將屬性A映射出的間隔并到屬性D的間隔中. 假設屬性M、N的間隔分別為[po1-to1，po1-to2]，[po2-to1，po2-to2]，若屬性M的間隔[po1-to1，po1-to2]，被包含在另一個屬性N的間隔[po2-to1，po2-to2]內(nèi)，即po2-to1 < po1-to1并且po2-to2 > po1-to2那么就說明在該偏序維度上屬性M優(yōu)于屬性N. 若兩個區(qū)間互不包含，則相應屬性的好壞無法比較. 例如圖3中，對于用戶u1來說，屬性C映射到全序域的間隔為[2，5]，屬性B映射到全序域的間隔為[3，3]，屬性C的間隔可以覆蓋屬性B的間隔，即對于用戶u1來說，屬性C要優(yōu)于屬性B.

掃描結束點：為方便描述，本文引入掃描結束點的概念，我們稱第一次掃描到滿足結束條件1的元組就是掃描結束點（參考結束條件1），掃描到掃描結束點時可以結束查詢，將結果集返回給用戶.

為了減少計算數(shù)據(jù)點的數(shù)量，本文采用了倒排索引結構來對數(shù)據(jù)進行管理. 倒排索引可以加快元組間支配關系的判定，快速找到掃描結束點，從而減少計算數(shù)據(jù)量. 具體地，對于所有的偏序維度按映射規(guī)則映射到全序域上，然后，針對每一維的數(shù)據(jù)，都按照從優(yōu)到劣的順序（本文例子中除PO-TO2維度以大值為優(yōu)外，其他維度均以小值為優(yōu)）建立倒排索引如圖4所示.

基礎循環(huán)掃描策略：由于全序域和偏序域上數(shù)據(jù)屬性值的數(shù)量差距較大，導致建立的倒排表不同維度分布不同，屬性值個數(shù)有差距，如圖4所示，因此對倒排索引上每個維度i維護一個timesi變量，用來記錄該維度上掃描過的點的個數(shù)，每次掃描均選擇timesi值最小的維度，并在該維度上選擇索引位置最靠前的元組進行計算，當timesi最小值對應多個維度時可以對這些維度按順序依次掃描.

圖4中，以第一次循環(huán)掃描順序為評分、價格，PO-TO1、PO-TO2為例，結束第一輪掃描后，4個維度的timesi值分別為1、1、3、3，進行第二輪掃描時，根據(jù)基礎循環(huán)掃描策略，應從timesi值最小的維度價格和評分維度按序依次掃描，即選擇價格維度，那么結束這次掃描后4個維度的timesi值變?yōu)?、1、3、3，此時應選取評分維度進行掃描. 這樣一直循環(huán)掃描下去，直到算法結束（參見結束條件1）.

在skyline查詢時，基礎循環(huán)掃描策略對倒排索引進行掃描，并對掃描過的點進行掃描次數(shù)標記. 對每一個元組僅在第一次掃描到的時候進行skyline計算，之后掃描到時僅增加該元組的掃描次數(shù).

3.2? ?冗余點過濾

在本小節(jié)中主要描述了算法過濾冗余點的過程，為描述方便首先給出結束條件1的內(nèi)容，用來描述算法的結束條件，之后再通過引理1證明其正確性.

結束條件1：當掃描到一個元組pi在所有維度上都被掃描過一次時，若pi在偏序維度POm對應多個間隔，判斷pi在POm上掃描到的值是否來自同一間隔，若是，則pi可以作為掃描結束點，此時可以結束算法，將結果集返回給用戶;否則pi不能作為掃描結束點，繼續(xù)循環(huán)掃描.

引理1[1]：若出現(xiàn)一個元組pi至少在每一個維度上都被掃描過一次，即pi.count>=|Dtotal|，根據(jù)基礎循環(huán)掃描策略，此時在任一維度上都沒有被掃描過的元組pj（pj.count=0）一定不會是skyline點.

證明：根據(jù)引理1，當有元組在每一個維度都掃描到一次時可以結束算法，但由于POm-TO1、POm-TO2是由同一個偏序維度m映射出的且存在一個元組對應多個間隔的情況，必須是同一個間隔掃描結束才能保證是該偏序維度掃描過一次.

證畢

圖4中，第一次count值達到4的元組為p8，此時判斷，p8在PO-TO1、PO-TO2上掃描到的值分別為7、3，由于p8偏序域映射出的間隔為[3，3]，[5，7]，3和7并不來自同一間隔，因此不停止算法，繼續(xù)進行循環(huán)掃描. 直到掃描到元組p17.count值為4時，且在PO-TO1、PO-TO2上掃描到的值分別為1、8，來自同一間隔，根據(jù)引理1和結束條件1，此時可以結束算法（如圖4中陰影所示），陰影下方還沒有被掃描過的點至少都可以被p17支配，一定不能成為skyline點，可以直接過濾.

為描述方便，定義Ri為暫時結果集，用來存放di維度上已掃描過的skyline點.

定理1：對維度Di建立對應的結果集Ri，那么對于掃描到在維度Di上的元組pi，若pi不被Ri中的元組支配，那么pi一定是skyline點.

證明：根據(jù)支配定義，一個元組若可以支配元組pi，則在所有維度都不能比pi差，因此，元組pi當前所在維度Dm表現(xiàn)不如元組pi的都不可能支配pi，因此僅考慮Dm對應的結果集Rm中的元組即可.

證畢

在圖4中，當掃描到價格維度上的第二個元組p14時，只需要與R1中的p17進行支配關系比較即可，如圖5所示，不需要與p12，p7比較，節(jié)省了比較成本.

由引理1和定理1可以過濾掉大量的冗余點，只針對最必要的元組進行skyline查詢，極大地提高了查詢效率.

算法1：基礎算法（PSP_B）

輸入：D維空間上的數(shù)據(jù)集P，其中：

|TO|個全序維度TO（d1，d2…）

|PO|個偏序維度PO（d1′，d2′…）;

輸出：數(shù)據(jù)集P的skyline集合R;

1. 初始化每個維度上的結果集Ri=？椎;

2. for each di′∈PO do

3. 根據(jù)映射規(guī)則將di′映射到全序域Pi - TO1和Pi - TO2;

4. end for;

5. |Dtotal| = |TO|+2×|PO|; （映射后的維度總個數(shù)）

6. 對所有維度 di∈（P-TO1∪P-TO2∪TO）建立倒排索引;

7. while （true）

8. 根據(jù)基礎循環(huán)掃描策略得到計算點pi，屬于維度j

9. if（pi.count=0）

10. if（comparesky（pi，Rj）=true）（見算法2）

11. ? ? 將計算點pi加入當前維度的結果集Rj;

12. ? pi .count++;

13. end if

14. else

15. pi .count++;

16. if（pi .count>= |Dtotal|

17. ? ? ? ? ? ? ? ?if（pi在POm上掃描到的值來自同一間隔）

18. ? ? ? ? ?break;

19. ? ? ? ? ? ? ? ?end if;

20. end if;

21. end if;

22. end while;

23. 對所有Rj取并集得到最終結果集R;

24. return R;

算法1第2～6行根據(jù)基礎循環(huán)掃描策略將偏序域映射到全序域，并建立倒排索引來維護數(shù)據(jù). 第8～22行是算法主體，根據(jù)維護的count值來進行skyline計算. 其中，元組僅在第一次被掃描到的時候（即count=0時）進行skyline計算（如算法2所示），當count>0時，只記錄掃描次數(shù)，不再進行skyline計算;當count值與|Dtotal|相等時，根據(jù)引理1與定理1判斷掃描到的偏序屬性是否來自同一間隔，若是，則跳出循環(huán)，執(zhí)行第23行，返回結果集，結束算法，否則繼續(xù)循環(huán)掃描，直到算法結束.

算法2：Skyline計算方法 comparesky（pi，Rj）

輸入：元組pi，pi所在維度對應的結果集Rj

輸出：待測pi是否為最終的skyline

1. for each pm ∈Rj

2. if（pm偏序-支配pi）

3. return false;

4. ? end if

5. end for

6. return true;

如圖4所示，以第一輪維度掃描順序為價格、評分PO-TO1、PO-TO2為例，結束一輪掃描后，4個維度的timesi值分別為1、1、3、3，且其中掃描過的元組{p17，p12，p2，p7}的count值為{3，1，2，2}，本輪中進行了skyline計算的元組為{p17，p12，p2，p7}，計入結果集的元組為{p17，p12，p2，p7}. 然后根據(jù)基礎循環(huán)掃描策略繼續(xù)進行掃描，處理價格、評分維度，掃描元組{p14，p16}，根據(jù)結束條件1，p14與R1中的p7、p17進行skyline計算，p16與相R2中的p12進行skyline計算. 依次循環(huán)計算，當掃描到元組p8的count值等于4時（即與|Dtotal|相等），根據(jù)定理1判斷掃描到PO-TO1、PO-TO2維度上的值不是來自同一個間隔，因此繼續(xù)循環(huán)掃描，直到掃描到元組p17的count值為4，與|Dtotal|相等，此時算法結束，最終得到結果集{p7，p8，p12，p16，p17}.

4? ?優(yōu)化算法

在將倒排索引引入算法的基礎上，本文又采用提前分組的方式對算法進行了進一步優(yōu)化.

4.1? ?分組倒排

分組策略：給定d維空間上的數(shù)據(jù)集P，根據(jù)數(shù)據(jù)集P的偏序維度（若有多個偏序維度則選擇屬性值最少的一個偏序維度）進行分組，將在該維度上擁有相同屬性值的元組分到一組，例如選取圖書種類作為分組維度，將具有相同種類的圖書分到一組，如圖6所示.

對數(shù)據(jù)集P按選定偏序維度進行分組，并將除該維度外的其他偏序維度按映射規(guī)則映射到全序維度，在組內(nèi)建立倒排索引. 之后根據(jù)除分組維度外的所有維度分別建立臨時表T i，用于存放每個分組中取值最小的一個或多個元組（本文以小值為優(yōu)）.

臨時表的更新：進行計算時，在每個維度i上從對應的臨時表T i中取出最優(yōu)值，與所在維度結果集Ri中的元組進行比較，若不被結果集中的點支配則加入結果集，將其從T i中刪除，從對應維度i的分組中再選擇最優(yōu)元組加入T i. 同時與基礎算法一樣，將記錄該數(shù)據(jù)點的掃描次數(shù)值加1. 當元組的count值與|Dtotal|-1（除分組維度外所有維度總數(shù)）相等時，根據(jù)結束條件1，判定該組計算是否結束.

優(yōu)化循環(huán)掃描策略：1）臨時表選擇：同基礎循環(huán)掃描策略類似，對每個臨時表i維護一個變量timesi′，用來記錄在臨時表T i中掃描過的元組的個數(shù)，每次掃描時選擇timesi′值最小的臨時表進行掃描. 2）元組選擇：每次掃描選定臨時表后，選擇該表內(nèi)具有最優(yōu)值的元組pi進行計算，并根據(jù)臨時表的更新策略更新臨時表.

如圖6所示，初始化時分別從每一個分組中，根據(jù)每一個維度的倒排索引取出第一個元組加入到對應維度的臨時表中（圖7）. 此時T 1，T 2的times′均為0，因此按順序選取T 1，那么第一次計算的就是T 1中值最優(yōu)的元組p17，計算完成后，此時T 1的times′為1，T 2的times′為0，因此第二次對T 2進行掃描，選取T 2中值最優(yōu)的元組p12進行計算. 這樣依次按優(yōu)化循環(huán)掃描策略計算，直到算法結束（參見結束條件2）.

4.2? ?整組過濾

定理2（整組過濾方法）：若掃描到的元組pi在除分組維度外其他維度上均滿足結束條件1，那么可以結束元組pi所在分組的計算，并且可以根據(jù)用戶偏好，將在分組維度上表現(xiàn)比元組pi差的所有分組的計算結束.

證明：當掃描到元組pi在除分組維度外其他維度上均滿足結束條件1時，根據(jù)引理1此時沒有掃描過的元組在除分組維度外所有維度上都不會優(yōu)于pi，根據(jù)支配的定義，同一分組內(nèi)的元組和分組維度上表現(xiàn)比pi屬性差的分組內(nèi)的元組，在分組維度表現(xiàn)也比pi差，因此不存在skyline元組，可以直接過濾，結束整個分組的計算.

證畢

例如在本文中，當p8被掃描到兩次時，通過圖2可知，對應的分組維度圖書分類上屬性值為B，對于用戶u3的偏好來說，根據(jù)整組過濾方法，E、D、A、C分組都可以整組過濾，因此算法此時可以結束，沒有掃描過的元組一定不會是skyline點.

結束條件2：所有分組的計算都結束時算法結束.

當所有分組的計算都結束時，算法結束，此時所有維度上結果集Ri的并集就是最終所求的結果. 由于實際情況中偏序屬性遠遠少于全序屬性，在刪除整個偏序分組時將直接過濾掉大量數(shù)據(jù)點，極大加快了計算速度. 并且在與結果集中的skyline點進行比較時，由于是按每個維度從最優(yōu)開始的順序，可以只與來自相同的維度的結果集中的點進行比較.

算法3：優(yōu)化算法（PSP_I）

輸入：根據(jù)分組策略的到的分為n組后的數(shù)據(jù)集{P1，P2，…，Pn}

輸出：P的skyline集合R

1. 初始化每個維度上的結果集Ri = ？椎

每個維度上的臨時表T i;

2. while（true）

3. 根據(jù)優(yōu)化循環(huán)掃描策略得到的計算點pi，屬于維度j

4. if（pi .count=0）

5. if（comparesky（pi，Rj）=true）

6. ? ? ? 將計算點pi加入當前維度的結果集Rj;

7. ? ? pi .count++;

8. end if

9.? end if;

10. else

11. pi .count++;

12. if（pi .count>=|Dtotal|-2）

13. 結束對應分組的計算;

14. if（所有分組均結束計算）

15. ? ? return R = {R1∪R2∪…∪Rr-1};

16. ? ? end if;

17. end if;

18.? end if;

19. end while;

5? ?實驗分析

本節(jié)展示了所提算法的高效性. 實驗環(huán)境配置為Inter Core i5 7300HQ 2.50 GHz CPU，8 GB內(nèi)存，1 T硬盤，Windows 10 操作系統(tǒng)的PC. 算法用C++語言編寫. 為了評估本文所提算法性能，以ZINC算法[3]和PSLP算法[4]為對比實驗進行.

本文分別用真實數(shù)據(jù)和合成數(shù)據(jù)驗證算法性能. 真實數(shù)據(jù)采用的是股票數(shù)據(jù)集（共包含2×106條股票記錄，每條股票記錄包含4個屬性：交易量、股票價格漲幅、股票類別和上市板塊，其中股票類別和上市板塊為偏序屬性維度）. 真實數(shù)據(jù)集計算結果如表2所示.

通過表2可以看出本文提出的PSP算法在真實數(shù)據(jù)集上的表現(xiàn)，在進行skyline計算的速度上較之前的算法有明顯提高，并且由于高效地剪枝過濾，需要計算的數(shù)據(jù)量也明顯少于ZINC算法和PSLP算法.

合成數(shù)據(jù)由文獻[14]給出的數(shù)據(jù)生成器生成，包括獨立分布數(shù)據(jù)集和反相關分布數(shù)據(jù)集. 默認數(shù)據(jù)集包括5個偏好維度，3個全序和2個偏序;默認數(shù)據(jù)量規(guī)模為106;默認用戶偏好DAG的寬度為4，深度為8，密度為0.6. 整體上數(shù)據(jù)服從隨機分布，本章實驗主要通過維度、數(shù)據(jù)集規(guī)模、哈斯圖寬度和深度以及哈斯圖密度的變化對實驗結果的影響來驗證算法的優(yōu)越性，衡量實驗的主要標準為skyline的計算時間，實驗中合成數(shù)據(jù)的主要參數(shù)及其變化范圍如表3所示.

5.1? ?維度變化對算法性能的影響

為了分析數(shù)據(jù)集維度對實驗的影響，在固定全序維度個數(shù)的情況下模擬了偏序維度個數(shù)變化的情況，組合（t，p）表示全序維度和偏序維度個數(shù)，其中t表示全序維度個數(shù)，p表示偏序維度個數(shù). 為了更加穩(wěn)定地測出算法性能，對于每種取值組合都利用數(shù)據(jù)生成器隨機生成了100次數(shù)據(jù)集，進行100次實驗，然后取這100次實驗的平均值進行記錄. 圖8記錄了在不同維度個數(shù)下進行skyline計算所消耗的時間，圖9記錄了在不同維度下計算過的元組的數(shù)量.

圖8和圖9表明了當偏序域維度個數(shù)增多時，4種算法的計算時間和計算元組數(shù)量的變化. 從圖中可以看出當|TO|相等，|PO|增多時4種算法所需時間均呈現(xiàn)指數(shù)上升趨勢，計算過的元組數(shù)量也呈現(xiàn)上升趨勢. 可以看出，4種算法中PSP_B和PSP_I算法要明顯優(yōu)于另兩種算法，這是因為當偏序域增多時，用戶偏好復雜，降維成本會很高，PSP_B算法在映射后采用倒排索引進行輪巡掃描，可以過濾掉大量冗余點，節(jié)省了計算時間與計算成本，PSP_I算法在PSP_B算法的基礎上對數(shù)據(jù)集進行分組，通過過濾方法對整組數(shù)據(jù)進行過濾，進一步提高了過濾效率.

5.2? ?數(shù)據(jù)集規(guī)模對算法性能的影響

測試了數(shù)據(jù)集規(guī)模對實驗的影響，在同樣TO? =2，PO=3的情況下，分別以數(shù)據(jù)量為105、5×105、106、5×106、107進行實驗. 為了更加穩(wěn)定地測出算法性能，采用多次實驗，取平均值的方式進行實驗記錄. 圖10所示為數(shù)據(jù)量不同的情況下計算skyline所需要的時間對比，圖11則說明了在數(shù)據(jù)量不同的條件下查詢需要計算的元組數(shù)量.

圖10和圖11描述了當數(shù)據(jù)集規(guī)模不同時，4種算法進行skyline查詢所需要的處理時間和所要計算的元組數(shù)量. 從圖中可以看出，隨著數(shù)據(jù)規(guī)模增大，計算所需的時間也明顯增加，特別是ZINC算法和PSLP算法，在數(shù)據(jù)量增大時顯出明顯的劣勢;在數(shù)據(jù)量增大時，PSP_B算法通過倒排索引可以對數(shù)據(jù)集進行提前過濾，避免了大量不必要的冗余點的計算，明顯加快了計算速度;PSP_I算法在此基礎上通過分組倒排可以一次性過濾掉整個分組，提高了過濾效率，進一步減少了計算時間. 實驗表明PSP_I算法有明顯的過濾剪枝效果，并且當數(shù)據(jù)量增大時對計算效率的提升效果更明顯.

5.3? ?哈斯圖寬度和深度對算法性能的影響

比較了當用戶偏好哈斯圖不同時4種算法的表現(xiàn)情況，實驗除哈斯圖形狀外其他參數(shù)均采用實驗默認值，并采用多次實驗求平均值的方式進行實驗記錄. 圖12和圖13分別記錄了在哈斯圖寬度和深度不同情況下的實驗結果.

從圖12中可以看出在哈斯圖寬度和深度不同的情況下，PSP_B算法和PSP_I算法計算時間均少于ZINC和PSLP算法，且隨著寬度和深度的增加差距逐漸明顯. 圖13則說明了PSP_I算法剪枝效果的優(yōu)越性，該算法大量地減少了需要計算的元組數(shù)量. 通過獨立分布數(shù)據(jù)集和反相關數(shù)據(jù)集的對比實驗表明在不同的數(shù)據(jù)分布情況下本文提出的算法對skyline計算效率有明顯提高，通過對數(shù)據(jù)剪枝過濾減少了計算時間.

5.4? ?哈斯圖密度對算法性能的影響

本小節(jié)的實驗比較了在其他屬性均取默認值的情況下，不同的哈斯圖密度對實驗結果的影響. 圖11記錄了哈斯圖密度分別取0.2、0.4、0.6、0.8和1.0時，4種算法的計算時間. 同之前的實驗相同，采用多次實驗求平均值的方法進行實驗記錄，結果如圖14、圖15所示.

圖14表明4種算法在哈斯圖密度不同的情況下進行skyline計算所需要的時間. 從圖中可以看出，在哈斯圖密度不同的情況下本文提出的PSP_B算法和PSP_I算法所需的計算時間均少于之前的算法.圖15表明本文提出的算法有明顯的過濾效果，大量減少了元組的計算數(shù)量，證明了本文提出的算法可以有效地提高skyline查詢的計算效率.

6? ?結? ?論

本文對偏序域上的skyline查詢技術進行了深入研究. 首先提出將倒排索引引入skyline查詢領域，利用倒排索引來管理數(shù)據(jù)，在查詢前進行大量的剪枝過濾，并通過實驗證明其可以有效地提高查詢效率;在此基礎上提出了一種優(yōu)化算法，在建立倒排索引前通過分組的方式對數(shù)據(jù)進行預處理，在進行計算時將一定不會成為結果的分組整組過濾，從而進一步加快了過濾效率，提高計算速度. 實驗結果表明，本文提出的新算法在計算速度和過濾效果上優(yōu)于之前的算法，具有合理性.

參考文獻

[1]? ? CHAN C Y，ENG P K，TAN L K，et al. Stratified computation of skylines with partially-ordered domains[C]//Proceedings of the ACM SIGMOD International Conference on Management of Data. Baltimore，Maryland，USA：DBLP，2005：203—214.

[2]? ? SACHARIDIS D，PAPADOPOULOS S，PAPADIAS D. Topologically sorted skylines for partially ordered domains[C]// 2009 IEEE 25th International Conference on Data Engineering. Shanghai：IEEE，2009：1072—1083.

[3]? ? LIU B，CHAN C Y. ZINC：efficient indexing for skyline computation [J]. Proceedings of the VLDB Endowment，2010，4（3）：197—207.

[4]? ? YIN B，GU K. Parallel skyline computation for partially ordered domains[C]// 2017 IEEE International Symposium on Parallel and Distributed Processing with Applications and 2017 IEEE International Conference on Ubiquitous Computing and Communications （ISPA/IUCC）. Guangzhou：IEEE，2017：699—706.

[5]? ? BORZSONYI S，KOSSMANN D，STOCKER K. The skyline operator[C]//Proceedings 17th International Conference on Data Engineering. Heidelberg：IEEE，2001：421—430.

[6]? ? CHOMICKI J，GODFREY P，GRYZ J，et al. Skyline with presorting[C]//Proceedings 19th International Conference on Data Engineering. Bangalore，India：IEEE，2003：717—719.

[7]? ? TAN K L，ENG P K，OOI B C. Efficient progressive skyline computation[C]// 27th International Conference on Very Large Data Bases. Roma：DBLP，2001：301—310.

[8]? ? KOSSMANN D，RAMSAK F，ROST S. Shooting stars in the sky：an online algorithm for skyline queries[C]//? Proceedings of 28th International Conference on Very Large Data Bases. Hong Kong：DBLP，2002：275—286.

[9]? ? HUANG Z H，WANG Z H，GUO J K，et al. Efficient preprocessing of subspace skyline queries in P2P networks[J]. Journal of Software，2009，20（7）：1825—1838.

[10]? WU P，ZHANG C J，F(xiàn)ENG Y，et al. Parallelizing skyline queries for scalable distribution[C]// International Conference on Advances in Database Technology-edbt. Heidelberg：Springer-Verlag，2006：112—130.

[11]? XIN J C，BAI M，WANG G R. Efficient threshold skyline query processing in uncertain databases[C]// Seventh International Conference on Natural Computation. Shanghai：IEEE，2011：311—315.

[12]? HSUEH Y L，LIN C C，CHANG C C. An efficient indexing method for skyline computations with partially ordered domains[J]. IEEE Transactions on Knowledge & Data Engineering，2017，29（5）：963—976.

[13]? 白梅，信俊昌，王國仁，等. 數(shù)據(jù)流上動態(tài)輪廓查詢處理技術的研究[J]. 計算機學報，2016，39（10）：81—104.

BAI M，XIN J C，WANG G R，et al. Research on dynamic skyline query processing over data streams[J]. Chinese Journal of Computers，2016，39（10）：81—104. （In Chinese）

[14]? PAPADIAS D，TAO Y，F(xiàn)U G，et al. An optimal and progressive algorithm for skyline queries[C]//Acm Sigmod International Conference. San Diego，California：SIGMOD，2003：467—478.