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

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

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

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

中圖分類號(hào)：TP391 ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)志碼：A? ? ? ? ? 文章編號(hào)：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)技術(shù)的發(fā)展以及信息獲取設(shè)備的進(jìn)步，數(shù)據(jù)庫收集處理的數(shù)據(jù)量增多，進(jìn)一步，數(shù)據(jù)庫中存儲(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條圖書信息記錄{p1，p2，…，p20}，每一條圖書信息包括了兩個(gè)維度信息：圖書價(jià)格和評(píng)分，評(píng)分維度利用倒數(shù)映射到[0，1]區(qū)間內(nèi)，使兩個(gè)維度均以小值為“優(yōu)”. 例如圖1中p8在每一維都比p15小，說明p8價(jià)格和評(píng)分都比p15要好，即p8支配p15. 經(jīng)過skyline查詢后，圖中最終skyline集合為{p8，p12，p16，p17}，其他圖書記錄都可以被這個(gè)集合中的點(diǎn)支配.

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

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

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

為了更有效地減少開銷，提高輪廓查詢效率，本文將倒排索引應(yīng)用到查詢中，首先提出了一種高效的偏序域上skyline查詢處理方法（Basic? Partially-ordered Skyline Processing based on inverted index，PSP_B）. 之后，在此算法的基礎(chǔ)上，通過提前對(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)行過濾. 實(shí)驗(yàn)證明，該算法能更高效地處理偏序域上的輪廓查詢.

總的來說，本文的主要貢獻(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)行掃描的問題. 算法對(duì)數(shù)據(jù)集在每個(gè)維度上建立倒排索引，通過循環(huán)掃描策略快速找到掃描結(jié)束點(diǎn)來結(jié)束算法，達(dá)到了對(duì)數(shù)據(jù)集過濾剪枝的目的，提高了計(jì)算效率.

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

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

1? ?相關(guān)工作

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

早期，人們主要關(guān)注于全序域上的skyline查詢. Borzsonyi等[5]第一次將skyline查詢的概念引入數(shù)據(jù)庫領(lǐng)域，并提出了BNL（Block Nested Loops）和D&C（Divide and Conquer）算法，BNL算法對(duì)待測(cè)元組建立臨時(shí)表，通過將每個(gè)待測(cè)元組與表內(nè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)行查詢來得到最終結(jié)果. 這兩種算法都會(huì)產(chǎn)生多次迭代，查詢效率較低.

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

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

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

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

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

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

2? ?問題描述

本文關(guān)注的是偏序域上的skyline查詢問題，以小值為優(yōu)舉例，遇到大值為優(yōu)的維度需要經(jīng)過預(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指不同的屬性維度）

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

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

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

3.1? ?倒排索引

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

映射規(guī)則[2]：算法采用將偏序域?qū)傩杂成涞絻蓚€(gè)全序域的方式來處理偏序域?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)系就可以用間隔間的覆蓋來表示.

如用戶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那么就說明在該偏序維度上屬性M優(yōu)于屬性N. 若兩個(gè)區(qū)間互不包含，則相應(yīng)屬性的好壞無法比較. 例如圖3中，對(duì)于用戶u1來說，屬性C映射到全序域的間隔為[2，5]，屬性B映射到全序域的間隔為[3，3]，屬性C的間隔可以覆蓋屬性B的間隔，即對(duì)于用戶u1來說，屬性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)來對(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所示.

基礎(chǔ)循環(huán)掃描策略：由于全序域和偏序域上數(shù)據(jù)屬性值的數(shù)量差距較大，導(dǎo)致建立的倒排表不同維度分布不同，屬性值個(gè)數(shù)有差距，如圖4所示，因此對(duì)倒排索引上每個(gè)維度i維護(hù)一個(gè)timesi變量，用來記錄該維度上掃描過的點(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é)束條件1）.

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

3.2? ?冗余點(diǎn)過濾

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

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

引理1[1]：若出現(xiàn)一個(gè)元組pi至少在每一個(gè)維度上都被掃描過一次，即pi.count>=|Dtotal|，根據(jù)基礎(chǔ)循環(huán)掃描策略，此時(shí)在任一維度上都沒有被掃描過的元組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é)束才能保證是該偏序維度掃描過一次.

