移動(dòng)設(shè)備的快速發(fā)展,生成了大量軌跡.基于位置的軌跡搜索,是指給定一組查詢點(diǎn),從數(shù)據(jù)集中檢索top-k條軌跡,但是所得到的軌跡可能不能近距離通過(guò)所有查詢點(diǎn).利用軌跡可拼接的想法,提出基于位置的可拼接軌跡對(duì)搜索,使用戶利用軌跡對(duì)得到的軌跡更加近距離地通過(guò)所有查詢點(diǎn).在搜索終止過(guò)程,給出可拼接的軌跡對(duì)搜索過(guò)程的有效終止條件.真實(shí)的數(shù)據(jù)集驗(yàn)證了所提方法的有效性. 

【文章來(lái)源】：北京理工大學(xué)學(xué)報(bào). 2019,39(03)北大核心EICSCD

【文章頁(yè)數(shù)】：7 頁(yè)

【部分圖文】：

圖１軌跡和查詢點(diǎn)Ｆｉｇ．１Ｔｒａｊｅｃｔｏｒｉｅｓａｎｄｑｕｅｒｙｐｏｉｎｔｓ

使得通過(guò)Ｔ可以找到與它形成可拼接軌跡對(duì)的所有軌跡．為了減少所占內(nèi)存和重復(fù)索引，每條軌跡的倒排表只儲(chǔ)存比該軌跡編號(hào)小的軌跡，在搜索過(guò)程中只需要讀取倒排表即可．如圖２，設(shè)Ｔ１上的軌跡點(diǎn)ｐ１，５所在網(wǎng)格為ａ，對(duì)ａ及其周圍８?jìng)�(gè)網(wǎng)格中的軌跡點(diǎn)進(jìn)行搜索，即粗線框中的軌跡點(diǎn)，找到軌跡點(diǎn)ｐ２，４到ｐ１，５的距離小于ｅ，由于ｐ２，４所在軌跡為Ｔ２，因此，為Ｔ２創(chuàng)建倒排表，利用Ｔ２可以找到Ｔ１．圖２網(wǎng)格索引Ｆｉｇ．２Ｇｒｉｄｉｎｄｅｘ３查詢過(guò)程本文中的方法是基于Ｒ－ｔｒｅｅ的最佳優(yōu)先ＮＮ搜索和ＧＨ算法框架提出的．候選集生成的首要任務(wù)就是檢索每個(gè)查詢點(diǎn)的最鄰近的軌跡點(diǎn)，是該階段的重要組成部分．在這項(xiàng)工作中，利用最佳優(yōu)先策略搜索最近的軌跡點(diǎn)．定義５［１９］ＭｉｎＤｉｓｔ距離ｎ維歐式空間中的軌跡點(diǎn)ｐ到該空間內(nèi)某一最小邊界矩形Ｒ（ｓ，ｔ）的最小距離定義為ＭｉｎＤｉｓｔ，用ＭｉｎＤｉｓｔ（ｐ，Ｒ（ｓ，ｔ））表示ＭｉｎＤｉｓｔ（ｐ，Ｒ）＝∑ｎｉ＝１ｐｉ－ｒｉ２，ｒｉ＝ｓｉｐｉ＜ｓｉｔｉｐｉ＞ｔｉｐｉ烅烄烆其他．（４）最佳優(yōu)先策略維持一個(gè)優(yōu)先隊(duì)列來(lái)儲(chǔ)存Ｒ－ｔｒｅｅ中所有瀏覽過(guò)的結(jié)點(diǎn)，優(yōu)先隊(duì)列使用查詢點(diǎn)到某個(gè)最小邊界矩形的ＭｉｎＤｉｓｔ距離排序，最初，隊(duì)列中只含有根結(jié)點(diǎn)，然后將根結(jié)點(diǎn)的孩子結(jié)點(diǎn)分別入隊(duì)，并刪除根結(jié)點(diǎn)，再選擇此時(shí)隊(duì)列中ＭｉｎＤｉｓｔ值最小的結(jié)點(diǎn)（

【參考文獻(xiàn)】：
碩士論文
[1]大數(shù)據(jù)下空間數(shù)據(jù)索引和kNN查詢技術(shù)的研究[D]. 董亭亭.大連理工大學(xué) 2013



本文編號(hào)：3279758