摘要： 近年來，相似性搜索已成為許多軌跡數(shù)據(jù)分析任務(wù)的重要組成部分合住。隨著軌跡數(shù)量的增加，我們必須在大量軌跡中找到類似的軌跡撒璧，需要一個(gè)可擴(kuò)展和有效的框架透葛。通常，大量的軌跡數(shù)據(jù)可以通過鍵值數(shù)據(jù)存儲(chǔ)來管理沪悲。然而获洲，現(xiàn)有的鍵值數(shù)據(jù)存儲(chǔ)的工作使用粗糙表示來存儲(chǔ)軌跡數(shù)據(jù)。此外殿如，它們不能提供有效的查詢處理來搜索相似的軌跡贡珊。為此，本文提出了一種高效的鍵值數(shù)據(jù)存儲(chǔ)軌道相似度搜索框架——TraSS涉馁。我們提出了一種新的空間索引门岔，XZ*，它利用不規(guī)則形狀和大小的細(xì)粒度索引空間來精細(xì)地表示軌跡烤送。進(jìn)一步寒随，我們設(shè)計(jì)了一個(gè)從XZ*的索引空間到連續(xù)整數(shù)的雙目標(biāo)函數(shù)，該函數(shù)簡單而有效帮坚。為了提高相似度搜索的效率妻往，我們采用兩步對不同軌跡進(jìn)行修剪:(1)全局修剪。它利用XZ*索引刪除沒有類似于查詢軌跡軌跡的索引空間试和。我們的全局剪枝只能挑選出與查詢軌跡大小和形狀相似的索引空間讯泣。與最先進(jìn)的索引相比，我們的全局剪枝在查詢處理期間減少了66.4%的I/O開銷;(2)當(dāng)?shù)氐倪^濾阅悍。它以一種低復(fù)雜度的方式過濾不同的軌跡好渠。我們利用道格拉斯-佩克算法從軌跡中提取的幾個(gè)代表性特征來加速局部濾波昨稼。我們在一個(gè)流行的鍵值數(shù)據(jù)存儲(chǔ)上實(shí)現(xiàn)了一個(gè)開源工具包(TraSS)。大量實(shí)驗(yàn)表明拳锚，TraSS的性能優(yōu)于最先進(jìn)的解決方案
面臨的問題：
1)它們以粗表示的方式存儲(chǔ)軌跡假栓，(2)缺乏搜索相似軌跡的高效查詢處理。
表示：軌跡由多維點(diǎn)組成霍掺，但鍵值數(shù)據(jù)存儲(chǔ)使用一維鍵值對存儲(chǔ)對象匾荆。因此，我們必須為軌跡分配一個(gè)適當(dāng)?shù)逆I抗楔。
查詢：計(jì)算兩個(gè)軌跡的相似度是耗時(shí)的棋凳，因?yàn)橄嗨贫鹊亩攘客喈?dāng)復(fù)雜。因此连躏，必須提前修剪盡可能多的不同軌跡剩岳，以避免在查詢處理期間產(chǎn)生不必要的I/O開銷和計(jì)算。因此入热，經(jīng)常采用兩個(gè)步驟來提高查詢效率:(1)全局刪除?可以避免訪問不相關(guān)的存儲(chǔ)區(qū)域 (2)局部濾波以低復(fù)雜度的方式快速去除每個(gè)數(shù)據(jù)區(qū)域內(nèi)的不同軌跡
方案:
1)我們提出了一種高效的基于鍵值數(shù)據(jù)存儲(chǔ)的軌跡相似度搜索框架TraSS拍棕。(Representation).我們提出XZ*索引來表示同一索引空間內(nèi)盡可能多的相似軌跡。具體來說勺良，它將xz - order的每個(gè)放大元素劃分為四個(gè)相等的子四邊形绰播，并將子四邊形的組合作為索引空間。較大的索引空間用于覆蓋較大的軌跡，而較小的索引空間用于覆蓋較小的軌跡。此外印颤，相似大小的軌跡可以通過它們的空間形狀來區(qū)分。
2）(Query processing). (Global pruning). 因?yàn)槲覀兊乃饕梢跃_地描述軌跡的大小和形狀谬泌，所以我們只訪問與查詢軌跡Q相似的幾個(gè)索引空間，避免訪問與Q不同的索引空間覆蓋的軌跡逻谦。(Local filtering).我們使用DP (Douglas-Peucker)算法從軌跡中提取代表點(diǎn)掌实。它利用很少的點(diǎn)來近似軌跡的空間形狀。
疑惑點(diǎn)：1)文中提出的(Representation)軌跡表示方法令人感到奇怪邦马，將空間劃分為更小的部分贱鼻，或者說是四叉樹的方式，用空間表示軌跡滋将。我的理解是利用最小外界矩陣（MBR）來表示要查詢的軌跡邻悬，但是文中沒有提到如何有效的切分軌跡。
? ? ? ? ?2)整個(gè)框架圖随闽，看到后很迷惑父丰。尤其在文中query部分。全局刪除部分完成后橱脸，剩下相似部分础米，但是文中是怎么實(shí)現(xiàn)全局刪除部分和representation關(guān)聯(lián)的，在圖中看不到相互之間存在的關(guān)聯(lián)性添诉。
