[發明專利]基于用戶日志分析的分布式倒排索引組織方法

有效

• 申請號: 201210169721.6
• 申請日: 2012-05-24
• 公開（公告）號: CN102722553A
• 公開（公告）日: 2012-10-10
• 發明（設計）人: 陳嶺;李卓豪
• 申請（專利權）人: 浙江大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 杭州天勤知識產權代理有限公司 33224
• 代理人: 胡紅娟

技術領域

本發明涉及計算機信息檢索技術領域,具體涉及一種基于用戶日志分析的分布式倒排索引組織方法。

背景技術

隨著互聯網技術的不斷發展，當今社會每天都會產生大量的信息，這些信息往往會以網頁、圖片、視頻、音頻等非結構化數據的形式展現。面對如此浩如煙海的數據量，人們要想從中獲得符合自己需求的信息，如大海撈針般困難。因此，在這個海量信息的時代，要想快速、效地獲得有用信息，必須借助各式各樣的信息檢索系統（Information?Retrieval?System，IRS）。IRS的主要目的是為人們提供有效的信息服務，是根據特定信息需求建立起來的，實現了信息搜索、加工、存儲和檢索等功能的程序化系統。從廣義上來講，任何具有了信息存儲和檢索功能的系統，都可以稱之為IRS系統。

IRS系統的種類繁多，如數字圖書館、搜索引擎等，但此類系統都有針對信息數據的索引。隨著信息數據量的不斷增加，索引也必然會不斷膨脹，最終導致存儲和檢索效率變得十分低下。為了解決這個問題，一般采用分布式索引，將原來存儲在單臺機器上的龐大的索引切割成大小合適的索引碎片，并將這些索引碎片分布到不同的機器上，形成索引集群，從而把原先對巨大單一索引的訪問轉換為對索引集群的查詢，索引集群則通過合適的索引分割方式、查詢路由策略以及最終的結果合并實現快速而有效的查詢。由此可以看出，分布式索引系統已經成為IRS系統乃至信息領域里一個至關重要的組成部分，要實現海量數據的有效管理，就必須先實現高性能的分布式索引系統。

在倒排索引的分布式處理過程中，最重要的問題之一就是索引的分割切片。目前最主要有三種方式：“全局分割”、“局部分割”和“混合分割”。

“全局分割”也叫基于“文檔”的分割，每塊索引碎片所包含的信息都具有全局意義。基于“文檔”的劃分策略雖然使整個索引結構易于維護，節點之間的負載更加均衡、但是每次查詢所有節點都要參與，系統資源浪費嚴重。

而在“局部分割”中，又叫基于“詞”的分割，每塊索引碎片所包含信息只具有局部的意義，即只針對某個子數據集的索引。基于“詞”的劃分策略能有效減少每次參與查詢的節點數，增大整個系統的吞吐，但由于“詞”之間被查詢頻率存在很大差別，容易造成節點間的負載不均。

這兩種分割方式在不同的應用壞境和查詢條件下各有優劣，出于各取其優的考慮，出現了“混合分割”的分片組織方式，“混合分割”的基本思想是部分“全局”部分“局部”，而不同方法的區別在于如何劃分“全局”與“局部”，以及這兩部分如何交互。現有“混合分割”方法一般設計簡單，沒有考慮“詞”之間被查詢頻率的差別，總體效果并不理想。

在實現分布式索引系統的基礎上，需要利用查詢路由來從分布式索引系統中獲取查詢結果。的查詢路由是建立在“索引分割”基礎之上的查詢節點選擇，其一方面利用索引分片信息選擇合適的索引集群節點進行查詢，另一方面在保證結果集準確率的前提下，盡可能減少參與查詢的節點，同時為集群的負載均衡、索引分片副本調整等方法提供依據。

發明內容

本發明要解決的技術問題是提供一種查詢開銷小、查詢效率高、查詢性能好、能實現整個系統吞吐量和每次查詢響應速度間的平衡、多詞查詢涉及的節點數少的基于用戶日志分析的分布式倒排索引組織方法。

為解決上述技術問題，本發明采用的技術方案為：

一種基于用戶日志分析的分布式倒排索引組織方法，其實施步驟如下：

1）分析用戶查詢日志并提取出高頻詞和非高頻詞，建立高頻詞的相關性矩陣，并根據高頻詞之間的相關性建立高頻詞關系圖；

2）計算每個高頻詞的負載，根據高頻詞關系圖和高頻詞的負載對高頻詞進行聚類；

3）將各個聚類分配到節點之上并建立高頻詞索引，將非高頻詞哈希到各個節點之上，并建立非高頻詞索引；

4）根據所述高頻詞索引和非高頻詞索引建立全局的索引表，并根據該索引表進行查詢路由。

作為本發明上述技術方案的進一步改進：

所述步驟1）的詳細步驟為：

1.1）解析用戶查詢日志，將用戶查詢日志進行分詞得到查詢詞典，統計每個詞的出現頻率并將查詢詞典按照出現頻率降序或者升序排列，從查詢詞典的高出現頻率端截取指定數量的詞作為高頻詞，剩余的詞則為非高頻詞；

1.2）將截取的高頻詞建立高頻詞典，將高頻詞典中的高頻詞從1到N統一編號建立N×N的高頻詞的相關性矩陣；

1.3）將所述高頻詞的相關性矩陣轉換為無向圖得到高頻詞關系圖。

所述步驟2）的詳細步驟包括：