[發明專利]top-m反近鄰空間關鍵字查詢方法

有效

• 申請號: 201710556389.1
• 申請日: 2017-07-10
• 公開（公告）號: CN107391636B
• 公開（公告）日: 2020-06-09
• 發明（設計）人: 鮮學豐;趙朋朋;曠曉鵬;崔志明
• 申請（專利權）人: 江蘇省現代企業信息化應用支撐軟件工程技術研發中心
• 主分類號: G06F16/29
• 分類號: G06F16/29;G06F16/901;G06F16/9537;G06Q30/02
• 代理公司: 北京遠大卓悅知識產權代理事務所(普通合伙) 11369
• 代理人: 史霞

1.一種top-m反近鄰空間關鍵字查詢方法，其特征在于，包括以下步驟：

步驟一、給定一個包含用戶U和空間文本對象P的數據集D，對于候選地點集合L和關鍵字組集合W，從L中選擇一個候選地點l以及W中選擇一個關鍵字組w，組成第i個新的查詢對象q＝l，w作為一個候選組合對象，將L中每個候選地點和W中每個候選關鍵字組兩兩組成新的候選組合對象，從而組合出M個候選組合對象；

步驟二、為每一個候選組合對象進行一次RSTkNN查詢，從而得到一個RSTkNN查詢結果集合；根據每一個候選組合對象的RSTkNN查詢結果集合，從M個候選組合對象中選擇出基數最大的候選組合對象；

所述步驟二中，其具體過程包括：

步驟(1)構建MIR-tree索引：根據空間文本對象數據集P建立R-tree，保存數據的地理位置信息；每個數據對象p以從下往上的方式將文本信息更新到R-tree中，保存到各樹節點的倒排列表中，從而構建MIR-tree；其中，在MIR-tree中，每個關鍵字r所對應的倒排列表為一個三元組序列p，Maxw_p，r，Minw_p，r，Maxw_p，r為最大權重而Minw_p，r為最小權重；

步驟(2)利用MIR-tree索引為U中的每個用戶u進行單獨的top-k查詢，返回top-k查詢結果；

步驟(3)計算候選組合對象的RSTkNN查詢結果，選出基數最大的m個候選組合對象。

2.如權利要求1所述的top-m反近鄰空間關鍵字查詢方法，其特征在于，所述步驟二的步驟(2)中，利用MIR-tree索引為U中的每個用戶u進行單獨的top-k查詢，返回top-k查詢結果，其具體過程包括：

步驟a)給出聚合用戶、上界相關性得分以及下界相關性得分的定義：

聚合用戶是將所有用戶U聚合形成的一個超級抽象用戶，表示為U_s，U_s的地理位置信息U_s.l為將所有用戶包含的最小邊界矩陣，而U_s的文本信息用兩個關鍵字詞向量表示，分別為聚合用戶-并向量U_s.uniT和聚合用戶-交向量U_s.intT；

U_s和MIR-tree中樹結點n之間的上界相關性得分為U_s和結點n最短距離得分和最大文本相似得分的綜合聚合得分，公式表示如下：

UB(n，U_s)＝α·MinDistS(n.l，U_s.l)+(1-α)·MaxTextS(n.T，U_s.uniT)，

其中，MinDistS(n.l，U_s.l)表示在空間維度上，結點n和聚合用戶U_s之間最短距離得分，而MaxTextS(n.T，U_s.uniT)則表示在文本維度上，n和U_s的最大可能文本相似度得分，兩個得分通過平滑因子α來表示用戶對空間維度的偏好；

U_s和MIR-tree中樹結點n之間的上界相關性得分，其公式表示如下：

LB(n，U_s)＝α·MaxDistS(n.l，U_s.l)+(1-α)·MinTextS(n.T，U_s.intT)，

其中，MaxDistS(n.l，U_s.l)表示在空間維度上，n和U_s之間最長距離得分，而n和U_s的最小文本相似度得分則用MinTextS(n.T，U_s.intT)表示；

步驟b)利用MIR-tree索引對聚合用戶U_s進行聚合top-k查詢，其具體過程包括：將所有用戶U聚合形成的一個超級抽象用戶，表示為U_s；然后，用U_s去遍歷MIR-tree檢索所有可能成為U中任一個用戶u的top-k結果之一的對象p，記為P′，同時還記錄U_s的第k個下界相關性得分；最后，基于P′為U中的每個用戶u進行單獨的top-k查詢，返回top-k查詢結果。