[發明專利]一種面向Top-k查詢的查詢結果即時多樣化的方法

有效

• 申請號: 201710685831.0
• 申請日: 2017-08-11
• 公開（公告）號: CN107688620B
• 公開（公告）日: 2020-01-24
• 發明（設計）人: 鐘鳴;王贏
• 申請（專利權）人: 武漢大學
• 主分類號: G06F16/2455
• 分類號: G06F16/2455;G06F16/2458
• 代理公司: 42222 武漢科皓知識產權代理事務所(特殊普通合伙)
• 代理人: 魯力

本發明涉及一種面向Top?k查詢的查詢結果即時多樣化的方法，基于一種多樣化算法框架TAD和基于此框架上的多樣化算法DivSA。多樣化算法框架TAD在查詢結果流式產生的過程中，將查詢結果分為兩部分：其一是超過當前相關度分數上界值的查詢結果；其二是低于當前相關度分數上界值的查詢結果和仍沒有生成的結果。在結果多樣化的過程中，僅考慮第一部分的查詢結果，減少了大量的計算開銷。本發明的多樣化算法DivSA首次使用了基于動態擴張相似圖上極大獨立集計算的多樣化方法，且提出了一種增量式算法計算動態擴張相似圖的極大獨立集，給出了一個結果多樣化過程完備而高效的解決方案。

技術領域

本發明涉及top-k查詢解釋及查詢結果多樣化技術領域，尤其涉及一種基于多樣化算法框架TAD的針對動態擴張相似圖上極大獨立集的多樣化算法。

背景技術

查詢結果多樣化是一項近年來非常熱門的信息處理技術。它旨在從龐大的查詢結果集中挑選出一個子集，使得該子集中的查詢結果不僅與查詢盡可能相關，而且互相之間信息冗余度盡可能低。

這些查詢結果多樣化方法都假定查詢結果集已經獲得，并從中搜索得到多樣化的top-k查詢結果。現有技術中，有將top-k查詢的結果構建成一個多樣性圖，圖中頂點代表搜索結果，邊代表鄰接的兩個頂點是相似的，它的目標是尋找k個互不鄰接的頂點并使得其相關性評分總和最大。現有技術中，還有構造了一個邊際增益的目標函數，每次選擇一個查詢結果作為多樣化結果時，考慮其對查詢的相關性和對已有多樣化結果的相似性，選擇增益最大的查詢結果成為新的多樣化結果。前兩者在考慮多樣性問題的時候，關注的是局部多樣性，即僅考慮了多樣化結果集中元素的互不相似性。現有技術中，還有加入了覆蓋度的概念來考慮結果集的全局多樣性。它使用歐式距離來衡量結果之間的相似程度，以一個結果為中心，其特定半徑范圍內的結果都與其相似，定義該結果覆蓋了其半徑范圍內的搜索結果。它的目標在于選取出能覆蓋所有搜索結果的代表結果集，這同時也保證了結果集一定的多樣化程度。

然而，隨著各種應用中數據量的急劇增長，生成所有查詢結果的時間和空間代價非常高昂，因而top-k查詢成為了普遍的選擇。Top-k查詢旨在找出與查詢相關度最高的k個結果，其特點是在滿足一定假設的前提下不必遍歷所有結果，能在top-k結果被發現后立即終止處理。但top-k查詢給多樣化技術帶來了新的挑戰，要求多樣化必須嵌入到查詢處理過程中，而不是在查詢處理完成之后再進行。

發明內容

針對以上技術問題，本發明提出了一種多樣化算法框架TAD(Top-And-Diversify)，和基于此框架上的一種針對動態擴張相似圖上極大獨立集的多樣化算法DivSA(diversified search algorithm)，是一種在top-k查詢處理的過程中，實時的生成多樣化結果集的解決方案。

多樣化算法框架TAD的提出是基于減少冗余計算的考慮，由于搜索的結果并不是按照其相對于查詢的相關度降序排列的，如果計算所有的生成結果之間的相似度，將是巨大的開銷，因此TAD將搜索結果分成兩部分，一部分是超過當前相關度分數上界值的搜索結果，設為集合T，另一部分是低于當前相關度分數上界值的搜索結果和仍沒有生成的結果。相關度分數上界值指的是目前可能生成的搜索結果相對于關鍵詞的相關度分數的最大值，將此值記為UpperBound，大部分經典的top-k查詢處理算法都提供了十分有效的相關度分數上界值。

一種面向Top-k查詢的查詢結果即時多樣化的方法，其特征在于，包括以下步驟：

步驟1：基于流式產生的查詢結果，使用nextTop模塊得到一個查詢結果，將該查詢結果加入到集合T中，nextTop模塊的具體執行步驟包括：

步驟1.1：基于流式產生的查詢結果，使用一個優先隊列Que存儲當前生成的查詢結果，按照其對于查詢的相關度從大到小在Que中依次排序；