面向稠密區(qū)域的本地化差分隱私自適應(yīng)空間分解

關(guān)鍵詞：本地化差分隱私；自適應(yīng)空間分解；自適應(yīng)網(wǎng)格劃分；隨機響應(yīng)；空間范圍查詢 中圖分類號：TP309.2 文獻標志碼：A 文章編號：1001-3695（2025）08-036-2518-07 doi：10.19734/j.issn.1001-3695.2024.11.0505

Adaptive spatial decomposition based on localized differential privacy for dense regions

Ji Bo，Li Xiaohui?，JiaXu （SchoolofElectronicsamp;Information Enginering，Liaoning UniversityofTechnology，JinzhouLiaoning21oo，China）

Abstract：Toaddress theisues oflowqueryaccuracyandeficiencyin processng spatialdatausing conventionaluniform gridmethodsandadaptive griddecompositionmethods，，this paperdevelopedanadaptive spatialdecompositionalgorithmbased onlocal diffrential privacy（LDP-ASDT）.LDP-ASDTperformed spatial decomposition hierarchicallyusing agrouping strategyto separate denseandsparseregions.For dense regions，it further adaptively decomposed them bysetting appropriate thresholds using aquadtre.Itperturbedthe decompositionresults using one-dimensionalcoding toachieve privacy protection. Theoreticalanalysisdemonstratesthatthisalgorithmsatisfieslocalizeddiferentialprivacy.Experimentsconductedonthree real datasetsshowthatthequeryacuracyandoperationaleficiencyofthisalgorithmaresuperiortothoseofGT-R，PrivAG， KDRQ，and ASDQT algorithms.Specificall，compared to the ASDQT algorithm，LDP-ASDT algorithm doubles thequery accuracy and increases the operational rate by 17% in dense regions.

Key words：localdiferential privacy；adaptivespatialdecomposition；adaptivegriddecomposition；randomizedresponse; spatial range query

0 引言

大數(shù)據(jù)時代，隨著信息技術(shù)的迅猛發(fā)展和智能設(shè)備的廣泛普及，空間數(shù)據(jù)因其巨大的潛在價值而備受關(guān)注。空間數(shù)據(jù)為人們提供了許多便利的服務(wù)。例如，根據(jù)用戶的偏好推薦附近評分高的娛樂場所或餐廳，通過衛(wèi)星定位系統(tǒng)為用戶提供精準的道路導(dǎo)航。這些應(yīng)用極大地提升了人們的生活質(zhì)量和出行效率。空間數(shù)據(jù)中包含大量敏感的個人信息，在使用過程中容易引發(fā)隱私泄露的問題。因此，如何在對空間數(shù)據(jù)進行分解時，既確保查詢數(shù)據(jù)的精度又保護用戶的隱私，已成為當前研究的一個熱點問題。

傳統(tǒng)的隱私保護機制（如 k -anonymity[3]、l-diversity[4]t -Closeness[5]）在處理空間數(shù)據(jù)進行空間劃分時，需要對某些特定攻擊和背景知識進行假設(shè)，且會因為新型攻擊手段的出現(xiàn)不斷完善，難以提供足夠的安全保障。針對此問題，Dwork等人[6]提出差分隱私這一概念，旨在對抗任意背景知識下的攻擊，保護隱私的安全。Qardaji等人基于差分隱私技術(shù)提出了均勻網(wǎng)格UG方法，將二維空間平均分配成大小相等的單元格，并采用拉普拉斯噪聲擾動每個單元格，從而達到保護隱私的目的，但此方法并未考慮數(shù)據(jù)分布的不均勻性。在此基礎(chǔ)上，Qardaji等人[7]又提出了自適應(yīng)網(wǎng)格AG方法，將第一層網(wǎng)格劃分與計數(shù)結(jié)果相對應(yīng)，從而自適應(yīng)劃分空間區(qū)域。Xiong等人8采用等高線圖來表示空間眾包中的位置分布，將整個區(qū)域劃分為不相交的單元網(wǎng)格，然后把通過噪聲計數(shù)的單元網(wǎng)格連接，組成一個更大的區(qū)域。文獻[9]對AG方法進行了擴展，在為員工提供隱私保障的同時，實現(xiàn)了有效的空間眾包服務(wù)。Zhou等人[10]根據(jù)每個網(wǎng)格的散度定義了隱私保護需求的強度，提出了一種基于AG方法的差分隱私噪聲動態(tài)分配算法。Yang等人[1]提出PrivAG方法，將二維空間區(qū)域劃分為粗粒度網(wǎng)格，并根據(jù)第一層網(wǎng)格單元頻率劃分為細粒度網(wǎng)格，但因其沒有索引結(jié)構(gòu)，所以查詢效率較低。

