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

吳吉斌 王箭

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

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

2 VPS查詢算法

2.1 基本概念

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

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

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

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

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

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

2.2 VPS算法步驟

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

1）選擇未返回Panc的服務器Ni，發送Ni序列頂端數據點P到查詢端

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

3）重復1-2，直到所有服務器返回Panc。

4）所有服務器計算Panc的本地支配區間，將不被Panc支配的數據點發送到查詢端

5）查詢端在剩余數據點上計算skyline

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

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

3.1 保序加密

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

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

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

6 結 論

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

參考文獻

[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，FU 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] 羅文俊，李祥.多方安全矩陣乘積協議及應用[J].計算機學報，2005，28（7）：1230—1235.