鄧詩卓，姚繼濤，王波濤，陳月梅，袁野，李艷輝，王國仁

?

PCPIR-V：基于Spark的并行隱私保護近鄰查詢算法

鄧詩卓，姚繼濤，王波濤，陳月梅，袁野，李艷輝，王國仁

（東北大學計算機科學與工程學院，遼寧沈陽 110819）

針對面向大數據的隱私保護查詢效率低問題，利用CPIR保護程度高，實現了基于Spark的并行CPIR空間近鄰查詢隱私保護算法PCPIR-V，提出了基于Row和Bit的并行策略，同時提出并實現了基于聚類的PCPIR-V的緩存優(yōu)化技術。利用均勻分布、高斯分布和真實數據對PCPIR-V進行了測試驗證，在40個核心范圍內，PCPIR-V具有良好的擴展性，PCPIR-V緩存優(yōu)化技術計算時間與樸素PCPIR-V時間相比，平均減少了20%。

查詢隱私保護；基于計算能力的隱私信息檢索；Spark；基于位置服務

1 引言

科學技術和互聯(lián)網的快速發(fā)展促使數據爆炸式增長，在大數據時代，每天的生活和生產環(huán)境都會產生大規(guī)模海量的數據信息，其中，伴隨著多樣定位手段、用戶終端及廣泛通信手段的出現，基于位置的服務[1]（LBS, location based services）已經成為當前研究的熱點并且產生了大量基于位置的空間數據。LBS已經深入到人們的日常生活中，例如，城市基礎交通設施優(yōu)化計劃和基于用戶行走路線的智能商店布局決策、智能路線導航（如Google Map等）、基于位置的社交服務（如WeChat、Foursquare等）、基于位置的游戲和娛樂（如Google Ingress等）。隨著LBS的用戶大量增加，用戶在享用位置服務的同時，其在互聯(lián)網上的行為數據存在泄露的風險。隨著用戶對個人隱私需求的提高，用戶希望在發(fā)起位置查詢從而獲得服務的過程中，用戶查詢信息的隱私能夠得到保護，因此，基于用戶隱私保護的大數據需求亟需實現。

單點位置信息的隱私查詢保護的典型手段主要分為3類：干擾技術[2~4]、區(qū)域覆蓋（隱匿空間技術）[5~8]、基于密碼學的保護方式。干擾技術和區(qū)域覆蓋都是通過損失可用性或隱私性的方式來實現的，而密碼學的隱私保護方式，可以比較好地達到可用性和隱私性的平衡，密碼學的隱私查詢保護技術較有代表性的是隱私信息檢索（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），在這個前提下，保證攻擊者不能通過區(qū)分與二次非剩余來區(qū)別用戶對不同數據項的訪問。

如圖1所示，CPIR待查詢數據庫[11]是一個4×4的數據矩陣，表示矩陣中的某個元素，矩陣的每個元素為用戶所要查詢的內容，查詢的過程是，移動用戶首先隨機產生2個大質數，，根據查詢內容位置信息生成包含的二次剩余與二次非剩余集組成查詢信息，其中，二次非剩余，其余為二次剩余，服務器會利用式(1)計算中每一行z值，其中，由式(2)和式(3)計算，式(2)是根據二次剩余相乘基本性質得出的。

近年來，基于PIR的近鄰查詢方面，文獻[12]針對大量興趣點（POI，points of interest）查詢代價問題，提出adaptive query plan，至少保證預定比例的查詢結果正確，但是adaptive query plan依賴真實用戶行為與之前發(fā)布查詢的階段性變化統(tǒng)計，為了避免違反保密性，結合-differential privacy和PIR構成計算框架；基于PIR的關鍵字搜索方面，文獻[13]中提出一種機制KSPIR，通過用戶指定的彈性隱私以及預算來最小化通信和計算代價，該方法是檢索代價和隱私強度（degree）之間的一個折中，實現關鍵字檢索；文獻[14]利用偽隨機數規(guī)則隨機生成排列數序列，偽隨機數加密規(guī)則能夠模糊和加密查詢結果。