由于上述研究沒有采用索引方法，在空間數(shù)據(jù)查詢時效率較低。Ali等人[12]采用KD-樹對區(qū)間重新分段，將隱私預(yù)算分配到不同區(qū)域，從而減少了均勻假設(shè)誤差，但需要采用指數(shù)機制保護分割線，當空間劃分較細時隱私預(yù)算耗費太大。Cor-mode等人[13]提出了名為Quadi-Geo的差分隱私空間分解算法，使用四叉樹將空間分割為更小區(qū)域，并使用集合預(yù)算分配策略對每個區(qū)域的點進行統(tǒng)計。結(jié)果表明，該算法滿足隱私保護且提高范圍查詢的準確率。Zhang等人[14]提出了PrivTree方法，其使用四叉樹進行空間分解，并引入偏置計數(shù)避免樹高作為預(yù)定義輸入的限制。但面對數(shù)據(jù)分布呈現(xiàn)極端的不均勻性，PrivTree算法在稠密區(qū)域可能由于噪聲的影響導(dǎo)致節(jié)點分裂決策不夠準確;而在稀疏區(qū)域，因為樹的構(gòu)建策略可能產(chǎn)生過多不必要的節(jié)點，增加了計算開銷和噪聲影響。Li等人[15]提出了一種基于四叉樹的差分私有混合分解DP-HDAQT方法，首先使用自適應(yīng)密度網(wǎng)格分解將空間區(qū)域劃分為密集區(qū)域與稀疏區(qū)域，在此基礎(chǔ)上使用四叉樹將空間細化，并引用偏置計數(shù)限制樹的無限分解。

