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

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

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

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

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