云計算是大數據處理的技術支撐，如分布式計算框架Hadoop[15]、Spark[16]、Storm等。Hadoop中MapReduce側重于離線數據分布式批處理，Strom側重于實時流分布式計算，而Spark側重基于內存計算，Spark的快速發(fā)展和使用，進一步提高了大數據處理的效率，特別是在迭代計算和快速計算上相對于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協(xié)議，主要用于檢索云上的大文件（large files）。pCloud是基于GR-PIR協(xié)議實現數據庫分區(qū)并行的；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數量最多為基準，不足的網格進行填充。當用戶發(fā)起查詢的時候，首先通過計算獲取查詢點所在的網格，隨機生成2個大質數1，2，對進行二次剩余的計算，生成圖3中的查詢，其中，查詢區(qū)域的網格對應的是的二次非剩余，其他位置是二次剩余，即對矩陣第2行、第1列的查詢信息的屬性為，利用CPIR計算值。

3 基于Spark的最近鄰查詢算法PCPIR-V

盡管CPIR-V實現了空間的最近鄰隱私保護查詢算法，可以有效地保護用戶的查詢隱私，但是，CPIR-V算法有以下的不足。

1) CPIR-V需要對整個矩陣進行掃描和計算，CPU花費比較大。矩陣中存在許多重復大整數乘法運算，計算量很大，當數據庫達到一定數量級的時候，單機環(huán)境已經無法應對，計算時間將無法滿足用戶的需求。

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種策略?；赗ow的并行策略有數據分布不均勻的情況，特別是在網格劃分過小的情況下無法充分利用集群的資源進行計算，造成集群資源的浪費，針對此問題，提出了一種基于更加細粒度的并行策略——基于Bit的并行策略。

3.1 數據組織格式

通過對HBase RowKey的設計達到數據在HRegionServer上的均勻分布，其中，數據存儲的格式為每個RowKey對應PCIR-V矩陣中的一行，RowKey以逆序的行號對齊存儲，列名按照列號名稱對齊存儲。具體如表1所示。

表1 PCIR-V信息表結構

3.2 并行策略

PCPIR-V采用2種并行的策略，分別為基于Row的并行策略和基于Bit的并行策略?；赗ow的并行策略是將數據中的每一行交給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并行策略的示意，通過對每一行的內容繼續(xù)細分，組劃分的個數可以通過集群現有資源進行確定。選取策略是將集群空閑的CPU核心數目作為分組個數，每一組可能會被分到1個或多個比特，圖4(a)中為1 bit。

圖4 PCIPR-V并行優(yōu)化策略

通過對計算的有效并行，可以使CPIR計算的效率隨著機器節(jié)點的增長，性能不斷提高，且可以適用于大規(guī)模的數據量。PCPIR-V不僅可以將數據均勻地存儲，而且可以將數據的CPIR計算進行均衡地分配，特別是基于Bit的并行策略，可以將并行的粒度更加細分，節(jié)點的CPIR計算更加均衡。

PCPIR-V算法讀取HBase中的數據并緩存到Spark的分布式彈性數據集中，由于數據在HBase中是分片存儲的，PCPIR-V會通過RowKey的設計策略使數據在集群中均勻地分配到各個HRegion，所以，分片數據在彈性分布式數據集（RDD，resilient distributed dataset）中存儲也被分散到各個Partition，通過Spark的BlockManager將CPIR計算分配到各個節(jié)點，從而降低計算的時間，提高效率。由圖5可知，通過對RowKey的設計將每行數據均勻地分布在各個HRegion Server的HRegion上，之后Spark通過對HBase的讀取將數據存放在RDD的各個Partition中供Spark進行CPIR計算，Executer為每個Partition啟動一個Task執(zhí)行CPIR計算，PCPIR-V的計算通過RDD的轉換[16]（Transform）和動作[16]（Action）2步執(zhí)行，其中，Action代表一個Spark任務的結束。如果在內存足夠的情況下，Transform是完全在內存中進行的，相對MapReduce有較大的提高。PCPIR-V的主要計算是在Transform中進行的，最后通過Action輸出結果。

圖5 基于Spark的PCIPR-V架構

3.3 PCPIR-V算法

