PCPIR-V：基于Spark的并行隐私保护近邻查询算法

邓诗卓，姚继涛，王波涛，陈月梅，袁野，李艳辉，王国仁



PCPIR-V：基于Spark的并行隐私保护近邻查询算法

邓诗卓，姚继涛，王波涛，陈月梅，袁野，李艳辉，王国仁

（东北大学计算机科学与工程学院，辽宁沈阳 110819）

针对面向大数据的隐私保护查询效率低问题，利用CPIR保护程度高，实现了基于Spark的并行CPIR空间近邻查询隐私保护算法PCPIR-V，提出了基于Row和Bit的并行策略，同时提出并实现了基于聚类的PCPIR-V的缓存优化技术。利用均匀分布、高斯分布和真实数据对PCPIR-V进行了测试验证，在40个核心范围内，PCPIR-V具有良好的扩展性，PCPIR-V缓存优化技术计算时间与朴素PCPIR-V时间相比，平均减少了20%。

查询隐私保护；基于计算能力的隐私信息检索；Spark；基于位置服务

1 引言

科学技术和互联网的快速发展促使数据爆炸式增长，在大数据时代，每天的生活和生产环境都会产生大规模海量的数据信息，其中，伴随着多样定位手段、用户终端及广泛通信手段的出现，基于位置的服务[1]（LBS, location based services）已经成为当前研究的热点并且产生了大量基于位置的空间数据。LBS已经深入到人们的日常生活中，例如，城市基础交通设施优化计划和基于用户行走路线的智能商店布局决策、智能路线导航（如Google Map等）、基于位置的社交服务（如WeChat、Foursquare等）、基于位置的游戏和娱乐（如Google Ingress等）。随着LBS的用户大量增加，用户在享用位置服务的同时，其在互联网上的行为数据存在泄露的风险。随着用户对个人隐私需求的提高，用户希望在发起位置查询从而获得服务的过程中，用户查询信息的隐私能够得到保护，因此，基于用户隐私保护的大数据需求亟需实现。

单点位置信息的隐私查询保护的典型手段主要分为3类：干扰技术[2~4]、区域覆盖（隐匿空间技术）[5~8]、基于密码学的保护方式。干扰技术和区域覆盖都是通过损失可用性或隐私性的方式来实现的，而密码学的隐私保护方式，可以比较好地达到可用性和隐私性的平衡，密码学的隐私查询保护技术较有代表性的是隐私信息检索（PIR，private information retrieval），密码学的保护方式大都为基于复杂计算的数学方式，隐私保护强度高，但是计算量十分巨大。基于隐私信息检索的研究主要分为两大类，分别是基于信息理论的私有信息检索（IT-PIR，information theoretical private information retrieval）[9]和基于计算的私有信息检索（CPIR，computational private information retrieval）[10]。CPIR的实现基于数论中的同余理论及相关的研究成果。求解二次剩余（QR，quadratic residue）问题的难度与因子分解难度相当，是其隐私保护的理论基础。CPIR假设攻击者（服务器）计算求解能力为多项式限制（polynomially bounded），在这个前提下，保证攻击者不能通过区分与二次非剩余来区别用户对不同数据项的访问。

如图1所示，CPIR待查询数据库[11]是一个4×4的数据矩阵，表示矩阵中的某个元素，矩阵的每个元素为用户所要查询的内容，查询的过程是，移动用户首先随机产生2个大质数，，根据查询内容位置信息生成包含的二次剩余与二次非剩余集组成查询信息，其中，二次非剩余，其余为二次剩余，服务器会利用式(1)计算中每一行z值，其中，由式(2)和式(3)计算，式(2)是根据二次剩余相乘基本性质得出的。

近年来，基于PIR的近邻查询方面，文献[12]针对大量兴趣点（POI，points of interest）查询代价问题，提出adaptive query plan，至少保证预定比例的查询结果正确，但是adaptive query plan依赖真实用户行为与之前发布查询的阶段性变化统计，为了避免违反保密性，结合-differential privacy和PIR构成计算框架；基于PIR的关键字搜索方面，文献[13]中提出一种机制KSPIR，通过用户指定的弹性隐私以及预算来最小化通信和计算代价，该方法是检索代价和隐私强度（degree）之间的一个折中，实现关键字检索；文献[14]利用伪随机数规则随机生成排列数序列，伪随机数加密规则能够模糊和加密查询结果。

云计算是大数据处理的技术支撑，如分布式计算框架Hadoop[15]、Spark[16]、Storm等。Hadoop中MapReduce侧重于离线数据分布式批处理，Strom侧重于实时流分布式计算，而Spark侧重基于内存计算，Spark的快速发展和使用，进一步提高了大数据处理的效率，特别是在迭代计算和快速计算上相对于MapReduce有很大程度的提高。随着数据量增加，大量用户希望得到在线隐私保护，针对面向大数据的高强度基于位置服务的隐私保护问题，Spark是在线的并行计算框架，实现基于Spark的分布式CPIR位置服务隐私保护技术具有研究意义与应用价值。

