基於差分隱私的數據倉庫星型連接查詢方法、系統及介質與流程

2024-04-13 00:05:05 1

1.本發明屬於數據收集與分析技術領域，具體涉及一種基於差分隱私的數據倉庫星型連接查詢方法、系統及介質。


背景技術：

2.隨著人工智慧與大數據技術迅速發展，使得數據收集與分析變得尤其容易，服務方根據收集到的數據提高服務質量，以便開發出更具有個性化的工具。星型連接查詢是關係資料庫中的典型應用之一，數據分析者向收集數據的可信伺服器提出查詢，伺服器根據收集到的數據響應查詢結果。然而，不可信的數據分析者可能會從多個響應結果中推測出用戶的隱私信息，進而威脅個人的財產和安全，主要原因是伺服器根據個人的原始數據響應查詢結果，而使得個人無法掌握自己的隱私數據，差分隱私的出現使伺服器擾動查詢結果之後再響應分析者的查詢，目前差分隱私著眼於聚合查詢等研究，而涉及星型連接查詢的工作卻很少。
3.近年來，數據倉庫中的星型連接查詢廣泛應用在olap(on-line analytic processing)中，而如何在保護用戶隱私的同時響應星型連接查詢已經成為一種差分隱私研究的新思路。目前基於連接查詢的差分隱私方案一般包含三個步驟：伺服器先計算關於連接查詢操作的全局敏感度，然後對真實查詢結果添加噪聲，其中根據計算的全局敏感度大小和隱私代價ε校驗噪聲，最後響應噪聲擾動後的查詢結果。然而，由於數據對星型連接查詢操作高度敏感，一條數據的刪除和添加可能對連接操作的查詢結果受維度表的數目影響，其全局敏感度為o(n
n-1
)，其中n為每個維度但閾值，n表示維度表的個數
1.。因此，當前面向星型連接查詢操作的差分隱私方案普遍存在全局敏感度過大的問題，最終導致查詢結果可用性較低。
4.針對全局敏感度過大的問題，目前的差分隱私方案集中於設計一種敏感度的計算方式近似代替全局敏感度，例如局部敏感度、平滑敏感度、彈性敏感度和殘差敏感度。但以上幾種計算方式都存在一些缺陷，局部敏感度依賴於數據，使用其校驗噪聲無法滿足差分隱私；而平滑敏感度、彈性敏感度和殘差敏感度均是求取局部敏感度的一個上限值，平滑敏感度數值最小但其計算代價高，而彈性敏感度和殘差敏感度計算代價較小但數值較大。因此，求取近似全局敏感度的方式並不能從本質上改善數據對連接查詢的影響。
5.除此之外，星型連接為一個事實表和多個維度表的連接，隨著維度表的擴展，數據對連接查詢操作的影響也隨之增加，敏感度也隨之增大，導致其噪聲增加，對查詢結果的影響是呈指數級增加的。同時，對於星型連接的查詢，伺服器會先將維度表進行連接，得到查詢結果之後再添加噪聲，而維度表的增加可能會導致高昂的計算開銷。
6.以上方案僅考慮到敏感度的計算方式並不能解決維度表擴展所引起的問題。
7.[1]wei dong and keyi.a nearly instance-optimal differentially private mechanism for conjunctive queries.in pods 2022.


技術實現要素：

