Mining Frequent Trajectory Patterns
Date Issued
2011
Date
2011
Author(s)
Chen, Yi-An
Abstract
In this dissertation, we propose three algorithms, GBM, FTM and LTM, for mining trajectory patterns. GBM focuses on finding frequent trajectory patterns consisting of consecutively adjacent points, where the time spent between two consecutive points in a frequent trajectory pattern is represented by a timespan. FTM mines frequent flexible trajectory patterns, where the consecutive points in a flexible pattern are not necessarily adjacent and the time spent between two consecutive points is denoted by a time interval. Although representing a trajectory pattern by a sequence of points is ideal to reduce the effect of noises and ease the mining process, these approaches may lead to generating long patterns and requiring a tremendous amount of mining time. Therefore, LTM models trajectories and patterns as consecutive line segments rather than discrete points so that the memory consumption, the lengths and number of frequent patterns can be effectively reduced.
All these three algorithms mine frequent patterns in a depth-first search (DFS) manner. GBM utilizes the adjacency property to effectively reduce the search space, while FTM employs frequent edges to prune unnecessary patterns. LTM uses two pruning strategies, CU-Bound and FU-Bound, to speed up the mining process.
Extensive experiments are conducted to evaluate the performance of GBM, FTM and LTM. The experimental results show that GBM significantly outperforms Apriori-G and PrefixSpan-G. FTM also gains considerable improvement in efficiency in comparison to Apriori-F and PrefixSpan-F. LTM effectively speeds up the mining process by using both CU-Bound and FU-Bound pruning strategies.
Subjects
Data mining
trajectory pattern
flexible trajectory pattern
line-based trajectory pattern
trajectory database
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-100-D95725004-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):935a44c027a4aea8a008063cd2e6dca2