在关于CPIR的分布式并行计算中，主要实现分为2种：基于Peer-to-Peer的并行化计算、基于主从结构（master-slave）的分布式计算。文献[17]提出一种基于P2P的并行CPIR，利用striping technique传输数据库给合作的peer，提高了CPIR查询的处理速度。文献[18,19]利用MapReduce计算框架实现PIR分布式计算。文献[18]中PIRMAP是一种适用于MapReduce的、有效的单服务器CPIR协议，主要用于检索云上的大文件（large files）。pCloud是基于GR-PIR协议实现数据库分区并行的；PIRMAP和PRISM对文件进行划分以实现并行化，属于I/O级的并行化，可以直接应用于CPIR计算的并行；本文的并行化是对CPIR矩阵行（Row）计算以及列（Bit）计算的并行，是CPU级的并行化，与上述研究成果相比，是2个不同维度的并行化，两者之间是互相补充的关系。

2 CPIR-V最近邻隐私保护查询算法

最近邻（NN，nearest neighbor）查询是LBS中一个应用比较广泛的查询，获得查询对象距离最近的对象，距离计算采用欧几里德距离。Voronoi图[20]通过对空间的划分体现空间对象之间的近邻拓扑关系，被广泛应用到各个方面，包括计算机图形学、空间数据关系、图像处理和多维数据等。图2(a)为1~5划分形成的Voronoi图[1,11]，其中，每个多边形称为Voronoi格，Voronoi格的边为相邻空间对象的垂直平分线，这样形成的多边形划分可以保证在同一个Voronoi格里面的所有空间对象的最近邻点都是同一个，例如，查询点的最近邻点就是跟点在同一个Voronoi格的点。

文献[11]提出一种基于隐私数据检索和Voronoi图的最近邻隐私保护查询算法CPIR-V，如图2(b)所示，CPIR-V利用兴趣点（POI，point of interests）将Voronoi图进行网格划分，实线是Voronoi边，虚线显示的是经过划分的网格的边。为POI，为查询点，查询点在网格标号为（2，1）的网格中，该网格与所形成的Voronoi格都有重合，查询点的最近邻可能是中的一个，所以，形成最近邻的候选集合。不同的网格可能有不同数量的最近邻点，这与点的分布、网格的大小都有关系。

构建网格矩阵，以每个网格中POI数量最多为基准，不足的网格进行填充。当用户发起查询的时候，首先通过计算获取查询点所在的网格，随机生成2个大质数1，2，对进行二次剩余的计算，生成图3中的查询，其中，查询区域的网格对应的是的二次非剩余，其他位置是二次剩余，即对矩阵第2行、第1列的查询信息的属性为，利用CPIR计算值。

3 基于Spark的最近邻查询算法PCPIR-V

尽管CPIR-V实现了空间的最近邻隐私保护查询算法，可以有效地保护用户的查询隐私，但是，CPIR-V算法有以下的不足。

1) CPIR-V需要对整个矩阵进行扫描和计算，CPU花费比较大。矩阵中存在许多重复大整数乘法运算，计算量很大，当数据库达到一定数量级的时候，单机环境已经无法应对，计算时间将无法满足用户的需求。

2) CPIR-V算法由于空间分布的特性，进行矩阵扫描和计算的时候有很多重复计算，重复计算占用大量的计算资源，从而降低了CPIR-V的计算效率。

并行计算的原理要求计算结果是可分解的且互相之间是没有影响的。文献[1,11]介绍了CPIR-V的并行计算原理：基于CPIR-V的隐私保护近邻查询过程中，每个值的计算仅需要矩阵中的一行数据和向量，不同的值结果互不影响。因此，基于这一特性，将矩阵进行水平划分，实现CPIR-V的并行计算。

因此，本文采用Spark作为计算平台，提出基于Spark实现并行的CPIR-V最近邻查询算法PCPIR-V，对CPIR-V基于Spark和HBase进行重新设计，并根据数据的特性，实现包括Row级并行和Bit级并行2种策略。基于Row的并行策略有数据分布不均匀的情况，特别是在网格划分过小的情况下无法充分利用集群的资源进行计算，造成集群资源的浪费，针对此问题，提出了一种基于更加细粒度的并行策略——基于Bit的并行策略。

3.1 数据组织格式

通过对HBase RowKey的设计达到数据在HRegionServer上的均匀分布，其中，数据存储的格式为每个RowKey对应PCIR-V矩阵中的一行，RowKey以逆序的行号对齐存储，列名按照列号名称对齐存储。具体如表1所示。

表1 PCIR-V信息表结构

3.2 并行策略

