基于Voronoi圖的路網(wǎng)軌跡數(shù)據(jù)查詢技術(shù)研究.pdf

1、移動互聯(lián)和移動計算已逐步走進千家萬戶，帶有定位功能的移動智能終端幫助人們實時記錄移動歷史，海量的軌跡數(shù)據(jù)信息反映了人們的行為信息和社交關(guān)系。多位置軌跡查詢作為一種應(yīng)用廣泛的軌跡查詢技術(shù)，已經(jīng)成為當(dāng)前的一個研究熱點。多位置軌跡查詢是搜索那些能連接多個查詢位置點的軌跡，其查詢結(jié)果依賴軌跡對多個位置的連接性。目前，多位置軌跡查詢研究主要集中在歐式空間，沒有考慮路網(wǎng)環(huán)境約束，且存在受軌跡數(shù)據(jù)集影響較大、查詢效率不高和擴展性不好的問題。針對這些不

2、足，本文對路網(wǎng)中的多位置軌跡查詢技術(shù)進行了研究。
　　首先，為了解決軌跡數(shù)據(jù)冗余性和異構(gòu)性對軌跡查詢的影響，本文提出了一種基于Voronoi圖的路網(wǎng)軌跡數(shù)據(jù)簡化算法。在考慮到采樣軌跡數(shù)據(jù)中存在的冗余性和不同軌跡數(shù)據(jù)采樣率不同的問題，對現(xiàn)有的軌跡簡化處理技術(shù)進行了分析和總結(jié)，通過利用Voronoi圖的空間近鄰關(guān)系預(yù)計算特征和路網(wǎng)結(jié)構(gòu)相對穩(wěn)定特性來簡化處理海量軌跡數(shù)據(jù)，使其統(tǒng)一為路網(wǎng)節(jié)點密度的路網(wǎng)語義軌跡。
　　其次，針對路網(wǎng)約

3、束下的多位置軌跡查詢，論文提出了一種路網(wǎng)中基于Voronoi圖的連接軌跡查詢算法。該算法首先利用Voronoi圖的近鄰關(guān)系把每個查詢位置轉(zhuǎn)換成相應(yīng)的路網(wǎng)節(jié)點，然后在給定的距離閾值范圍內(nèi)對查詢節(jié)點進行網(wǎng)絡(luò)范圍查詢，并通過合并所有查詢節(jié)點的查詢結(jié)果得到連接多個查詢位置的軌跡，這不但保證了軌跡在每個查詢位置的有限可達性，而且保證了多位置的連接性。
　　最后，提出了一種基于路徑距離的最佳連接軌跡查詢算法。算法引入了軌跡路徑距離的概念，能夠

4、滿足最佳連接軌跡查詢的應(yīng)用需求。該算法不但要求軌跡近鄰多個查詢位置，而且需要根據(jù)軌跡對多位置連接的路網(wǎng)路徑距離來衡量軌跡的連接性，并排名、輸出最佳連接軌跡。這保證了最佳連接軌跡在距離閾值內(nèi)近鄰連接多查詢位置的同時獲得最短的連接路徑距離。
　　本文針對以上三個創(chuàng)新點展開了理論研究。在真實路網(wǎng)的模擬軌跡數(shù)據(jù)集上展開了實驗研究，結(jié)果表明，本文介紹的方法可以有效的簡化處理軌跡數(shù)據(jù)，尤其是高采樣的軌跡數(shù)據(jù)。基于Voronoi圖的多位置連接軌