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

有效

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

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

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

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

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

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

2.根據權利要求1所述的基于用戶日志分析的分布式倒排索引組織方法，其特征在于，所述步驟1）的詳細步驟為：

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

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

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

3.根據權利要求1所述的基于用戶日志分析的分布式倒排索引組織方法，其特征在于，所述步驟2）的詳細步驟包括：

2.1）計算每個高頻詞的負載，將節點按照負載降序排列得到節點集合，計算節點集合中任意兩個節點之間的節點距離；

2.2）定義每個聚類的負載上限、聚類個數以及聚類中心之間的最短距離和中心節點集合，從所述節點集合中取出一個節點作為當前節點，然后跳轉執行步驟2.3）；

2.3）將當前節點與中心節點集合中的中心節點進行比較，如果中心節點集合中找到某個節點與當前節點之間的節點距離小于所述聚類中心之間的最短距離，則將所述中心節點集合中找到的節點和當前節點合并作為中心節點集合中的一個新的中心節點，否則將當前節點作為中心節點集合中的一個新的中心節點；最終執行下一步；

2.4）判斷中心節點集合的大小是否達到聚類個數，如果仍未達到聚類個數則從所述節點集合中取出下一個節點作為當前節點并返回繼續執行步驟2.3）；如果已經達到聚類個數則執行步驟2.5）；

2.5）根據中心節點集合中的中心節點生成聚類得到聚類集合，計算中心節點集合中每一個中心節點到其他非中心節點的最短距離，并降序排列得到最短距離集合；

2.6）針對聚類集合的每一個聚類，查找所述聚類對應最短距離集合中的下一個節點作為目標節點；計算所述目標節點的負載并判斷負載是否超過所述負載上限，如果超過負載上限則忽略該目標節點；判斷包含所述目標節點的聚類數是否超過聚類個數，如果超過就忽略所述目標節點；判斷所述目標節點是否已經加入其他聚類且所述目標節點在最短距離集合中的上一個節點也屬于所述其他聚類中，如果符合條件則在所述目標節點和所述目標節點在最短距離集合中的上一個節點中選擇更接近當前聚類和其他聚類中點的節點作為邊境節點，所述邊境節點同時屬于當前聚類和其他聚類兩個聚類；如果不符合條件，則直接將目標節點直接加入當前聚類；最終將所有節點歸類后完成聚類并返回聚類結果。

4.根據權利要求1所述的基于用戶日志分析的分布式倒排索引組織方法，其特征在于，所述步驟3）的詳細步驟包括：

3.1）計算每個聚類的負載，將聚類按照負載降序排列得到聚類集合；

3.2）建立系統性能目標函數，從所述聚類集合中選擇一個聚類作為當前聚類；

3.3）往所述當前聚類中嘗試添加節點并計算所述目標函數值，然后將當前聚類加入目標函數值最小的節點上并建立索引，然后執行步驟3.4）；

3.4）判斷聚類集合中是否還有聚類未處理，如果仍有聚類未處理則取出下一個未處理的聚類作為當前聚類并返回執行步驟3.3）；如果所有聚類處理完成則高頻詞索引建立完畢；

3.5）將非高頻詞哈希到各個節點之上建立非高頻詞索引。