證畢

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

為描述方便，定義Ri為暫時(shí)結(jié)果集，用來存放di維度上已掃描過的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可以過濾掉大量的冗余點(diǎn)，只針對(duì)最必要的元組進(jìn)行skyline查詢，極大地提高了查詢效率.

算法1：基礎(chǔ)算法（PSP_B）

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

|TO|個(gè)全序維度TO（d1，d2…）

|PO|個(gè)偏序維度PO（d1′，d2′…）;

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

1. 初始化每個(gè)維度上的結(jié)果集Ri=？椎;

2. for each di′∈PO do

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

4. end for;

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

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

7. while （true）

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

9. if（pi.count=0）

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

11. ? ? 將計(jì)算點(diǎn)pi加入當(dāng)前維度的結(jié)果集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. 對(duì)所有Rj取并集得到最終結(jié)果集R;

24. return R;

算法1第2～6行根據(jù)基礎(chǔ)循環(huán)掃描策略將偏序域映射到全序域，并建立倒排索引來維護(hù)數(shù)據(jù). 第8～22行是算法主體，根據(jù)維護(hù)的count值來進(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ū)傩允欠駚碜酝婚g隔，若是，則跳出循環(huán)，執(zhí)行第23行，返回結(jié)果集，結(jié)束算法，否則繼續(xù)循環(huán)掃描，直到算法結(jié)束.

算法2：Skyline計(jì)算方法 comparesky（pi，Rj）

輸入：元組pi，pi所在維度對(duì)應(yīng)的結(jié)果集Rj

輸出：待測(cè)pi是否為最終的skyline

1. for each pm ∈Rj

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

3. return false;

4. ? end if

5. end for

6. return true;

如圖4所示，以第一輪維度掃描順序?yàn)閮r(jià)格、評(píng)分PO-TO1、PO-TO2為例，結(jié)束一輪掃描后，4個(gè)維度的timesi值分別為1、1、3、3，且其中掃描過的元組{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í)（即與|Dtotal|相等），根據(jù)定理1判斷掃描到PO-TO1、PO-TO2維度上的值不是來自同一個(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)行分組，將在該維度上擁有相同屬性值的元組分到一組，例如選取圖書種類作為分組維度，將具有相同種類的圖書分到一組，如圖6所示.

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

