04-01-2013, 04:51 PM
Mining Group Movement Patterns for Tracking Moving Objects Efficiently
1Mining Group.pdf (Size: 3.03 MB / Downloads: 29)
Abstract
Existing object tracking applications focus on finding the moving patterns of a single object or all objects. In contrast, we
propose a distributed mining algorithm that identifies a group of objects with similar movement patterns. This information is important in
some biological research domains, such as the study of animals’ social behavior and wildlife migration. The proposed algorithm
comprises a local mining phase and a cluster ensembling phase. In the local mining phase, the algorithm finds movement patterns
based on local trajectories. Then, based on the derived patterns, we propose a new similarity measure to compute the similarity of
moving objects and identify the local group relationships. To address the energy conservation issue in resource-constrained
environments, the algorithm only transmits the local grouping results to the sink node for further ensembling. In the cluster ensembling
phase, our algorithm combines the local grouping results to derive the group relationships from a global view. We further leverage the
mining results to track moving objects efficiently. The results of experiments show that the proposed mining algorithm achieves good
grouping quality, and the mining technique helps reduce the energy consumption by reducing the amount of data to be transmitted.
INTRODUCTION
RECENT advances in location-acquisition technologies,
such as global positioning systems (GPSs) and wireless
sensor networks (WSNs), have fostered many novel
applications like object tracking, environmental monitoring,
and location-dependent service. These applications generate
large amounts of location data, and many approaches
focus on compiling the collected data to identify the
repeating movement patterns of objects of interest. The
objective is to facilitate the analysis of past movements and
estimate future movements, as well as support approximate
queries on the original data [17], [34], [38], [48], [52].
In object tracking applications, many natural phenomena
show that moving objects often exhibit some degree of
regularity in their movements. For example, the famous
annual wildebeest migration demonstrates that the movement
of creatures is temporally and spatially correlated. In
addition, biologists have found that many creatures, such as
elephants, zebra, whales, and birds, form large social groups
when migrating to find food, or for breeding, wintering.
Related Work
Movement Pattern Mining
The temporal-and-spatial correlations and the regularity in
the trajectory data sets of moving objects are often modeled
as sequential patterns for use in data mining. Agrawal and
Srikant [4] first defined the sequential pattern mining
problem and proposed an Apriori-like algorithm to mine
frequent sequential patterns. Han et al. proposed FreeSpan
[20], which is an FP-growth-based algorithm that addresses
the sequential pattern mining problem by considering the
pattern-projection method. For handling the uncertainty in
trajectories of mobile objects, Yang and Hu [52] developed a
new match measure and proposed TrajPattern to mine
sequential patterns from imprecise trajectories. Moreover, a
number of research works have been elaborated upon
mining traversal patterns for various applications. For
example, Chen et al. [13] proposed the FS and SS algorithms
for mining path traversal patterns in a Web environment
while Peng and Chen [37] proposed an incremental
algorithm to mine user moving patterns for data allocation
in a mobile computing system. However, sequential
patterns or path traversal patterns do not provide sufficient
information for location prediction or clustering. The
reasons are as follows: First, for sequential pattern mining
or path traversal pattern mining extract frequent patterns of
all objects, meaningful movement characteristics of individual
objects may be ignored. Second, a sequential pattern or
a traversal pattern carries no time information between
consecutive items, so they cannot provide accurate information
for location prediction when time is concerned.
Third, sequential patterns are not full representative to
individual trajectories because a sequential pattern does not
contain the information about the number of times it occurs
in each individual trajectory. To discover significant
patterns for location prediction, Morzy proposed Apriori-
Traj [33] and Traj-PrefixSpan [34] to mine frequent
trajectories, where consecutive items of a frequent trajectory
are also adjacent in the original trajectory data.
DESIGN OF THE DISTRIBUTED MINING ALGORITHM
In this work, we model the movement of an object by a
VMM, and use a PST to mine the significant movement
patterns. The advantages of PST include its computing and
storage efficiency as well as the information it carries. In the
tracking application, objects are tracked periodically so that
the time interval of consecutive items of a location sequence
is implied. The PST building algorithm scans the sequence
for significant movement patterns, whose items are constrained
to be consecutive in the location sequence. This is
also why the computing cost is much lower than sequence
pattern mining. Moreover, a PST provides us important
information in similarity comparison. For a pattern and a
PST, we can predict the occurrence probability of the
pattern, which is viewed as the importance of the pattern
regarding the PST.