移動模式為基礎之軌跡搜尋機制設計與實作

Abstract

近年來，GPS 裝置常被使用在日常生活中。人們可以紀錄他們的行走軌跡並分享到網際網路上。由於這種資料量不斷上升，因而衍生一些問題。然而，從軌跡資料庫中尋找有意義的軌跡是很重要的。在軌跡搜尋中，使用者可以從資料庫中找尋一個區域中有哪些軌跡經過這個區域，或者是查詢相似程度高的軌跡。在本篇論文中，我們想要將資料庫內的軌跡做分數排序，並在給定一個查詢範圍時，找出前幾個有意義的軌跡。我們將引進一個架構，以移動模式為基礎，來做軌跡搜 尋。在這個架構下，我們提出一個 PageRank-Like 的方式來尋找資料庫中軌跡的隱藏樣式，並提出一個加速機制來加速在大容量資料庫下之軌跡搜尋。我們從台灣一些軌跡分享網站上獲得軌跡來驗證我們的方法。實驗結果有說明我們提出的方法的正確性及效率。

In recent years, GPS-equipped devices are widely used in daily life. People can record their trajectories and share them on the Internet. As such data increases dramatically, several issues on trajectories have arisen. However, exploring meaningful trajectories from a trajectory database is important. In the traditional trajectory search, users can query a range to derive all trajectories in a trajectory database passing the region, or query a trajectory to derive trajectories in a trajectories database with higher similar- ities. In this paper, we intent to rank trajectories in a trajectory database and search top-k meaningful trajectories from the database with a given query range. We introduce a framework of pattern-aware trajectory search. In this framework, we propose a PageRank-like approach to discover implicit patterns from a trajectory database, and a pruning approach to improve the e?ciency for searching pattern-aware trajectories from a large database. We collect shared trajectories in Taiwan from several travel websites to evaluate the performance of our proposed approaches. Experimental results show ?effectiveness and e?ciency of our proposed approaches.