[發明專利]一種外包空間數據庫中反最遠鄰居驗證方法

有效

• 申請號: 201710196480.7
• 申請日: 2017-03-29
• 公開（公告）號: CN106970983B
• 公開（公告）日: 2020-02-21
• 發明（設計）人: 谷峪;王海霞;李芳芳;于戈
• 申請（專利權）人: 東北大學
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/24
• 代理公司: 沈陽優普達知識產權代理事務所(特殊普通合伙) 21234
• 代理人: 俞魯江

1.一種適合外包空間數據庫中反最遠鄰居驗證方法，其特征在于，外包數據過程中，使得第三方服務器和客戶端之間不存在安全信任關系，客戶端通過MR-Tree索引機制對數據來源的可靠性進行正確地檢驗，整個處理流程分為第三方服務器端處理和客戶端驗證兩個部分，包括以下步驟：

第三方服務器端處理：

步驟1：基于MR-Tree索引機制，預處理高維空間數據；

步驟2：離線構建k-depth contour并為處于k-depth contour內部的無效數據對象生成fVO；

步驟3：判斷用戶請求與k-depth contour的所屬關系；

步驟4：利用Influenced Zone篩選出結果集，生成驗證結果集的fVO；

步驟5：第三方服務器發送其計算的結果集、uVO、fVO、uRoot、fRoot、Influenced Zone；

客戶端驗證：

步驟6：uVO、fVO、uRoot、fRoot逆向生成驗證數據來源的正確性；

步驟7：利用fVO驗證Influenced Zone的正確性；

步驟8：利用四象限測試法驗證Influenced Zone為空；

步驟9：驗證結果集的正確性；

客戶端驗證Influenced Zone方式，所述步驟7利用fVO來檢驗Influenced Zone的邊和頂點正確性，所述步驟8利用四象限測試法和fVO來驗證Influenced Zone為空的情況，而客戶端驗證的核心技術就是對Influenced Zone的檢驗，其驗證過程如下：

在Influenced Zone存在的前提下，利用fVO來驗證Influenced Zone是否正確；

步驟7-1：驗證Influenced Zone的邊界點是否正確；

Influenced Zone的邊界點由非數據空間邊界點組成或者由非數據空間邊界點和數據空間邊界點共同組成，因此，對于非數據空間邊界點的驗證用如下公式：

count(¤(v_i,q)∩d_k)>k

count(¤(v_i,q)∩M_k)＝0

而對于數據空間邊界點的驗證將采用下面的公式：

count(¤(v_j,q)∩d_k)<＝k

count(¤(v_j,q)∩M_k)＝0

這里，count()代表計數函數，q代表用戶查詢請求，v_i代表非數據空間邊界點，v_j代表數據空間邊界點，¤表示圓上及外部區域，¤(v_i,q)代表v_i為圓心，v_i到q的距離為半徑形成的圓上及外部區域，d_k代表fVO中的數據對象，M_k代表fVO中的實體對象；

如果Influenced Zone的邊界點驗證失敗，則客戶端將拒絕接受服務器端發送來的結果集；否則，將進行步驟7-2處理；

步驟7-2：驗證Influenced Zone的邊是否正確；

Influenced Zone邊由查詢請求q和fVO中某數據對象的中垂線構成的，或者可能外加部分數據空間邊界線構成的；首先檢驗Influenced Zone邊是否是q和fVO中某數據對象形成的中垂線，對于不是中垂線形成的邊，進一步檢驗該邊是不是數據空間的邊界線，如果都不是，則驗證失敗，客戶端拒收服務器端發送來的結果，否則，將繼續驗證Influenced Zone邊；

驗證無數據空間邊界頂點組成的邊e_i采用如下公式：

count(¤(e_i,q)∩d_k)＝k+1

而有數據空間邊界頂點組成的邊e_j則采用下面公式進行檢驗：

count(¤(e_j,q)∩d_k)<k+1

如果Influenced Zone通過了上述驗證，則說明該Influenced Zone是正確的，客戶端需要進行下一步結果集的檢驗；

步驟8：Influenced Zone不存在，客戶端將判斷服務器端發來的信息的可靠性和正確性；

對于Influenced Zone為空的情況有兩種：一是查詢請求處于在k-depth contour內部，即為無效查詢，二是查詢請求處于k-depth contour上或者外部，Influenced Zone為空是由于被修剪至空，這兩種情況采用的思想一致；

以查詢請求q為原點，以查詢請求q為原點，根據四象限測試法的原理，劃分數據空間為四個象限，統計fVO中數據對象分布在每個象限的數目，如果某個象限的數目超過k個，則對角線的象限被修剪，通過被修剪的象限中數據對象來修剪未被修剪的象限，如果整個數據空間被修剪掉，則說明服務器端發送來的信息是完全正確的，否則，驗證失敗，重新發送查詢請求。