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

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

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

【部分圖文】：

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

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

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



本文編號：3279758