n-Gram Geo-trace Modeling

As location-sensing smart phones and location-based services gain mainstream popularity, there is increased interest in developing techniques that can detect anomalous activities. Anomaly detection capabilities can be used in theft detection, remote elder-care monitoring systems, and many other applications. In this paper we present an

n

-gram based model for modeling a user’s mobility patterns. Under the Markovian assumption that a user’s location at time

t

depends only on the last

n

 − 1 locations until

t

 − 1, we can model a user’s idiosyncratic location patterns through a collection of

n

-gram geo-labels, each with estimated probabilities. We present extensive evaluations of the

n

-gram model conducted on real-world data, compare it with the previous approaches of using T-Patterns and Markovian models, and show that for anomaly detection the

n

-gram model outperforms existing work by approximately 10%. We also show that the model can use a hierarchical location partitioning system that is able to obscure a user’s exact location, to protect privacy, while still allowing applications to utilize the obscured location data for modeling anomalies effectively.