[發明專利]一種基于文本-域倒排的空間文本查詢方法及裝置

有效

• 申請號: 201810292840.8
• 申請日: 2018-04-04
• 公開（公告）號: CN108628950B
• 公開（公告）日: 2022-07-19
• 發明（設計）人: 沈兵林;賈連印;丁家滿;游進國;李曉武;左喻灝;胡俊濤;雷妍
• 申請（專利權）人: 昆明理工大學
• 主分類號: G06F16/9537
• 分類號: G06F16/9537;G06F16/31
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明涉及一種基于文本?域倒排的空間文本查詢方法及裝置，本發明方法包括：數據預處理步驟，將數據集D中所有位置點編碼成長度為n的字符串，以該字符串為排序對象按字典序對數據集中的記錄排序并生成編號id，每一行數據稱為一條記錄r，則由一至多行記錄r組成的數據集稱為記錄集R；空間文本索引建立步驟，對記錄集R中的文本建立倒排索引，倒排索引的列表元素為與字符串相對應的id列表，得到文本?域倒排索引結構；布爾范圍查詢步驟，檢索文本?域倒排索引結構，獲取滿足查詢條件的id，經過濾得到id候選集，并對候選集驗證返回查詢范圍內的所有位置點。本發明采用文本?域倒排索引結構可高效支持任意空間范圍的文本查詢。

技術領域

本發明涉及一種基于文本-域倒排的空間文本查詢方法及裝置，屬于空間文本查詢(Spatial Keyword query)領域、基于位置的服務(Location-Based Service,LBS)等領域。

背景技術

隨著互聯網的發展、GPS移動設備的普及，導致產生了大量具有位置屬性的文本數據，且數據量急劇增長，例如：具有文本描述的興趣點（POIs）、具有位置標識的微博（Twitter）、具有位置與文本標識的圖片信息（Flickr）、基于FourSquare的簽到信息、含有位置屬性的網頁等。具有位置屬性的文本數據稱之為空間文本，空間數據與文本數據彼此賦予對方更詳細的表述。面對這樣的發展趨勢，高效支持空間文本查詢亟需高效的索引結構。空間文本查詢指以位置、查詢關鍵字為查詢條件，返回滿足查詢條件的相關內容。空間文本查詢分為：布爾kNN查詢、布爾范圍查詢、top-k kNN查詢與top-k 范圍查詢。

在空間文本查詢領域，已提出許多索引結構，這些索引結構通常組合了空間索引結構與文本索引結構。根據所采用的空間索引結構的不同，可將其分為：基于R-Tree、grid、space-filling curve的空間文本索引；根據所采用的文本索引結構，可將其分為：基于倒排列表與簽名文件的空間文本索引。空間索引與文本索引的組合方式為：獨立組合、松散組合、緊湊組合。目前，主流的空間文本索引結構是R樹家族與倒排列表組合的索引結構。R樹采用對象的最小外包矩形(Minimum Bounding Rectangle, MBR)近似表示空間實體。如圖8所示，從圖中可看出，有許多重疊區域，如R16既屬于R1又屬于R2，但如圖9所示，R6僅屬于R2的孩子結點，存在多條查詢路徑。數據量越大，重疊區域將越多，直接降低查詢效率。針對R樹的多路徑查詢問題，R樹變體對其進行了改進，檢索性能雖有一定的提升，但仍受到R樹多路徑查詢問題的限制。數據量較大時，尤其明顯。

發明內容

為了解決現有技術中存在的問題，本發明提供了一種基于文本-域倒排的空間文本查詢方法及裝置。

本發明的技術方案是：一種基于文本-域倒排的空間文本查詢方法，包括：

數據預處理步驟，將數據集D中所有位置點編碼成長度為n的字符串，以該字符串為排序對象按字典序對數據集中的記錄排序并生成編號id，每一行數據稱為一條記錄r，則由一至多行記錄r組成的數據集稱為記錄集R；

空間文本索引建立步驟，對記錄集R中的文本建立倒排索引，倒排索引的列表元素為與字符串相對應的id列表，得到文本-域倒排索引結構；

布爾范圍查詢步驟，檢索文本-域倒排索引結構，獲取滿足查詢條件的id，經過濾得到id候選集，并對候選集驗證返回查詢范圍內的所有位置點。

所述數據預處理步驟，具體包括如下步驟：

步驟110：給定一個由一系列位置點、關鍵詞集構成的數據集D，通過geohash空間編碼方法將D中的位置點編碼成長度為n的字符串geoStr；其中，位置點由緯度、經度數據構成；geoStr即geohash編碼，表示geohash精度表中n對應的范圍區域；