PCPIR-V采用2种并行的策略，分别为基于Row的并行策略和基于Bit的并行策略。基于Row的并行策略是将数据中的每一行交给Spark的一个Task处理，图4(a)是基于Row的并行策略的PCPIR-V算法，左侧CPIR矩阵每个网格存储2 bit的信息，实际情况远不止这些，可能是几百个或者几千个双精度的经纬度数值。PCPIR-V算法将每一行的数据均单独交给Spark的一个Task进行CPIR计算，将单机CPIR-V算法并行化，提高了计算的效率，并最终把每行的结果返回到客户端。但这种并行策略在网格内数据量较多的情况下，由于每一行是并行的最小单位，导致有些Task没有分配到任务，因此，存在集群计算资源分布不均的情况，无法充分利用集群的计算资源。

基于Bit的并行策略通过将每一行按照Bit进行再次分组，并按照当前的集群资源的状况（包括当前Executer的个数和每个Executer最多运行的Task的个数）确定分组的个数，从而提高集群的利用率。图4(b)是基于Bit并行策略的示意，通过对每一行的内容继续细分，组划分的个数可以通过集群现有资源进行确定。选取策略是将集群空闲的CPU核心数目作为分组个数，每一组可能会被分到1个或多个比特，图4(a)中为1 bit。

图4 PCIPR-V并行优化策略

通过对计算的有效并行，可以使CPIR计算的效率随着机器节点的增长，性能不断提高，且可以适用于大规模的数据量。PCPIR-V不仅可以将数据均匀地存储，而且可以将数据的CPIR计算进行均衡地分配，特别是基于Bit的并行策略，可以将并行的粒度更加细分，节点的CPIR计算更加均衡。

PCPIR-V算法读取HBase中的数据并缓存到Spark的分布式弹性数据集中，由于数据在HBase中是分片存储的，PCPIR-V会通过RowKey的设计策略使数据在集群中均匀地分配到各个HRegion，所以，分片数据在弹性分布式数据集（RDD，resilient distributed dataset）中存储也被分散到各个Partition，通过Spark的BlockManager将CPIR计算分配到各个节点，从而降低计算的时间，提高效率。由图5可知，通过对RowKey的设计将每行数据均匀地分布在各个HRegion Server的HRegion上，之后Spark通过对HBase的读取将数据存放在RDD的各个Partition中供Spark进行CPIR计算，Executer为每个Partition启动一个Task执行CPIR计算，PCPIR-V的计算通过RDD的转换[16]（Transform）和动作[16]（Action）2步执行，其中，Action代表一个Spark任务的结束。如果在内存足够的情况下，Transform是完全在内存中进行的，相对MapReduce有较大的提高。PCPIR-V的主要计算是在Transform中进行的，最后通过Action输出结果。

图5 基于Spark的PCIPR-V架构

3.3 PCPIR-V算法

PCPIR-V算法首先对文件中的空间位置信息进行读取，生成Voronoi图，然后，通过Voronoi图和网格相交或者包含的位置关系，求出每个网格的潜在最近邻点的矩阵存放到数组中，之后将预处理的矩阵数据存放在HBase中，数据通过RowKey设计被均衡分配到各个HRegion中，并由各个节点的HRegion Server管理，从而可以提高Spark从HBase获取的效率。

PCPIR-V基于矩阵Row的并行策略和基于Bit的并行策略算法描述如算法1所示。

算法1 PCPIR-V服务端算法

输入：查询(12…y)，网格划分数目，，并行策略

输出：CPIR计算结果Array()

1) 根据网格划分获取CPIR矩阵数据缓存到RDD；

2) if() then

3) 对RDD中的CPIR矩阵数据按照行进行分组；

4) end if

5) if()then

6) 获得当前集群分配的CPU数量；

7) 将每一行数据分为组，即总共组；

8)end if

9) Spark对每个分组进行CPIR计算获得；

10) Spark将结果聚合发送到客户端；

11) 结束。

算法1中，步骤1) 首先通过客户端传来的参数，计算出HBase中存储的行和列的最大值，并通过RowKey最大值对HBase进行扫描获得矩阵，HBase每一行作为RDD的一条记录；步骤2)~4)是算法按照给定方式进行分组，基于Row的并行策略是按照每一行对数据进行分组；步骤5)~8)是策略为Bit时的分组情况，首先，根据当前集群分配计算资源的数量，对每一行进行分组，分组方式为取模，为查询序列的个数，主要是通过Spark的flatMap和组数量的参数对每一行的内容进行分组并形成新的条目；步骤9)~10)通过Spark的map对每个小分组进行CPIR计算，并将每一组的结果返回。

3.4 PCPIR-V算法性能分析

由于CPIR算法需要对整个数据空间进行扫描和计算，因此，计算代价和总的数据量成正比。PCIR-V算法通过采用Spark集群技术将CPIR-V进行重新设计，通过HBase的高速列存储和Spark基于内存的并行计算提高CPIR计算的速度，并且拥有很高的扩展性。PCIR-V的服务端代价模型可用式(5)表示。

