PSP：一種高效的偏序域上skyline 查詢處理方法

白梅，王京徽，王習(xí)特，朱斌，李冠宇

（大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院，遼寧大連 116000）

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

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

圖1 skyline 集合舉例Fig.1 The example of skyline

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

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

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

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

圖2 偏序域上的skyline 查詢舉例Fig.2 The example of skyline for partially ordered domains

總的來(lái)說(shuō)，本文的主要貢獻(xiàn)如下：

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

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

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

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

1 相關(guān)工作

1.1 傳統(tǒng)skyline 查詢

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

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

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

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

1.2 偏序域上的skyline 查詢

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

2009 年，Sacharidis 等[2]提出了一種基于拓?fù)渑判虻膕kyline 查詢方法TSS（Topologically Sorted Skylines for Partially Ordered Domains），利用拓?fù)渑判驅(qū)⑵蛴蛴成涑扇蛴蛏系拈g隔，并且，TSS 算法可以用來(lái)處理動(dòng)態(tài)skyline 查詢.2010 年，Liu 等[3]提出了ZINC 算法，通過(guò)降維來(lái)簡(jiǎn)化用戶偏好情況，并使用嵌套碼將其轉(zhuǎn)化為部分階映射到總階數(shù).最后用ZB樹(shù)來(lái)索引編碼值，然而，當(dāng)用戶偏好復(fù)雜時(shí)，偏序降維成本將會(huì)很高.

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

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

2 問(wèn)題描述

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

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

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

1）?i∈{1，2，…，d}，p1[i]＜p2[i]；

2）?j∈{1，2，…，d}，p1[j]＜p2[j].

定義2 （skyline[5]）給定數(shù)據(jù)集P，其skyline 是所有不被其他點(diǎn)支配的點(diǎn)的集合，即SKY（P）={pj|

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

表1 符號(hào)定義Tab.1 List of symbols

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

1）?i∈TO，p1[i]不差于p1[i]；

2）?j∈PO，p1[j]不差于p2[j]；

3）?m∈{TO∪PO}，p1[m]優(yōu)于p2[m].

利用圖2（a）的數(shù)據(jù)集舉例說(shuō)明，圖1 是對(duì)該數(shù)據(jù)集僅考慮價(jià)格和評(píng)分兩個(gè)全序域，直接在全序域上求skyline 的結(jié)果，最終計(jì)算得到的skyline 集合為{p8，p12，p16，p17}，但在圖2（b）中，加入了偏序域上不同用戶對(duì)不同種類圖書(shū)的偏好，對(duì)3 個(gè)不同用戶分別求得的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ù)索引（倒排索引）；然后，介紹了利用倒排索引的過(guò)濾方法；最后，介紹了基于倒排索引的基礎(chǔ)算法PSP_B.算法利用倒排索引對(duì)數(shù)據(jù)提前進(jìn)行處理，對(duì)數(shù)據(jù)集進(jìn)行過(guò)濾剪枝，使得進(jìn)行skyline 查詢時(shí)不必掃描整個(gè)數(shù)據(jù)集.

3.1 倒排索引

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

映射規(guī)則[2]：算法采用將偏序域?qū)傩杂成涞絻蓚€(gè)全序域的方式來(lái)處理偏序域?qū)傩?如圖3 所示，對(duì)于偏好哈斯圖[13]進(jìn)行深度優(yōu)先遍歷，并用間隔[po-to1，po-to2]進(jìn)行標(biāo)記，其中po-to1表示節(jié)點(diǎn)在深度優(yōu)先遍歷時(shí)第一次被掃描到的時(shí)刻，po-to2表示節(jié)點(diǎn)結(jié)束掃描的時(shí)刻，即該點(diǎn)的子節(jié)點(diǎn)全部遍歷結(jié)束.偏序域上的偏好關(guān)系就可以用間隔間的覆蓋來(lái)表示.

圖3 映射規(guī)則舉例Fig.3 Examples of the mapping function

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

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

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

圖4 倒排索引應(yīng)用舉例（用戶u3）Fig.4 The example of the inverted index application

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

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

在skyline 查詢時(shí)，基礎(chǔ)循環(huán)掃描策略對(duì)倒排索引進(jìn)行掃描，并對(duì)掃描過(guò)的點(diǎn)進(jìn)行掃描次數(shù)標(biāo)記.對(duì)每一個(gè)元組僅在第一次掃描到的時(shí)候進(jìn)行skyline計(jì)算，之后掃描到時(shí)僅增加該元組的掃描次數(shù).

3.2 冗余點(diǎn)過(guò)濾

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

結(jié)束條件1：當(dāng)掃描到一個(gè)元組pi在所有維度上都被掃描過(guò)一次時(shí)，若pi在偏序維度POm對(duì)應(yīng)多個(gè)間隔，判斷pi在POm上掃描到的值是否來(lái)自同一間隔，若是，則pi可以作為掃描結(jié)束點(diǎn)，此時(shí)可以結(jié)束算法，將結(jié)果集返回給用戶；否則pi不能作為掃描結(jié)束點(diǎn)，繼續(xù)循環(huán)掃描.

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

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

