indexforcitytrajectories(已修改)
2025-10-29 01:48 本頁(yè)面
【正文】 Index for city trajectories Mobile Group, IDKE Renmin University of China Caifeng Lai 城市路網(wǎng)的特點(diǎn)： ? 城市路網(wǎng)中的路線一般較為平直，且地面一般較為平坦，現(xiàn)代城市的路網(wǎng)規(guī)劃也較為合理，因此，我們考慮可以用一種很簡(jiǎn)單的方法對(duì)其降維。 ? 城市路網(wǎng)中的車(chē)流量較大，在同一路線上的距離相近的移動(dòng)對(duì)象的運(yùn)動(dòng)狀態(tài)基本相似，移動(dòng)對(duì)象也比較密集，因此我們可以考慮將這類(lèi)的移動(dòng)對(duì)象封裝起來(lái)，在其之上建立索引，然后進(jìn)行相應(yīng)的操作。 兩個(gè)解決的方法 ? 降維 分為兩種情況： ? 如果路線的斜率小于 1，則將路線上的點(diǎn)映射到 x軸上，求出其相對(duì)該路線的相對(duì)位置 ? 反之，則映射到 y軸上，求出其相對(duì)該路線的相對(duì)位置 ? 分組移動(dòng)對(duì)象 ? 將在同一路線上的、距離相近、移動(dòng)方向一致、速度接近的移動(dòng)對(duì)象組合成一組，將其稱(chēng)為 AU。 0101Group moving objects Previous approach –TPRtree ( t interval ) Previous approach –TPRtree ( t+1 interval ) Our approach –AU ( t interval ) Our approach –AU ( t+1 interval ) AU index Architecture ? The AU index scheme consists of four ponents: ? The top R*tree captures the work connectivity. Each leaf node contains several road segments. ? The bottom R*tree contains currentAU index and pastAU index. ? The currentAU is a main memory index which represents the current state of each AU. ? The pastAU represents the past state of each AU and was left in a container on disk. AU index Architecture (cont.) root leaf T current AU past AU R* tree Rtree（ A. Guttman SIGMOD’1984） Rtree的特點(diǎn) ? Rtree是 BTree對(duì)多維對(duì)象（點(diǎn)和區(qū)域）的擴(kuò)展 ? Rtree是一棵平衡樹(shù) ? 一個(gè)多維對(duì)象只能被分到一個(gè)子空間中去 ? 若用動(dòng)態(tài)插入算法構(gòu)建 Rtree，在樹(shù)的結(jié)點(diǎn)中會(huì)引起過(guò)多的空間重疊和死區(qū)（ deadspace） ,使算法性能降低 Rtree的典型算法 ? 查找 ? 插入 ? 選擇葉子結(jié)點(diǎn) ? 分裂結(jié)點(diǎn)（有多種算法） ? 調(diào)整樹(shù) ? 必要時(shí)增加樹(shù)的高度 ? 刪除 ? 找到包含要?jiǎng)h除記錄的葉子結(jié)點(diǎn) ? 刪除 ? 壓縮樹(shù) ? 必要時(shí)減小樹(shù)的高度 ? 更新 ? 先刪除老的記錄索引，在插入新的記錄索引 Rtree的典型算法 ? 查找 ? 插入 ? 選擇葉子結(jié)點(diǎn) ? 分裂結(jié)點(diǎn)（有多種算法） ? 調(diào)整樹(shù) ? 必要時(shí)增加樹(shù)的高度 ? 刪除 ? 找到包含要?jiǎng)h除記錄的葉子結(jié)點(diǎn) ? 刪除 ? 壓縮樹(shù) ? 必要時(shí)減小樹(shù)的高度 ? 更新 ? 先刪除老的記錄索引，在插入新的記錄索引 R*Tree（ N. Beckmann SIGMOD’1990） ? R*Tree通過(guò)修改插入、分裂算法，并通過(guò)引入強(qiáng)制重插機(jī)制對(duì) RTree的性能進(jìn)行改進(jìn)。 ? R*Tree和 RTree一樣允許矩形的重疊， ? R*Tree在選擇插入路徑時(shí)同時(shí)考慮矩形的面積、空白區(qū)域和重疊的大小，而 RTree只考慮面積的大小。 R*tree ? Recursively cluster objects into minimum bounding rectangles (MBR). ? Organize the MBRs into a dynamic, diskbased, balanced tree structure, similar to the B+tree.
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1