PCPIR-V算法首先對文件中的空間位置信息進行讀取，生成Voronoi圖，然后，通過Voronoi圖和網格相交或者包含的位置關系，求出每個網格的潛在最近鄰點的矩陣存放到數組中，之后將預處理的矩陣數據存放在HBase中，數據通過RowKey設計被均衡分配到各個HRegion中，并由各個節(jié)點的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將結果聚合發(fā)送到客戶端；

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集群規(guī)模的增大而減小，而和均隨著節(jié)點的CPU核心數的增多而降低，和可以進一步用式(6)和式(7)表示，其中，為CPU的核心數量，代表時間隨CPU增大而減小的系數。

3.5 基于Spark的CPIR-V的緩存優(yōu)化

CPIR-V算法由于空間分布的關系[1]，相鄰網格的潛在最近鄰點存在較多的冗余點，因此，在進行CPIR計算的過程中，有較多重復的計算和比較。

圖3體現出了CPIR-V相鄰的網格中存在較多重復的潛在最近鄰，這是CPIR-V的空間對象分布相鄰導致的。當重復過多的時候，CPIR的計算就會出現很多冗余計算，因此，對數據的預處理十分重要，需要對數據進行精簡和緩存策略來提高數據的計算效率。PCPIR-V算法由于是CPIR基于Spark的并行化設計的方法，所以，存在同樣的問題，雖然通過并行使問題得到了解決，但還是存在冗余計算及計算資源的浪費，因此，需要對計算數據進行預處理和基于Spark的特性進行優(yōu)化，從而減少冗余計算。圖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次，即存在很多冗余計算，如果每次都重復地計算，由于是大整數的乘法，將急劇消耗集群的計算資源。因此，需要對數據進行處理和采用緩存進行優(yōu)化以解決冗余計算的問題。

圖6 PCPIR-V優(yōu)化算法架構

3.5.1 PCIPR-V緩存優(yōu)化算法

不同于文獻[1]中的關聯(lián)規(guī)則方法，本文提出一種基于聚類和二進制交集的緩存優(yōu)化方法，并通過Spark集群節(jié)點的特性將緩存分布式存儲，提高計算速度。該方法將隱私查詢分為2個階段：數據預處理階段和在線緩存查詢階段。其中，數據預處理階段分為2個小的步驟：CPIR數據聚類和緩存二元組生成。具體過程如下。

1) 將二進制的數組作為聚類的條目，如圖6(b)中的第一行的數據為111110序列，利用均值聚類算法對數據庫中所有的二進制數組進行聚類，對于這種二進制0或1的數據，本文提出一種優(yōu)化距離和聚類中心的計算方式，從而適用于將位值大部分相同的記錄聚集到一起的情況，為了適用于二進制0或1形式的聚類，設計一個新的距離和聚類中心的計算方法，新的計算方式如式(8)、式(9)所示。假設通過公式將類別分為類，其中，，代表數據矩陣中任意2行數據的二進制數組。為四舍五入函數，為某類中的一列中的二進制的數值，代表列數，為本類的元素個數，c代表每一列的平均值，則（1,2,…,c）為這一類的中心，其中，為CPIR矩陣的列數。以=111110，=111100為例，式(8)計算如下，首先，計算^=111100，（^）=4，則。若，為同一類，且本類中只有，2個元素，則計算為，其他的計算方式類似。

通過-均值聚類算法，用式(8)、式(9)的距離公式和聚類中心計算公式對數據庫所有的數據聚為類，的取值與集群節(jié)點個數相同，這樣就能保證相似度較高的二進制序列都在一類，并為每一類都標記上標簽。

2) 分別對每一類中的所有數據相互進行判斷，滿足式(10)的條目添加到本類待緩存的map中，為id，其中，是一個閾值，表示2條記錄，同時為1位數的最小個數為，其中，的取值規(guī)則為：滿足個大整數相乘的時間大于一次內存查表時間條件的最小取值。如果滿足下列條件則將，中為1的部分置為0，分別變?yōu)?，并將這2條記錄分別以一個二元組的形式保存，如，其中，叫作共享差，叫作共享基。如果每條記錄產生了多個二元組，則選擇最小的進行保存。

3) 通過Spark將不同類別劃分到不同節(jié)點上運行，并將每一類的待緩存數據優(yōu)先計算，之后再對二元組進行計算，其中，所需要計算的值均可以從節(jié)點的本地緩存中獲得，從而實現計算的共享，并且每個節(jié)點的運算都是并行執(zhí)行的，大大減少了計算代價，提高了計算的效率。

