地理定位日志中的軌跡搜索研究.pdf

1、近幾年來(lái)，隨著移動(dòng)信息技術(shù)的迅猛發(fā)展與集成了定位芯片的移動(dòng)終端的迅速普及，云端能夠非常方便的獲取個(gè)人的出行軌跡。許多基于地理位置信息的研究層出不窮，同時(shí)也催生了大量相關(guān)應(yīng)用。這些與時(shí)空軌跡相關(guān)的新興研究和應(yīng)用給人們的日常生活帶來(lái)便利的同時(shí)也對(duì)空間數(shù)據(jù)庫(kù)中時(shí)空軌跡數(shù)據(jù)的有效管理帶來(lái)了很大的挑戰(zhàn)。與此同時(shí)，如何高效利用這些海量數(shù)據(jù)已經(jīng)成為了時(shí)空數(shù)據(jù)的管理和利用領(lǐng)域的研究熱點(diǎn)。
　　k-BCT查詢(k Best-Connected Tr

2、ajectories query)是最近提出的一種多查詢點(diǎn)k最近鄰軌跡對(duì)象搜索問(wèn)題。其在旅游路線推薦以及個(gè)人出行模式研究上具有較為廣泛的應(yīng)用，但是由于k-BCT只考慮歐氏距離不考慮時(shí)間因素，對(duì)實(shí)際應(yīng)用指導(dǎo)有限，因此本文提出了一種改進(jìn)的查詢模型，同時(shí)提出相應(yīng)的兩種應(yīng)答算法，并通過(guò)實(shí)驗(yàn)證明了這兩種算法的有效性。
　　本文主要通過(guò)以下兩個(gè)方面展開(kāi):
　　1)通過(guò)分析k-BCT查詢，發(fā)現(xiàn)k-BCT查詢僅僅只考慮了軌跡點(diǎn)之間的歐氏距離

3、，而定位日志中的軌跡點(diǎn)都具有時(shí)間屬性，處在不同的時(shí)間段的軌跡具有不同的現(xiàn)實(shí)意義，通過(guò)進(jìn)一步分析，得到k-BCT查詢對(duì)現(xiàn)實(shí)生活的指導(dǎo)是有限的。因此，本文對(duì)k-BCT查詢進(jìn)行改進(jìn)，得到了基于軌跡點(diǎn)權(quán)重的軌跡查詢—k-WCT(k Weighted Connected Trajectories)，k-WCT查詢模型同時(shí)考慮了時(shí)間因素和歐氏距離，并分析得到k-WCT查詢具備更好的現(xiàn)實(shí)指導(dǎo)意義。然后，為了設(shè)計(jì)一個(gè)有效的算法來(lái)應(yīng)答k-WCT查詢，本文

4、提出了基于加權(quán)Max Rtree索引的軌跡搜索算法Rtree-FA，最后通過(guò)實(shí)驗(yàn)對(duì)比分析證明了該算法比k-BCT查詢應(yīng)答算法BF-O具有更高的搜索質(zhì)量。
　　2)盡管Rtree-FA算法能夠較好的解決了k-WCT查詢問(wèn)題，但是該算法因?yàn)樽陨斫Y(jié)構(gòu)特點(diǎn)，具有查詢次數(shù)多、計(jì)算消耗大、I/O占用高等缺陷。為了彌補(bǔ)Rtree-FA算法在查詢性能較低與I/O占用高等方面的不足，為k-WCT查詢帶來(lái)更大的性能提升，本文借鑒加權(quán)Voronoi圖，