其中，为PCPIR-V算法的总代价，为从HBase中读取的代价，此代价可以通过RDD的cache功能减免，为Spark的RDD进行转换的时间，是Spark的RDD进行动作的时间。其中，与HBase集群的数量、数据的分布和网络都有关系，随着查询数量的增大而增长，并随着HBase集群规模的增大而减小，而和均随着节点的CPU核心数的增多而降低，和可以进一步用式(6)和式(7)表示，其中，为CPU的核心数量，代表时间随CPU增大而减小的系数。

3.5 基于Spark的CPIR-V的缓存优化

CPIR-V算法由于空间分布的关系[1]，相邻网格的潜在最近邻点存在较多的冗余点，因此，在进行CPIR计算的过程中，有较多重复的计算和比较。

图3体现出了CPIR-V相邻的网格中存在较多重复的潜在最近邻，这是CPIR-V的空间对象分布相邻导致的。当重复过多的时候，CPIR的计算就会出现很多冗余计算，因此，对数据的预处理十分重要，需要对数据进行精简和缓存策略来提高数据的计算效率。PCPIR-V算法由于是CPIR基于Spark的并行化设计的方法，所以，存在同样的问题，虽然通过并行使问题得到了解决，但还是存在冗余计算及计算资源的浪费，因此，需要对计算数据进行预处理和基于Spark的特性进行优化，从而减少冗余计算。图6(a)展示了CPIR基本的计算方法，按照式(1)的计算方式，的计算结果为1=1×2×3×4×5，2=2×3×6，3=2×6，4=1×2×3×4，5=2×3×6，6=2×6，可以看出2×3计算了4次，2×6计算了4次，1×2×3×4计算了2次，2×3×6计算了2次，即存在很多冗余计算，如果每次都重复地计算，由于是大整数的乘法，将急剧消耗集群的计算资源。因此，需要对数据进行处理和采用缓存进行优化以解决冗余计算的问题。

图6 PCPIR-V优化算法架构

3.5.1 PCIPR-V缓存优化算法

不同于文献[1]中的关联规则方法，本文提出一种基于聚类和二进制交集的缓存优化方法，并通过Spark集群节点的特性将缓存分布式存储，提高计算速度。该方法将隐私查询分为2个阶段：数据预处理阶段和在线缓存查询阶段。其中，数据预处理阶段分为2个小的步骤：CPIR数据聚类和缓存二元组生成。具体过程如下。

1) 将二进制的数组作为聚类的条目，如图6(b)中的第一行的数据为111110序列，利用均值聚类算法对数据库中所有的二进制数组进行聚类，对于这种二进制0或1的数据，本文提出一种优化距离和聚类中心的计算方式，从而适用于将位值大部分相同的记录聚集到一起的情况，为了适用于二进制0或1形式的聚类，设计一个新的距离和聚类中心的计算方法，新的计算方式如式(8)、式(9)所示。假设通过公式将类别分为类，其中，，代表数据矩阵中任意2行数据的二进制数组。为四舍五入函数，为某类中的一列中的二进制的数值，代表列数，为本类的元素个数，c代表每一列的平均值，则（1,2,…,c）为这一类的中心，其中，为CPIR矩阵的列数。以=111110，=111100为例，式(8)计算如下，首先，计算^=111100，（^）=4，则。若，为同一类，且本类中只有，2个元素，则计算为，其他的计算方式类似。

通过-均值聚类算法，用式(8)、式(9)的距离公式和聚类中心计算公式对数据库所有的数据聚为类，的取值与集群节点个数相同，这样就能保证相似度较高的二进制序列都在一类，并为每一类都标记上标签。

2) 分别对每一类中的所有数据相互进行判断，满足式(10)的条目添加到本类待缓存的map中，为id，其中，是一个阈值，表示2条记录，同时为1位数的最小个数为，其中，的取值规则为：满足个大整数相乘的时间大于一次内存查表时间条件的最小取值。如果满足下列条件则将，中为1的部分置为0，分别变为，并将这2条记录分别以一个二元组的形式保存，如，其中，叫作共享差，叫作共享基。如果每条记录产生了多个二元组，则选择最小的进行保存。

3) 通过Spark将不同类别划分到不同节点上运行，并将每一类的待缓存数据优先计算，之后再对二元组进行计算，其中，所需要计算的值均可以从节点的本地缓存中获得，从而实现计算的共享，并且每个节点的运算都是并行执行的，大大减少了计算代价，提高了计算的效率。

