基于垂直劃分的隱私保護(hù)skyline查詢

吳吉斌 王箭

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

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

中圖法分類號(hào)：TP309.7 文獻(xiàn)標(biāo)識(shí)碼：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查詢?cè)诰频晖扑]等場(chǎng)景下有著廣泛的應(yīng)用，并研究了大規(guī)模數(shù)據(jù)集上的skyline查詢算法。此后，skyline查詢?cè)跀?shù)據(jù)庫(kù)及其相關(guān)領(lǐng)域受到廣泛關(guān)注[3]-[6]。Balke等人在文獻(xiàn)[7]中提出了垂直劃分?jǐn)?shù)據(jù)集上的skyline查詢算法BDS和IDS，這兩種算法中待測(cè)試數(shù)據(jù)集垂直分布在不同的服務(wù)器中，每個(gè)服務(wù)器僅存儲(chǔ)一維數(shù)據(jù)，算法拓展性較差?；贐alke等人的研究基礎(chǔ)，Trimponias等人在文獻(xiàn)[8]中提出了VPS（Vertical Partition Skyline）算法，該算法中待測(cè)試數(shù)據(jù)集垂直分布在多個(gè)服務(wù)器中，并且每個(gè)服務(wù)器可存儲(chǔ)多維數(shù)據(jù)。但以上幾種垂直分布數(shù)據(jù)集上的skyline查詢算法中數(shù)據(jù)均以明文形式傳輸，查詢過(guò)程中服務(wù)器內(nèi)存儲(chǔ)的敏感數(shù)據(jù)直接泄露給查詢端。如何實(shí)現(xiàn)垂直劃分?jǐn)?shù)據(jù)集上隱私保護(hù)的skyline查詢成為當(dāng)前信息安全領(lǐng)域的研究熱點(diǎn)。本文在VPS算法基礎(chǔ)上提出了一種垂直劃分?jǐn)?shù)據(jù)集上的隱私保護(hù)skyline查詢算法。

2 VPS查詢算法

2.1 基本概念

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

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

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

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

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

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

2.2 VPS算法步驟

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

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

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

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

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

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

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

3 基于垂直劃分的隱私保護(hù)skyline查詢

3.1 保序加密

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

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

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

6 結(jié) 論

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

參考文獻(xiàn)

[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].計(jì)算機(jī)學(xué)報(bào)，2005，28（7）：1230—1235.