在物聯(lián)網(wǎng)、地理信息系統(tǒng)、全球定位系統(tǒng)、眾包系統(tǒng)等領(lǐng)域采用傳統(tǒng)差分隱私進行隱私保護會面臨不可信第三方的風險。例如用戶的物流信息和位置信息會遭到不可信服務(wù)器的惡意泄露。相比之下，本地化差分隱私（local differential privacy）[16]采取去中心化的方法，要求每個用戶在本地對數(shù)據(jù)進行擾動處理，然后發(fā)送到數(shù)據(jù)收集中心，這樣，原始數(shù)據(jù)從未離開用戶設(shè)備，顯著降低了隱私泄露的風險。基于本地化差分隱私[的空間劃分方法利用網(wǎng)格對空間進行初步分割，采用樹結(jié)構(gòu)對空間數(shù)據(jù)進行索引并擾動，進而在保證數(shù)據(jù)隱私的前提下確保查詢的準確性。但現(xiàn)有基于本地化差分隱私的空間劃分方法還存在一定的局限性。張嘯劍等人[提出基于網(wǎng)格的四叉樹范圍查詢GT-R方法，使用UG對空間區(qū)域進行均勻分割，然后在此基礎(chǔ)上使用四叉樹進行索引，利用優(yōu)化隨機應(yīng)答機制與隨機采樣技術(shù)進行本地擾動，但其沒有考慮數(shù)據(jù)分布的不均勻性，導(dǎo)致查詢誤差較大。金媛媛等人[18提出基于KD-樹的空間數(shù)據(jù)分層自適應(yīng)劃分KDG-HT方法，使用KD-樹的思想劃分區(qū)域，并使用抽樣技術(shù)對用戶進行劃分，最后根據(jù)分組用戶統(tǒng)計的結(jié)果所提供的先驗知識完成多層細粒度劃分。但由于其復(fù)雜的分層處理和樹結(jié)構(gòu)構(gòu)建，在稠密區(qū)域可能因頻繁的節(jié)點分裂和統(tǒng)計操作導(dǎo)致時間復(fù)雜度上升。Wang等人[19]提出了基于四叉樹的自適應(yīng)空間分解ASDQT方法，使用儲層抽樣對數(shù)據(jù)進行采集，提出通過設(shè)置適當閾值，將空間區(qū)域劃分不同粒度的自適應(yīng)空間方法，但該方法在數(shù)據(jù)分布不均勻的情況下查詢精度誤差較大。Li等人[20]提出了一種具有混洗差分隱私的空間數(shù)據(jù)范圍查詢方案KDRQ，采用KD-樹和四叉樹的思想，利用密度閾值計算將數(shù)據(jù)空間遞歸劃分。該算法在不均勻分布的數(shù)據(jù)中可以自適應(yīng)劃分空間，但是由于在構(gòu)建索引時采用多種樹結(jié)合的方式，導(dǎo)致計算開銷較大，查詢速度較慢。Feng等人[21]在聯(lián)邦環(huán)境下提出了基于本地化差分隱私的空間查詢方法LDP-FSRQ算法，該算法采用均勻網(wǎng)格與四叉樹結(jié)合的混合結(jié)構(gòu)來索引客戶端位置，客戶端進行編碼與擾動，收集器調(diào)整四叉樹共享給客戶端，從而達到隱私保護的效果，但該方法的計算復(fù)雜度較高，存在通信開銷較大的問題。

針對上述相關(guān)文獻存在的問題，本文提出了基于本地化差分隱私的自適應(yīng)空間分解算法（LDP-ASDT），具體貢獻如下：a）采用用戶分組策略對用戶進行分組，在滿足本地化差分隱私的前提下，減少隱私預(yù)算的分割，進而降低噪聲誤差。b）運用混合分解法，首先采用數(shù)據(jù)依賴自適應(yīng)密度網(wǎng)格分解第一層網(wǎng)格，將其劃分為稀疏/稠密區(qū)域，再利用四叉樹對區(qū)域進行劃分，提升查詢效率。c）針對稠密區(qū)域劃分，設(shè)定頻率閾值來限制四叉樹的細化程度，防止過度分割，確保空間劃分合理，避免出現(xiàn)計算復(fù)雜及性能下降的情況。

d）設(shè)計一種高效的后處理技術(shù)，通過對葉子節(jié)點的頻率進行規(guī)范，從而提高空間范圍的準確性。

1相關(guān)工作

1.1本地化差分隱私

定義1 ε -本地化差分隱私[22]。假設(shè)存在一個隨機算法M ，當且僅當兩個不同輸入 x，x^′（x，x^′∈Dom） ，得到的結(jié)果y（y∈Ran） 滿足

則 M 滿足 ε -本地化差分隱私。其中： Dom（M） 是用戶所有可能的空間數(shù)據(jù)； Ran（M） 是所有可能的輸出； Pr[] 表示事件發(fā)生的概率； ε 是隱私預(yù)算，當 ε 值越小則算法的隱私保護程度越高。

定理1序列組合[22]。若給定數(shù)據(jù)集 D 和隨機算法 {M₁ ，M₂，M₃，…，M_j} ，若算法 M 滿足 ε -本地化差分隱私，則數(shù)據(jù)集D 上的序列組合 {M₁，M₂，M₃，…，M_j} 滿足 ε -本地化差分隱私。

定理2并行組合[22]。設(shè)數(shù)據(jù)集 D 上幾個獨立不相交子集 {D₁，D₂，D₃，…，D_j} ，有隨機算法 {M₁，M₂，M₃，…，M_j} 滿足子集 D_i 上的 ε -本地化差分隱私，則 {M₁，M₂，M₃，…，M_j} 在數(shù)據(jù)集 D 上提供 ε -本地化差分隱私。

1.2最優(yōu)一元編碼

頻率估計 FO^[23] 是提供關(guān)于數(shù)據(jù)分布信息的一種工具，滿足本地化差分隱私，大多數(shù)FO協(xié)議包括編碼、擾動和聚合三個步驟。最優(yōu)一元編碼 0UE^[24] 是一個典型的FO 協(xié)議，其在保護用戶數(shù)據(jù)隱私的同時，仍然能夠有效進行數(shù)據(jù)分析。OUE使用一元編碼對值 v 進行編碼，編碼后的結(jié)果是一個長度為 d 的二進制向量 b ，其中只有第 v 位是1，其他位均是 0：encode（v）= [0，…，0，1，0，…，0] 。OUE通過擾動編碼向量 來生成擾動后的向量 b^′ ，擾動規(guī)則如下：

其中： ε 是隱私預(yù)算，決定了擾動強度。

在數(shù)據(jù)收集階段，數(shù)據(jù)收集者將收集到的所有擾動向量進行聚合，并估計每個值 χ_i 的頻率。由于OUE的編碼和擾動方式，其估計方差為

1.3四叉樹

常用空間分解方法分為數(shù)據(jù)依賴分解和數(shù)據(jù)獨立分解兩種。KD-樹和R樹[25是兩種常見的數(shù)據(jù)依賴分解方法，依賴數(shù)據(jù)本身的分布特性來劃分空間。在本地化差分隱私中由于不存在可訪問用戶數(shù)據(jù)的可信第三方數(shù)據(jù)收集器，所以數(shù)據(jù)依賴分解方法無法直接使用。數(shù)據(jù)獨立分解不依賴于數(shù)據(jù)的實際分布，而是使用固定的規(guī)則對空間進行劃分，最常見的方法是四叉樹，常常用于解決二維空間問題，它遞歸地將一個空間劃分為四個子空間，當子區(qū)域面積足夠小時，遞歸就會停止。

定義2四叉樹[26]是一種樹型數(shù)據(jù)結(jié)構(gòu)，每個非葉子節(jié)點都有四個子節(jié)點，適用于對二維空間進行高效分割和管理。在構(gòu)造四叉樹時，以空間的中心點為基準，通過相互垂直的水平和垂直線條，遞歸地將空間連續(xù)地分割成四個等大的象限或區(qū)域。遞歸至達到預(yù)定的終止條件，如每個區(qū)域的尺寸或包含的對象數(shù)量。

圖1展示了初始狀態(tài)有15個空間數(shù)據(jù)的隨機分布，假設(shè)u 是所要查詢的數(shù)據(jù)，則需要依次查詢到 Q₁，Q₂，Q₃，Q₄ 四個區(qū)域的節(jié)點集最終找尋到空間數(shù)據(jù) u

圖1四叉樹分解示意圖Fig.1Diagram of quadtree decomposition

四叉樹通過遞歸的方式將地理空間劃分為四個大小相等的象限，可以根據(jù)數(shù)據(jù)的分布情況自適應(yīng)地進行細分。這種遞歸的分割方式使它能夠很好地處理GIS、遙感圖像等地理空間數(shù)據(jù)。相比之下，KD-樹在規(guī)則數(shù)據(jù)上會增加多余分割，R樹則更適合管理不規(guī)則的形狀數(shù)據(jù)。此外，四叉樹結(jié)構(gòu)簡單，每個節(jié)點僅分為四個子節(jié)點，因此在內(nèi)存消耗上低于R樹的復(fù)雜節(jié)點管理，也比KD-樹的動態(tài)分割結(jié)構(gòu)更為節(jié)省資源。這使得四叉樹在資源有限的情況下，尤其在大規(guī)模數(shù)據(jù)處理任務(wù)中表現(xiàn)更優(yōu)。

2基于本地化差分隱私的自適應(yīng)空間分解算法

2.1 設(shè)計思想

本文針對稠密空間的分解以及數(shù)據(jù)查詢的問題，提出了一種基于本地化差分隱私的自適應(yīng)空間分解算法LDP-ASDT。LDP-ASDT算法流程如圖2所示。首先，利用采樣技術(shù)對用戶進行分組，使其滿足 ε -本地化差分隱私的并行組合性；然后根據(jù)空間數(shù)據(jù)分布使用分層分解的方法，在第一層分解中，依據(jù)計算出的密度閾值將空間劃分為稀疏區(qū)域與稠密區(qū)域，對于稀疏區(qū)域?qū)⒉辉賱澐郑藭r稀疏區(qū)域每組用戶采用局部隨機響應(yīng)方法對自己的位置數(shù)據(jù)進行局部擾動，并將擾動結(jié)果發(fā)送給數(shù)據(jù)采集器;最后，對于稠密區(qū)域采用四叉樹索引對其進行進一步劃分，每一層的用戶組進行局部隨機擾動并將擾動結(jié)果發(fā)送給數(shù)據(jù)收集器進行頻率構(gòu)造，當葉子節(jié)點的估計頻率小于給定的頻率閾值或到達指定樹高時，則停止迭代。

圖2LDP-ASDT工作流程Fig.2LDP-ASDT workflow

2.2 算法實現(xiàn)

LDP-ASDT算法描述如算法1所示。

算法1 LDP-ASDT算法

輸入：數(shù)據(jù)集 D ；隱私預(yù)算 ε ；網(wǎng)格單元數(shù) ∣m ;樹高 h ；密度閾值 頻率閾值 θ

輸出：查詢結(jié)果。

1將數(shù)據(jù)集 D 隨機分為 n 個子集 {D[1]，D[2]，D[3]，…，D[n]}

2根據(jù) 其中 D 為區(qū)域內(nèi)數(shù)據(jù)集的個數(shù)， k_x，k_y 為權(quán)重系數(shù)， ΔX，ΔY 為區(qū)間長度）分辨出稠密區(qū)域與稀疏區(qū)域相交的網(wǎng)格單元集；

3構(gòu)建一個以 V₀ 為根節(jié)點的樹，將每個網(wǎng)格作為一個節(jié)點插入其中，并將 V₀ 的的頻率估計設(shè)為1；

4for i=1：n

5 Z=LRR（D[i]，T.leave，ε） //算法2；

6 （20號

7 if then numgt;p //稠密區(qū)域；

8 V_j f=πj]

9 while V_j.fgt;θ （204號

10 用四叉樹分解方法進行分解并更新樹

11 end while

12 end if

13 end for

14 post processing（T） //算法3；（20 //算法4; （204號

LDP-ASDT通過用戶分組和空間區(qū)域劃分將數(shù)據(jù)集 D 隨機劃分為 Ω_n 個子集，形成多個數(shù)據(jù)小塊。與傳統(tǒng)的UG方法相比，LDP-ASDT在區(qū)域劃分時，不是簡單地將空間劃分為 m×m 的網(wǎng)格單元，而是根據(jù)密度閾值進行稀疏區(qū)域與稠密區(qū)域的自適應(yīng)劃分。這種方法能夠更靈活地適應(yīng)不同數(shù)據(jù)密度的分布，有效縮小稠密區(qū)域的范圍，優(yōu)化了數(shù)據(jù)采集過程中產(chǎn)生的噪聲誤差（行1、2）。構(gòu)建根節(jié)點（ V₀ ）并將所劃分出的網(wǎng)格單元所謂子節(jié)點插入到樹中，將 V₀ 的頻率估計設(shè)為1（行3）。每個用戶組使用本地隨機響應(yīng)（LRR）方法對自身的位置數(shù)據(jù)進行局部擾動，并將這些擾動后的結(jié)果發(fā)送給數(shù)據(jù)采集器。LRR保證了用戶數(shù)據(jù)的隱私性，即使在數(shù)據(jù)傳輸過程中，外界也難以直接獲取用戶的真實位置。根據(jù)區(qū)域內(nèi)用戶密度與密度閾值進行比較，當用戶密度大于密度閾值時為稠密區(qū)域，反之則為稀疏區(qū)域。對于稠密區(qū)域，將進一步判斷葉子節(jié)點的估計頻率是否小于頻率閾值，將此區(qū)域進行四叉樹索引分解，遞歸直到字節(jié)節(jié)點估計頻率小于等于頻率閾值或達到指定樹高（行 4～ 13）。最后樹進行后處理操作，查詢結(jié)果，返回查詢頻率（行14～16）。

在LDP-ASDT中主要采用參考文獻[16]設(shè)計的LRR算法對樹中節(jié)點進行擾動從而對數(shù)據(jù)進行隱私保護，該算法流程如下：

算法2LRR算法

輸入：用戶的位置（ 1

輸出：用戶擾動后的位置信息。

1 ∠=α （用于存放擾動值）；

2 for所有節(jié)點do

3 證 l_i in V_i then

4 W（V_i）=1 （20號

5 else

6 W（V_i）=0 （204號

7 end if

8 end for

9組合一個向量 V_i∈{0，1} 總?cè)~子節(jié)點個數(shù)

10 for W（V_j） in V_i do

11 if W（V_j）=1 then

12 （204號

13 else

14

15 end if

16 end for

17 return Z

LRR算法的主要流程為：數(shù)據(jù)采集器依次將前一步得到的索引樹分配到每個用戶群組，用戶在索引樹中確定自己的空間位置所屬的葉節(jié)點，對所屬葉節(jié)點進行獨立編碼，編碼結(jié)果向量的長度等于葉節(jié)點的總數(shù)，最后利用優(yōu)化的隨機應(yīng)答機制擾動并生成報告。

在LDP-ASDT算法中，由于在構(gòu)造樹時并沒有對節(jié)點頻率進行約束，所以通過后處理方式對節(jié)點進行處理。后處理算法步驟如下：

算法3post processing 算法

輸人：索引樹 T

輸出：索引樹 T

1 for i from1 to h do

2 //頻率歸一化

3 end for

4 for j from h-1 to 1 do //頻率更新

5 for所有節(jié)點do

6

7

8

9 end for

10 end for

11forkfrom1to h-1 do

12 for所有節(jié)點do

13 道 k=1 then

14

15 else

16

17 end if

18 end for

19 end for

如算法3所示，后處理過程采用頻率歸一化對每個節(jié)點進行規(guī)范，使其在后續(xù)處理過程中具有可比較性。在此基礎(chǔ)上自下而上遍歷樹的所有節(jié)點更新頻率，使得各節(jié)點的加權(quán)平均頻率值為節(jié)點自身的頻率值與其所有子節(jié)點的加權(quán)平均頻率值之和；然后自上而下進行均值一致性處理，將父節(jié)點估計頻率與子節(jié)點估計頻率之和的總差均勻分布到四個子節(jié)點中。

結(jié)合LDP-ASDT樹進行空間范圍查詢 Q ，具體查詢步驟如算法4所示。

算法4RQT算法

輸人：樹 T ，空間范圍查詢區(qū)域 Q

輸出：查詢結(jié)果。

（204號

2初始化根節(jié)點 V₀ ，設(shè)置其標記為未訪問unvisited （V₀）=1 3while存在未訪問的節(jié)點 V_i do

4 標記當前節(jié)點 V_i 為已訪問， （

5 if V_i 與 Q 不相交then

6 忽略節(jié)點 V_i （20

7 elseif Q 完全包含節(jié)點 V_i then

8 （204號

9 elseif V_i 不是葉子節(jié)點且與 Q 部分相交then

10 標記 V_i 的所有子節(jié)點 V_j 為未訪問，unvisited （V_j）=1 11

12 elseif V_i 是葉子節(jié)點且與 Q 部分相交then

13 計算 Q 和 V_i 的重疊部分 overlap（Q，V_i）

14

15 endif

16endwhile

算法4展示了擾動后數(shù)據(jù)聚合和空間范圍查詢的過程。查詢過程中首先將查詢區(qū)域設(shè)為空，將樹中所有節(jié)點標記為未訪問并設(shè)為1（行1、2）。自上而下遍歷所有節(jié)點，將已訪問節(jié)點標為0，當該節(jié)點與查詢 Q 不相交，則直接忽略；若該節(jié)點被Q 完全包含，則將該點的估計頻率添加到響應(yīng)結(jié)果的估計頻率中；若該節(jié)點不是葉子節(jié)點但與 Q 部分相交，則重新遍歷該節(jié)點的子節(jié)點;若該節(jié)點是葉子節(jié)點且與 Q 部分相交，則計算該節(jié)點與 Q 重疊部分，并將重疊部分的估計頻率添加到結(jié)果中（行3～17）。

2.3 隱私分析

定理3LDP-ASDT方法滿足 ε -本地化差分隱私。

證明LRR擾動算法滿足 ε 本地化差分隱私。令 V 為樹的節(jié)點編碼 L 為最后計算出空間范圍查詢結(jié)果，用戶群組為 G ，則有

OUE方法滿足 ε -本地化差分隱私。當任意輸入為 V₁，V₂ 輸出為 b 時，有

因此，LRR擾動算法與OUE方法均滿足 ε -本地化差分隱私，則LDP-ASDT滿足 ε -本地化差分隱私。

定理4LDP-ASDT算法的誤差滿足

證明LDP-ASDT算法的噪聲誤差來源于OUE的擾動，每進行一次OUE需進行一次擾動，同時，對于區(qū)間來說，若為稠密空間，則劃分區(qū)間較多，用于回答查詢的數(shù)量就越多，噪聲也就越高。而非均勻誤差來源于數(shù)據(jù)集的分布，若區(qū)間中的數(shù)據(jù)均勻分布，則不存在非均勻誤差。因此，當區(qū)間劃分越細非均勻誤差越小。其中非均勻誤差的計算為

LDP-ASDT針對稠密區(qū)域通過將估計值與閥值進行比較，將每個區(qū)間單獨劃分為四份，使用 表示四個子節(jié)點的真實頻率值。在進行空間分解的過程中，每一個區(qū)間的分解都伴隨著噪聲誤差與非均勻誤差。本文將估計節(jié)點的頻率平均分配給各子節(jié)點可得期望的估計誤差：

其中： _;X 為添加的噪聲 ， 為估計頻率。

為了平衡噪聲誤差和非均勻誤差，本文參考文獻[21]將頻率閾值設(shè)為

其中： h 為樹的指定高度。此閾值保證了在稠密區(qū)域內(nèi)使用本算法的總體誤差低于UG算法。

2.4 時間復(fù)雜度分析

LDP-ASDT算法采用自適應(yīng)網(wǎng)格對空間進行初步分解，假設(shè)數(shù)據(jù)集坐標點數(shù)為 N ，將 N 個數(shù)據(jù)劃分到 n 個用戶組中，并對用戶組進行掃描將第一層劃分為稠密區(qū)域與稀疏區(qū)域，此過程的時間復(fù)雜度為 O（N） 。在構(gòu)建樹的過程中，采用四叉樹結(jié)構(gòu)對稠密區(qū)域進行分解，對用戶組和節(jié)點進行擾動并更新葉子節(jié)點頻率，該過程每個節(jié)點均被掃描。假設(shè)共有 ?_m 個節(jié)點，則在最壞情況下，樹的構(gòu)造過程的時間復(fù)雜度為 O（NlogN+ 4m ）。但是由于數(shù)據(jù)個數(shù)與節(jié)點個數(shù)相差較大，所以該算法的時間復(fù)雜度近似于 O（NlogN） 。LDP-ASDT算法的總體時間復(fù)雜度約為 O（NlogN） 。

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

3.1 實驗設(shè)置

實驗在PyCharm2024.1.3開發(fā)平臺上使用Python語言編寫，硬件環(huán)境為 Intel^°ledast Core i7-8565U CPU 處理器與Windows10操作系統(tǒng)。

實驗數(shù)據(jù)：采用Checkin數(shù)據(jù)集、北京出租車數(shù)據(jù)集與Tokyo數(shù)據(jù)集三個真實的地理數(shù)據(jù)集，具體參數(shù)如表1所示。其中Checkin數(shù)據(jù)集來自Gowalla網(wǎng)站，記錄了2009年2月 ～2010 年10月Gowalla用戶的簽到及位置信息；北京出租車數(shù)據(jù)集涵蓋2008年2月2～8日期間北京市內(nèi)10357輛出租車的GPS軌跡，總點數(shù)約1500萬，總距離達900萬千米；Tokyo數(shù)據(jù)集包含2012年4月12日至2013年2月16日的573 703個東京簽到信息。三個數(shù)據(jù)集的可視化如圖3所示。

表1數(shù)據(jù)集信息

Tab.1Datasetinformation

圖3數(shù)據(jù)集可視化Fig.3Data setvisualization

3.2 實驗結(jié)果

為了驗證基于本地化差分隱私的自適應(yīng)網(wǎng)格分解算法LDP-ASDT的性能，本文使用均方誤差（mean-square error，MSE）來評估GT-R[17]、PrivAG[11]、KDRQ[20]、ASDQT[19]以及LDP-ASDT算法在查詢范圍，隱私預(yù)算的精度以及運行時間上的差距。均方誤差的公式為

其中： Q 為查詢范圍； q 為在查詢區(qū)間內(nèi)的任一查詢 為查詢區(qū)域內(nèi) q 的估計頻率 _;f 為查詢區(qū)域內(nèi) q 的真實頻率。

3.2.1隱私預(yù)算 ε 對MSE的影響

本文評估了不同隱私預(yù)算對算法查詢誤差的影響情況。如圖4所示，橫坐標表示在三種不同數(shù)據(jù)集的隱私預(yù)算，縱坐標表示均方誤差MSE。圖4描述了三個數(shù)據(jù)集在隱私預(yù)算為0.1～0.9 時，幾種算法的均方誤差變化情況。可以從實驗結(jié)果的變化中看到，在所有情況下，隨著隱私預(yù)算的增加，本文LDP-ASDT算法的均方誤差逐漸降低。產(chǎn)生這一結(jié)果的根本原因在于，隨著隱私預(yù)算的增加，算法對數(shù)據(jù)的隱私保護程度降低，導(dǎo)致數(shù)據(jù)擾動程度減少，數(shù)據(jù)精度提高，因此算法的均方誤差逐漸減小。同時，從圖中可以看出，其他算法的均方誤差都高于本文算法，這表明本文算法的數(shù)據(jù)可用性較高。具體來說，與GT-R對比，LDP-ASDT的查詢精度提高了接近兩個數(shù)量級，相較于PrivAG、KDRQ和ASDQT也有顯著的提升。這歸因于LDP-ASDT算法不僅可以通過設(shè)定適當閾值定義稠密區(qū)域，而且算法本身能夠靈活地進行區(qū)域劃分：在稀疏區(qū)域采取粗粒度劃分方式，在稠密區(qū)域則進行細粒度劃分，這樣就有效地降低了查詢誤差。此外，LDP-ASDT算法在不同數(shù)據(jù)集上的表現(xiàn)始終保持穩(wěn)定，而GT-R與ASDQT算法的性能則受數(shù)據(jù)集的影響較大。在數(shù)據(jù)分布較為均勻且偏度較低的數(shù)據(jù)集上，兩種算法表現(xiàn)相對較好，這是由于GT-R算法采用均勻網(wǎng)格進行分割所導(dǎo)致的，而ASDQT算法僅通過四叉樹直接劃分區(qū)間，未考慮區(qū)域數(shù)據(jù)的密集程度，使得查詢誤差不穩(wěn)定。由于LDP-ASDT算法能夠通過先劃分稠密區(qū)域?qū)?shù)據(jù)進行更有效的處理，所以其結(jié)果更加穩(wěn)定。

