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

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

?

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

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

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

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

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

1 引言

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

單點位置信息的隱私查詢保護的典型手段主要分為3類：干擾技術(shù)[2~4]、區(qū)域覆蓋（隱匿空間技術(shù)）[5~8]、基于密碼學的保護方式。干擾技術(shù)和區(qū)域覆蓋都是通過損失可用性或隱私性的方式來實現(xiàn)的，而密碼學的隱私保護方式，可以比較好地達到可用性和隱私性的平衡，密碼學的隱私查詢保護技術(shù)較有代表性的是隱私信息檢索（PIR，private information retrieval），密碼學的保護方式大都為基于復雜計算的數(shù)學方式，隱私保護強度高，但是計算量十分巨大?；陔[私信息檢索的研究主要分為兩大類，分別是基于信息理論的私有信息檢索（IT-PIR，information theoretical private information retrieval）[9]和基于計算的私有信息檢索（CPIR，computational private information retrieval）[10]。CPIR的實現(xiàn)基于數(shù)論中的同余理論及相關(guān)的研究成果。求解二次剩余（QR，quadratic residue）問題的難度與因子分解難度相當，是其隱私保護的理論基礎(chǔ)。CPIR假設(shè)攻擊者（服務(wù)器）計算求解能力為多項式限制（polynomially bounded），在這個前提下，保證攻擊者不能通過區(qū)分與二次非剩余來區(qū)別用戶對不同數(shù)據(jù)項的訪問。

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

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

云計算是大數(shù)據(jù)處理的技術(shù)支撐，如分布式計算框架Hadoop[15]、Spark[16]、Storm等。Hadoop中MapReduce側(cè)重于離線數(shù)據(jù)分布式批處理，Strom側(cè)重于實時流分布式計算，而Spark側(cè)重基于內(nèi)存計算，Spark的快速發(fā)展和使用，進一步提高了大數(shù)據(jù)處理的效率，特別是在迭代計算和快速計算上相對于MapReduce有很大程度的提高。隨著數(shù)據(jù)量增加，大量用戶希望得到在線隱私保護，針對面向大數(shù)據(jù)的高強度基于位置服務(wù)的隱私保護問題，Spark是在線的并行計算框架，實現(xiàn)基于Spark的分布式CPIR位置服務(wù)隱私保護技術(shù)具有研究意義與應(yīng)用價值。

在關(guān)于CPIR的分布式并行計算中，主要實現(xiàn)分為2種：基于Peer-to-Peer的并行化計算、基于主從結(jié)構(gòu)（master-slave）的分布式計算。文獻[17]提出一種基于P2P的并行CPIR，利用striping technique傳輸數(shù)據(jù)庫給合作的peer，提高了CPIR查詢的處理速度。文獻[18,19]利用MapReduce計算框架實現(xiàn)PIR分布式計算。文獻[18]中PIRMAP是一種適用于MapReduce的、有效的單服務(wù)器CPIR協(xié)議，主要用于檢索云上的大文件（large files）。pCloud是基于GR-PIR協(xié)議實現(xiàn)數(shù)據(jù)庫分區(qū)并行的；PIRMAP和PRISM對文件進行劃分以實現(xiàn)并行化，屬于I/O級的并行化，可以直接應(yīng)用于CPIR計算的并行；本文的并行化是對CPIR矩陣行（Row）計算以及列（Bit）計算的并行，是CPU級的并行化，與上述研究成果相比，是2個不同維度的并行化，兩者之間是互相補充的關(guān)系。

2 CPIR-V最近鄰隱私保護查詢算法

最近鄰（NN，nearest neighbor）查詢是LBS中一個應(yīng)用比較廣泛的查詢，獲得查詢對象距離最近的對象，距離計算采用歐幾里德距離。Voronoi圖[20]通過對空間的劃分體現(xiàn)空間對象之間的近鄰拓撲關(guān)系，被廣泛應(yīng)用到各個方面，包括計算機圖形學、空間數(shù)據(jù)關(guān)系、圖像處理和多維數(shù)據(jù)等。圖2(a)為1~5劃分形成的Voronoi圖[1,11]，其中，每個多邊形稱為Voronoi格，Voronoi格的邊為相鄰空間對象的垂直平分線，這樣形成的多邊形劃分可以保證在同一個Voronoi格里面的所有空間對象的最近鄰點都是同一個，例如，查詢點的最近鄰點就是跟點在同一個Voronoi格的點。

文獻[11]提出一種基于隱私數(shù)據(jù)檢索和Voronoi圖的最近鄰隱私保護查詢算法CPIR-V，如圖2(b)所示，CPIR-V利用興趣點（POI，point of interests）將Voronoi圖進行網(wǎng)格劃分，實線是Voronoi邊，虛線顯示的是經(jīng)過劃分的網(wǎng)格的邊。為POI，為查詢點，查詢點在網(wǎng)格標號為（2，1）的網(wǎng)格中，該網(wǎng)格與所形成的Voronoi格都有重合，查詢點的最近鄰可能是中的一個，所以，形成最近鄰的候選集合。不同的網(wǎng)格可能有不同數(shù)量的最近鄰點，這與點的分布、網(wǎng)格的大小都有關(guān)系。

構(gòu)建網(wǎng)格矩陣，以每個網(wǎng)格中POI數(shù)量最多為基準，不足的網(wǎng)格進行填充。當用戶發(fā)起查詢的時候，首先通過計算獲取查詢點所在的網(wǎng)格，隨機生成2個大質(zhì)數(shù)1，2，對進行二次剩余的計算，生成圖3中的查詢，其中，查詢區(qū)域的網(wǎng)格對應(yīng)的是的二次非剩余，其他位置是二次剩余，即對矩陣第2行、第1列的查詢信息的屬性為，利用CPIR計算值。

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

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

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

2) CPIR-V算法由于空間分布的特性，進行矩陣掃描和計算的時候有很多重復計算，重復計算占用大量的計算資源，從而降低了CPIR-V的計算效率。

