吳吉斌 王箭

摘 要：Skyline查詢是一種重要的數(shù)據(jù)分析方法，在推薦系統(tǒng)中有著廣泛的應(yīng)用。近年來，隨著隱私保護需求的不斷增長，分布式數(shù)據(jù)集上的隱私保護skyline查詢問題受到越來越多的關(guān)注。然而，現(xiàn)有的分布式數(shù)據(jù)集上的隱私保護skyline查詢方案大多只適用于水平分布數(shù)據(jù)集，不能滿足垂直分布數(shù)據(jù)集上的skyline查詢需求。為此，深入研究了垂直分布式數(shù)據(jù)集上保護隱私的skyline查詢問題，提出了一種基于保序加密的垂直分布數(shù)據(jù)集上的隱私保護skyline查詢算法，可以在保護數(shù)據(jù)隱私的同時，有效支持skyline查詢過程。理論分析證明了提出協(xié)議的正確性和安全性，并通過理論分析和模擬實驗對協(xié)議運行效率進行了評估，結(jié)果顯示新方案具有較高的運行效率。

關(guān)鍵詞：skyline查詢；隱私保護；垂直分布

中圖法分類號：TP309.7 文獻標識碼：A

Abstract： As a method of data analysis，skyline query plays an important role in many real-world applications，such as recommender system.Recently，with the growth of privacy concerns，many schemes have been proposed to achieve privacy-preserving skyline query on distributed databases.Nevertheless，most of them focus on horizontally-partitioned dataset，and cannot support secure skyline query on vertically-distributed databases.In this paper，we focus on privacy-preserving skyline query on vertically-partitioned data and propose an efficient scheme based on order-preserving encryption for it.In the proposed scheme，we can guarantee the privacy of each data.We theoretically prove the security of our scheme.Additionally，we leverage extensive experiments to evaluate our proposed method，which shows our scheme can achieve high efficiency.

Keywords： skyline query；privacy-preserving；vertically-partitioned data

1 引 言

Skyline查詢[1]算是一種重要的數(shù)據(jù)分析方法，2001年，Borzsonyi等[2]展示了skyline查詢在酒店推薦等場景下有著廣泛的應(yīng)用，并研究了大規(guī)模數(shù)據(jù)集上的skyline查詢算法。此后，skyline查詢在數(shù)據(jù)庫及其相關(guān)領(lǐng)域受到廣泛關(guān)注[3]-[6]。Balke等人在文獻[7]中提出了垂直劃分數(shù)據(jù)集上的skyline查詢算法BDS和IDS，這兩種算法中待測試數(shù)據(jù)集垂直分布在不同的服務(wù)器中，每個服務(wù)器僅存儲一維數(shù)據(jù)，算法拓展性較差。基于Balke等人的研究基礎(chǔ)，Trimponias等人在文獻[8]中提出了VPS（Vertical Partition Skyline）算法，該算法中待測試數(shù)據(jù)集垂直分布在多個服務(wù)器中，并且每個服務(wù)器可存儲多維數(shù)據(jù)。但以上幾種垂直分布數(shù)據(jù)集上的skyline查詢算法中數(shù)據(jù)均以明文形式傳輸，查詢過程中服務(wù)器內(nèi)存儲的敏感數(shù)據(jù)直接泄露給查詢端。如何實現(xiàn)垂直劃分數(shù)據(jù)集上隱私保護的skyline查詢成為當前信息安全領(lǐng)域的研究熱點。本文在VPS算法基礎(chǔ)上提出了一種垂直劃分數(shù)據(jù)集上的隱私保護skyline查詢算法。

2 VPS查詢算法

2.1 基本概念

Skyline查詢是指從給定數(shù)據(jù)集D中篩選出子集S，使得子集S內(nèi)的數(shù)據(jù)點不被任意其他數(shù)據(jù)點支配。這里假設(shè)數(shù)據(jù)較小值優(yōu)于較大值，比如對顧客而言，商品價格越低越優(yōu)。

定義1（支配關(guān)系） 對于d維空間中的兩個數(shù)據(jù)點Pa = （Pa1，Pa2，…，Pad）和Pb = （Pb1，Pb2，…，Pbd），若對于任意正整數(shù)j[1，d]，都有Paj≤Pbj，并且存在正整數(shù)i[1，d]，使得Pai < Pbi，則稱數(shù)據(jù)點Pa支配Pb。

定義2（錨點） 對于給定數(shù)據(jù)集D中的數(shù)據(jù)點P，若數(shù)據(jù)點P支配該數(shù)據(jù)集內(nèi)較多的數(shù)據(jù)點，則稱該數(shù)據(jù)點為錨點，記做Panc。

該算法假設(shè)d維數(shù)據(jù)集D = {P1，P2，…，Pn}垂直分布在m個服務(wù)器中。這里以m為2舉例，數(shù)據(jù)垂直分布方式如圖1所示，服務(wù)器N1和N2分別存儲數(shù)據(jù)點不同維度，并且除數(shù)據(jù)點的ID外，兩服務(wù)器存儲維度不重復(fù)。

這里通過一個例子介紹skyline查詢在推薦系統(tǒng)中的應(yīng)用。假設(shè)某旅客要去海邊旅游，需要訂一個價格便宜并且離海邊近的酒店。某旅游公司的數(shù)據(jù)庫中存儲了各個酒店的價格和到海邊的距離，如圖2所示，以每個點表示一個酒店，其中x軸表示酒店價格，y軸表示酒店到海邊的距離。

