[發明專利]一種基于差分隱私的批量線性查詢方法

有效

• 申請號: 201810042656.8
• 申請日: 2018-01-17
• 公開（公告）號: CN108280366B
• 公開（公告）日: 2021-10-01
• 發明（設計）人: 王迪;袁健;申澤宇
• 申請（專利權）人: 上海理工大學
• 主分類號: G06F21/62
• 分類號: G06F21/62
• 代理公司: 上海德昭知識產權代理有限公司 31204
• 代理人: 郁旦蓉

一種基于差分隱私的批量線性查詢方法，包括以下步驟：步驟1：查詢原始數據集R，得到數據查詢結果集M；步驟2：將R的屬性頻度按降序排列，篩選頻度不大于最小支持度的屬性并將該屬性以及與該屬性對應的數據丟棄；將大于最小支持度的屬性進行數據無關性處理，得到屬性頻度大于最小支持度的無關數據集D；步驟3：利用M在建立初始負載矩陣的基礎上建立數據無關負載矩陣W，采用并行梯度下降矩陣分解技術并行分解W，得到W的完整的分解結果的第一矩陣B以及分解結果的第二矩陣L；步驟4：基于差分隱私進行自適應加噪，對L以及D添加拉普拉斯噪音，并對丟棄的屬性以及數據進行還原，獲得加噪查詢結果數據集S；步驟5：將S返回給用戶。

技術領域

本發明涉及計算機技術領域，具體涉及一種基于差分隱私的批量線性查詢方法。

背景技術

隨著互聯網的發展，人類進入大數據時代。在對大數據進行處理時，批量線性查詢是最常用的操作，然而其查詢規模極大，查詢過程繁雜，性能較低。另外，在使用大數據的過程中，很多敏感信息極易被泄漏，而無法同時保證查詢精度(數據可用性)和隱私保護程度。

現有技術的算法無法同時保證批量線性查詢的算法性能、查詢精度和隱私保護程度。在算法性能上，現有算法復雜度高，不適用于大規模批量線性查詢；在查詢精度上，現有算法在查詢結果上添加噪音來減小所需的噪音量，以此優化查詢精度。然而，當查詢序列是用戶任意給定時，這些機制為了找到最優的噪音分布需要的計算開銷非常大，隨數據維度增加呈指數增長，無法用于大數據集；在隱私保護程度上，現有算法沒有將添加的噪音量與用戶權限結合起來考慮，無法保證對不同權限用戶添加的噪音量都合適，對于高權限用戶，若添加噪音過多，則其受噪音干擾大，查詢精度降低；對于低權限用戶，若添加噪音過少，則會導致隱私保護程度不足。

發明內容

本發明是為了解決上述問題而進行的，目的在于提供一種基于差分隱私的批量線性查詢方法。

本發明提供了一種基于差分隱私的批量線性查詢方法，具有這樣的特征，包括：步驟1：查詢原始數據集R，得到數據查詢結果集M；步驟2：將原始數據集R的屬性頻度按降序排列，設定最小支持度篩選頻度不大于最小支持度的屬性并將該屬性以及與該屬性對應的數據丟棄；將大于最小支持度的屬性采用FP-tree獲取數據的關聯屬性后進行數據無關性處理，得到屬性頻度大于所述最小支持度的無關數據集D；步驟3：利用數據查詢結果集M，建立初始負載矩陣，利用步驟2中的屬性相關性在所述初始負載矩陣的基礎上建立數據無關負載矩陣W，采用并行梯度下降矩陣分解技術并行分解所述數據無關負載矩陣W，得到數據無關負載矩陣W的完整的分解結果的第一矩陣B以及分解結果的第二矩陣L；步驟4：基于差分隱私進行自適應加噪，對所述分解結果的第二矩陣L以及所述屬性頻度大于所述最小支持度的無關數據集D添加拉普拉斯噪音，并對步驟2中丟棄的頻度不大于最小支持度的屬性以及該屬性對應的數據進行還原，獲得加噪查詢結果數據集S；步驟5：將加噪查詢結果數據集S返回給用戶。

在本發明提供的基于差分隱私的批量線性查詢方法中，還可以具有這樣的特征：其中，步驟2中的基于關聯性分析的所述數據無關性處理包括以下步驟：步驟2-1：對所述原始數據集R進行掃描，得出所述原始數據集R中每一個屬性的頻度，按照屬性頻度進行降序排列，得到屬性頻度降序列表；步驟2-2：設定最小支持度，根據所述屬性頻度降序列表，將頻度不大于所述最小支持度的屬性及與該屬性對應的數據去掉；步驟2-3：將去掉所述頻度不大于所述最小支持度的屬性及對應數據的剩余原始數據集R’以前綴樹進行存儲，構成FP-tree，并對第一次出現的節點建立鏈表；步驟2-4：用FP-growth算法對FP-tree進行整理，挖掘出關聯模式；步驟2-5：判斷葉子節點是否為單路徑，當判斷結果為是時，去除所述葉子節點，生成前綴路徑的集合，進入步驟2-6；當判斷結果為否時，生成各路徑前綴路徑的集合，構成一個新的FP-tree，返回至步驟2-4；步驟2-6：獲取步驟2-5生成的所述前綴路徑的集合，定義為數據的關聯屬性；步驟2-7：進行數據的無關性處理，利用屬性的關聯性去除冗余數據。