證畢

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

為描述方便，定義Ri為暫時(shí)結(jié)果集，用來(lái)存放di維度上已掃描過(guò)的skyline 點(diǎn).

定理1：對(duì)維度Di建立對(duì)應(yīng)的結(jié)果集Ri，那么對(duì)于掃描到在維度Di上的元組pi，若pi不被Ri中的元組支配，那么pi一定是skyline 點(diǎn).

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

證畢

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

由引理1 和定理1 可以過(guò)濾掉大量的冗余點(diǎn)，只針對(duì)最必要的元組進(jìn)行skyline 查詢，極大地提高了查詢效率.

圖5 維度Ri 上的結(jié)果集舉例（用戶u3）Fig.5 The example of result set on domain Ri

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

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

4 優(yōu)化算法

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

4.1 分組倒排

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

圖6 分組倒排舉例Fig.6 The example of grouping inversion

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

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

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

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

圖7 臨時(shí)表舉例Fig.7 The example of temporary tables

4.2 整組過(guò)濾

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

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

證畢

例如在本文中，當(dāng)p8被掃描到兩次時(shí)，通過(guò)圖2可知，對(duì)應(yīng)的分組維度圖書(shū)分類上屬性值為B，對(duì)于用戶u3的偏好來(lái)說(shuō)，根據(jù)整組過(guò)濾方法，E、D、A、C分組都可以整組過(guò)濾，因此算法此時(shí)可以結(jié)束，沒(méi)有掃描過(guò)的元組一定不會(huì)是skyline 點(diǎn).

結(jié)束條件2：所有分組的計(jì)算都結(jié)束時(shí)算法結(jié)束.

當(dāng)所有分組的計(jì)算都結(jié)束時(shí)，算法結(jié)束，此時(shí)所有維度上結(jié)果集Ri的并集就是最終所求的結(jié)果.由于實(shí)際情況中偏序?qū)傩赃h(yuǎn)遠(yuǎn)少于全序?qū)傩?，在刪除整個(gè)偏序分組時(shí)將直接過(guò)濾掉大量數(shù)據(jù)點(diǎn)，極大加快了計(jì)算速度.并且在與結(jié)果集中的skyline 點(diǎn)進(jìn)行比較時(shí)，由于是按每個(gè)維度從最優(yōu)開(kāi)始的順序，可以只與來(lái)自相同的維度的結(jié)果集中的點(diǎn)進(jìn)行比較.

5 實(shí)驗(yàn)分析

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

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

表2 真實(shí)數(shù)據(jù)集實(shí)驗(yàn)結(jié)果Tab.2 Result of real data set

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

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

表3 實(shí)驗(yàn)參數(shù)Tab.3 Experimental parameters

5.1 維度變化對(duì)算法性能的影響

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

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

圖8 數(shù)據(jù)集維度對(duì)計(jì)算時(shí)間的影響Fig.8 The effect of dataset dimensions on calculation time

圖9 數(shù)據(jù)集維度對(duì)計(jì)算過(guò)元組數(shù)量的影響Fig.9 Effect of dimensions on the number of calculated tuples

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

圖10 數(shù)據(jù)集規(guī)模對(duì)計(jì)算時(shí)間的影響Fig.10 The effect of cardinality on calculation time

圖11 數(shù)據(jù)集規(guī)模對(duì)計(jì)算過(guò)元組數(shù)量的影響Fig.11 The effect of cardinality on the number of calculated tuples

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

5.3 哈斯圖寬度和深度對(duì)算法性能的影響

比較了當(dāng)用戶偏好哈斯圖不同時(shí)4 種算法的表現(xiàn)情況，實(shí)驗(yàn)除哈斯圖形狀外其他參數(shù)均采用實(shí)驗(yàn)?zāi)J(rèn)值，并采用多次實(shí)驗(yàn)求平均值的方式進(jìn)行實(shí)驗(yàn)記錄.圖12 和圖13 分別記錄了在哈斯圖寬度和深度不同情況下的實(shí)驗(yàn)結(jié)果.

圖12 哈斯圖寬度和深度對(duì)計(jì)算時(shí)間的影響Fig.12 The effect of the depth and width of the hasse on running time

圖13 哈斯圖寬度和深度對(duì)計(jì)算過(guò)元組數(shù)量的影響Fig.13 The effect of the depth and width of the hasse on the number of calculated tuples

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

5.4 哈斯圖密度對(duì)算法性能的影響

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

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

圖14 哈斯圖密度對(duì)計(jì)算時(shí)間的影響Fig.14 The effect of the density of the hasse on running time

圖15 哈斯圖密度對(duì)計(jì)算過(guò)元組數(shù)量的影響Fig.15 The effect of the density of the hasse on the number of calculated tuples

6 結(jié)論

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