圖6(b)的PCPIR計算框架展示了本優(yōu)化算法的基本過程。首先，將數據聚類，采用式(8)和式(9)，將所有數據聚為1，2兩類，然后將這兩類分發(fā)到相同的節(jié)點并分別進行二元組轉換，對類內的每一條記錄都互相進行判斷，如果滿足式(10)的條件，則生成一個新的二元組。二元組的第1個元素為共享差，第2個位置為共享基，共享基為2條記錄取交后的編碼，圖6中的60代表111100的編碼，代表2個1類的重復為1的位置為前4位，其中，如果一條記錄有多條重復的情況，則以最大的為準。共享差為將共享基為1的位置0所得的二進制數據，例如，圖6中1類的第一行數據為111110，將111100為1的位置置0后為000000。最后，通過將不同類的二元組發(fā)送給Spark的不同節(jié)點進行執(zhí)行，首先，對二元組的共享基進行計算，放入到本節(jié)點的cache中，之后，再對二元組的共享差進行計算。由于共享差0的部分不需要進行大整數相乘計算，而共享基的位置已經存放到緩存中，所以，計算不僅可以分配到各個節(jié)點，而且能提高計算效率并有效地減少重復計算。

表2 PCIR-V實驗數據參數

算法2 二進制-均值聚類算法

輸入：集群節(jié)點個數，CPIR-V數據

輸出：類別標簽

1) 隨機選擇條數據作為初始聚類中心；

2) 對于每條數據使用式(8)計算與每個聚類中心的距離，并將該條數據并入距離最近的中心；

3) 對于每一類按照式(9)重新計算聚類中心；

4) 如果聚類中心沒有發(fā)生改變則結束，否則跳到2)；

5) 結束。

算法2中，步驟1) 首先從數據集合中隨機選擇條數據作為初始的聚類中心，其中，的取值為Spark集群啟動Executer節(jié)點個數，每一類均有自己的緩存數據，這樣做可以將更加相似的記錄聚集到一起，緩存的命中率會更高；步驟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) 是在第一層循環(huán)完畢后，從中選取一個重復為1最多的元素，添加到二元組中，同時二元組第2個元素為重復為1部分的編碼。算法3對應圖6中的第2個步驟預處理的數據可以通過Spark集群進行查詢。

算法4 緩存優(yōu)化PCPIR-V查詢服務端算法

輸入：查詢(12…y)，網格劃分數目，

輸出：CPIR計算結果Array()

1) 將二元組信息緩存到RDD；

2) 對RDD中的二元組進行聚合，獲得(,())的形式；

3) 通過查詢對(,())中對應的數據進行CPIR計算，緩存到RDD；

4) 利用緩存的數據和計算()的CPIR結果，并緩存到RDD；

5) 聚合數據發(fā)回客戶端；

6) 結束。

算法4中，步驟1) 首先將前2步生成的二元組數據讀入到Spark的RDD中；步驟2) 按照緩存對二元組進行聚合（groupByKey）生成一個新的二元組（，（）），這樣保證在RDD中是唯一的；步驟3) 則對進行解碼并同查詢進行CPIR計算得出結果，步驟4) 對剩下的相乘得到(())的序列。算法4展示了圖6中Spark進行并行計算的過程：首先，對共享基緩存進行計算；然后，對整個數據進行計算；最后，對數據進行合并后將結果返回客戶端。

3.5.2 PCIPR-V緩存優(yōu)化算法性能分析

PCPIR-V緩存優(yōu)化算法通過3個步驟解決了PCPIR-V中由于空間分布特性導致的過多冗余計算問題，第1步對數據進行聚類，是為了將相近的數據聚集在一起，為第2個步驟提供方便；只需要在類內比較就可以找到相似度最高的記錄；最后，通過Spark對緩存數據進行優(yōu)先計算，并對緩存數據進行重用。

PCIPR-V緩存優(yōu)化算法的主要性能優(yōu)化在于可以將各條記錄內大整數乘法的計算進行緩存，從而提高計算效率。緩存優(yōu)化算法的代價模型可以用式(11)表示。

4 實驗結果與分析

本實驗采用的服務平臺為IBM xSeries System 3650M4，集群共有5個節(jié)點，每個節(jié)點詳細配置如下。

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

內存：32 GB；

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

