基于時間線段樹的城市可達區域搜索

孫鶴立，張優優，楊 洲，何 亮，賈曉琳

（西安交通大學計算機科學與技術學院，西安 710049）

（*通信作者電子郵箱xlinjia@xjtu.edu.cn）

0 引言

近年來，隨著智慧城市的快速發展，城市計算的概念被提出并很快受到了極大的關注。城市可達區域搜索是城市計算中基于位置的最重要的服務之一，可在用戶指定的空間位置和時間間隔等條件下，根據大量的軌跡數據［1］挖掘出特定路段。它對于許多城市應用具有重要的意義，如基于位置的推薦、基于位置的廣告、商業覆蓋分析等。

Jeung 等［2］于2010 年提出了基于預測線路的方法來進行城市區域查詢。同年，Zhang 等［3］提出了基于閔科夫斯基和與k最近鄰（k-Nearest Neighbor，kNN）算法進行區域查詢。2015 年，Li 等［4］提出了一種基于采樣的方法獲取用戶指定區域的軌跡數目。Li 等［5］和Alarabi［6］提出了在大量軌跡中的高效管理查詢方法。除此之外，針對可達性查詢問題也開展了一些相關工作。可達性查詢是指查詢在圖中的兩個節點之間是否存在一條通路，這是其他許多應用的基本問題。Chen等［7-8］和van Schaik 等［9］提出了多種高效的方法來解決圖可達查詢問題。此外，Bramandia 等［10］和Cai 等［11］還引入了兩跳標記模式來解決查詢問題，并提出了一些啟發式方法來減小標簽的大小。Du 等［12］引入了k跳改進了兩跳標記模式方法。Seufert 等［13］和Veloso 等［14］提出構造一個小索引，以較小的構造成本來解決可達性查詢。以上這些傳統的圖可達性查詢方法主要集中在靜態圖結構上［15-16］，而不是像軌跡這樣與圖結構相關聯的動態數據。與這些查詢不同，Anastasiou等［17］提出了數據驅動的可達性分析方法。Wu 等［18］提出了單點上下界限區域可達查詢（Single-location reachability Query Maximum/minimum Bounding region search，SQMB）方法，時空可達性查詢結果依賴于查詢時間且查詢速度較快，但是在實際大規模應用中，該方法仍會存在查詢效率和查詢準確率低下的問題。

針對以上問題，本文提出一種基于時間線段樹的城市可達區域搜索tst_search（urban reachable region search based on time segment tree）算法，主要包括：道路的概率時間權重生成、層級跳躍表的生成與存儲、構建時間線段樹索引結構和道路網絡迭代搜索4 個步驟。實驗結果表明，與現有方法相比，本文提出的可達區域搜索方法具有更高的效率與準確率。

本文的主要工作如下：

1）提出了基于道路速度分布模型的概率時間權重計算方法；

2）設計了存儲局部可達區的層級跳躍表和時間線段樹，提高了算法搜索效率；

3）提出了動態自適應的可達區域搜索算法，提高了搜索準確率。

1 城市可達區域搜索框架

1.1 基本概念

定義1道路網絡。道路網絡RN可以被視為有向圖G=(V，R)，其中V={v1，v2，…，vm}是交叉口的集合，R={r1，r2，…，rn}是路段的集合。

定義2軌跡。軌跡Tr是時間有序的序列Tr={p1，p2，…，pn}，其中每個點pi=(lati，lngi，ti)，1 ≤i≤n，pi是包含經度lngi、緯度lati和時間戳ti的全球定位系統（Global Positioning System，GPS）記錄。

定義3可達性。給定起始位置S，起始時間T，行程時間L，道路網絡中的路段ri，如果由歷史軌跡生成的帶時間權重的道路網絡中存在一條通路，在給定的行程時間L之內從起始位置穿過給定路段，則可達，否則不可達。可達性具體表示為：

其中：mt為S在T時刻的到ri的最小時間間隔。

定義4可達區域。給定起始位置S，起始時間T，行程時間L，可達區域是一組包含所有從S開始的可達路段。可達區域的具體表示為：