臨時(shí)表的更新：進(jìn)行計(jì)算時(shí)，在每個(gè)維度i上從對(duì)應(yīng)的臨時(shí)表T i中取出最優(yōu)值，與所在維度結(jié)果集Ri中的元組進(jìn)行比較，若不被結(jié)果集中的點(diǎn)支配則加入結(jié)果集，將其從T i中刪除，從對(duì)應(yīng)維度i的分組中再選擇最優(yōu)元組加入T i. 同時(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′，用來記錄在臨時(shí)表T i中掃描過的元組的個(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í)T 1，T 2的times′均為0，因此按順序選取T 1，那么第一次計(jì)算的就是T 1中值最優(yōu)的元組p17，計(jì)算完成后，此時(shí)T 1的times′為1，T 2的times′為0，因此第二次對(duì)T 2進(jìn)行掃描，選取T 2中值最優(yōu)的元組p12進(jìn)行計(jì)算. 這樣依次按優(yōu)化循環(huán)掃描策略計(jì)算，直到算法結(jié)束（參見結(jié)束條件2）.

4.2? ?整組過濾

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

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

證畢

例如在本文中，當(dāng)p8被掃描到兩次時(shí)，通過圖2可知，對(duì)應(yīng)的分組維度圖書分類上屬性值為B，對(duì)于用戶u3的偏好來說，根據(jù)整組過濾方法，E、D、A、C分組都可以整組過濾，因此算法此時(shí)可以結(jié)束，沒有掃描過的元組一定不會(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í)將直接過濾掉大量數(shù)據(jù)點(diǎn)，極大加快了計(jì)算速度. 并且在與結(jié)果集中的skyline點(diǎn)進(jìn)行比較時(shí)，由于是按每個(gè)維度從最優(yōu)開始的順序，可以只與來自相同的維度的結(jié)果集中的點(diǎn)進(jìn)行比較.

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

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

輸出：P的skyline集合R

1. 初始化每個(gè)維度上的結(jié)果集Ri = ？椎

每個(gè)維度上的臨時(shí)表T i;

2. while（true）

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

4. if（pi .count=0）

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

6. ? ? ? 將計(jì)算點(diǎn)pi加入當(dāng)前維度的結(jié)果集Rj;

7. ? ? pi .count++;

8. end if

9.? end if;

10. else

11. pi .count++;

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

13. 結(jié)束對(duì)應(yīng)分組的計(jì)算;

14. if（所有分組均結(jié)束計(jì)算）

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

16. ? ? end if;

17. end if;

18.? end if;

19. end while;

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

本節(jié)展示了所提算法的高效性. 實(shí)驗(yàn)環(huán)境配置為Inter Core i5 7300HQ 2.50 GHz CPU，8 GB內(nèi)存，1 T硬盤，Windows 10 操作系統(tǒng)的PC. 算法用C++語言編寫. 為了評(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可以看出本文提出的PSP算法在真實(shí)數(shù)據(jù)集上的表現(xiàn)，在進(jìn)行skyline計(jì)算的速度上較之前的算法有明顯提高，并且由于高效地剪枝過濾，需要計(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)主要通過維度、數(shù)據(jù)集規(guī)模、哈斯圖寬度和深度以及哈斯圖密度的變化對(duì)實(shí)驗(yàn)結(jié)果的影響來驗(yàn)證算法的優(yōu)越性，衡量實(shí)驗(yàn)的主要標(biāo)準(zhǔn)為skyline的計(jì)算時(shí)間，實(shí)驗(yàn)中合成數(shù)據(jù)的主要參數(shù)及其變化范圍如表3所示.

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

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

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

圖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算法通過倒排索引可以對(duì)數(shù)據(jù)集進(jìn)行提前過濾，避免了大量不必要的冗余點(diǎn)的計(jì)算，明顯加快了計(jì)算速度;PSP_I算法在此基礎(chǔ)上通過分組倒排可以一次性過濾掉整個(gè)分組，提高了過濾效率，進(jìn)一步減少了計(jì)算時(shí)間. 實(shí)驗(yàn)表明PSP_I算法有明顯的過濾剪枝效果，并且當(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中可以看出在哈斯圖寬度和深度不同的情況下，PSP_B算法和PSP_I算法計(jì)算時(shí)間均少于ZINC和PSLP算法，且隨著寬度和深度的增加差距逐漸明顯. 圖13則說明了PSP_I算法剪枝效果的優(yōu)越性，該算法大量地減少了需要計(jì)算的元組數(shù)量. 通過獨(dú)立分布數(shù)據(jù)集和反相關(guān)數(shù)據(jù)集的對(duì)比實(shí)驗(yàn)表明在不同的數(shù)據(jù)分布情況下本文提出的算法對(duì)skyline計(jì)算效率有明顯提高，通過對(duì)數(shù)據(jù)剪枝過濾減少了計(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表明本文提出的算法有明顯的過濾效果，大量減少了元組的計(jì)算數(shù)量，證明了本文提出的算法可以有效地提高skyline查詢的計(jì)算效率.

6? ?結(jié)? ?論

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

參考文獻(xiàn)

[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ù)流上動(dòng)態(tài)輪廓查詢處理技術(shù)的研究[J]. 計(jì)算機(jī)學(xué)報(bào)，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.