[發明專利]一種基于層次模型的差分隱私邏輯網格空間數據發布方法

有效

• 申請號: 202110040810.X
• 申請日: 2021-01-13
• 公開（公告）號: CN112784297B
• 公開（公告）日: 2022-11-08
• 發明（設計）人: 張偉;倪松;陳云芳
• 申請（專利權）人: 南京郵電大學
• 主分類號: G06F21/62
• 分類號: G06F21/62
• 代理公司: 南京蘇高專利商標事務所(普通合伙) 32204
• 代理人: 柏尚春

本發明公開了一種基于層次模型的差分隱私邏輯網格空間數據發布方法，具體步驟包括：(1)四分自適應劃分；(2)邏輯合并；(3)邏輯劃分；(4)構建層次模型，利用邏輯合并，在不引入較多均勻假設誤差的前提下大幅度降低了噪聲誤差，有效地解決了由于數據點分布偏斜所導致的劃分不充分問題；并創新性地通過查詢貢獻度，將大區域劃分為若干形狀均勻的小區域，進一步降低均勻假設誤差，實現噪聲誤差與均勻假設誤差的優化，從而在保證數據隱私的同時提高發布數據的可用性。

技術領域

本發明涉及數據隱私保護領域，特別涉及一種基于層次模型的差分隱私邏輯網格空間數據發布方法。

背景技術

隨著物聯網與大數據技術的迅速發展，數據的采集與發布愈發普遍，數據的價值也在不斷提升。其中，二維空間數據更是與人類的日常生活息息相關，在人們日常生活中很多與網絡的交互行為都不經意間會生成空間數據。對這些空間數據的合理利用能使企業為用戶帶來更多便利，從而獲取巨大的商業利潤。同時，空間數據往往涉及到用戶的個人隱私，若被不法分子加以利用會產生不可預估的后果。因此，如何在保證數據隱私性的前提下，最大程度地提高二維空間數據的可用性顯得格外重要。

目前最常見的隱私保護模型是匿名模型和差分隱私模型。差分隱私模型相較于基于匿名技術的隱私保護模型不需要進行過多特定的背景知識假設是當前保護二維空間數據的主流方法。

在差分隱私二維空間數據發布任務中，影響發布結果查詢精確度的因素主要源于兩種誤差。按誤差產生的方式來分，可以分為由差分隱私實現機制引入的噪聲誤差和劃分后的結構在響應查詢時采用均勻分布假設引入的均勻假設誤差。兩類誤差在劃分中的產生都是不可避免的。一般情況下，噪聲誤差和均勻假設誤差的存在是相互對立的，當數據域被劃分得粗糙時噪聲誤差雖然很小，但是此時估計均勻誤差卻很大，若是數據域被劃分得過于細致，雖然降低了估計均勻誤差的值，然而卻累積了過大的噪聲誤差。由此可見差分隱私空間數據發布問題本質上就是尋找兩類誤差之間的均衡點。

當前基于差分隱私的空間數據發布方法采用的數據索引技術主要是網格結構和層次結構。網格結構的代表算法UG和AG均未能充分考慮到真實數據分布的偏斜性，而樹形結構的代表算法Quad-post和DP-Tree所添加噪聲大小都嚴重依賴與樹的高度，這些算法均未能很好的均衡兩種誤差。

發明內容

發明目的：本發明的目的是提供一種基于層次模型的差分隱私邏輯網格空間數據發布方法，能夠均衡自適應網格劃分AG與層次模型的誤差，使誤差和降到最優,同時構建層次模型來構建索引結構，并對層次模型進行后置處理，提高大范圍查詢的響應時間和查詢精度。

技術方案：本發明所述的一種基于層次模型的差分隱私邏輯網格空間數據發布方法，包括有以下步驟：

S1：四分自適應劃分：對數據域進行四分自適應網格劃分，將數據域劃分為若干個細粒度網格，并對這些細粒度網格的真實計數值添加噪聲；

S2：邏輯合并：將噪聲計數值相似的鄰近細粒度網格進行合并，形成邏輯網格；進一步將分布密度相似的邏輯網格合并成若干個邏輯網格域；

S3：邏輯劃分：根據查詢貢獻率，將邏輯網格劃分成若干個葉子網格；

S4：構建層次模型：將邏輯網格域、邏輯網格、葉子網格構建成層次模型并對每層的節點計數添加噪聲并進行后置處理，最后將所得層次模型發布。

作為優選，所述S1具體包括以下步驟：

S1.1：根據數據域的數據點個數N、分配的隱私保護預算α₁ε和常數c，計算粗粒度劃分參數m₁：