图6(b)的PCPIR计算框架展示了本优化算法的基本过程。首先，将数据聚类，采用式(8)和式(9)，将所有数据聚为1，2两类，然后将这两类分发到相同的节点并分别进行二元组转换，对类内的每一条记录都互相进行判断，如果满足式(10)的条件，则生成一个新的二元组。二元组的第1个元素为共享差，第2个位置为共享基，共享基为2条记录取交后的编码，图6中的60代表111100的编码，代表2个1类的重复为1的位置为前4位，其中，如果一条记录有多条重复的情况，则以最大的为准。共享差为将共享基为1的位置0所得的二进制数据，例如，图6中1类的第一行数据为111110，将111100为1的位置置0后为000000。最后，通过将不同类的二元组发送给Spark的不同节点进行执行，首先，对二元组的共享基进行计算，放入到本节点的cache中，之后，再对二元组的共享差进行计算。由于共享差0的部分不需要进行大整数相乘计算，而共享基的位置已经存放到缓存中，所以，计算不仅可以分配到各个节点，而且能提高计算效率并有效地减少重复计算。

表2 PCIR-V实验数据参数

算法2 二进制-均值聚类算法

输入：集群节点个数，CPIR-V数据

输出：类别标签

1) 随机选择条数据作为初始聚类中心；

2) 对于每条数据使用式(8)计算与每个聚类中心的距离，并将该条数据并入距离最近的中心；

3) 对于每一类按照式(9)重新计算聚类中心；

4) 如果聚类中心没有发生改变则结束，否则跳到2)；

5) 结束。

算法2中，步骤1) 首先从数据集合中随机选择条数据作为初始的聚类中心，其中，的取值为Spark集群启动Executer节点个数，每一类均有自己的缓存数据，这样做可以将更加相似的记录聚集到一起，缓存的命中率会更高；步骤2) 对所有数据与各类聚类中心进行距离的计算，距离公式采用式(8)并将每条记录分配到距离最近的中心，即式(9)取值最小的中心；步骤3) 对已经进行聚类完毕的类别分别计算聚类中心，使用式(10)；最后，步骤4) 对收敛条件进行判断，收敛条件为进行再次聚类的聚类中心较之前的中心没有改变。

算法3 数据简化和待缓存数据生成算法

输入：其中一类的数据，数据的条数，阈值

输出：简化数据和待缓存数据的二元组

1) 声明临时数组变量，；

2) for（0;;）

3) for（0;;）

4) if（!）

5)[][][]

6) if（（[]））

7)[]（[]）[]）；

8) end if

9) end if

10) end for

11) 从中选取最小的[]，[]=([],([j]))；

12) end for

13) 结束。

算法3中，步骤2)~12)是对类内记录的相互判断；步骤4)是排除与本身比较的情况；步骤5) 计算2条记录之间重复为1的结果；步骤6) 按照式(8)进行判断，满足才进行记录；步骤11) 是在第一层循环完毕后，从中选取一个重复为1最多的元素，添加到二元组中，同时二元组第2个元素为重复为1部分的编码。算法3对应图6中的第2个步骤预处理的数据可以通过Spark集群进行查询。

算法4 缓存优化PCPIR-V查询服务端算法

输入：查询(12…y)，网格划分数目，

输出：CPIR计算结果Array()

1) 将二元组信息缓存到RDD；

2) 对RDD中的二元组进行聚合，获得(,())的形式；

3) 通过查询对(,())中对应的数据进行CPIR计算，缓存到RDD；

4) 利用缓存的数据和计算()的CPIR结果，并缓存到RDD；

5) 聚合数据发回客户端；

6) 结束。

算法4中，步骤1) 首先将前2步生成的二元组数据读入到Spark的RDD中；步骤2) 按照缓存对二元组进行聚合（groupByKey）生成一个新的二元组（，（）），这样保证在RDD中是唯一的；步骤3) 则对进行解码并同查询进行CPIR计算得出结果，步骤4) 对剩下的相乘得到(())的序列。算法4展示了图6中Spark进行并行计算的过程：首先，对共享基缓存进行计算；然后，对整个数据进行计算；最后，对数据进行合并后将结果返回客户端。

3.5.2 PCIPR-V缓存优化算法性能分析

PCPIR-V缓存优化算法通过3个步骤解决了PCPIR-V中由于空间分布特性导致的过多冗余计算问题，第1步对数据进行聚类，是为了将相近的数据聚集在一起，为第2个步骤提供方便；只需要在类内比较就可以找到相似度最高的记录；最后，通过Spark对缓存数据进行优先计算，并对缓存数据进行重用。

PCIPR-V缓存优化算法的主要性能优化在于可以将各条记录内大整数乘法的计算进行缓存，从而提高计算效率。缓存优化算法的代价模型可以用式(11)表示。

4 实验结果与分析

本实验采用的服务平台为IBM xSeries System 3650M4，集群共有5个节点，每个节点详细配置如下。

CPU：2×Xeon E5-2620 CPU（每个有6核心×2线程）

内存：32 GB；

硬盘：5 TB, 10 000 rpm, raid 5；

操作系统：CentOS 6.4；

开发工具：GNU Toolkits（G++、GDB）、Make、Vim，JDK等。

