[發明專利]道路網絡中基于RRN-Tree的移動對象CKNN查詢方法

有效

• 申請號: 201310520592.5
• 申請日: 2013-10-29
• 公開（公告）號: CN103544291A
• 公開（公告）日: 2014-01-29
• 發明（設計）人: 孫海龍;王春艷;于鳴;劉丹
• 申請（專利權）人: 東北林業大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 哈爾濱市松花江專利商標事務所 23109
• 代理人: 岳泉清

技術領域

本發明涉及一種數據查詢方法。

背景技術

隨著無線通信技術的發展和具有GPS定位功能的移動電話、PDA等便攜設備的普及，基于位置服務（LBS，Location?Based?Service）得以快速發展，已廣泛應用于地理信息系統、應急服務、汽車導航和旅游路徑規劃等領域。空間查詢與基于位置服務密切相關，其中基于道路網絡的移動對象連續K最近鄰查詢（CKNN，Continouns?K?Nearest?Neighbors）就是一類重要的查詢請求，能夠在道路網絡環境下不斷查找距離給定查詢對象最近的K個最近鄰目標，例如，在消防指揮中，查找距離指揮中心最近的4輛消防車。解決此類問題的關鍵在于：1）快速實時計算任意兩個移動對象之間的最短路徑；2）移動對象位置更新的維護與管理。

國內外針對道路網絡的CKNN查詢問題，學者們做了一些工作。Kolahdouzan提出IE/UBA方法，利用Voronoi圖處理網絡空間的CNN問題，通過減少查詢路徑上的KNN計算次數提高算法效率，但當K值增大、對象分布密度增加時，算法效率急劇下降。Cho針對IE/UBA方法中查詢性能受對象分布密度影響提出UNICONS技術，充分利用預計算匯聚節點（Condensing?Point）的最近鄰提高最短路徑計算速度；為完成CKNN查詢，將查詢路徑分成若干子段，快照式計算每個子段端點的KNNs，每個端點的KNNs及子段上的對象構成最終查詢結果。以上方法都是研究查詢對象是移動而興趣點對象是靜止的情況。Mouratidis^[3]提出IMA/GMA方法處理查詢對象和興趣點對象在道路網上任意移動的CKNN查詢問題。該算法是目前公認的處理基于道路網絡的CKNN查詢經典算法，系統采用基于內存的數據結構存儲網絡邊、節點以及查詢信息，提出IMA/GMA算法處理查詢請求。IMA算法從查詢對象所在邊開始擴展網絡邊，并遍歷網絡邊上的興趣點對象，形成初始KNNs查詢結果集，同時以查詢點為根，建立查詢擴展樹，處理查詢請求、移動對象和道路邊權重更新時的連續查詢請求；GMA采用IMA和共享執行機制，算法的核心是稱作序列（Seqence）的概念，即：序列上的查詢請求結果為序列上的對象和序列端點處KNNs結果的并集，當多個查詢請求處在同一序列上時可共享已獲得的查詢結果。為了維護查詢結果的更新，在計算初始KNNs時建立影響列表。IMA/GMA方法采用基于內存的方式存儲網絡及移動對象，不適合大型道路網絡。Wang提出MovNet框架處理道路網絡環境下的基于位置的查詢，使用基于磁盤的R樹索引道路網絡，基于內存的格網索引管理移動對象的位置更新，通過網格重疊計算算法將道路網與格網單元進行關聯，完成基于位置的范圍查詢和KNN查詢。Demisyurek針對IMA/GMA算法使用Dijkstra算法網絡距離計算時盲目擴展以及對象位置更新時盲目映像的缺點，提出ER-CKNN算法，基于PMR-QuadTree索引道路網絡，基于格網索引管理移動對象位置更新，使用稱作edge-bitmap-encoding技術結合A*啟發式搜索算法，提高最短路徑計算速度；同時，在查詢時使用歐式距離約束（Euclidean?Restriction）限制K近鄰搜索區域；對象位置更新時，只對區域內的移動對象進行更新，從而加快查詢處理速度。廖巍[6]針對基于道路網絡的CKNN查詢處理,提出一種新的道路網絡有向圖模型,分別利用基于內存的哈希表和線性鏈表結構對移動對象當前位置和道路網絡有向圖模型進行存儲和管理.通過引入單向網絡距離度量和雙向網絡距離度量,提出單向網絡擴展(UNE)算法和雙向網絡擴展(BNE)算法以支持不同語義的連續k近鄰查詢處理，并采用影響樹及網絡擴展策略來減少連續k近鄰查詢更新的搜索代價。趙亮[7]針對數據頻繁更新時查詢性能下降問題，結合多核多線程技術，提出了一種基于多線程的連續查詢處理框架。該框架周期性重計算所有查詢結果，將查詢處理分為順序執行的數據更新階段和查詢執行階段，分別使用任務并行和數據并行的方法執行各階段的操作。設計了數據更新階段使用的數據結構，提出了查詢處理階段的k近鄰查詢處理策略，包含離線預計算和在線k近鄰查詢處理算法兩個部分，并對k近鄰算法復雜性及多線程處理框架的加速比進行了理論分析。

然而，以上文獻都是采用一種索引結構對道路網絡段進行索引，將道路網絡建模為有向/無向圖，基于內存數據結構處理最近鄰查詢請求，但是當道路網絡數據量較大、路段較多時，查詢效率急劇降低；并且，基于圖的建模方式，無法反映出移動對象在十字路口的轉向關系，無法解決具有十字路口轉向和U型轉彎約束的復雜道路網絡最近鄰查詢問題。

發明內容