發(fā)布時(shí)間：2024-05-19 07:03

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

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

【部分圖文】：

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

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

圖2地圖匹配

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

圖3層級(jí)跳躍表

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

圖4時(shí)間線段樹

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

本文編號(hào)：3977766