并行計算的原理要求計算結(jié)果是可分解的且互相之間是沒有影響的。文獻[1,11]介紹了CPIR-V的并行計算原理：基于CPIR-V的隱私保護近鄰查詢過程中，每個值的計算僅需要矩陣中的一行數(shù)據(jù)和向量，不同的值結(jié)果互不影響。因此，基于這一特性，將矩陣進行水平劃分，實現(xiàn)CPIR-V的并行計算。

因此，本文采用Spark作為計算平臺，提出基于Spark實現(xiàn)并行的CPIR-V最近鄰查詢算法PCPIR-V，對CPIR-V基于Spark和HBase進行重新設(shè)計，并根據(jù)數(shù)據(jù)的特性，實現(xiàn)包括Row級并行和Bit級并行2種策略?；赗ow的并行策略有數(shù)據(jù)分布不均勻的情況，特別是在網(wǎng)格劃分過小的情況下無法充分利用集群的資源進行計算，造成集群資源的浪費，針對此問題，提出了一種基于更加細粒度的并行策略——基于Bit的并行策略。

3.1 數(shù)據(jù)組織格式

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

表1 PCIR-V信息表結(jié)構(gòu)

3.2 并行策略

PCPIR-V采用2種并行的策略，分別為基于Row的并行策略和基于Bit的并行策略?；赗ow的并行策略是將數(shù)據(jù)中的每一行交給Spark的一個Task處理，圖4(a)是基于Row的并行策略的PCPIR-V算法，左側(cè)CPIR矩陣每個網(wǎng)格存儲2 bit的信息，實際情況遠不止這些，可能是幾百個或者幾千個雙精度的經(jīng)緯度數(shù)值。PCPIR-V算法將每一行的數(shù)據(jù)均單獨交給Spark的一個Task進行CPIR計算，將單機CPIR-V算法并行化，提高了計算的效率，并最終把每行的結(jié)果返回到客戶端。但這種并行策略在網(wǎng)格內(nèi)數(shù)據(jù)量較多的情況下，由于每一行是并行的最小單位，導致有些Task沒有分配到任務(wù)，因此，存在集群計算資源分布不均的情況，無法充分利用集群的計算資源。

基于Bit的并行策略通過將每一行按照Bit進行再次分組，并按照當前的集群資源的狀況（包括當前Executer的個數(shù)和每個Executer最多運行的Task的個數(shù)）確定分組的個數(shù)，從而提高集群的利用率。圖4(b)是基于Bit并行策略的示意，通過對每一行的內(nèi)容繼續(xù)細分，組劃分的個數(shù)可以通過集群現(xiàn)有資源進行確定。選取策略是將集群空閑的CPU核心數(shù)目作為分組個數(shù)，每一組可能會被分到1個或多個比特，圖4(a)中為1 bit。

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

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

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

圖5 基于Spark的PCIPR-V架構(gòu)

3.3 PCPIR-V算法

PCPIR-V算法首先對文件中的空間位置信息進行讀取，生成Voronoi圖，然后，通過Voronoi圖和網(wǎng)格相交或者包含的位置關(guān)系，求出每個網(wǎng)格的潛在最近鄰點的矩陣存放到數(shù)組中，之后將預(yù)處理的矩陣數(shù)據(jù)存放在HBase中，數(shù)據(jù)通過RowKey設(shè)計被均衡分配到各個HRegion中，并由各個節(jié)點的HRegion Server管理，從而可以提高Spark從HBase獲取的效率。

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

