[發明專利]一種區間持久性top-k查詢的雙哈希表關聯方法

有效

• 申請號: 201210080249.9
• 申請日: 2012-03-23
• 公開（公告）號: CN102663030A
• 公開（公告）日: 2012-09-12
• 發明（設計）人: 張勇;明華;邢春曉
• 申請（專利權）人: 清華大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京聿宏知識產權代理有限公司 11372
• 代理人: 王建軍;謝鑫

技術領域

本發明涉及數據庫以及查詢領域，尤其涉及一種區間持久性top-k查詢的雙哈希表關聯方法。

背景技術

隨著互聯網的迅猛發展以及信息量的爆炸性增長，精確搜索用戶所需信息的難度越來越大，如何從海量數據中查找到用戶最關心的信息已成為業界普遍關注的問題。因此，出現了top-k查詢技術，即根據評分函數在潛在的數據空間中返回k個最重要的結果。此技術非常有效而且已經非常成熟，廣泛應用于各個領域。有效地解決了從海量數據中精確查詢的排名問題，與全文檢索技術一起為數據庫查詢領域作出了巨大的貢獻，深受用戶歡迎。文檔是記錄各類信息的重要載體，其重要性不言而喻。企業特別是大中型企業，文檔數據呈現一些新的特點：類型多樣、數量日益劇增，版本更新頻繁等等。大量的文檔數據以及文檔產生的不同版本對關鍵詞的查詢檢索提出了新的難題：隨著時間的推移，電子文檔(包括企業文檔、各類網站電子文檔等)的內容不斷地被更新或修改逐漸形成各種不同的版本，每個版本具有一個有效的時間間隔。一般而言，在此時間間隔內文檔與關鍵詞的匹配度恒定，而在此時間間隔外每個版本的內容與查詢關鍵字的相關性(匹配度)不盡相同，正是由于這種相關性(匹配度)在查詢條件的時間范圍內存在不同，致使傳統查詢(如：top-k查詢、全文檢索等)方法都無法返回精確的結果。因此，引入了區間持久性top-k查詢技術。此技術能返回長期處于top-k結果中表現主題一致的文檔對象。彌補了top-k查詢技術只能返回某一時間點的、(查詢關鍵字與文檔內容匹配度)得分不變的、前k個最重要結果的缺陷。區間持久性top-k查詢能有效地查找到長期反映某一主題的文檔對象，為文檔的版本管理和涉及時間序列的版本查詢等領域提供了一種有效的技術。

區間持久性top-k查詢技術是針對文檔的不同版本，查詢關鍵字與文檔內容的相關性得分隨時間不同而不同的一種新型的查詢技術。返回處于top-k結果列表中時間長度最長的k個記錄。定義：假如一個文檔集D由n個文檔{d₁，...，d_n}組成，每個文檔d_i∈D存在多個不同的版本，每個版本v_d∈d有一個有效的時間間隔[v_d.t_b，v_d.t_e]，假如同一文檔的不同版本的時間間隔不重疊。設q為一查詢(關鍵字集qW和時間間隔[q.t_b，q.t_e])。給定一個整數k(0＜k＜n)和一個實數r(0＜r≤1，r表示松弛因子，是一個可調整大小的變量)，區間持久性top-k問題是為了找到所有的d∈D使得每一個文檔d出現在top-k結果集中的時間總長度不于r×[q.t_e-q.t_b]。

目前，國內基本還沒有相關的研究，國外對區間持久性top-k查詢技術研究尚處于初級階段。相關的研究有一致top-k查詢技術，但這種技術需要預先定義對象的排名，解決不了非預先定義(ad-hoc)的、查詢關鍵字與文檔內容匹配權重不同的查詢問題。區間持久性top-k查詢是關于文檔版本的查詢問題。算法包括：窮舉法、貪婪法、動態自適應算法DDA(Dynamic?Adaptive?Algorithm)、BBA(Band?based?Algorithm)算法以及物化思想等。

窮舉法和貪婪法需要將所有記錄從頭到尾檢索一遍，時間效率極低。DDA是對究舉法和貪婪法的改進，設置閥值以盡快結果查詢，但是需要為每個元組記錄上邊界和下邊界，將占據大量的存儲空間，BBA算法是前幾種算法的優化，同樣需要大量的存儲空間來保存候選帶以及top-k帶的記錄段。這些算法能夠實現區間持久性top-k查詢，但存在某些方面的缺陷。

發明內容

針對現有技術中存在的上述問題，本發明提供了一種區間持久性top-k查詢的雙哈希表關聯方法。

本發明提供了一種區間持久性top-k查詢的雙哈希表關聯方法，包括：

步驟10，輸入關鍵詞和查詢時間范圍；