实验所用开发语言为标准C++、Java、Scala语言，使用合成数据和真实数据进行实验并对实验结果进行分析，由于本文PCPIR-V与相关研究成果的并行化思路是不同维度且为互为补充的关系，同时未发现同一CPU并行化维度的相关成果，因此，对比了CPIR-V和PCPIR-V，验证云环境下PCPIR-V的查询性能。合成数据采用生成均匀分布和高斯分布2种分布方式，其中，高斯分布满足(,)×(1,1,0,0,1)。真实数据来自加利福尼亚的Sequoia[21]。本文的数据取值范围为1 046 435×1 929 615，其中，、坐标类型都为int型，本文所指网格划分为，是指将空间划分为×的均匀网格。本文C++所使用的大数计算库为GMP[22]，Java为JDK自带的大整数计算工具。其中，CPU核心数量指的是虚拟核心的数量，即操作系统级别上的核心数量，而非物理核心数量，其中，阈值的取值规则为满足个大整数相乘的时间大于一次内存查表时间条件的最小取值，通过实验得出，当时，大整数相乘的耗时超过了内存查表时间，因此，本文取值为3。阈值的最优解问题将在未来工作中进行研究。

4.1 PCPIR-V不同数据服务端时间

图7为不同数据在不同网络划分下的服务端时间，其中，图7(a)~图7(c)是利用式(2)进行的网络划分，图7(d)是利用式(3)进行的网格划分。图7(a)为基于Spark的并行CPIR-V算法（PCPIR-V）Row并行和Bit并行策略与未优化的CPIR-V算法在不同网格划分下使用不同数据服务端计算时间的对比，其中，PCPIR-V-R为基于Row并行策略的PCPIR-V算法，PCPIR-V-B为基于Bit并行策略的PCPIR-V算法。从图7(a)中可以看出，3种算法都是随着网格划分的增大而变慢，这是由于CPIR-V的矩阵列数与网格列数是一致的，网格越多说明CPIR-V的矩阵越多，需要相乘的大整数也就越多，时间也就越长。在网格数目为10的时候，3种算法的计算时间基本是在同一个数量级上，这是因为在网格划分太小的情况下，PCPIR-V启动的任务是有限的，不能很好地发挥并行的优势，且在计算的过程可能会产生节点间通信的代价，所以，基于行并行的PCPIR-V算法在刚开始网格划分小的时候甚至超过单机的CPIR-V算法计算时间，在对PCPIR-V进行Bit并行策略的优化之后，可以充分利用集群资源进行并行计算，在网格较小时，相对基于行的PCPIR-V有很大的提升。随着网格数目的增长，PCPIR-V相对传统的CPIR-V已经有明显的优势，在网格数目在400的时候，大概有1个数量级的提升，且随网格增长，时间增长的趋势比较平缓，相对CPIR-V随网格增长计算时间增长较快。

图7(b)为在高斯分布基于Spark的并行CPIR-V算法（PCPIR-V）Row并行和Bit并行策略对比。不同网格划分对高斯分布中最近邻查询影响的变化趋势与均匀分布相同，但是高斯分布的服务端的计算时间相对于均匀分布有明显提高，这是由于高斯数据中每个网格中潜在最近邻数量的最大值远远超过均匀分布，从而导致计算数和返回的QR、QNR数目增大，最终导致时间增大。

图7(c)为在真实数据中数据中基于Spark的并行CPIR-V算法（PCPIR-V）Row并行和Bit并行策略与未优化的CPIR-V算法在不同网格划分下服务端计算时间对比图。虽然潜在最近邻的最大值很大，但是潜在最近邻中的0 bit比较多，所以，计算时间相对均匀分布数据和高斯分布数据小很多。

图7(d)展示了利用式(3)不同网格划分对均匀分布数据集最近邻查询的影响，从图7(d)中可以看出3种算法都随着网格数量的增加而增大，基本的变化趋势和图7(a)基本相同，但是时间与图7(a)相比都有所增大，这是由于在计算矩阵中存在大量的0 bit，造成大量大整数的平方计算，从而增加了计算代价。对于CPIR-V来说，影响非常大，而PCPIR-V就增长不明显，仍可以保证良好的性能，这是由于基于Spark的PCPIR-V算法有比较高的扩展性，通过将复杂的计算分配到各个节点，从而达到高性能的计算水平，所以，当计算量急剧增大时，对CPIR-V的影响很大，但是对PCPIR-V却较小。

4.2 不同模量服务器时间

图8为基于Spark的并行CPIR-V算法（PCPIR- V）Bit并行策略与未优化的CPIR-V算法在不同模量下服务端计算时间对比。

从图8中可以看出，随着模量的不断增加，服务端的计算时间也会随之增加，其中，PCPIR-V-B的增长速度较为平缓，而CPIR-V增长速度比较快。这说明在集群资源充足的情况下，模量的增长不会对PCPIR-V-B算法造成过大的影响。

