[發(fā)明專利]一種軌跡查詢方法、系統(tǒng)及裝置

有效

• 申請?zhí)枺?/td>: 201710121650.5
• 申請日: 2017-03-02
• 公開（公告）號: CN108536704B
• 公開（公告）日: 2022-02-08
• 發(fā)明（設(shè)計）人: 袁明軒;曾嘉;饒衛(wèi)雄
• 申請（專利權(quán)）人: 華為技術(shù)有限公司
• 主分類號: G06F16/29
• 分類號: G06F16/29
• 代理公司: 北京弘權(quán)知識產(chǎn)權(quán)代理有限公司 11363
• 代理人: 逯長明;許偉群

本申請實施例公開了一種軌跡查詢方法、系統(tǒng)和裝置。所述方法包括：匹配歷史軌跡數(shù)據(jù)和道路網(wǎng)的路段數(shù)據(jù)，建立路段與歷史軌跡之間的映射關(guān)系；根據(jù)路段數(shù)據(jù)生成以所述路段數(shù)據(jù)為空間對象的路網(wǎng)索引；根據(jù)路段數(shù)據(jù)，計算查詢點到各個路段的距離；確定待選軌跡所屬的候選集，包括：對每個查詢點，使用路網(wǎng)索引查找距離最近的一條或多個路段，將與所述最近的一條或多條路段相映射的歷史軌跡放入查詢點的子候選集中，直至子候選集的交集中存在至少K條歷史軌跡；將子候選集合并為候選集；選取候選集中與所述查詢點的距離和最小的K條歷史軌跡。這種方式能夠提高軌跡查詢的效率和準確度。

技術(shù)領(lǐng)域

本申請涉及導航技術(shù)領(lǐng)域，尤其涉及一種軌跡查詢方法、系統(tǒng)及裝置。

背景技術(shù)

給定多個查詢點,在歷史軌跡中找到與這些查詢點的距離的和最小的一條或多條軌跡，是多點軌跡查詢方法所要解決的問題。其中，所述軌跡可以是動物的行動軌跡或者交通工具的行駛軌跡。例如旅游過程中，游客希望在一天內(nèi)游覽多個景點，如果將這些景點作為查詢點，多點軌跡查詢就是從歷史行駛路線中找到距離這些景點最近的一條或多條行駛路線，從而幫助游客進行路線規(guī)劃。

多點軌跡查詢方法中，歷史軌跡由在動物或交通工具行動或行駛過程中實時采集的GPS位置信息組成。基于采集的歷史軌跡數(shù)據(jù)，多點軌跡查詢方法通常分為兩個步驟：先通過查詢算法確定離查詢點最近，也就是與查詢點的距離的和最小的一條或多條軌跡所在的候選集，所述候選集為歷史軌跡數(shù)據(jù)集合的子集；然后對候選集中的每條軌跡，計算其到各個查詢點的距離和，將各個軌跡按所述距離和從小到大排列，選取最小的前K條歷史軌跡，作為最終結(jié)果。其中，查詢算法是多點軌跡查詢方法的重點。

現(xiàn)有的多點軌跡查詢算法主要包括IKNN(Incremental k-NN based Algorithm，擴展的K近鄰算法)、GH(Global Heap，全局堆)和SRA(Spatial Range-based Approach，基于空間區(qū)域的算法)。

其中，IKNN構(gòu)建以軌跡為結(jié)點的R樹空間索引，使用擴展的K近鄰算法在R樹中進行搜索，確定離查詢點最近的K條歷史軌跡所在的候選集。IKNN中，擴展的K近鄰算法以查詢點與軌跡之間的相似度為搜索距離：

上式中m為查詢點個數(shù)，Q是查詢點的集合，T是一條軌跡，e是自然常數(shù)，Dist(q_i,T)是查詢點q_i到軌跡T的歐氏距離，相似度會越大，查詢點距離軌跡越近。

GH對每個查詢點q_i都建立一個獨立堆,獨立堆中含有該查詢點和所有軌跡點組成的二元組，并使其按照軌跡點到查詢點的距離從小到大排列，再選擇其中距離最小的二元組，以此為基礎(chǔ)建立一個全局堆，然后以全局堆為索引基礎(chǔ)進行搜索，確定離查詢點最近的K條歷史軌跡所在的候選集。GH中的搜索距離是查詢點到軌跡T_x的歐式距離的累加：

SRA構(gòu)建以軌跡為結(jié)點的R樹空間索引，基于軌跡R樹進行空間區(qū)域搜索，來確定離查詢點最近的K條歷史軌跡所在的候選集，其所使用的搜索距離與GH所使用的搜索距離相同。

但是，現(xiàn)有的多點軌跡查詢算法都是基于查詢點到軌跡的歐氏距離進行搜索，查詢點到軌跡的歐氏距離根據(jù)軌跡的GPS(Global Positioning System，全球定位系統(tǒng))數(shù)據(jù)計算，由于GPS數(shù)據(jù)與真實位置數(shù)據(jù)之間存在偏移，查詢點到軌跡的歐氏距離也將偏移查詢點到實際軌跡的真實距離，產(chǎn)生很大的計算誤差，導致查詢準確度降低。再者，現(xiàn)有的多點軌跡查詢方法都是基于軌跡構(gòu)造空間索引，把所有軌跡的GPS點放在一個R樹下或者堆中，由于軌跡和軌跡點數(shù)量眾多，索引結(jié)構(gòu)將非常龐大，導致索引速度慢，查詢效率低。

發(fā)明內(nèi)容

本申請?zhí)峁┝艘环N軌跡查詢方法、系統(tǒng)及裝置，以解決現(xiàn)有技術(shù)中軌跡查詢效率低的問題。