定義5概率速度vp。給定道路網絡中某條路段的歷史速度分布函數f(v)，累積分布函數F(v)，概率p，那么概率速度vp是指使P(v＞vlim)=1-F(v)=p的速度vlim。具體表示為：

定義6概率可達區域。概率可達區域是可達區域更一般的描述，可達概率描述了歷史軌跡數據集中支持在給定行程時間內從S可達路段ri這一事實的概率速度對應的置信度。

1.2 問題定義

給定道路網絡G(V，R)，起始位置S，起始時間T，行程時間L，置信度P，軌跡數據庫Tr，查詢某路段集合作為G中的概率可達區域，使得區域中的路段都至少能在給定的行程時間內從起始位置S到達。

1.3 整體框架

本文方法使用了高效的數據結構和動態的自適應搜索算法，使得城市可達區域的查詢既快速又準確。整體方案框架如圖1 所示，主要包括4 個環節：1）進行軌跡與道路的地圖匹配，根據道路速度分布模型生成道路段的概率時間權重；2）利用層級跳躍表算法生成多時間粒度的局部可達區域集合，并進行短時間可達區域存儲；3）利用時間線段樹對層級跳躍表所存儲的多時間粒度可達區域建立高效的層次樹狀索引結構；4）使用時間線段樹索引在道路網絡中進行迭代搜索，最終輸出可達區域集合。

圖1 可達區域搜索框架Fig.1 Framework of reachable region search

2 城市可達區域搜索算法

2.1 道路概率時間權重生成

首先使用地圖匹配算法將軌跡數據映射到道路網絡中［19］，得到各條城市道路段對應的歷史軌跡。然后將歷史軌跡在時間維度上進行分箱，這里以10 min為間隔，根據歷史軌跡計算短時間間隔內道路的平均速度和速度方差，如圖2所示。

圖2 地圖匹配Fig.2 Map matching

通過卡方檢驗等數據檢驗方法發現，道路的速度分布滿足對數正態分布［20-21］。概率密度函數為：

其中：μ與σ分別是變量對數的平均值與標準差。根據平均速度E(v)與方差D(v)，可以通過以下兩式求得μ與σ的值：

得到了道路段的速度分布模型后，根據概率速度的定義即可生成不同置信度對應的速度，進而生成道路的概率時間權重。

2.2 層級跳躍表生成算法

由于城市道路網絡的規模較大，在道路網絡中直接使用貪心搜索算法會導致搜索效率低下，因此，本文提出了層級跳躍表（Hierarchical Skip List，HSL）生成算法，該算法通過生成多時間粒度而非單一時間粒度的局部可達區域集合，并進行短時間可達區域信息的存儲來提升長時間查詢的效率與準確率。具體來說，本文設計的HSL 算法引入了層級跳躍表中的時間粒度約束。在算法迭代的過程中，當道路網絡中從某路段起始的可達路徑的時間間隔超過附加的時間約束時，如果繼續執行網絡擴張算法，可達時間超過行程時間間隔的可達路段會在存儲時丟棄，屬于冗余信息，因此算法會提前終止。算法1展示了層級跳躍表生成的具體過程。

層級跳躍表如圖3 所示，記錄了任意一條路段在連續時間間隔T1-T2、T2-T3、T3-T4 內可以到達的路段。當所有的層級跳躍表都計算并存儲完畢時，對于用戶輸入的某行程時間L，在搜索的開始階段可以利用層級跳躍表快速地進行粗粒度時間的路網擴張搜索，在搜索過程接近尾聲時，層級跳躍表可以適應細粒度時間的搜索要求，使搜索結果更加準確。

2.3 時間線段樹索引構建

若直接在層級跳躍表上進行可達區域搜索，在高頻次搜索情況下，可達區域搜索仍然存在低效的問題。因此，在獲得了道路的層級跳躍表之后，在其基礎上構建時間線段樹索引來進一步提升查詢效率。

圖3 層級跳躍表Fig.3 Hierarchical skip list

