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

有效

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

1.一種區間持久性top-k查詢的雙哈希表關聯方法，其特征在于，包括：

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

步驟11，創建倒排表，將查詢時間分拆為多個間隔時間，并根據倒排表和間隔時間建立第一哈希表和第二哈希表；倒排表中記錄文檔ID、該文檔ID的得分以及屬于該文檔ID的文檔版本的有效間隔時間；第一哈希表記錄具有有效時間間隔的文檔版本對應的文檔ID、各倒排表中最后被查詢的記錄的得分以及具有有效時間間隔的文檔版本對應的被查詢的相同文檔ID在不同倒排表中的總得分，第二哈希表記錄具有有效時間間隔的文檔版本對應的文檔ID、文檔ID對應的倒排表ID和各倒排表中最后被查詢記錄的總得分；各倒排表中最后被查詢記錄的總得分為當前被查詢記錄的得分與其余倒排表中最后被查詢記錄得分之和，各倒排表中最后被查詢的記錄的得分對應于當前被查詢的記錄對應的文檔ID；

步驟12，如果第二哈希表中各倒排表中最后被查詢記錄的總得分小于當前被查詢記錄對應ID在第一倒排表中具有有效時間間隔的文檔版本對應的被查詢的相同文檔ID在不同倒排表中的總得分，則按降序排列第二哈希表中各倒排表中最后被查詢記錄的總得分并輸出前k個總得分對應的文檔ID及其間隔時間；

步驟13，將具有相同文檔ID對應的時間間隔相加，將相加的結果降序排列并輸出前k個結果對應的文檔ID。

2.如權利要求1所述的雙哈希表關聯方法，其特征在于，文檔的分值根據下述公式計算：其中w_ik為具有該文檔ID的文檔的分值，w1ik=0,freqik=01,freqik≥0,]]>freq_ik為關鍵字在文檔中出現的頻率，n為文檔的總數，面doctotal_k為出現關鍵字的文檔數量，p為關鍵字的權重。

3.如權利要求1所述的雙哈希表關聯方法，其特征在于，步驟11中，如果文檔版本的有效時間未完全落入查詢時間范圍內，則對該文檔進行時間裁剪。

4.如權利要求1所述的雙哈希表關聯方法，其特征在于，步驟11中，利用拉鏈法、多哈希法或開放地址法解決建立第一哈希表或第二哈希表的沖突。

5.如權利要求1所述的雙哈希表關聯方法，其特征在于，步驟11中，根據直接定址法、平方取中法、折疊法或除留余數法建立第一哈希表或第二哈希表。

6.如權利要求1所述的雙哈希表關聯方法，其特征在于，文檔ID對應的最大得分為文檔在倒排表中的原始得分與該文檔在其它倒排表中最后讀取記錄的得分之和。