4.3 不同CPU个数服务端时间

图9显示PCPIR-V算法在不同CPU核心数量下计算时间的变化，实验Spark集群共有5个服务器节点，应用到YARN集群的计算资源共有100个虚拟CPU核心。实验结果表明，随着CPU数量的增加，计算时间也在不断锐减。当达到一定程度后，速度开始变缓，这是因为CPU核心数量越多，算法的并行度就越大，计算时间就越少，但核心数量在达到一定程度时开始变缓，图9中核心数为40个，这说明在本组实验数据和实验条件下CPU核心数量超过40个的时候，主要瓶颈已经从CPU转到节点之间通信和交互。

4.4 基于Spark最近邻CPIR缓存优化服务端时间

本实验主要对服务端的算法做出优化，减少了数据的冗余计算，实现了计算共享。因此，只对服务端的算法做出实验分析，分别针对不同数据集和不同网格划分下的实验做出分析。

图10分别是缓存优化的PCPIR-V和PCPIR-V在均匀分布数据集、高斯分布数据集和真实数据集下，不同网格划分下的服务端计算时间的对比。其中，PCPIR-V-CA为基于缓存优化的PCPIR-V算法。

从3个实验结果对比来看，真实数据集和高斯数据集要比均匀数据集合高出很多，这是由于高斯数据和真实数据的集中分布导致的，越集中分布的数据，可能存在的重复计算也就越多，这样缓存优化的效果也就越好。这2种算法都会在网格刚开始的时候有一个较大的峰值，之后降低，这是因为在起初网格划分较小的时候，网格内的潜在最近邻较多，这样数据就不能很好地分配到各个节点分布式执行，因此导致计算速度慢，缓存的优化效果也不好。缓存的效果在网格划分小的时候不明显，这是因为开始的主要瓶颈不是在大整数的计算上而是判断当前位是否为1上，因此，缓存的优化都是从网格数目在100之后才开始显著地提高，特别是高斯分布的数据和真实数据，主要是因为它们存在更多的重复计算。

5 结束语

针对面向大数据的隐私保护查询问题，本文以Spark计算框架为基础，利用CPIR高保护强度，在HBase上设计了数据的组织格式，RDD实现了并行CPIR-V最近邻查询算法（PCPIR-V），并提出2种并行策略。针对PCPIR-V算法中冗余计算的问题，提出了基于缓存的PCPIR-V算法，通过使用聚类和二进制交集方法对数据进行了预处理，减少了冗余计算，提高了计算的效率。最后，通过对实验进行分析，在40个核心范围内，基于Row和Bit并行策略的PCPIR具有良好的加速比，PCPIR-V缓存优化技术计算时间与朴素PCPIR-V时间相比，平均降低了20%。

[1] 王璐, 孟小峰. 位置大数据隐私保护研究综述[J]. 软件学报, 2014, 25(4):693-712.

WANG L, MENG X F. Position big data privacy protection research review[J]. Journal of Software, 2014, 25(4) : 693-712.

[2] NIU B, LI Q, ZHU X, et al. Achieving-anonymity in privacy-aware location-based services[C]//2014 IEEE Conference on Computer Communications(Infocom). c2014: 754-762.

[3] ZHOU C, MA C, YANG S, et al. A location privacy preserving method based on sensitive diversity for LBS[M]//Network and Parallel Computing. Berlin: Springer, 2014: 409-422.

[4] CICEK A E, NERGIZ M E, SAYGIN Y. Ensuring location diversity in privacy-preserving spatio-temporal data publishing[J]. The International Journal on Very Large Data Bases, 2014, 23(4): 609-625.

[5] PAN X, XU J, MENG X. Protecting location privacy against location-dependent attacks in mobile services[J]. IEEE Transactions on Knowledge and Data Engineering, 2012, 24(8): 1506-1519.

[6] ŠIKŠNYS L, THOMSEN J R, ŠALTENIS S, et al. A location privacy aware friend locator[M]. Berlin:Springer, 2009: 405-410.

[7] CHOW C Y, MOKBEL M F, BAO J, et al. Query-aware location anonymization for road networks[J]. Geoinformatica, 2011, 15(3): 571-607.

[8] CHOW C Y, MOKBEL M F, LEONG H V. On efficient and scalable support of continuous queries in mobile peer-to-peer environments[J]. IEEE Transactions on Mobile Computing, 2011, 10(10): 1473-1487.

[9] AMBAINIS A. Upper bound on the communication complexity of private information retrieval[M]. Berlin: Springer, 1997: 401-407.

[10] KUSHILEVITZ E, OSTROVSKY R. Replication is not needed: single database, computationally-private information retrieval[C]// Annual Symposium on Foundations of Computer Science. c1997: 364-373.

[11] GHINITA G, KALNIS P, KHOSHGOZARAN A, et al. Private queries in location based services: anonymizers are not necessary[C]//The ACM Sigmod International Conference on Management of Data. c2008:121-132.