3.2.2 查詢范圍對MSE的影響

為了研究查詢范圍對查詢結(jié)果的影響，本文對比了不同查詢范圍下五種算法的精確度。如圖5所示，實驗中查詢范圍覆蓋三個數(shù)據(jù)集的 [5% ， 50% ]，[ 10% 55% 」， [15%，60%] 。為了確保實驗的準確性，本文隨機對查詢范圍進行300次查詢，并取其平均值作為最終結(jié)果。從圖5所示結(jié)果可以看出，在隱私預(yù)算固定的情況下，查詢范圍與查詢精度呈負相關(guān)關(guān)系，即查詢范圍越小，查詢精度相對越高；查詢范圍越大，查詢精度則可能越低。但通過圖5可以發(fā)現(xiàn)，在不同隱私預(yù)算的Checkin數(shù)據(jù)集中，查詢范圍從 [5%，50%] 到[ 10% 新 55% ]變化時，均方誤差均隨著查詢范圍的增加而減小，即查詢精度更大，這是由于Checkin數(shù)據(jù)集中數(shù)據(jù)分布不均勻，隨著查詢范圍增加，范圍內(nèi)四叉樹索引節(jié)點個數(shù)變少，使得精度更加準確。

3.2.3 運行時間的對比

表2是在Checkin數(shù)據(jù)集查詢范圍為 [5% 50% ]時，不同隱私預(yù)算下五種算法的運行時間對比。本實驗的運行時間由空間劃分、樹的建立以及范圍查詢時間組成。由實驗結(jié)果可以看出，LDP-ASDT與ASDQT兩種算法在不同數(shù)據(jù)集中運算效率基本保持穩(wěn)定，而GT-R與PrivAG算法運行時間受隱私預(yù)算的影響較大，這是因為GT-R與PrivAG算法的網(wǎng)格粒度受隱私預(yù)算影響，而KDRQ由于在構(gòu)建索引時采用多種樹結(jié)合的方式，導(dǎo)致計算開銷較大，查詢速度較慢。LDP-ASDT相對于ASDQT算法的運行時間較短是由于LDP-ASDT算法可以劃分出稠密區(qū)域并做進一步分解，在數(shù)據(jù)分布不均勻或稠密數(shù)據(jù)集中具有更好的運行效率。

表2不同隱私預(yù)算的運行時間比較

Tab.2Comparison of runtimes for differentprivacybudgets

圖5不同查詢范圍的MSE比較Fig.5Comparison of MSE with different query ranges

4結(jié)束語

本文提出了一種LDP-ASDT算法，旨在基于本地化差分隱私解決稠密區(qū)間數(shù)據(jù)空間劃分的隱私保護問題。該算法首先使用自適應(yīng)網(wǎng)格劃分方法分出稀疏區(qū)域與稠密區(qū)域，解決了數(shù)據(jù)采集造成的噪聲誤差；然后在此基礎(chǔ)上進行自適應(yīng)分層分解方法，采用四叉樹索引與頻率估計的方法對稠密區(qū)域進一步分解；最后針對于各節(jié)點的頻率進行高效的后處理技術(shù)，提高數(shù)據(jù)查詢的精度。通過實驗與GT-R、PrivAG、KDRQ、ASDQT四種算法進行對比，結(jié)果表明，面對數(shù)據(jù)分布不均勻或稠密區(qū)域的數(shù)據(jù)集時，LDP-ASDT算法具有更好的查詢精度與運行效率。未來工作考慮將本文算法在動態(tài)數(shù)據(jù)發(fā)布與收集中進行拓展。

參考文獻：

[1］吳元洪，郭平，應(yīng)新洋．空間數(shù)據(jù)結(jié)構(gòu)分析［J]．計算機應(yīng)用研 究，2004，21（3）：39-41，84.（Wu Yuanhong，Guo Ping，Ying Xinyang. Analysis of spatial data structures [J].Application Research of Computers，2004，21（3）：39-41，84.）

[2]He Xiaofan，JinRicheng，Dai Huaiyu.Leveraging spatial diversity forprivacy-aware location-based services in mobile networks [J]. IEEE Trans on Information Forensics and Security，2018，13（6）： 1524- 1534.

[3]Omran E，Bokma A，Abu-Almaati S.A k -anonymity based semantic model for protecting personal information and privacy [C]//Proc of IEEE International Advance Computing Conference.Piscataway，NJ： IEEE Press，2009：1443-1447.

[4]Machanavajhala A，GehrkeJ，KiferD，etal.l-diversity：privacy beyond k -anonymity[C]//Proc of the22nd International Conference onData Engineering.Piscataway，NJ：IEEE Press，2006：24.

[5]Li Ninghui，Li Tiancheng，Venkatasubramanian S. t -closeness：privacy beyond k -anonymityand ξ_l -diversity[C]//Procofthe23rd IEEE International Conference on Data Engineering.Piscataway，NJ： IEEE Press，2007：106-115.

[6]Dwork C，McSherry F，Nissm K，et al. Calibrating noise to sensitivity in private data analysis[C]//Proc of the 3rd Theory of Cryptography Conference.New York：ACM Press，2006：265-284.

[7]Qardaji W，YangWeining，LiNinghui.Differentiallyprivate grids for geospatial data[C]// Proc of the 29th IEEE International Conference on Data Engineering. Piscataway，NJ： IEEE Press，2O13： 757-768.

[8] Xiong Ping，Zhang Lefeng，Zhu Tianqing.Reward-based spatial crowdsourcing with differential privacy preservation[J].Enterprise Information Systems，2017，11（10）：1500-1517.

[9]ToH，GhinitaG，F(xiàn)anLiyue，etal．Differentiallyprivatelocation protection for worker datasets in spatial crowdsourcing[J].IEEE Trans on Mobile Computing，2017，16（4）：934-949.

[10]Zhou Guoqiang，Qin Shui， Zhou Hongfei，et al.A differential privacynoise dynamic allocation algorithm for big multimedia data[J]. Multimedia Tools and Applications，2019，78（3）：3747-3765.

[11]Yang Jianyu，Cheng Xiang，Su Sen，et al.Collecting individual trajectories under local differential privacy[C]//Proc of the 23rd IEEE Intermational Conference on Mobile Data Management.Piscataway， NJ：IEEE Press，2022：99-108.

[12]Ali I，Murat K，Gabriel G，etal.Private record matching using differential privacy[C]//Procof the13th International Conference onExtending Database Technology.New York：ACM Press，2010：123-134.

[13]Cormode G，Procopiuc C，Srivastava D，et al．Diferentially private spatial decompositions [C]//Proc of the 28th IEEE International Conference on Data Engineering.Piscataway，NJ： IEEE Press，2O12：20-31.

[14]Zhang Jun，Xiao Xiaokui，Xie Xing.PrivTree：a differentially privatealgorithm for hierarchical decompositions[C]//Proc of International Conference on Management of Data. New York：ACM Press， 2016：155-170.

[15]Li Shuyu，Geng Yue，Li Yingle.A diferentially private hybrid decomposition algorithm based on quad-tree[J].Computers amp; Security，2021，109：102384.

[16]Kasiviswanathan SP，Lee HK，Nissm K，et al.What can we learn privately？[C]// Proc of the 49th Annual IEEE Symposium on Foundations of Computer Science.Piscataway，NJ：IEEE Press，2008： 531-540.

［17］張嘯劍，付楠，孟小峰．基于本地差分隱私的空間范圍查詢方法 [J]．計算機研究與發(fā)展，2020，57（4）：847-858．（Zhang Xiaojian，F(xiàn)u Nan，Meng Xiaofeng.Towards spatial rangequeries under local differential privacy[J].Joumal of Computer Research and Development，2020，57（4）：847-858.）

[18］金媛媛，倪志偉，朱旭輝，等．基于本地差分隱私的空間數(shù)據(jù)自 適應(yīng)劃分算法［J]．計算機工程，2022，48（5）：136-144.（Jin Yuanyuan，Ni Zhiwei，Zhu Xuhui，et al.Spatial data adaptive partition algorithm based on local diffrential privacy[J]. Computer Engineering，2022，48（5）：136-144.）

[19]Wang Huiwei，Huang Yaqian，Li Huaqing.Quadtree-based adaptive spatial decomposition for range queriesunder local differential privacy [J]. IEEE Trans on Emerging Topics in Computing，2023，11（4）： 1045-1056.

[20]Li Kaixuan，Zhang Hua，Xu Yanxin，et al.A range query scheme for spatial data with shuffled diferential privacy[J].Mathematics， 2024，12（13）： 1934.

[21]Feng Guanghui， Wang Guojun，Peng Tao.Toward answering federated spatial rangequeries under local diffrential privacy[J].International Joumal of Intelligent Systems，2024，2024（1）： 2408270.

[22]葉青青，孟小峰，朱敏杰，等．本地化差分隱私研究綜述［J]. 軟件學報，2018，29（7）：1981-2005.（Ye Qingqing，Meng Xiaofeng， Zhu Minjie，et al. Survey on local differential privacy[J].Journal of Software，2018，29（7）：1981-2005.）

