[發(fā)明專利]一種基于四叉樹自適應劃分技術的二維空間數(shù)據(jù)差分隱私發(fā)布方法

在審

• 申請?zhí)枺?/td>: 202011013025.7
• 申請日: 2020-09-24
• 公開（公告）號: CN112131603A
• 公開（公告）日: 2020-12-25
• 發(fā)明（設計）人: 金媛媛;劉勝軍;謝飛;倪志偉;卜凡耀;陳千;朱旭輝;周芳;倪麗萍
• 申請（專利權(quán)）人: 合肥城市云數(shù)據(jù)中心股份有限公司;合肥工業(yè)大學
• 主分類號: G06F21/62
• 分類號: G06F21/62;G06K9/62
• 代理公司: 合肥國和專利代理事務所(普通合伙) 34131
• 代理人: 張祥騫

本發(fā)明涉及一種基于四叉樹自適應劃分技術的二維空間數(shù)據(jù)差分隱私發(fā)布方法，與現(xiàn)有技術相比解決了難以高效劃分復雜分布數(shù)據(jù)空間、數(shù)據(jù)可用性差的缺陷。本發(fā)明包括以下步驟：二維空間數(shù)據(jù)的獲取；網(wǎng)格區(qū)域的劃分；自適應網(wǎng)格區(qū)域的劃分處理；對四叉樹進行后置處理；差分隱私二維空間數(shù)據(jù)的發(fā)布。本發(fā)明能夠有效的劃分各種復雜分布形式的二維空間數(shù)據(jù)集，降低數(shù)據(jù)的長范圍查詢誤差，實現(xiàn)二維空間數(shù)據(jù)的差分隱私有效發(fā)布。

技術領域

本發(fā)明涉及數(shù)據(jù)隱私發(fā)布技術領域，具體來說是一種基于四叉樹自適應劃分技術的二維空間數(shù)據(jù)差分隱私發(fā)布方法。

背景技術

近年來，移動社交網(wǎng)絡、車聯(lián)網(wǎng)等許多實際熱門應用產(chǎn)生了大量二維空間數(shù)據(jù)，使得二維空間數(shù)據(jù)及其統(tǒng)計數(shù)據(jù)的采集和使用越來越便捷。隨著信息技術的發(fā)展，需要將大量的用戶數(shù)據(jù)進行發(fā)布，為數(shù)據(jù)挖掘、分析處理等工作提供支持，然而這些數(shù)據(jù)的直接發(fā)布會給個人隱私造成威脅，用戶的隱私保護問題亟需得到保護。

針對這一問題，傳統(tǒng)基于K匿名的隱私保護技術需要對攻擊者的能力和背景知識進行假設估計，在實際應用中存在一定局限性。目前，差分隱私技術作為一種新出現(xiàn)的隱私保護框架，通過對發(fā)布數(shù)據(jù)進行隨機擾動，能夠為防止攻擊者在任意背景知識下的攻擊提供有力保護，在數(shù)據(jù)安全發(fā)布領域得到了廣泛應用。然而二維空間大數(shù)據(jù)尤為龐大，實際生活中的大數(shù)據(jù)隨著區(qū)域不同，其分布變化多樣，與差分隱私模型相結(jié)合后長范圍查詢誤差累積問題嚴重，所帶來的噪音誤差造成了數(shù)據(jù)的可用性降低，因此，在二維空間數(shù)據(jù)發(fā)布時如何平衡數(shù)據(jù)的隱私安全和數(shù)據(jù)的可用性，是當前隱私保護技術的一個主要目的。

對于二維空間統(tǒng)計數(shù)據(jù)的發(fā)布，通常需要將數(shù)據(jù)集進行劃分，其中常用的有基于網(wǎng)格結(jié)構(gòu)和樹結(jié)構(gòu)的劃分方法。在網(wǎng)格劃分方法中，均勻網(wǎng)格劃分算法(見文獻Qardaji W,Yang W,Li N.Differentially Private Grids for Geospatial Data[C]//2013 IEEE29th International Conference on Data Engineering(ICDE).IEEE,2013:757-758)對二維空間數(shù)據(jù)均勻的劃分為等寬的單元格，為每個單元格計數(shù)添加拉普拉斯噪音，沒有考慮到數(shù)據(jù)分布的不均勻性；自適應劃分策略(見文獻Qardaji W,Yang W,LiN.Differentially Private Grids for Geospatial Data[C]//2013 IEEE 29thInternational Conference on Data Engineering(ICDE).IEEE,2013:757-758)先以α·ε(0α1)的隱私預算使用均勻網(wǎng)格進行粗粒度劃分，再根據(jù)網(wǎng)格的密度以(1-α)·ε的隱私預算進行第二次自適應網(wǎng)格劃分，其考慮到數(shù)據(jù)分布的密度，但是沒有給出啟發(fā)式規(guī)則來區(qū)分數(shù)據(jù)稠密和稀疏的邊界。