軌跡數(shù)據(jù)相似性查詢及其應(yīng)用研究.pdf

1、軌跡數(shù)據(jù)在日常生活、商業(yè)應(yīng)用與科學(xué)研究等方面起著日益重要的作用。隨著無線通信與移動(dòng)計(jì)算技術(shù)的快速發(fā)展，我們所能獲取到的軌跡數(shù)據(jù)規(guī)模也變得前所未有的龐大。如此大量的軌跡數(shù)據(jù)既帶來了巨大的研究價(jià)值，也對(duì)數(shù)據(jù)管理、計(jì)算與挖掘提出了嚴(yán)峻的挑戰(zhàn)。受限于存儲(chǔ)與計(jì)算能力，一方面需要研究如何在確保數(shù)據(jù)質(zhì)量的前提下對(duì)軌跡數(shù)據(jù)進(jìn)行壓縮，另一方面需要研究如何高效地完成一些基礎(chǔ)操作，例如軌跡的相似性查詢。本文以軌跡數(shù)據(jù)相似性查詢?yōu)檠芯恐攸c(diǎn)，針對(duì)現(xiàn)有研究成果的不

2、足，提出了相應(yīng)的軌跡壓縮算法與高效的軌跡相似性查詢算法。在此基礎(chǔ)上，本文還探索了軌跡數(shù)據(jù)的應(yīng)用，設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)基于磁場(chǎng)傳感器的細(xì)粒度字符輸入系統(tǒng)。具體而言，本文開展了以下研究:
　　1.基于重要軌跡段的軌跡相似性查詢研究。
　　現(xiàn)有的軌跡壓縮算法只是孤立地壓縮單條軌跡，而且壓縮之后的軌跡與原始軌跡相比，丟失了細(xì)節(jié)的語義信息。為此，本文提出了一種新的軌跡壓縮算法，通過將軌跡分段，并計(jì)算每一段的權(quán)重，可以將權(quán)重較高的軌跡段提取

3、出來，組成壓縮軌跡。本算法可以將軌跡中重要部分的細(xì)節(jié)全部保留下來，使得壓縮軌跡的語義更完整。實(shí)驗(yàn)結(jié)果表明本算法可以在確保軌跡數(shù)據(jù)可用性的前提下，達(dá)到較好的壓縮率。
　　2.基于軌跡段旋轉(zhuǎn)的軌跡相似性查詢研究。
　　作為使用最廣泛的軌跡距離度量函數(shù)，動(dòng)態(tài)時(shí)間彎曲(Dynamic TimeWarping，DTW)具有能處理軌跡中的局部時(shí)間偏移、查詢準(zhǔn)確度高的優(yōu)點(diǎn)，但是其計(jì)算開銷也較大。在實(shí)際應(yīng)用中，通常先根據(jù)DTW的下限距離排除

4、不可能出現(xiàn)在結(jié)果集合中的候選軌跡，從而提高查詢效率?，F(xiàn)有的DTW下限計(jì)算方法并沒有考慮多維軌跡的特性，因此本文設(shè)計(jì)了一種新的DTW下限計(jì)算方法，可以有效提高多維軌跡數(shù)據(jù)上的相似性查詢效率，并通過實(shí)驗(yàn)驗(yàn)證了該方法的有效性。
　　3.基于磁場(chǎng)傳感器的字符輸入系統(tǒng)。
　　作為對(duì)軌跡數(shù)據(jù)應(yīng)用的探索，本文設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)基于磁場(chǎng)傳感器的字符輸入系統(tǒng)，可以用于任何配備了磁場(chǎng)傳感器的智能設(shè)備。該系統(tǒng)首先通過一個(gè)軌跡變換算法，消除用戶的不同