操作系統(tǒng)：CentOS 6.4；

開發(fā)工具：GNU Toolkits（G++、GDB）、Make、Vim，JDK等。

實驗所用開發(fā)語言為標準C++、Java、Scala語言，使用合成數據和真實數據進行實驗并對實驗結果進行分析，由于本文PCPIR-V與相關研究成果的并行化思路是不同維度且為互為補充的關系，同時未發(fā)現同一CPU并行化維度的相關成果，因此，對比了CPIR-V和PCPIR-V，驗證云環(huán)境下PCPIR-V的查詢性能。合成數據采用生成均勻分布和高斯分布2種分布方式，其中，高斯分布滿足(,)×(1,1,0,0,1)。真實數據來自加利福尼亞的Sequoia[21]。本文的數據取值范圍為1 046 435×1 929 615，其中，、坐標類型都為int型，本文所指網格劃分為，是指將空間劃分為×的均勻網格。本文C++所使用的大數計算庫為GMP[22]，Java為JDK自帶的大整數計算工具。其中，CPU核心數量指的是虛擬核心的數量，即操作系統(tǒng)級別上的核心數量，而非物理核心數量，其中，閾值的取值規(guī)則為滿足個大整數相乘的時間大于一次內存查表時間條件的最小取值，通過實驗得出，當時，大整數相乘的耗時超過了內存查表時間，因此，本文取值為3。閾值的最優(yōu)解問題將在未來工作中進行研究。

4.1 PCPIR-V不同數據服務端時間

圖7為不同數據在不同網絡劃分下的服務端時間，其中，圖7(a)~圖7(c)是利用式(2)進行的網絡劃分，圖7(d)是利用式(3)進行的網格劃分。圖7(a)為基于Spark的并行CPIR-V算法（PCPIR-V）Row并行和Bit并行策略與未優(yōu)化的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啟動的任務是有限的，不能很好地發(fā)揮并行的優(yōu)勢，且在計算的過程可能會產生節(jié)點間通信的代價，所以，基于行并行的PCPIR-V算法在剛開始網格劃分小的時候甚至超過單機的CPIR-V算法計算時間，在對PCPIR-V進行Bit并行策略的優(yōu)化之后，可以充分利用集群資源進行并行計算，在網格較小時，相對基于行的PCPIR-V有很大的提升。隨著網格數目的增長，PCPIR-V相對傳統(tǒng)的CPIR-V已經有明顯的優(yōu)勢，在網格數目在400的時候，大概有1個數量級的提升，且隨網格增長，時間增長的趨勢比較平緩，相對CPIR-V隨網格增長計算時間增長較快。

圖7(b)為在高斯分布基于Spark的并行CPIR-V算法（PCPIR-V）Row并行和Bit并行策略對比。不同網格劃分對高斯分布中最近鄰查詢影響的變化趨勢與均勻分布相同，但是高斯分布的服務端的計算時間相對于均勻分布有明顯提高，這是由于高斯數據中每個網格中潛在最近鄰數量的最大值遠遠超過均勻分布，從而導致計算數和返回的QR、QNR數目增大，最終導致時間增大。

圖7(c)為在真實數據中數據中基于Spark的并行CPIR-V算法（PCPIR-V）Row并行和Bit并行策略與未優(yōu)化的CPIR-V算法在不同網格劃分下服務端計算時間對比圖。雖然潛在最近鄰的最大值很大，但是潛在最近鄰中的0 bit比較多，所以，計算時間相對均勻分布數據和高斯分布數據小很多。

圖7(d)展示了利用式(3)不同網格劃分對均勻分布數據集最近鄰查詢的影響，從圖7(d)中可以看出3種算法都隨著網格數量的增加而增大，基本的變化趨勢和圖7(a)基本相同，但是時間與圖7(a)相比都有所增大，這是由于在計算矩陣中存在大量的0 bit，造成大量大整數的平方計算，從而增加了計算代價。對于CPIR-V來說，影響非常大，而PCPIR-V就增長不明顯，仍可以保證良好的性能，這是由于基于Spark的PCPIR-V算法有比較高的擴展性，通過將復雜的計算分配到各個節(jié)點，從而達到高性能的計算水平，所以，當計算量急劇增大時，對CPIR-V的影響很大，但是對PCPIR-V卻較小。