對于圖中的酒店A和酒店B，酒店A的價格和到海岸的距離都小于酒店B，根據(jù)定義1可知，酒店A支配酒店B，因此酒店B不是skyline點。圖中不存在某酒店價格和到海岸的距離均小于酒店A，因此酒店A不被任何其他酒店支配，酒店A是skyline點。根據(jù)skyline點的定義，可以看出虛線相連的4個點是這些酒店中的skyline點。

2.2 VPS算法步驟

假設(shè)數(shù)據(jù)點P在服務(wù)器Ni中的投影為P.Ni，則數(shù)據(jù)點P在服務(wù)器Ni中的維度和為fsum（P.Ni）。服務(wù)器按fsum從小到大順序排列數(shù)據(jù)點，查詢端Client初始化Panc為空，該算法執(zhí)行過程如下。

1）選擇未返回Panc的服務(wù)器Ni，發(fā)送Ni序列頂端數(shù)據(jù)點P到查詢端

2）若數(shù)據(jù)點P與Panc的維度和滿足fsum（P） < fsum（Panc），則令Panc = P

3）重復(fù)1-2，直到所有服務(wù)器返回Panc。

4）所有服務(wù)器計算Panc的本地支配區(qū)間，將不被Panc支配的數(shù)據(jù)點發(fā)送到查詢端

5）查詢端在剩余數(shù)據(jù)點上計算skyline

文獻[8]給出了該算法詳細的正確性分析和準確性證明。但該算法中數(shù)據(jù)以明文形式傳輸，服務(wù)器存儲的數(shù)據(jù)直接泄露給查詢端，無法滿足用戶隱私保護的需求。

3 基于垂直劃分的隱私保護skyline查詢

3.1 保序加密

該實驗過程利用socket實現(xiàn)服務(wù)器與查詢端之間的數(shù)據(jù)通信。本實驗結(jié)果受到待測試數(shù)據(jù)集基數(shù)和服務(wù)器數(shù)量的影響，并且不同數(shù)據(jù)集錨點分布不同，會對實驗結(jié)果造成一定的影響。

圖5展示了在Core數(shù)據(jù)集中，本算法和VPS算法在服務(wù)器數(shù)量從2增長到9的過程中的計算時間。圖6展示了在NBA數(shù)據(jù)集中，本算法和VPS算法在服務(wù)器數(shù)量從2增長到8的過程中的計算時間變化曲線。從圖中可以看出，隨著服務(wù)器數(shù)量的增加，本算法和VPS算法的計算時間不斷增加，這是因為隨著服務(wù)器數(shù)目的增長，服務(wù)器與查詢端之間的數(shù)據(jù)通信量增加，算法運行時間隨之增長。當服務(wù)器數(shù)量小于5時，本算法和VPS算法計算時間相差不大。且服務(wù)器數(shù)量越少，計算時間越相近。

當服務(wù)器數(shù)量較少時，本算法在實現(xiàn)安全skyline查詢的條件下，計算時間與VPS算法近似，該實驗證明了本算法的可行性。

6 結(jié) 論

提出了一種垂直分布數(shù)據(jù)集上保護隱私的skyline查詢協(xié)議。理論分析顯示我們的方案能夠正確地實現(xiàn)skyline查詢，并保護數(shù)據(jù)集的隱私信息。進一步，還通過理論分析和模擬實驗對新協(xié)議的運行效率進行了評估，結(jié)果顯示可以取得較高的運行效率。在未來的工作中，將著重研究協(xié)議效率的提升和通信復(fù)雜度的降低，使其在現(xiàn)實中得到廣泛的應(yīng)用。

參考文獻

[1] KUNG H T.On the computational complexity of finding the maxima of a set of vectors[C].In：IEEE Conference Record of Symposium on Switching and Automata Theory.1974：117—121.

[2] STEPHAN B，STOCKER K，KOSSMANN D.The Skyline Operator[C].In：IEEE International Conference on Data Engineering.2002：421—430.

[3] BARTOLINI I，CIACCIA P，PATELLA M.Efficient sort-based skyline evaluation[J].ACM Transactions on Database Systems，2008，33（4）：1—49.

[4] CHOMICKI J，GODFREY P，GRYZ J，et al.Skyline with presorting[C].In：IEEE International Conference on Data Engineering.2003：717—719.

[5] LEE K C K，ZHENG B，LI H，et al.Approaching the skyline in z order[C].In：International Conference on Very Large Data Bases.VLDB Endowment 2007：279—290.

[6] PAPADIAS D，TAO Y，F(xiàn)U G，et al.Progressive skyline computation in database systems[J].ACM Transactions on Database Systems，2005，30（1）：41—82.

[7] BALKE W T，GUNTZER U，ZHENG J.Efficient distributed skylining for web information systems[C].In：International Conference on Extending Database Technology.2004：573—574.

[8] TRIMPONIAS G，BARTOLINI I，PAPADIAS D，et al.Skyline processing on distributed vertical decompositions[J].IEEE Transactions on Knowledge and Data Engineering，2013，25（4）：850—862.

[9] AGRAWAL R，KIERNAN J，SRIKANT R，et al.Order preserving encryption for numeric data[C].Proceedings of the 2004 ACM SIGMOD international conference on Management of data.ACM，2004：563—574.

[10] CHUNG S S，OZSOYOGLU G.Anti-tamper databases：processing aggregate queries over encrypted databases[C].Data Engineering Workshops，2006.Proceedings.22nd International Conference on.IEEE，2006：98—98.

[11] 羅文俊，李祥.多方安全矩陣乘積協(xié)議及應(yīng)用[J].計算機學報，2005，28（7）：1230—1235.