[發明專利]一種海量數據多維排序搜索方法

在審

• 申請號: 201710362446.2
• 申請日: 2017-05-12
• 公開（公告）號: CN107169114A
• 公開（公告）日: 2017-09-15
• 發明（設計）人: 趙志濱;顧佳良;姚蘭;高福祥
• 申請（專利權）人: 東北大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明涉及數據搜索技術領域，尤其涉及一種海量數據多維排序搜索方法。

背景技術

無線體域網的信息隱私包括用戶的各項生理參數，大量的隱私數據被存儲在云服務器中，密文檢索技術是解決云環境隱私安全問題的有效方法。當前的數據保護技術中，加密算法能夠較好地保護數據，但加解密計算會對系統效率產生極大的影響；數據拆分重裝策略的效率較高，但其對云平臺的結構和物理層次依賴性過大。因此，找到數據的實用性與安全性的平衡點是云存儲平臺應用中最為關鍵的問題。

CLEAR M提出基于多身份、多密鑰的層次全同態加密方案，滿足多用戶共享，不同身份密文計算。QIANH提出了適用于多機構系統的訪問控制方案。CLEAR M提出基于身份的純全同態加密方案，滿足多用戶共享和不同身份、不同屬性密文計算。Song DX提出了一種加密方式和密文順序檢索架構，該方法證明，在只知道密文的情況下，云存儲服務提供商不能截取任何明文的信息。但是，該方案的加密和查詢算法的時間復雜度為o(n)，其中n表示文檔長度。Goh EJ形式化的定義了安全索引結構-Z索引，該索引模型通過偽隨機函數和布隆過濾器(Bloom Filter)實現，可以抵抗適應性選擇關鍵字攻擊，然而，Z索引并不提供查詢排序機制，若查詢詞出現在大量文檔中，用戶需要從大量的結果集中篩選所需文檔。通過在倒排表中加入相關度分數，Wang C實現了支持結果集排序的密文檢索方法。在查詢階段，云服務器僅需返回與查詢條件匹配的前k個相關文檔，而不是所有滿足條件的文檔，這不但減少了帶寬的消耗，還改善了用戶體驗。然而，上述工作僅能解決單關鍵詞密文檢索的問題，即用戶在一次查詢中僅能提交一個查詢檢索詞。

為了更全面的表達用戶的查詢意圖，多關鍵字檢索技術應運而生。Sun W提出一種新的密文檢索框架MRSE以解決多關鍵字密文檢索問題。在索引建立階段，每個文檔被表示成一個二進制向量，其中每一位的值代表當前文檔是否包含該關鍵字。查詢向量以同樣的方式被表示成一個二進制向量。云服務器通過執行矩陣運算和安全k近鄰算法獲取排序的結果集并返回給用戶。然而，MRSE框架的查詢響應時間隨著文檔集的增長而增長，難以適應大數據時代數據迅速增長的需求。

為了加快查詢的速度，樹形結構普遍應用于索引的構建，比如在數據庫領域，Leslie H使用B樹來加快查詢速度，Ciaccia P通過構造M樹加快了對度量空間的索引過程。田雪等人將密文檢索框架MRSE進行優化，提出一種新型的密文索引結構：MRSE-SS，將相似查詢樹結構引入密文索引框架用于提升多關鍵字排序檢索的效率，并且提出一種動態聚類算法DK-MEDOIDS，聚類過程隨文檔量增加而動態變化，適用于云計算環境下的密文檢索場景，但是在該方法中在構建超球體時最壞的時間復雜度會達到o(n2)，并且若在查詢算法傳遞回文檔時，若最相關的超球體中文檔數少于所查詢的k個，則該方法不能解決這個問題。

發明內容

針對上述問題，本發明的目的在于提供一種快速的海量數據多維排序搜索方法。

為了解決背景技術中所存在的問題，本發明的技術方案為：

一種海量數據多維排序搜索方法，包括以下步驟：

1)根據數據庫中文檔的領域相關度，將文檔進行聚類，得到聚類組織相似查詢樹；

2)將不同的領域的聚類組織進行聚類，形成相似查詢樹；

3)獲取用戶提交的查詢向量，將查詢向量表示為查詢超球體；

4)根據查詢超球體與相似查詢樹中節點所代表的超球體的位置關系，獲取與查詢超球體交集最多的超球體，并對該超球體向下一層節點尋找，直到葉子節點，并查詢其左右鄰居節點，按照相關比例返回節點中k個最相關的文檔列表以及文檔向量。

所述步驟1)具體為：

1.1、根據數據庫中文檔的領域相關度，對相同領域的文檔生成一個多維的文檔向量DC；

1.2、設置單個槽中元素的門限值T；

1.3、初始化文檔向量DC中選擇向量值最大和最小的對象，分別做所有槽的上下界；

1.4、確定初始k值，將文檔向量DC化為等大小區間槽，利用公式(1)將所有文檔集放入對應槽中，選取其中與槽中心點最近的對象作為該聚類中心，所述公式(1)：

其中，p為文檔集中的點，Omax為文檔集中向量最大的對象，Omin為文檔集中向量最小的對象；

1.5、檢測所有槽中成員元素是否超過門限值T，若存在超過門限值T，則對該槽繼續進行聚類，生成子槽。

所述步驟1.3與1.4之間還包括步驟：