如圖4 所示，時間線段樹的基本結構是一棵二叉搜索樹，它存儲的是不同時間間隔的可達區域信息，每個節點包含以下信息：時間間隔的起始時刻和終止時刻；每個時間間隔內可達區域集合。以節點1 為例，1∶0-1 的含義是時間線段樹索引為1 的節點存儲了時間間隔索引0 到1 的可達區域信息，該區域信息可由節點1 的左孩子節點3 和右孩子節點4 得到，其中節點3 維護的時間間隔索引0 的可達區域信息，同理，節點4維護的時間間隔索引1 的可達區域信息。由于時間線段樹存儲了多時間間隔的可達區域信息，在可達區域搜索的過程中，本文算法會根據行程時間自動調整當前搜索的時間間隔，以適應不同的搜索條件。

時間線段樹索引的操作主要有兩個：構建與查詢。時間線段樹索引的構建過程如下：1）對于每一個樹節點，確定其起始與終止時間索引的范圍；2）若節點為葉子節點，保存該節點時間索引所維護的區域信息，否則遞歸建立以左右孩子為根節點的時間線段樹；3）遞歸返回時合并各個孩子節點所保存的區域信息，從而完成整棵樹的建立。

當時間線段樹構建完成后，線段樹中的各個節點分別存儲了不同長短時間間隔對應的可達區域（道路段）信息。以圖4 為例，假設層級跳躍表中存儲了以下信息：從某起始路段r0出發在0～1，1～2，…，3～4 min 內到達的區域分別為A1、A2、A3、A4，那么時間線段樹構建完成后，葉子節點3、4、5、6存儲的可達區域分別為A1、A2、A3、A4，節點1、2 存儲的可達區域分別為A1∪A2，A3∪A4，根節點0存儲的可達區域為A1∪A2∪A3∪A4。

圖4 時間線段樹Fig.4 Time segment tree

2.4 可達區域搜索算法

可達區域搜索算法以時間線段樹索引為基礎，根據搜索輸入的概率P，起始位置S，起始時刻T，行程時間L來輸出可達區域的路段集合。首先，介紹時間線段樹索引查詢過程：1）若查詢時間區間與根節點時間區間相等，直接返回根節點維護的區域信息即可，否則根據查詢區間與左右孩子節點的關系遞歸在左子樹或者右子樹中搜索；2）遞歸返回過程中對兩個孩子節點的區域信息進行合并并返回。

然后，對于城市可達區域搜索的整個過程，具體步驟如下：首先初始化可達區域，然后根據時間線段樹索引查詢當前時刻T可達區域中所有路段擴展的區域，并動態更新區域內所有路段的剩余權重，之后，更新可達區域，迭代上述過程直到所有路段的剩余權重為零時算法終止。算法2 展示了可達區域搜索的具體過程。

具體流程如下：

1）初始化可達區域。使用起始位置S對可達區域進行初始化，并將S的剩余時間remainder初始化為L；

2）擴增可達區域。根據時間線段樹和路段ri的剩余時間remainderi查詢當前可達區域中所有路段ri的局部可達區域，擴增當前可達區域并根據ri與其局部可達區域之間的行程時間ti更新所有可達路段的剩余時間remainderi，具體地，若某路段ri的剩余時間remainderi，根據時間線段樹查詢其局部可達區域中某路段rj距離ri的行程時間為ti，那么將rj擴增為當前可達區域后，rj的剩余時間更新為remainderi-ti；

3）循環步驟2）直至所有可達路段的剩余時間為零，輸出可達區域。

3 實驗與結果分析

3.1 實驗環境與數據集

在本研究過程中，實驗環境為64 位Windows 10，Intel Core i5-4590，3.30 GHz 四核CPU，8 GB 內存。主要使用了兩類數據集［22-24］：地圖網絡數據和軌跡數據。地圖網絡數據使用了北京市的路網數據，包括196 307 條道路和148 110 個路口；軌跡數據是由北京市上萬輛出租車從2013 年9 月1 日—10 月31 號2 個月內所產生的，包括673 469 757 個GPS 點，總長度達到26 218 407 km。

3.2 評價指標

為驗證算法在城市可達區域搜索中的性能，使用運行時間和準確率來評價算法。設窮舉算法的可達區域集合為Se，其他算法搜索所得的可達區域集合為Sa，那么，本文定義兩者的Jaccard系數為該算法的準確率：

