[發明專利]基于安全區域的關鍵字連續查詢方法

在審

• 申請號: 201310233833.8
• 申請日: 2013-06-13
• 公開（公告）號: CN103279560A
• 公開（公告）日: 2013-09-04
• 發明（設計）人: 李國良;馮建華;黃維篁
• 申請（專利權）人: 清華大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京清亦華知識產權代理事務所(普通合伙) 11201
• 代理人: 張大威

技術領域

本發明涉及網絡技術領域，特別涉及一種基于安全區域的關鍵字連續查詢方法。

背景技術

移動設備與互聯網技術的發展，使得基于位置的服務（Location?Based?Service，簡稱LBS）成為人們日常生活中必不可少的一部分。咖啡廳，地鐵，銀行，超市等使用移動設備的用戶無處不在。以智能手機為例，人們利用它在任何方便的場合查找資料、玩游戲、與朋友溝通交流，以消磨冗長乏味的時間。也正是這個過程中潛藏的巨大商機，讓各大互聯網公司、研究機構紛紛投入巨大的時間與精力來從事移動互聯網相關的開發研究工作。在這些研究內容中，空間數據庫占據了重要地位。

空間數據庫的研究開始于上個世紀七十年代，隨著移動互聯網的興起，它煥發出了新的生機，研究目的也從如何有效利用衛星遙感資源進行研究工作轉變為如何為人們日常生活提供更好的服務。空間數據庫的特點包括：（1）數據量大，粗略估計，百度地圖的包含至少兩千萬條記錄，每條記錄對應于一個興趣點（Point?of?Interest，簡稱POI）。（2）模型復雜，空間數據庫的基本單元是POI，每一個POI至少要包含位置和文本兩部分信息，位置信息一般通過經緯度表示，文本信息用來存儲POI對應的名稱、描述等。并且在很多情況下，空間數據庫還要借助圖形圖像來展現，例如地圖。空間數據庫的這些特征決定了在表征與處理方面，它們需要更加復雜的索引結構以及對應的檢索、分析算法。R-tree是一種經典的用來表示、處理空間數據的結構。它具有高度的平衡性，滿足一定的建樹規則。在R-tree中，空間中的物體和區域都被作為MBR（Minimum?Bounding?Rectangle）來處理，每個MBR對應于R-tree中的一個節點，節點之間的父子關系反映了MBR之間的包含關系，通過這樣的方式，為空間數據庫上的檢索提供了便利。R-tree支持的查詢包括k近鄰搜索（查找距離指定位置的k個點），范圍查詢（查找給定區域內的點）等。

地圖搜索是空間數據庫上一個十分基礎的應用，現在國內外很多大型網絡公司都提供了地圖搜索服務，例如：百度地圖，搜搜地圖，谷歌地圖，必應地圖等。通過訪問相應的網站，即可獲得對應的搜索服務。一般的地圖服務包括兩大類型：點查詢與線路查詢，點查詢的重點在于獲取用戶感興趣的點，而線路查詢則是為用戶提供兩個或更多點之間的合理規劃后的線路，例如，公交、駕車等。點查詢的方式很多，例如百度地圖就提供了分類搜索，用戶通過指定需要查找的地點類型來獲取滿足這個約束條件的點。更加常見的則是關鍵詞搜索，即通過輸入關鍵詞來查找興趣點。移動設備的發展使得更多用戶個性化信息的獲得變得快捷便利，人們可以方便地通過GPS或Wi-Fi信號定位，因而，地圖上的關鍵詞查詢也變得更加個性化、人性化，例如：一個行駛在高速公路上的用戶可以查找距離他最近的加油站等。在這個過程中，移動設備作為客戶端，與提供地圖服務的服務器端構成了一個客戶端-服務器模型（Client-Server?Model）。這樣就要求查詢結果滿足兩方面的約束：（1）位置約束，查找的點距離當前位置不遠；（2）關鍵詞約束，查找的點滿足關鍵詞提供的描述信息。需求的更新推動了技術的進步，一種新的索引結構被提出——IR-tree。IR-tree是一種基于R-tree的樹形結構。它的底層仍然是由MBR以及相互之間的包含關系組成的R-tree。與之不同的是，IR-tree在每一個節點上附加了一個倒排索引（Inverted?List）。倒排索引是信息檢索領域中最常使用的結構，每個關鍵詞對應了一個由包含它的所有文檔組成的列表。在IR-tree中，每個節點的倒排索引也包含了一些關鍵詞，這些關鍵詞必須在這個MBR中出現，每個關鍵詞對應于一個列表，列表中的元素為包含這個關鍵詞的子節點。R-tree與倒排索引的結合使得查詢時可以快速獲得滿足空間限制和關鍵詞約束的點。