[發明專利]一種無線數據廣播環境下的空間關鍵字檢索方法

有效

• 申請號: 201210346215.X
• 申請日: 2012-09-18
• 公開（公告）號: CN102867058A
• 公開（公告）日: 2013-01-09
• 發明（設計）人: 孫未未;陳楚南;陳翀
• 申請（專利權）人: 復旦大學
• 主分類號: G06F17/30
• 分類號: G06F17/30;H04L12/18;H04H20/38
• 代理公司: 上海正旦專利代理有限公司 31200
• 代理人: 陸飛;盛志范

技術領域

本發明屬于無線數據廣播技術領域，具體涉及一種在無線數據廣播環境下的空間關鍵字檢索的方法。

背景技術

隨著信息系統中，特別是互聯網上的文本文獻數量的急劇增長，關鍵字查詢技術已經成為了當今計算機研究的熱點之一，并在各個領域得到廣泛應用。另一方面，隨著無線通訊技術的發展以及移動設備的大規模應用，空間數據庫在現實中得到了很好的應用，成為了當今的研究熱點之一，其發展前景被廣泛看好。這兩者的結合，使互聯網上文本信息和位置信息結合的文檔（如企業黃頁）越來越普遍，從而使空間關鍵字檢索技術成為新的研究熱點。

在空間關鍵字檢索領域，區域限制的關鍵字查詢是一種很常見的查詢。其定義為：給定N個文檔D={d₁,?d₂,?…,?d_N}，每個文檔都包含位置信息loc_i以及文本信息text_i，對于用戶提交的查詢RCKQ?(loc_q,?text_q,?radius)，其中，loc_q表示查詢點的位置，text_q表示用戶提交的關鍵字集合，返回距離查詢點不超過radius，且包含的所有關鍵字text_q文檔集合。

無線數據廣播是移動數據管理的一個重要研究分支，通過向空中廣播數據，可以支持大量移動計算設備并發訪問服務器上的數據，發送代價與接收者個數基本無關；利用無線信道的天然廣播特性，提高了系統的可伸縮性。數據庫和移動計算這兩個領域最重要的會議和期刊均發表了多篇研究無線數據廣播的論文。同時，無線數據廣播技術有著很好的應用前景，在消費電子、公共信息的發布、軍事等很多領域已有實際的應用。而無線局域網的高速推廣和3G網絡的部署，將為無線數據應用提供更好的基礎網絡平臺。

無線數據廣播是目前無線移動網絡中廣泛采用的數據傳遞方法，廣播服務器通過公共的信道發送信息，用戶在廣播信道上偵聽并及時將自己感興趣的數據下載到本地。從用戶角度，無線信道可看成是存儲數據的載體，和可隨機訪問的內存和硬盤不同，無線信道中的數據只能順序訪問。

如何快速訪問和節省能源是無線數據廣播中研究的兩個主要問題，相應的，有兩個評價廣播性能的主要參數：訪問時間（Access?Time）和調諧時間（Tuning?Time）：

（1）訪問時間(AT)：從用戶提出請求到請求得到滿足之間經過的時間；?

（2）調諧時間(TT)?：用戶在提出請求到請求得到滿足之間需要保持偵聽狀態的時間。在廣播信道中插入索引時減少調諧時間的主要方法，如何設計高效率的索引也得到了很多研究者的關注。

將關鍵字檢索技術與無線數據廣播結合是近年來比較熱門的研究領域。已出現的技術有基于倒排表索引和哈希索引的無線數據廣播環境下的全文檢索技術。已有的技術只考慮了文本信息，而沒有考慮位置信息，因此已有的技術并不能有效支持空間關鍵字檢索，存在一定的局限。

發明內容

本發明針對背景技術中所述的現有方法僅考慮文檔的文本信息，而沒有考慮位置信息的缺陷，提出了一種無線數據廣播環境下有效支持空間關鍵字檢索的方法，該方法結合網格索引和倒排表索引，進一步提高了無線數據廣播系統的性能。

本發明提出的無線數據廣播下的空間關鍵字檢索的方法，其總體思路是：首先對服務器端的文檔進行預處理，生成網格索引以及每個網格的倒排表索引。然后將索引和文檔集合周期性地廣播。移動終端提出空間關鍵字查詢請求，并進入廣播信道，下載索引，通過索引得到落在感興趣區域并包含感興趣關鍵字的文檔的到達時間。接著用戶根據文檔的到達時間，進入信道下載文檔。最后，用戶在本地端進行計算確認最終結果。

本發明具體步驟如下：

（1）對服務器端的文檔進行預處理：