[發明專利]基于多關鍵字和用戶偏好的組合興趣點查詢方法

有效

• 申請號: 201910217464.0
• 申請日: 2019-03-21
• 公開（公告）號: CN109977309B
• 公開（公告）日: 2021-05-04
• 發明（設計）人: 俞東進;吳義宇;孫笑笑
• 申請（專利權）人: 杭州電子科技大學
• 主分類號: G06F16/9535
• 分類號: G06F16/9535;G06F16/9537
• 代理公司: 浙江千克知識產權代理有限公司 33246
• 代理人: 周希良

本發明公開了一種基于多關鍵字和用戶偏好的組合興趣點查詢方法。本發明提出的方法在查詢時綜合考慮了用戶偏好、興趣點之間的距離、興趣點到查詢位置的距離、興趣點的流行度和擁擠度等重要因素。針對時間約束下訪問成本最小化的興趣點查詢問題，提出了多關鍵字和用戶偏好的組合興趣點查詢方法。特別地，本發明設計了一個多目標的成本函數來計算候選集體興趣點的訪問成本，用于評價一組查詢結果的可行性。然后，基于目標函數，提出了一種基于IR樹的高效剪枝算法，有效的降低了查詢處理時間。通過在來自多倫多的真實數據下進行的廣泛實驗，證明了基于多關鍵字和用戶偏好的組合興趣點查詢方法的效率和準確性。

技術領域

本發明屬于空間關鍵字查詢技術領域，在查詢時綜合考慮了用戶偏好、興趣點之間的距離、興趣點到查詢位置的距離、興趣點的流行度和擁擠度等重要因素。針對時間約束下訪問成本最小化的興趣點查詢問題，提出了基于多關鍵字和用戶偏好的組合興趣點查詢方法。

背景技術

隨著定位技術的不斷發展以及智能手機的普及，Yelp和Foursquare等基于位置的服務(Located-based Service，LBS)取得了前所未有的發展。以國外著名的LBS提供商Foursquare為例，它鼓勵用戶在任意時間任意興趣點進行簽到，分享自己所在的興趣點到社交網絡中，因此Foursquare在成立后的兩年內迅速擁有了2000萬的活躍用戶。近年來，涉及位置信息和一組文本描述關鍵字的空間關鍵詞查詢問題在學術界和工業界引起了廣泛的關注。空間關鍵字查詢通常需要檢索一組滿足特定位置和關鍵字約束的空間興趣點，這些興趣點要滿足用戶給定的關鍵字，而且與用戶當前所在位置之間的距離要盡可能的近。

目前國內外學者在空間興趣點查詢方面做了許多有價值的研究工作。一是基于一個考慮空間位置和文本相關性的排名函數在空間中尋找Top-k個對象，稱為top-k kNN查詢。例如，Qiao M等人研究了在圖結構上的top-k kNN查詢，提出了兩個精確算法來分別處理有查詢邊界和任意邊界情況，并提出了一種全局存儲技術來進一步減小索引大小和查詢時間。二是尋找一組興趣點作為滿足用戶需求的解決方案，因為有時很難找到匹配所有查詢關鍵字并且距離用戶較近的單個興趣點。例如，Zhang D等人提出了一種新穎的空間關鍵詞查詢問題，稱為m-closet關鍵詞查詢(mCK)，旨在尋找m個與用戶指定關鍵字相匹配并且距離用戶最近的興趣點組合。在查詢階段，Zhang D等人提出了一個名為bR*-tree的空間索引，并利用基于先驗的搜索策略來有效地減少搜索空間。

現有的興趣點查詢問題大多僅考慮空間位置和查詢關鍵字兩個約束條件，而沒有考慮用戶對這些興趣點的偏好和用戶訪問這些興趣點的最佳時間。事實上，受歡迎的興趣點在繁忙時間會過于擁擠，導致用戶需要長時間的排隊并且感受到較差的服務質量，從而降低了用戶對這些興趣點的訪問興趣。

發明內容

本發明針對現有技術的不足，提出了一種基于多關鍵字和用戶偏好的組合興趣點查詢方法。該方法旨在基于用戶給出的多個關鍵字，結合用戶潛在興趣偏好、興趣點的流行度和擁擠度來檢索空間內的興趣點。本發明首先，設計了一個多目標的成本函數來計算候選興趣點的訪問成本。然后，基于目標函數，提出了一種基于IR樹的高效剪枝算法，可以有效地獲得符合查詢要求的興趣點。

本發明方法的具體步驟是：

步驟(1).輸入查詢問題q，其中查詢問題q包含用戶q.u、查詢位置q.λ、查詢時間q.τ和一組查詢關鍵字q.ψ。

步驟(2).初始化查詢方法的基本參數，包括查詢范圍r(公里)、平衡參數γ、平衡參數β、平衡參數α；初始化一個IR樹作為查詢索引，IR樹本質上是在R樹的基礎上，為其每個節點都附加了一個相應的倒排文件用于存儲節點中興趣點的關鍵字信息；初始化一個最小優先級隊列U用來維護中間查詢結果，并將IR樹的根節點插入最小優先級隊列U；初始化最小訪問成本curCost(初始值設置為無窮大)和最優訪問方案curGroup。