- 學位論文
以感域雜湊法加速軌跡查詢
Fast Trajectory Query via Locality-Sensitive Hashing
摘要
隨著可攜帶GPS設備的快速發展和普及，越來越多的軌跡資料被收集、存儲並應用於各類資料分析當中。而以獲取某條給定軌跡的相似軌跡為目的的軌跡相似性研究是軌跡分析的基礎。本論文中，我們對軌跡資料在向量場內進行建模，基於此模型，我們可以在此向量空間內度量兩條軌跡的相似程度。同時在此模型下，大多數不相似的軌跡可以通過感域雜湊法（Locality-Sensitive Hashing）過濾掉，藉此實現快速有效的軌跡查詢。我們使用Geolife資料集进行了實驗，結果表明此方法能夠在召回率接近98%的條件下，滤除接近70%不相似的軌跡。不僅如此，在進行同樣萬次軌跡查詢的條件下，我們的方法比傳統的最長公共子序列法（Longest Common Sub-Sequence）在時間效率上有百倍的提升。
並列摘要
With the increasing number of mobile GPS devices, more and more trajectory data are collected, stored, and analyzed for various applications. One of the basic operations in trajectory analysis is the similarity query, which retrieves similar trajectories of a given one. In this thesis, we model trajectory data as vector fields, by which the similarity between two trajectories can be measured in the vector space that they are transformed to. We call this algorithm of similarity measure for trajectory data Cosine Similarity for Vector Filed (CSVF). With such model, trajectory queries can be performed efficiently using Locality Sensitive Hashing (LSH) to filter out most dissimilar trajectories. Experiments which use Geolife dataset demonstrate that LSH can filter out nearly 70% candidate trajectories while maintaining the recall close to 98%. Meanwhile, experiments show that CSVF is 100 times faster than the tradition Longest Common Subsequence(LCSS) method when querying ten thousands of trajectory data.