算法1 PCPIR-V服務(wù)端算法

輸入：查詢(12…y)，網(wǎng)格劃分數(shù)目，，并行策略

輸出：CPIR計算結(jié)果Array()

1) 根據(jù)網(wǎng)格劃分獲取CPIR矩陣數(shù)據(jù)緩存到RDD；

2) if() then

3) 對RDD中的CPIR矩陣數(shù)據(jù)按照行進行分組；

4) end if

5) if()then

6) 獲得當前集群分配的CPU數(shù)量；

7) 將每一行數(shù)據(jù)分為組，即總共組；

8)end if

9) Spark對每個分組進行CPIR計算獲得；

10) Spark將結(jié)果聚合發(fā)送到客戶端；

11) 結(jié)束。

算法1中，步驟1) 首先通過客戶端傳來的參數(shù)，計算出HBase中存儲的行和列的最大值，并通過RowKey最大值對HBase進行掃描獲得矩陣，HBase每一行作為RDD的一條記錄；步驟2)~4)是算法按照給定方式進行分組，基于Row的并行策略是按照每一行對數(shù)據(jù)進行分組；步驟5)~8)是策略為Bit時的分組情況，首先，根據(jù)當前集群分配計算資源的數(shù)量，對每一行進行分組，分組方式為取模，為查詢序列的個數(shù)，主要是通過Spark的flatMap和組數(shù)量的參數(shù)對每一行的內(nèi)容進行分組并形成新的條目；步驟9)~10)通過Spark的map對每個小分組進行CPIR計算，并將每一組的結(jié)果返回。

3.4 PCPIR-V算法性能分析

由于CPIR算法需要對整個數(shù)據(jù)空間進行掃描和計算，因此，計算代價和總的數(shù)據(jù)量成正比。PCIR-V算法通過采用Spark集群技術(shù)將CPIR-V進行重新設(shè)計，通過HBase的高速列存儲和Spark基于內(nèi)存的并行計算提高CPIR計算的速度，并且擁有很高的擴展性。PCIR-V的服務(wù)端代價模型可用式(5)表示。

其中，為PCPIR-V算法的總代價，為從HBase中讀取的代價，此代價可以通過RDD的cache功能減免，為Spark的RDD進行轉(zhuǎn)換的時間，是Spark的RDD進行動作的時間。其中，與HBase集群的數(shù)量、數(shù)據(jù)的分布和網(wǎng)絡(luò)都有關(guān)系，隨著查詢數(shù)量的增大而增長，并隨著HBase集群規(guī)模的增大而減小，而和均隨著節(jié)點的CPU核心數(shù)的增多而降低，和可以進一步用式(6)和式(7)表示，其中，為CPU的核心數(shù)量，代表時間隨CPU增大而減小的系數(shù)。

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

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

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

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

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

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

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

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

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

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

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

表2 PCIR-V實驗數(shù)據(jù)參數(shù)

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

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

輸出：類別標簽

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

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

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

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

5) 結(jié)束。

算法2中，步驟1) 首先從數(shù)據(jù)集合中隨機選擇條數(shù)據(jù)作為初始的聚類中心，其中，的取值為Spark集群啟動Executer節(jié)點個數(shù)，每一類均有自己的緩存數(shù)據(jù)，這樣做可以將更加相似的記錄聚集到一起，緩存的命中率會更高；步驟2) 對所有數(shù)據(jù)與各類聚類中心進行距離的計算，距離公式采用式(8)并將每條記錄分配到距離最近的中心，即式(9)取值最小的中心；步驟3) 對已經(jīng)進行聚類完畢的類別分別計算聚類中心，使用式(10)；最后，步驟4) 對收斂條件進行判斷，收斂條件為進行再次聚類的聚類中心較之前的中心沒有改變。

算法3 數(shù)據(jù)簡化和待緩存數(shù)據(jù)生成算法

輸入：其中一類的數(shù)據(jù)，數(shù)據(jù)的條數(shù)，閾值

輸出：簡化數(shù)據(jù)和待緩存數(shù)據(jù)的二元組

1) 聲明臨時數(shù)組變量，；

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) 結(jié)束。

算法3中，步驟2)~12)是對類內(nèi)記錄的相互判斷；步驟4)是排除與本身比較的情況；步驟5) 計算2條記錄之間重復為1的結(jié)果；步驟6) 按照式(8)進行判斷，滿足才進行記錄；步驟11) 是在第一層循環(huán)完畢后，從中選取一個重復為1最多的元素，添加到二元組中，同時二元組第2個元素為重復為1部分的編碼。算法3對應(yīng)圖6中的第2個步驟預(yù)處理的數(shù)據(jù)可以通過Spark集群進行查詢。

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

