[發(fā)明專利]滑動窗口下基于位置top-k關(guān)鍵詞查詢的優(yōu)先查詢算法及系統(tǒng)

有效

• 申請?zhí)枺?/td>: 201710864389.8
• 申請日: 2017-09-22
• 公開（公告）號: CN107506490B
• 公開（公告）日: 2020-08-11
• 發(fā)明（設(shè)計）人: 毛睿;李榮華;陸敏華;王毅;羅秋明;商爍;劉剛
• 申請（專利權(quán)）人: 深圳大學(xué)
• 主分類號: G06F16/31
• 分類號: G06F16/31;G06F16/332
• 代理公司: 上海宏京知識產(chǎn)權(quán)代理事務(wù)所(普通合伙) 31297
• 代理人: 王函

1.一種滑動窗口下基于位置top-k關(guān)鍵詞查詢的優(yōu)先查詢算法，其特征在于，包括如下步驟：

第一步，輸入構(gòu)建好的四叉樹索引模型和查詢節(jié)點以及k，建立一個列表作為結(jié)果集，初始化為空；k表示用戶可指定的結(jié)果關(guān)鍵詞的個數(shù)；

第二步，根據(jù)構(gòu)建好的四叉樹的根節(jié)點的MG摘要以及k進行剪枝操作，得到候選結(jié)果集；第二步中，所述剪枝操作過程如下：從用戶輸入得到確切的k值之后，重新計算第k個詞的分值，將該分值中的“距離部分”設(shè)置為0算出的分值作為一個下界；接著，從根節(jié)點摘要中的第(k+1)個詞開始，重新計算這些詞的“距離部分”，使用最大的距離進行計算作為上界；當?shù)趇(ik)個詞的上界分值仍然小于第k個詞的下界分值，那么認定第i個之后的詞在不久的未來k次操作也不能到達優(yōu)先隊列的頂部；

第三步，使用一個最大堆C存儲候選結(jié)果集中的每個詞語以及其分值；C是存儲所有候選詞的一個優(yōu)先隊列；第三步中，所述分值按以下步驟計算：

(1)利用每一個節(jié)點中存儲的摘要來計算分值：等式(1)定義了計算分值的公式，

令D為一個二維的歐式空間，W為滑動窗口，S是在D和W內(nèi)的一系列地理文本信息的集合；每一個地理文本信息表示為o＝(pos,text)，其中pos是D中的一個位置點，text是文本信息；定義滑動窗口W中一個詞t的位置感知詞頻分值：

其中，freq(t)是包含詞t的信息的數(shù)目，|W|是在滑動窗口中的信息的總數(shù)目，d(q,W_t)是查詢點q與窗口W中包含t的信息的距離之和，d_diag是矩形區(qū)域R的對角線長度，|W_t|表示的是W中包含詞t的信息的數(shù)目，α是平衡在詞頻與位置鄰近度之間的權(quán)重的參數(shù)，該分值實質(zhì)是W中的詞的詞頻和該詞與查詢點q之間的距離的線性組合；將分數(shù)的計算公式分為“頻率部分”和“距離部分”由于MG摘要在最多誤差為n/(k+1)的情況下估算任意項的頻率，n是所有訊息的數(shù)目，將這個最大的誤差加到freq來計算“頻率部分”；d(q，W_t)是包含詞t的信息與查詢點之間的距離之和，使用查詢點到包含這個詞的節(jié)點的四條邊的最小距離來作為一個上界；“距離部分”計算要考慮對于同一個詞的冗余計算，包含了對一個節(jié)點中同一個詞出現(xiàn)的信息數(shù)目的一個除法操作，以及通過一個線性權(quán)重參數(shù)α計算兩部分的和，將其歸一化到[0,1]的區(qū)間；

(2)在得到每一個節(jié)點內(nèi)每一個詞的分值后，詞的分值需要被整合來計算該詞在整棵樹中的分值；該步通過將某些節(jié)點中該詞的分值相加，使得該分值盡可能地大，在這個過程中，必須遵守一個規(guī)則是這些節(jié)點必須要覆蓋整棵四叉樹；

第四步，當結(jié)果集的大小小于k時，依次取出C中的隊列頭的詞語，從根節(jié)點遍歷到葉節(jié)點，每遍歷一層得到比原來的分值小的值就替換原始值，直到遍歷到葉節(jié)點找到該詞語的精確分值，放入隊列；

第五步，循環(huán)第四步，當隊列頭的詞語的分值等于該詞在葉節(jié)點的精確分值，放入結(jié)果集中；

第六步，當結(jié)果集的大小等于k時，返回結(jié)果集。

2.如權(quán)利要求1所述的算法，其特征在于，第一步中，所述四叉樹索引模型的構(gòu)建方法包括如下步驟：

步驟一，確定四叉樹覆蓋的地理范圍以及節(jié)點分裂規(guī)則；

步驟二，接受數(shù)據(jù)流，向節(jié)點中插入數(shù)據(jù)；

步驟三，符合步驟一節(jié)點分裂規(guī)則的節(jié)點分裂，數(shù)據(jù)插入不斷生成完整的四叉樹；

步驟四，對每一個葉節(jié)點，統(tǒng)計其詞頻，存儲倒排索引；

步驟五，對每一個非葉節(jié)點，存儲其所有子節(jié)點的MG聚合摘要信息；

步驟六，針對步驟四和步驟五兩步的數(shù)據(jù)插入過程中，在這個過程中需要維護滑動窗口的大小，刪掉具有最舊時間戳的數(shù)據(jù)項，添加最新的數(shù)據(jù)，調(diào)整四叉樹的索引結(jié)構(gòu)。

3.如權(quán)利要求2所述的算法，其特征在于，步驟一中，所述確定四叉樹覆蓋的地理范圍是給定左上角和右上角的緯度坐標經(jīng)；所述確定節(jié)點分裂規(guī)則為：設(shè)置每一個葉節(jié)點中的數(shù)據(jù)項不超過某個設(shè)定的閾值M，如果超過了則進行分裂為四個葉子節(jié)點；或者直接限定樹的深度。