針對城市計算中的可達(dá)區(qū)域搜索問題,提出一種基于時間線段樹的搜索方法。該方法中,設(shè)計了存儲局部可達(dá)區(qū)域的時間線段樹結(jié)構(gòu),并提出動態(tài)自適應(yīng)的可達(dá)區(qū)域搜索算法,從而提高了城市可達(dá)區(qū)域搜索的效率與準(zhǔn)確率。該方法主要包括4個步驟:根據(jù)道路速度分布模型和軌跡數(shù)據(jù)生成道路段的概率時間權(quán)重;利用層級跳躍表算法進(jìn)行短時間可達(dá)區(qū)域的查詢與存儲;利用時間線段樹對層級可達(dá)區(qū)域建立高效的索引結(jié)構(gòu);使用時間線段樹索引在道路網(wǎng)絡(luò)中進(jìn)行迭代搜索,最終輸出可達(dá)區(qū)域集合。在北京市道路網(wǎng)絡(luò)和出租車軌跡數(shù)據(jù)集上進(jìn)行了大量實驗,結(jié)果表明,與最新的單點上下界限區(qū)域可達(dá)查詢(SQMB)方法比較,該方法在時間效率和準(zhǔn)確率上分別提高了18.6%和25%。

【文章頁數(shù)】：6 頁

【部分圖文】：

圖1可達(dá)區(qū)域搜索框架

本文方法使用了高效的數(shù)據(jù)結(jié)構(gòu)和動態(tài)的自適應(yīng)搜索算法，使得城市可達(dá)區(qū)域的查詢既快速又準(zhǔn)確。整體方案框架如圖1所示，主要包括4個環(huán)節(jié)：1）進(jìn)行軌跡與道路的地圖匹配，根據(jù)道路速度分布模型生成道路段的概率時間權(quán)重；2）利用層級跳躍表算法生成多時間粒度的局部可達(dá)區(qū)域集合，并進(jìn)行短時間可達(dá)區(qū)....

圖2地圖匹配

首先使用地圖匹配算法將軌跡數(shù)據(jù)映射到道路網(wǎng)絡(luò)中[19]，得到各條城市道路段對應(yīng)的歷史軌跡。然后將歷史軌跡在時間維度上進(jìn)行分箱，這里以10min為間隔，根據(jù)歷史軌跡計算短時間間隔內(nèi)道路的平均速度和速度方差，如圖2所示。通過卡方檢驗等數(shù)據(jù)檢驗方法發(fā)現(xiàn)，道路的速度分布滿足對數(shù)正態(tài)分布....

圖3層級跳躍表

若直接在層級跳躍表上進(jìn)行可達(dá)區(qū)域搜索，在高頻次搜索情況下，可達(dá)區(qū)域搜索仍然存在低效的問題。因此，在獲得了道路的層級跳躍表之后，在其基礎(chǔ)上構(gòu)建時間線段樹索引來進(jìn)一步提升查詢效率。如圖4所示，時間線段樹的基本結(jié)構(gòu)是一棵二叉搜索樹，它存儲的是不同時間間隔的可達(dá)區(qū)域信息，每個節(jié)點包含以下....

圖4時間線段樹

當(dāng)時間線段樹構(gòu)建完成后，線段樹中的各個節(jié)點分別存儲了不同長短時間間隔對應(yīng)的可達(dá)區(qū)域（道路段）信息。以圖4為例，假設(shè)層級跳躍表中存儲了以下信息：從某起始路段r0出發(fā)在0～1,1～2，…，3～4min內(nèi)到達(dá)的區(qū)域分別為A1、A2、A3、A4，那么時間線段樹構(gòu)建完成后，葉子節(jié)點3、4....

本文編號：3977766