輸入：查詢(12…y)，網(wǎng)格劃分數(shù)目，

輸出：CPIR計算結(jié)果Array()

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

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

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

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

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

6) 結(jié)束。

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

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

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

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

4 實驗結(jié)果與分析

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

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

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

4.1 PCPIR-V不同數(shù)據(jù)服務(wù)端時間

圖7為不同數(shù)據(jù)在不同網(wǎng)絡(luò)劃分下的服務(wù)端時間，其中，圖7(a)~圖7(c)是利用式(2)進行的網(wǎng)絡(luò)劃分，圖7(d)是利用式(3)進行的網(wǎng)格劃分。圖7(a)為基于Spark的并行CPIR-V算法（PCPIR-V）Row并行和Bit并行策略與未優(yōu)化的CPIR-V算法在不同網(wǎng)格劃分下使用不同數(shù)據(jù)服務(wù)端計算時間的對比，其中，PCPIR-V-R為基于Row并行策略的PCPIR-V算法，PCPIR-V-B為基于Bit并行策略的PCPIR-V算法。從圖7(a)中可以看出，3種算法都是隨著網(wǎng)格劃分的增大而變慢，這是由于CPIR-V的矩陣列數(shù)與網(wǎng)格列數(shù)是一致的，網(wǎng)格越多說明CPIR-V的矩陣越多，需要相乘的大整數(shù)也就越多，時間也就越長。在網(wǎng)格數(shù)目為10的時候，3種算法的計算時間基本是在同一個數(shù)量級上，這是因為在網(wǎng)格劃分太小的情況下，PCPIR-V啟動的任務(wù)是有限的，不能很好地發(fā)揮并行的優(yōu)勢，且在計算的過程可能會產(chǎn)生節(jié)點間通信的代價，所以，基于行并行的PCPIR-V算法在剛開始網(wǎng)格劃分小的時候甚至超過單機的CPIR-V算法計算時間，在對PCPIR-V進行Bit并行策略的優(yōu)化之后，可以充分利用集群資源進行并行計算，在網(wǎng)格較小時，相對基于行的PCPIR-V有很大的提升。隨著網(wǎng)格數(shù)目的增長，PCPIR-V相對傳統(tǒng)的CPIR-V已經(jīng)有明顯的優(yōu)勢，在網(wǎng)格數(shù)目在400的時候，大概有1個數(shù)量級的提升，且隨網(wǎng)格增長，時間增長的趨勢比較平緩，相對CPIR-V隨網(wǎng)格增長計算時間增長較快。

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

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

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

4.2 不同模量服務(wù)器時間

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

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

4.3 不同CPU個數(shù)服務(wù)端時間

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

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

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

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

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

5 結(jié)束語

針對面向大數(shù)據(jù)的隱私保護查詢問題，本文以Spark計算框架為基礎(chǔ)，利用CPIR高保護強度，在HBase上設(shè)計了數(shù)據(jù)的組織格式，RDD實現(xiàn)了并行CPIR-V最近鄰查詢算法（PCPIR-V），并提出2種并行策略。針對PCPIR-V算法中冗余計算的問題，提出了基于緩存的PCPIR-V算法，通過使用聚類和二進制交集方法對數(shù)據(jù)進行了預(yù)處理，減少了冗余計算，提高了計算的效率。最后，通過對實驗進行分析，在40個核心范圍內(nèi)，基于Row和Bit并行策略的PCPIR具有良好的加速比，PCPIR-V緩存優(yōu)化技術(shù)計算時間與樸素PCPIR-V時間相比，平均降低了20%。

[1] 王璐, 孟小峰. 位置大數(shù)據(jù)隱私保護研究綜述[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] 張峰, 倪巍偉. 基于偽隨機數(shù)加密的保護位置隱私近鄰查詢方法[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 圖應(yīng)用綜述[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-），女，遼寧凌源人，東北大學博士生，主要研究方向為大數(shù)據(jù)、云計算、位置隱私保護。

姚繼濤（1990-），男，山東泰安人，東北大學碩士生，主要研究方向為大數(shù)據(jù)、云計算、隱私保護。

王波濤（1968-），男，山東福山人，東北大學教授、博士生導師，主要研究方向為隱私保護、大數(shù)據(jù)、云計算、基于位置服務(wù)、數(shù)據(jù)流管理系統(tǒng)、發(fā)布/訂閱系統(tǒng)、移動數(shù)據(jù)庫。

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

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

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

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