從式（7）可看出，被評價算法的可達區域集合與窮舉算法的可達區域集合交集數量與并集數量之比即為被評價算法的準確率。

3.3 層級跳躍表生成的效率比較

圖5 展示了在層級跳躍表的生成過程中使用了時間粒度約束后，本文的HSL 算法相較于基準的貪心算法DH（Dijkstra with Heap）的運行效率。

由圖5 可知，相較于DH 算法，本文提出的HSL 算法在p=0.6，0.7，0.8 等不同查詢概率下，本文算法的運行時間均小于DH 算法。分析其原因，DH 算法在網絡擴張過程中只有單一的網絡大小條件約束，而HSL 算法加入了新的時間維度的約束，使得算法避免在全局網絡中進行搜索，而僅僅在包含結果的局部網絡中迭代擴增，因此，本文算法效率大幅提升。

圖5 層級跳躍表生成的效率比較Fig.5 Efficiency comparison of generation of hierarchical skip list

3.4 可達區域搜索的效率比較

與最新的研究一致，將基準方法設置為窮舉搜索es_search（exhaustive search），該算法通過在道路網絡中不斷搜索相鄰路段來獲取可達區域［18］。除此之外，還對比了目前最新的連接表搜索（search based on connection table，con_table_search）算法［18］和tst_search，以驗證本文算法的高效性和準確性。

圖6 展示了不同行程時間對算法運行時間的影響。其中，圖6（a）表示的是Δt=400，p=0.6 條件下各種算法效率對比，由實驗結果可知es_search 算法的運行時間穩定在34 s 左右，con_table_seach 與tst_search 算法的運行時間隨著行程時間的增加而增加，但是即使在行程時間長達1 h 的條件下，這兩個算法的運行時間依然遠小于es_search，且本文的tst_search 算法運行時間總低于con_table_seach。此外，為了驗證不同參數對實驗結果的影響，本文針對不同的線段樹時間間隔和查詢概率進行了大量實驗。圖6（b）～（f）分別表示了在其他5 種不同條件下，3 種算法運行時間的對比。不難發現，本文tst_search 算法效率依然高于其他兩種算法。分析其原因，tst_search 使用了線段樹在時間區間上存儲的局部可達區域信息，可以快速地查找某時間間隔內可達區域的集合。相較于直接查找，線段樹的查找時間復雜度為O(logN)，在數據量較大的情況下，查詢效率遠高于時間復雜度為O(N)的直接查找。除此之外，多層跳躍表的設計也擴增了跳躍搜索的最大時間間隔，允許算法在更大范圍上進行快速迭代，減少算法的運行時間。

3.5 可達區域搜索的準確率比較

不同算法的準確率如圖7 所示。由實驗結果可知，本文提出的tst_search 算法的準確率在不同行程時間不同查詢概率的情況下均遠高于con_table_search 算法，分析其原因，con_table_search 算法在地圖網絡中迭代搜索時，不管起始位置到中間路段的具體時間值，均在下次迭代時將查詢時間削減一個定值，即連接表的最大時間間隔。而本文提出的tst_search 動態地記錄了每條路段的時間權重，能較準確地查詢出可達區域結果。此外，本文線段樹的層級設計結構在算法即將終止時能在細粒度時間上搜索，也對可達區域的準確性有益。

圖6 不同行程時間的效率比較Fig.6 Efficiency comparison of different travel times

圖7 不同行程時間的準確率比較Fig.7 Accuracy comparison of different travel times

4 結語

本文提出了一種根據用戶指定的條件在城市中搜索可達區域的方法。該方法通過道路的概率時間權重生成、層級跳躍表的生成與存儲、構建時間線段樹索引結構、道路網絡迭代搜索等四個環節，完成城市可達區域搜索過程。本文方法使用了時間線段樹索引，將局部可達信息提前存儲起來，并且使用了動態自適應的迭代搜索策略，在保證高效的前提下盡可能減小搜索結果的錯誤。實驗結果表明，本文方法與現有方法相比，城市可達區域的搜索既高效又準確。在接下來的工作中，將研究多個起始位置情況下的可達區域搜索問題，以便為復雜場景下的應用提供思路。