[23]ErlingssonU，Pihur V，Korolova A.RAPPOR：randomized aggregatable privacy-preserving ordinal response[C]//Proc of ACM SIGSAC Conference on Computer and Communications Security. New York：ACM Press，2014：1054-1067.

[24]Wang Tianhao，BlockiJ，LiNinghui，et al.Optimizing locally differentially private protocols [EB/OL].（2017-05-12）.https：//arxiv. org/abs/1705.04421.

[25］徐明．基于節(jié)點分裂優(yōu)化的R-樹索引結(jié)構(gòu)［J]．計算機應(yīng)用研 究，2016，33（12）：3530-3534.（Xu Ming.R-tree index structure based on node splitting optimization[J].Application Research of Computers，2016，33（12）：3530-3534.）

[26]Samet H. The quadtree and related hierarchical data structures[J]. ACM Computing Surveys，1984，16（2）：187-260.

收稿日期：2024-11-05；修回日期：2025-01-13 基金項目：國家自然科學基金青年基金資助項目（61802161）；省應(yīng)用基礎(chǔ)研究計劃資助項目（2022JH2/101300278，2022JH2/101300279））;2024年省屬本科高校基本科研業(yè)務(wù)費專項資金資助項目（LJZ212410154025，LJZZ222410154004）；研究生教育改革創(chuàng)新項目（YJG2023013）

作者簡介：季博（201—），女，河南南陽人，碩士研究生，CCF會員，主要研究方向為差分隱私、隱私保護;李曉會（1978—），女（通信作者），盤錦人，教授，博士，主要研究方向為網(wǎng)絡(luò)安全、信任管理、隱私保護 （lhxlxh@163.com ）；賈旭（1983—），男，開原人，教授，博士，主要研究方向為機器學習、計算機視覺.