[發明專利]基于圖數據的集合關鍵字查詢方法

有效

• 申請號: 201410746565.4
• 申請日: 2014-12-08
• 公開（公告）號: CN105740246B
• 公開（公告）日: 2019-08-06
• 發明（設計）人: 程祥;蘇森;趙森;雙鍇;徐鵬;王玉龍;張忠寶;楊放春
• 申請（專利權）人: 北京郵電大學
• 主分類號: G06F16/29
• 分類號: G06F16/29
• 代理公司: 北京路浩知識產權代理有限公司 11002
• 代理人: 李相雨

本發明涉及一種基于圖數據的集合關鍵字查詢方法，包括：確定目標圖中的節點，節點所能提供的服務，提供服務的評分，節點之間的距離和相應開銷；解析查詢指令，確定起始節點、n個服務關鍵字、開銷約束和半徑約束，確定備選集合；對備選集合進行減少冗余計算；對減少冗余計算后的集合進行剪枝；標記查詢到的最優集合進行顯示。通過本發明的技術方案，能夠根據用戶提出的多個參數進行查詢，滿足用戶精準的需要，并且通過過濾處理和減冗余處理，可以極大地提高節點查詢的速度，從而更快地為用戶反饋結果，并且對于大規模的圖數據，可以進行分治處理技術，建立多級的索引結構，進而減小問題求解規模并降低算法求解的時間開銷。

技術領域

本發明涉及數據處理技術領域，具體而言，涉及一種基于圖數據的集合關鍵字查詢方法。

背景技術

地理定位技術的成熟使得對各種各樣的基于位置的服務的支持成為可能。興趣點的查詢在這些服務中起著重要的作用。例如，通過使用類似百度地圖和谷歌地圖等基于位置的服務，用戶可以找到附近的中餐館。然而，這些服務并不能夠滿足用戶更多的個性化需求。例如，一個用戶可能想在離家不遠的地方度過一個愉快的周末。為達到這個目的，他可能需要找到一個包含了游泳池、電影院、商店和餐館的最受歡迎的區域，區域的直徑不超過兩公里，并且這個區域在距離家的30公里以內。

這個查詢中包含了以下三個約束：(1)區域中包含帶“游泳池”，“電影院”，“商店”和“餐館”等關鍵字的興趣點；(2)區域中每對興趣點之間的距離不超過2公里；(3)區域到用戶位置的距離不超過30公里。該查詢的目標在于尋找滿足這三個約束條件的最受歡迎的區域。

在圖數據中的關鍵字查詢的相關研究已經引起了廣泛關注。雖然現有技術中存在基于分塊處理的多級索引結構和相應的查詢機制用來解決圖數據中的關鍵字查詢問題，或者基于最短路徑生成樹的結構，針對大規模圖數據提出了top-k最鄰近節點的查詢算法。然而，以上研究僅能夠解決了單個關鍵字的查詢問題。另外，現有技術中還存在一種分布式的處理方法解決基于圖的關鍵字查詢問題，以及一種基于關鍵字的路徑查詢問題，即為查詢一條有固定起點和終的并通過多個興趣點的最短路徑，并提出了貪心算法和得分預測等算法。但是，以上的研究都不能綜合以下四個參數進行查詢，即用戶的位置，查詢所需求的關鍵字，用戶位置到區域的距離約束以及區域中興趣點的半徑約束。最后，現有技術中還提出了一種在空間數據中集合關鍵字查詢問題，并提出了一系列的解決方案，但是該技術采用的歐幾里德距離常用于空間數據距離估算，其估算值與實際距離值往往差距很大。

發明內容

本發明所要解決的技術問題是，對于大規模的圖數據，如何建立高效的、層次化的、可擴展的索引結構，并在查詢過程中降低算法的求解時間開銷，保證其可應用于圖數據規模較大的查詢場景，滿足用戶實時高效的查詢需求。

為此目的，本發明提出了一種基于圖數據的集合關鍵字查詢方法，包括：S1，解析目標圖，確定目標圖中的節點，確定每個節點所能提供的服務，并查詢對每個節點提供服務的評分，計算每兩個節點之間的距離和相應開銷；S2，解析查詢指令，確定起始節點、n個服務關鍵字、開銷約束和半徑約束，查詢到起始節點的距離滿足開銷約束且分別具有每個服務關鍵字的節點集合，將節點集合中每個節點之間的距離滿足半徑約束的集合作為備選集合；S3，根據所述半徑約束對備選集合進行減少冗余計算，得到初步處理集合；S4，根據初步處理集合中每個節點提供服務的評分對初步處理集合進行剪枝計算，得到目標集合；S5，在目標圖中標記查詢到的目標集合進行顯示。