基于垂直划分的隐私保护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，这两种算法中待测试数据集垂直分布在不同的服务器中，每个服务器仅存储一维数据，算法拓展性较差。基于Balke等人的研究基础，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.