4.2 不同模量服務器時間

圖8為基于Spark的并行CPIR-V算法（PCPIR- V）Bit并行策略與未優(yōu)化的CPIR-V算法在不同模量下服務端計算時間對比。

從圖8中可以看出，隨著模量的不斷增加，服務端的計算時間也會隨之增加，其中，PCPIR-V-B的增長速度較為平緩，而CPIR-V增長速度比較快。這說明在集群資源充足的情況下，模量的增長不會對PCPIR-V-B算法造成過大的影響。

4.3 不同CPU個數服務端時間

圖9顯示PCPIR-V算法在不同CPU核心數量下計算時間的變化，實驗Spark集群共有5個服務器節(jié)點，應用到YARN集群的計算資源共有100個虛擬CPU核心。實驗結果表明，隨著CPU數量的增加，計算時間也在不斷銳減。當達到一定程度后，速度開始變緩，這是因為CPU核心數量越多，算法的并行度就越大，計算時間就越少，但核心數量在達到一定程度時開始變緩，圖9中核心數為40個，這說明在本組實驗數據和實驗條件下CPU核心數量超過40個的時候，主要瓶頸已經從CPU轉到節(jié)點之間通信和交互。

4.4 基于Spark最近鄰CPIR緩存優(yōu)化服務端時間

本實驗主要對服務端的算法做出優(yōu)化，減少了數據的冗余計算，實現了計算共享。因此，只對服務端的算法做出實驗分析，分別針對不同數據集和不同網格劃分下的實驗做出分析。

圖10分別是緩存優(yōu)化的PCPIR-V和PCPIR-V在均勻分布數據集、高斯分布數據集和真實數據集下，不同網格劃分下的服務端計算時間的對比。其中，PCPIR-V-CA為基于緩存優(yōu)化的PCPIR-V算法。

從3個實驗結果對比來看，真實數據集和高斯數據集要比均勻數據集合高出很多，這是由于高斯數據和真實數據的集中分布導致的，越集中分布的數據，可能存在的重復計算也就越多，這樣緩存優(yōu)化的效果也就越好。這2種算法都會在網格剛開始的時候有一個較大的峰值，之后降低，這是因為在起初網格劃分較小的時候，網格內的潛在最近鄰較多，這樣數據就不能很好地分配到各個節(jié)點分布式執(zhí)行，因此導致計算速度慢，緩存的優(yōu)化效果也不好。緩存的效果在網格劃分小的時候不明顯，這是因為開始的主要瓶頸不是在大整數的計算上而是判斷當前位是否為1上，因此，緩存的優(yōu)化都是從網格數目在100之后才開始顯著地提高，特別是高斯分布的數據和真實數據，主要是因為它們存在更多的重復計算。

5 結束語

針對面向大數據的隱私保護查詢問題，本文以Spark計算框架為基礎，利用CPIR高保護強度，在HBase上設計了數據的組織格式，RDD實現了并行CPIR-V最近鄰查詢算法（PCPIR-V），并提出2種并行策略。針對PCPIR-V算法中冗余計算的問題，提出了基于緩存的PCPIR-V算法，通過使用聚類和二進制交集方法對數據進行了預處理，減少了冗余計算，提高了計算的效率。最后，通過對實驗進行分析，在40個核心范圍內，基于Row和Bit并行策略的PCPIR具有良好的加速比，PCPIR-V緩存優(yōu)化技術計算時間與樸素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-），男，山東福山人，東北大學教授、博士生導師，主要研究方向為隱私保護、大數據、云計算、基于位置服務、數據流管理系統(tǒng)、發(fā)布/訂閱系統(tǒng)、移動數據庫。

陳月梅（1991-），女，湖北大冶人，東北大學碩士生，主要研究方向為隱私保護、大數據、數據管理。

袁野（1981-），男，遼寧沈陽人，東北大學教授，主要研究方向為云計算、大數據管理、P2P計算。

李艷輝（1989-），女，黑龍江訥河人，東北大學博士生，主要研究方向為查詢處理、隱私保護。

王國仁（1966-），男，湖北黃岡人，東北大學教授、博士生導師，主要研究方向為XML數據管理、查詢處理優(yōu)化、高維數據索引、分布式數據庫、隱私保護。