[12] FUNG E, KELLARIS G, PAPADIAS D. Combining differential privacy and pir for efficient strong location privacy[M]//Advances in Spatial and Temporal Databases. Berlin: Springer, 2015: 295-312.

[13] YU M, YANG K, WEI L, et al. Practical private information retrieval supporting keyword search in the cloud[C]// 2014 6th International Conference on Wireless Communications and Signal Processing (WCSP). c2014:1-6

[14] 张峰, 倪巍伟. 基于伪随机数加密的保护位置隐私近邻查询方法[J]. 华东师范大学学报(自然科学版), 2015(5):128-142.

ZHANG F, NI W W. Protect the location privacy neighbor query methods based on the pseudo random number of encryption [J]. Journal of East China Normal University( Natural Science Edition), 2015(5): 128-142.

[15] SHVACHKO K, KUANG H, RADIA S, et al. The Hadoop distributed file system[C]// The 26th Symposium on Mass Storage Systems and Technologies (MSST), IEEE. c2010:1-10.

[16] ZAHARIA M, CHOWDHURY M, DAS T, et al. Resilient distributed datasets: a fault-tolerant abstraction for in-memory cluster computing[C]//Usenix Conference on Networked Systems Design and Implementation (NSDI).c2012:141-146.

[17] PAPADOPOULOS S, BAKIRAS S, PAPADIAS D. pCloud: a distributed system for practical PIR[J]. IEEE Transactions on Dependable and Secure Computing, 2012, 9(1): 115-127.

[18] MAYBERRY T, BLASS E O, CHAN A H. PIRMAP: efficient private information retrieval for MapReduce[M]//Financial Cryptography and Data Security. Berlin: Springer, 2013: 371-385.

[19] BLASS E O, DI P R, MOLVA R, et al. PRISM–privacy-preserving search in MapReduce[M]//Privacy Enhancing Technologies. Berlin: Springer, 2012: 180-200.

[20] 刘金义, 刘爽. Voronoi 图应用综述[J]. 工程图学学报, 2004, 25(2): 125-132.

LIU J Y, LIU S. Voronoi diagram application review[J]. Journal of Engineering Graphics, 2004, 25(2): 125-132.

[21] ASC sequoia benchmark codes[EB/OL]. https://asc.llnl.gov/sequoia/ benchmarks/.

[22] GMP[EB/OL]. http://gmplib.org/.

PCPIR-V: parallel privacy protected algorithms for nearest neighbor query based on Spark

DENG Shi-zhuo, YAO Ji-tao, WANG Bo-tao, CHEN Yue-mei, YUAN Ye, LI Yan-hui, WANG Guo-ren

(College of Computer Science and Engineering, Northeastern University, Shenyang 110819, China)

To address the low-efficiency problem for query privacy protection on big data, parallel CPIR-V (PCPIR-V), which had a high level of privacy protection for nearest neighbor query, was presented and implemented based on spark. Two parallel strategies for PCPIR-V, Row strategy and Bit strategy, were proposed. To avoid redundant multiplications, the repeated products were cached based on a clustering technique while computing CPIR on Spark. According to the evaluation results of PCPIR-V on three datasets, the scalablity of PCPIR-V is good until the number of core is larger than 40. The cost of PCPIR-V with the method of caching partial multiplication results is reduced by 20% averagely.

query privacy protection, computational private information retrieval, Spark, location based service

The National Natural Science Foundation of China (No.61173030, No.61272181, No.61272182, No.61332014, No.61370154, No.61332006）

TP309

A

10.11959/j.issn.2096-109x.2016.00057

2016-03-18；

2016-04-25。

王波涛，wangbotao@cse.neu.edu.cn

国家自然科学基金资助项目（No.61173030, No.61272181, No.61272182, No.61332014, No.61370154，No.61332006）

邓诗卓（1990-），女，辽宁凌源人，东北大学博士生，主要研究方向为大数据、云计算、位置隐私保护。

姚继涛（1990-），男，山东泰安人，东北大学硕士生，主要研究方向为大数据、云计算、隐私保护。

王波涛（1968-），男，山东福山人，东北大学教授、博士生导师，主要研究方向为隐私保护、大数据、云计算、基于位置服务、数据流管理系统、发布/订阅系统、移动数据库。

陈月梅（1991-），女，湖北大冶人，东北大学硕士生，主要研究方向为隐私保护、大数据、数据管理。

袁野（1981-），男，辽宁沈阳人，东北大学教授，主要研究方向为云计算、大数据管理、P2P计算。

李艳辉（1989-），女，黑龙江讷河人，东北大学博士生，主要研究方向为查询处理、隐私保护。

王国仁（1966-），男，湖北黄冈人，东北大学教授、博士生导师，主要研究方向为XML数据管理、查询处理优化、高维数据索引、分布式数据库、隐私保护。