[0008]
本發明的目的在於針對上述現有技術中的問題，提供一種基於差分隱私的數據倉庫星型連接查詢方法、系統及介質，可從查詢的角度降低星型連接查詢的全局敏感度，減少噪聲對查詢結果的影響，不僅可以提高查詢精度，還可以擴展至多個維度表的星型連接查詢。
[0009]
為了實現上述目的，本發明有如下的技術方案：
[0010]
第一方面，提供一種基於差分隱私的數據倉庫星型連接查詢方法，包括：
[0011]
伺服器接收星型連接查詢，提取查詢謂詞，對查詢謂詞涉及的查詢區間範圍添加噪聲；
[0012]
在添加噪聲後的查詢區間對查詢中的聚合函數進行響應，得到擾動後的查詢結果；
[0013]
將擾動後的查詢結果響應給數據分析師。
[0014]
優選的，假定數據倉庫d＝{d1,d2,
…
,dn}包含n個維度表，每個維度表的閾值設置為n；根據查詢所涉及到的維度數目為k，k≤n分別添加噪聲，如果一條記錄的變化影響n個區間，則每個維度的全局敏感度均為n；假設一星型連接查詢q的查詢謂詞涉及所有的維度區間為q＝{d1：[l1，h1]，d2：[l1，h1]，...，dn：[ln，hn]}，其中，[li，hi]表示在第i∈n個維度上的查詢區間。
[0015]
優選的，所述對查詢謂詞涉及的查詢區間範圍添加噪聲的方式包括：
[0016]
區間兩端加噪：對每個查詢區間的兩個端點添加拉普拉斯噪聲；
[0017]
區間寬度加噪：固定每個查詢區間其中的一個端點，對區間寬度添加拉普拉斯噪聲；
[0018]
區間分解加噪：在每個維度上根據概念層次分別構建維度樹，在擾動查詢區間之前先根據維度樹分解為多個子區間，再分別對每個子區間添加噪聲。
[0019]
進一步的，作為本發明噪聲添加方式的一種優選方案，所述的區間兩端加噪，將隱私代價均分為兩個部分，一部分用於左端點，另一部分用於右端點；
[0020]
擾動後的查詢為q
′
＝{d
′1：[l
′1，h
′1]，d
′2：[l
′2，h
′2]，...，d
′n：[l
′n，h
′n]}；
[0021]
其中，為第i維上擾動後的查詢區間。
[0022]
進一步的，作為本發明噪聲添加方式的一種優選方案，所述的區間寬度加噪，擾動後的查詢為q
′
＝{d
′1：[l
′1，h
′1]，d
′2：[l
′2，h
′2]，...，d
′n：[l
′n，h
′n]}；
[0023]
其中，[l
′i，h
′i]＝[li，li+(|h
i-li+1|+lap(n/ε))]為第i維上擾動後的查詢區間。
[0024]
進一步的，作為本發明噪聲添加方式的一種優選方案，所述的區間分解加噪，假設維度樹的分支是b，則其樹高為t＝logbn；星型連接查詢q的查詢謂詞為{d1：[l1，h1]，d2：[l1，h1]，...，dn：[ln，hn]}，對於第i∈n個維度的查詢區間[li，hi]，根據第i維上的樹結構將查詢區間[li，hi]分解為[li，hi]＝{[l
i1
，h
i1
]，...，[l
it
，h
it
]}，對每個子區間進行噪聲擾動得到[l
′i，h
′i]＝{[l
′
i1
，h
′
i1
]，...，[l
′
it
，h
′
it
]}，其中，[l
′
ij
，h
′
ij
]，j∈t為擾動後的子區間。
[0025]
更進一步的，所述擾動後的子區間[l
′
ij
，h
′
ij
]通過以下兩種方式計算：
[0026][0027]
或為
[0028][0029]
第二方面，提供一種基於差分隱私的數據倉庫星型連接查詢系統，包括：
[0030]
噪聲添加模塊，用於伺服器接收星型連接查詢之後，提取查詢謂詞，對查詢謂詞涉及的查詢區間範圍添加噪聲；
[0031]
查詢結果擾動模塊，用於在添加噪聲後的查詢區間對查詢中的聚合函數進行響應，得到擾動後的查詢結果；
[0032]
響應模塊，用於將擾動後的查詢結果響應給數據分析師。
[0033]
優選的，所述噪聲添加模塊對查詢謂詞涉及的查詢區間範圍添加噪聲的方式包括：
[0034]
區間兩端加噪：對每個查詢區間的兩個端點添加拉普拉斯噪聲；
[0035]
區間寬度加噪：固定每個查詢區間其中的一個端點，對區間寬度添加拉普拉斯噪聲；
[0036]
區間分解加噪：在每個維度上根據概念層次分別構建維度樹，在擾動查詢區間之前先根據維度樹分解為多個子區間，再分別對每個子區間添加噪聲。
[0037]
第三方面，提供一種計算機可讀存儲介質，所述計算機可讀存儲介質存儲有電腦程式，所述電腦程式被處理器執行時實現所述基於差分隱私的數據倉庫星型連接查詢方法的步驟。
[0038]
相較於現有技術，本發明至少具有如下的有益效果：
[0039]
本發明從可用性、效率和擴展性三個方面考慮，提出一種面向數據倉庫中星型連接查詢的差分隱私方案，針對差分隱私的星型連接查詢設計了一種先對查詢方式添加噪聲再響應查詢的方案，可從查詢的角度降低星型連接查詢的全局敏感度，減少噪聲對查詢結果的影響。採取對每個維度上的查詢區間的擾動方式，從本質上降低了星型連接查詢操作的全局敏感度。此外，即使是擴展至n個維度表，所引入的噪聲也不會隨維度表的個數呈冪次增加。由於對每個維度查詢區間分別添加擾動再響應查詢的方式，可採取並行的方式進行擾動，減少了計算開銷。該方案不僅可以提高查詢精度，還可以擴展至多個維度表的星型連接查詢。
附圖說明
[0040]
為了更加清楚地說明本發明實施例的技術方案，下面將對實施例中所需要使用的附圖作以簡單地介紹，應當理解，以下附圖僅示出了本發明部分實施例，對於本領域普通技術人員而言，在不付出創造性勞動的前提下，還可以根據這些附圖獲得其他相關的附圖。
[0041]
圖1本發明基於差分隱私的數據倉庫星型連接查詢方法場景應用示意圖；
[0042]
圖2本發明基於差分隱私的數據倉庫星型連接查詢方法流程圖。
具體實施方式
[0043]
下面將結合本發明實施例中的附圖，對本發明實施例中的技術方案進行清楚、完整地描述，顯然，所描述的實施例僅僅是本發明一部分實施例，而不是全部的實施例。基於本發明中的實施例，本領域普通技術人員還可以在沒有做出創造性勞動的前提下獲得其他
實施例。
[0044]
由於數據對連接查詢操作高度敏感，一條數據的刪除和添加可能對連接操作的查詢結果的影響是無限值。因此當前面向數據倉庫中星型連接查詢操作的差分隱私方案普遍存在全局敏感度過大的問題，導致查詢結果可用性較低。此外，現有的星型連接查詢的差分隱私方案無法均衡可用性、效率和擴展性三個方面。本發明從可用性、效率和擴展性三個方面考慮，提出一種面向數據倉庫中星型連接查詢的差分隱私方案，可從查詢的角度降低星型連接查詢的全局敏感度，減少噪聲對查詢結果的影響，該方案不僅可以提高查詢精度，還可以擴展至多個維度表的星型連接查詢。現有的數據倉庫星型連接查詢方案主要有以下缺點：
[0045]
1、查詢結果的可用性低。數據對星型連接查詢操作高度敏感，即使是局部敏感度的近似上限值，其數值也很大，直接會導致對查詢結果引入過多的噪聲。
[0046]
2、擴展性差。通常數據倉庫的星型連接包含多個維度表的連接，現有方案針對維度表的增加，其敏感度的數值也是隨維度表個數的冪次變化，因此當擴展至n個維度表時使用受限。
[0047]
3、計算耗時間。現有的差分隱私方案先連接維度表再添加噪聲，而多個維度表會導致高昂的計算開銷。
[0048]
本發明針對現有技術的不足，提出一種設計合理、安全高效的查詢方法，即先對查詢方式添加噪聲再響應查詢。從敏感度的計算方式上會比現有方案的敏感度降至多個數量級，即使是擴展至n個維度表，所引入的噪聲也不會隨維度表的個數呈冪次增加。由於採取先對查詢方式添加噪聲再響應查詢的方式，可對連接查詢的謂詞可並行擾動，減少計算開銷。
[0049]
參見圖2，本發明實施例基於差分隱私的數據倉庫星型連接查詢方法，包括以下步驟：
[0050]
伺服器接收星型連接查詢，提取查詢謂詞，對查詢謂詞涉及的查詢區間範圍添加噪聲；
[0051]
在添加噪聲後的查詢區間對查詢中的聚合函數進行響應，得到擾動後的查詢結果；
[0052]
將擾動後的查詢結果響應給數據分析師。
[0053]
參見圖1，圖1示出了本發明基於差分隱私的數據倉庫星型連接查詢方法場景應用，不受信任的數據分析者向伺服器提出星型連接查詢q，伺服器根據收集到的數據倉庫d以加噪的方式向數據分析者響應查詢。其中主要過程為伺服器以差分隱私的方式響應星型連接查詢，即如何設計滿足差分隱私的加噪方式。而本發明方法採取對查詢添加噪聲再響應的方式，設計了三種針對查詢的加噪方式，本發明方法主要包含以下兩個過程：
[0054]
a.查詢加噪，即q
′
＝q+noise；
[0055]
b.聚合加噪查詢，即q
′
(d)；
[0056]
假定數據倉庫d＝{d1,d2,
…
,dn}包含n個維度表，每個維度表的閾值設置為n。根據查詢所涉及到的維度數目為k(k≤n)分別添加噪聲，一條記錄的變化影響n個區間，因此每個維度的全局敏感度均為n。假設一星型連接查詢q的查詢謂詞涉及所有的維度區間為q＝{d1:[l1,h1],d2:[l1,h1],
…
,dn:[ln,hn]},其中[li,hi]表示在第i∈n個維度上的查詢區間。
[0057]
針對過程a，本發明設計了三種不同的查詢區間加噪方式。
[0058]
一、區間兩端加噪
[0059]
對每個查詢區間的兩個端點添加拉普拉斯噪聲，將隱私代價均分為兩個部分，一部分用於左端點，另一部分用於右端點。
[0060]
即擾動後的查詢為q
′
＝{d
′1：[l
′1，h
′1]，d
′2：[l
′2，h
′2]，...，d
′n：[l
′n，h
′n]}；
[0061]
其中，為第i維上擾動後的查詢區間。
[0062]
二、區間寬度加噪
[0063]
固定每個查詢區間其中的一個端點，對區間寬度添加拉普拉斯噪聲。
[0064]
擾動後的查詢為q
′
＝{d
′1：[l
′1，h
′1]，d
′2：[l
′2，h
′2]，...，d
′n：[l
′n，h
′n]}。
[0065]
其中，[l
′i，h
′i]＝[li，li+(|h
i-li+1|+lap(n/ε))]為第i維上擾動後的查詢區間。
[0066]
三、區間分解加噪
[0067]
在每個維度上根據概念層次分別構建維度樹，在擾動查詢區間之前先根據維度樹分解為多個子區間，再分別對每個子區間添加噪聲。
[0068]
假設維度樹的分支是b，則其樹高為t＝logbn。
[0069]
q的查詢謂詞為{d1：[l1，h1]，d2：[l1，h1]，...，dn：[ln，hn]}，以第i∈n個維度的查詢區間[li，hi]為例，根據第i維上的樹結構可將[li，hi]分解為[li，hi]＝{[l
i1
，h
i1
]，...，[l
it
，h
it
]}，對每個子區間進行噪聲擾動得到[l
′i，h
′i]＝{[l
′
i1
，h
′
i1
]，...，[l
′
it
，h
′
it
]}。其中，[l
′
ij
，h
′
ij
]，j∈t為擾動後的子區間。
[0070]
[l
′
ij
，h
′
ij
]可以有兩種計算方式：
[0071][0072]
或為
[0073][0074]
最後，進行過程b。由上述的三種加噪方式可得到擾動後的查詢q
′
，再對查詢中的聚合函數進行響應得到最終的查詢結果q
′
(d)，將其響應至數據分析者。
[0075]
本發明的另一實施例提出一種基於差分隱私的數據倉庫星型連接查詢系統，包括：
[0076]
噪聲添加模塊，用於伺服器接收星型連接查詢之後，提取查詢謂詞，對查詢謂詞涉及的查詢區間範圍添加噪聲；
[0077]
查詢結果擾動模塊，用於在添加噪聲後的查詢區間對查詢中的聚合函數進行響應，得到擾動後的查詢結果；
[0078]
響應模塊，用於將擾動後的查詢結果響應給數據分析師。
[0079]
在一種可能的實施方式中，所述噪聲添加模塊對查詢謂詞涉及的查詢區間範圍添加噪聲的方式包括：
[0080]
區間兩端加噪：對每個查詢區間的兩個端點添加拉普拉斯噪聲；
[0081]
區間寬度加噪：固定每個查詢區間其中的一個端點，對區間寬度添加拉普拉斯噪聲；
[0082]
區間分解加噪：在每個維度上根據概念層次分別構建維度樹，在擾動查詢區間之
前先根據維度樹分解為多個子區間，再分別對每個子區間添加噪聲。
[0083]
本發明針對差分隱私的星型連接查詢設計了一種先對查詢方式添加噪聲再響應查詢的方案，技術方案中的重點和關鍵點至少體現在以下幾個方面：
[0084]
1.考慮到目前星型連接查詢的差分隱私方案中全局敏感度過大的問題，本發明設計了一種對查詢擾動的方式降低敏感度的影響。
[0085]
2.每個維度相互獨立，分別對星型連接查詢涉及到的維度查詢區間添加噪聲，設計了三種不同的查詢區間加噪方式。
[0086]
3.考慮區間端點和區間寬度兩個區間表達方式的擾動。
[0087]
3.採用樹形結構對區間分解之後再添加噪聲，進一步提高查詢精度。
[0088]
本發明的另一實施例還提供一種計算機可讀存儲介質，所述計算機可讀存儲介質存儲有電腦程式，所述電腦程式被處理器執行時實現所述基於差分隱私的數據倉庫星型連接查詢方法的步驟。
[0089]
所述的電腦程式可以被分割成一個或多個模塊/單元，所述一個或者多個模塊/單元被存儲在所述存儲器中，並由所述處理器執行，以完成本發明一種基於差分隱私的數據倉庫星型連接查詢方法。
[0090]
所述的終端可以是桌上型計算機、筆記本、掌上電腦及雲端伺服器等計算設備，也可以是處理器、存儲器。處理器可以是中央處理單元(centralprocessingunit，cpu)，還可以是其他通用處理器、數位訊號處理器(digitalsignalprocessor，dsp)、專用集成電路(applicationspecificintegratedcircuit，asic)、現成可編程門陣列(field-programmablegatearray，fpga)或者其他可編程邏輯器件、分立門或者電晶體邏輯器件、分立硬體組件等。存儲器可用於存儲電腦程式和/或模塊，所述處理器通過運行或執行存儲在所述存儲器內的電腦程式和/或模塊，以及調用存儲在存儲器內的數據，實現本發明基於差分隱私的數據倉庫星型連接查詢系統的各種功能。
[0091]
以上內容是結合具體的優選實施方式對本發明所作的進一步詳細說明，不能認定本發明的具體實施方式僅限於此，對於本發明所屬技術領域的普通技術人員來說，在不脫離本發明構思的前提下，還可以做出若干簡單的推演或替換，都應當視為屬於本發明由所提交的權利要求書確定專利保護範圍。