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

有效

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

1.道路網絡中基于RRN-Tree的移動對象CKNN查詢方法，其特征在于：該查詢方法的實現步驟為：

步驟一：首先，分別定義道路網絡G、路線r、路段seg、交叉路口j、移動對象o和KNN監測區；

所述道路網絡G為一個二元組G=（R，J），其中R是道路網中路線集合，每條路線包含若干路段，J是道路網中多條路線的交叉點集合；

所述路線r是指道路網絡中可獨立命名的一條完整路徑，定義為：

r=(rid,len,(jidj,posj)j=1m);]]>

其中，rid是路線標識；len表示路線長度，len∈[0,1]；表示路線上的交叉路口及其在路線上相對路線起點的位置集合，pos_j∈[0,1]；

所述路段seg是指相鄰交叉路口之間的一段路線，定義為：

seg=(sid,rid,p_s,p_e,dir)；

其中，sid、rid分別表示路段及所在路線的標識；p_s、p_e表示路段的起始點和終點；dir∈{-1,0,1}，當值為1時表示移動對象在該路段上允許從起點向終點方向運動，值為-1則表示從路段終點向起始點方向運動，0表示該路段允許雙向通行；

所述交叉路口j是指多條路線的交叉節點，定義為：

其中jid為交叉路口的標識；(rid_j,pos_j)表示該交叉路口在第j條路線上的位置；adjList為交叉路口的鄰接列表，存儲該交叉路口處各路段的連接關系；

所述移動對象o是指在道路網絡中，將移動對象o建模為：o=(oid,x,y,rid,pos,dir)；

其中，oid、rid分別表示移動對象及其所在路線；x，y表示移動對象的經緯度坐標；pos表示移動對象距離所在路線起點的距離，pos∈[0,1]；dir表示移動對象的運行方向，值為1表示從所在路段起點向終點方向運行，值為-1則是從所在路段的終點向起點方向運行；

所述KNN監測區是指以查詢對象q為根，KNN_dist為距離上限，所有與q相連的路段構成的查詢區域；

步驟二、構建RRN-Tree索引結構，將鄰接鏈表技術引入索引結構中，用鄰接鏈表來表示路線上交叉路口處的道路邊之間的連接關系，基于網絡邊擴展思想，計算查詢對象的K個最近鄰對象；同時在計算KNN查詢結果集時建立K近鄰監測區；

所述RRN-Tree索引結構由三部分組成：對道路網絡的路線進行索引的頂層2D?R-Tree、表示路線上交叉節點鄰接關系的鄰接鏈表和索引各個路線上移動對象的底層R-Tree；

所述對道路網絡的路線進行索引的頂層2DR-Tree，其葉子節點是一個三元組：<mbb,polypt,treept>；

其中，mbb表示路線對應polyline的最小外包邊界；polypt指向路線的實際表示，treept指向底層R樹；

所述索引各個路線上移動對象的底層R-Tree，其葉子節點是一個二元組：<mbb,childpt>，其中mbb表示所有孩子節點的MBBs集合，childpt指向孩子節點，即：索引某路線對應的各路段及路段上的移動對象的底層R樹指針；

所述表示路線上交叉節點鄰接關系的鄰接鏈表是由hash表和兩級單鏈表組成，hash表部分與MON-Tree中含義相同，第一級單鏈表表示路線上的各個節點，第二級節點表示某節點的出度；

步驟三：根據步驟二所構建的RRN-Tree索引結構，進行基于道路網絡的CKNN查詢；

所述基于道路網絡的CKNN查詢包括KNN查詢初始集計算和CKNN查詢更新兩個階段：

首先，第一階段所述KNN查詢初始集計算是指：當查詢對象基于當前位置發出KNN查詢請求時，首先通過RRN-Tree索引結構快速定位查詢對象所在路段，并將路段的兩個端點入隊列，并按照距離查詢點的距離從小到大排序；然后讀取距離查詢點最近的興趣點對象存入結果隊列中，當對象數少于K個時，沿著查詢對象前進方向的路段頂點繼續擴展，通過讀取路段頂點的鄰接鏈表確定各路段的連接關系，在有連接關系的路段上擴展查找最近鄰對象，直到找到K個對象為止；最后，為了提高連續查詢的查詢效率，以第K個對象距離查詢點的距離為距離上限，將所有與查詢點有連接關系的路段建立KNN查詢監測區，凡是落在該監測區域內的對象將成為候選的KNN結果；

第二階段進行CKNN查詢更新，所述CKNN查詢更新分為兩種情況：當查詢點對象位置不變，而興趣點對象移動時，利用查詢過程生成的KNN監測區可降低查詢更新代價；當查詢點對象移動時，應用上述的第一階段的KNN查詢初始集計算的查詢算法重新計算查詢請求。