Unveiling the complexity of human mobility by querying and mining massive trajectory data
The VLDB JournalPublished 29 July 2011
Fosca Giannotti, Mirco Nanni, Dino Pedreschi, Fabio Pinelli, Chiara Renso, Salvatore Rinzivillo
Citations282
SJR quartileQ1
SJR score1.18
SNIP2.29
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This work presents the results of a large-scale experiment, based on the detailed trajectories of tens of thousands private cars with on-board GPS receivers, tracked during weeks of ordinary mobile activity, showing the striking analytical power of massive collections of trajectory data in unveiling the complexity of human mobility.
Abstract
The technologies of mobile communications \npervade our society and wireless networks sense the movement \nof people, generating large volumes of mobility data, \nsuch as mobile phone call records and Global Positioning \nSystem (GPS) tracks. In this work, we illustrate the striking \nanalytical power of massive collections of trajectory data in \nunveiling the complexity of human mobility. We present the \nresults of a large-scale experiment, based on the detailed trajectories \nof tens of thousands private cars with on-board GPS \nreceivers, tracked during weeks of ordinary mobile activity. \nWe illustrate the knowledge discovery process that, based on \nthese data, addresses some fundamental questions of mobility \nanalysts: what are the frequent patterns of people’s travels? \nHow big attractors and extraordinary events influence mobility? \nHow to predict areas of dense traffic in the near future? \nHow to characterize traffic jams and congestions? We also \ndescribe M-Atlas, the querying and mining language and system \nthat makes this analytical process possible, providing the \nmechanisms to master the complexity of transforming raw \nGPS tracks into mobility knowledge. M-Atlas is centered \nonto the concept of a trajectory, and the mobility knowledge \ndiscovery process can be specified by M-Atlas queries that \nrealize data transformations, data-driven estimation of the \nparameters of the mining methods, the quality assessment \nof the obtained results, the quantitative and visual exploration \nof the discovered behavioral patterns and models, the composition of mined patterns, models and data with further \nanalyses and mining, and the incremental mining strategies \nto address scalability.
Keywords
Social SciencesComputer Science
A density-based algorithm for discovering clusters in large spatial Databases with Noise
19,114 Citations1996Martin Ester, Hans‐Peter Kriegel +2 more
DBSCAN, a new clustering algorithm relying on a density-based notion of clusters which is designed to discover clusters of arbitrary shape, is presented which requires only one input parameter and supports the user in determining an appropriate value for it.
NatureUnderstanding individual human mobility patterns
6,079 Citations2008Marta C. González, César A. Hidalgo +1 more
The trajectory of 100,000 anonymized mobile phone users whose position is tracked for a six-month period is studied, finding that, in contrast with the random trajectories predicted by the prevailing Lévy flight and random walk models, human trajectories show a high degree of temporal and spatial regularity.
ScienceLimits of Predictability in Human Mobility
3,190 Citations2010Chaoming Song, Zehui Qu +2 more
Analysis of the trajectories of people carrying cell phones reveals that human mobility patterns are highly predictable, and a remarkable lack of variability in predictability is found, which is largely independent of the distance users cover on a regular basis.
NatureThe scaling laws of human travel
2,247 Citations2006Dirk Brockmann, Lars Hufnagel +1 more
It is shown that human travelling behaviour can be described mathematically on many spatiotemporal scales by a two-parameter continuous-time random walk model to a surprising accuracy, and concluded that human travel on geographical scales is an ambivalent and effectively superdiffusive process.
Nature PhysicsSpontaneous atomic-scale magnetic skyrmion lattice in two dimensions
1,959 Citations2011Stefan Heinze, Kirsten von Bergmann +6 more
Mining interesting locations and travel sequences from GPS trajectories
1,915 Citations2009Yu Zheng, Lizhu Zhang +2 more
This work first model multiple individuals' location histories with a tree-based hierarchical graph (TBHG), and proposes a HITS (Hypertext Induced Topic Search)-based inference model, which regards an individual's access on a location as a directed link from the user to that location.
Trajectory clustering
1,335 Citations2007Jae-Gil Lee, Jiawei Han +1 more
A new partition-and-group framework for clustering trajectories is proposed, which partitions a trajectory into a set of line segments, and then, groups similar line segments together into a cluster, and a trajectory clustering algorithm TRACLUS is developed, which discovers common sub-trajectories from real trajectory data.
Nature PhysicsModelling the scaling properties of human mobility
1,304 Citations2010Chaoming Song, Tal Koren +2 more
Empirical data is used to show that the predictions of the CTRW models are in systematic conflict with the empirical results, and two principles that govern human trajectories are introduced, allowing for a statistically self-consistent microscopic model for individual human mobility.
Trajectory pattern mining
1,009 Citations2007Fosca Giannotti, Mirco Nanni +2 more
This paper develops an extension of the sequential pattern mining paradigm that analyzes the trajectories of moving objects and introduces trajectory patterns as concise descriptions of frequent behaviours in terms of both space and time.
ACM Transactions on Database SystemsA foundation for representing and querying moving objects
756 Citations2000Ralf Hartmut Güting, Michael H. Böhlen +5 more
The paper formally defines the types and operations, offers detailed insight into the considerations that went into the design, and exemplifies the use of the abstract data types using SQL.
Human mobility, social ties, and link prediction
674 Citations2011Dashun Wang, Dino Pedreschi +3 more
It is shown that mobility measures alone yield surprising predictive power, comparable to traditional network-based measures, and the prediction accuracy can be significantly improved by learning a supervised classifier based on combined mobility and network measures.
Mining user similarity based on location history
643 Citations2008Quannan Li, Yu Zheng +4 more
A framework, referred to as hierarchical-graph-based similarity measurement (HGSM), is proposed for geographic information systems to consistently model each individual's location history and effectively measure the similarity among users and outperforms related similarity measures, such as the cosine similarity and Pearson similarity measures.
WhereNext
546 Citations2009Anna Monreale, Fabio Pinelli +2 more
This paper proposes WhereNext, which is a method aimed at predicting with a certain level of accuracy the next location of a moving object, which uses previously extracted movement patterns named Trajectory Patterns, which are a concise representation of behaviors of moving objects as sequences of regions frequently visited with a typical travel time.
ScienceUnderstanding the Spreading Patterns of Mobile Phone Viruses
499 Citations2009Pu Wang, Marta C. González +2 more
The mobility of mobile phone users is modeled in order to study the fundamental spreading patterns that characterize a mobile virus outbreak and it is found that although Bluetooth viruses can reach all susceptible handsets with time, they spread slowly because of human mobility, offering ample opportunities to deploy antiviral software.
Never Walk Alone: Uncertainty for Anonymity in Moving Objects Databases
497 Citations2008Osman Abul, Francesco Bonchi +1 more
It is proved that the problem of achieving (k,delta) -anonymity by space translation with minimum distortion is NP-hard, and a greedy algorithm based on clustering and enhanced with ad hoc pre-processing and outlier removal techniques is proposed.
Communications of the ACMA database perspective on knowledge discovery
470 Citations1996Tomasz Imieliński, Heikki Mannila
The concept of data mining as a querying process and the first steps toward efficient development of knowledge discovery applications are discussed.
Trajectory clustering with mixtures of regression models
445 Citations1999Scott Gaffney, Padhraic Smyth
This paper addresses the problem of clustering trajectories, namely sets of short quences of data measured as a function of a dependent variable such as time, and develops generalizations of the method to handle non-parametric (kernel) regression components as well as multi-dimensional outputs.
Lecture notes in computer scienceOn Discovering Moving Clusters in Spatio-temporal Data
421 Citations2005Panos Kalnis, Nikos Mamoulis +1 more
This work provides a formal definition for moving clusters and describes three algorithms for their automatic discovery, a straight-forward method based on the definition, a more efficient method which avoids redundant checks and an approximate algorithm which trades accuracy for speed by borrowing ideas from the MPEG-2 video encoding.
Journal of Intelligent Information SystemsTime-focused clustering of trajectories of moving objects
416 Citations2006Mirco Nanni, Dino Pedreschi
This paper proposes an adaptation of a density-based clustering algorithm to trajectory data based on a simple notion of distance between trajectories, with the aim of exploiting the intrinsic semantics of the temporal dimension to improve the quality of trajectory clustering.
ACM SIGKDD Explorations NewsletterVisual analytics tools for analysis of movement data
278 Citations2007Gennady Andrienko, Natalia Andrienko +1 more
It is argued that by using the right visual analytics tools for the analysis of massive collections of movement data, it is possible to effectively support human analysts in understanding movement behaviors and mobility patterns.
Computing longest duration flocks in trajectory data
276 Citations2006Joachim Gudmundsson, Marc van Kreveld
This work considers the computational efficiency of computing two of the most basic spatio-temporal patterns in trajectories, namely flocks and meetings, and gives several exact and approximation algorithms.
TrajStore: An adaptive storage system for very large trajectory data sets
213 Citations2010Philippe Cudré-Mauroux, Eugene Wu +1 more
TrajStore is a dynamic storage system optimized for efficiently retrieving all data in a particular spatiotemporal region that maintains an optimal index on the data and dynamically co-locates and compresses spatially and temporally adjacent segments on disk.
Interactive visual clustering of large collections of trajectories
210 Citations2009Gennady Andrienko, Natalia Andrienko +4 more
This work proposes an approach to extracting meaningful clusters from large databases by combining clustering and classification, which are driven by a human analyst through an interactive visual interface.
Searching trajectories by locations
204 Citations2010Zaiben Chen, Heng Tao Shen +3 more
This work defines a new similarity function for measuring how well a trajectory connects the query locations, with both spatial distance and order constraint being considered, and examines the feasibility of using a general-purpose spatial index to achieve efficient k-BCT search, based on a simple Incremental k-NN based Algorithm (IKNN).
Computational GeometryReporting flock patterns
190 Citations2007Marc Benkert, Joachim Gudmundsson +2 more
A new definition of a flock is given that is argued to be more realistic than the previous ones, and fast approximation algorithms to report flocks are presented.
Information SystemsAnonymization of moving objects databases by clustering and perturbation
164 Citations2010Osman Abul, Francesco Bonchi +1 more
A novel concept of k-anonymity based on co-localization, that exploits the inherent uncertainty of the moving object's whereabouts is proposed, and the novel method, named W4M (WaitforMe), is empirically shown to produce higher quality anonymization than NWA, at the price of higher computational requirements.
Movement Data Anonymity through Generalization
139 Citations2010Anna Monreale, Gennady Andrienko +5 more
Mining mobility user profiles for car pooling
128 Citations2011Roberto Trasarti, Fabio Pinelli +2 more
A methodology for extracting mobility profiles of individuals from raw digital traces (in particular, GPS traces), and study criteria to match individuals based on profiles, and a matching criterion that satisfies various basic constraints obtained from the background knowledge of the application domain are introduced.
MoveMine
89 Citations2010Zhenhui Li, Ji Ming +5 more
The system, MoveMine, is designed for sophisticated moving object data mining by integrating several attractive functions including moving object pattern mining and trajectory mining and a user-friendly interface is provided to facilitate interactive exploration of mining results and flexible tuning of the underlying methods.
Lecture notes in computer scienceHermes – A Framework for Location-Based Data Management
76 Citations2006Nikos Pelekis, Yannis Theodoridis +2 more
The aim of this paper is to demonstrate Hermes, a robust framework capable of aiding a spatio-temporal database developer in modeling, constructing and querying a database with dynamic objects that change location, shape and size, either discretely or continuously in time.
Elsevier eBooksATLAS
68 Citations2003Haixun Wang, Carlo Zaniolo +1 more
This chapter implements ATLAS, a powerful database language and system that enables users to develop complete data-intensive applications in structured query language (SQL)—by writing new aggregates and table functions in SQL, rather than in procedural languages as in current Object- Relational systems.
Lecture notes in geoinformation and cartographyTowards Semantic Interpretation of Movement Behavior
56 Citations2009Miriam Baglioni, José Antônio Fernandes de Macêdo +3 more
A model for the conceptual representation and deductive reasoning of trajectory patterns obtained from mining raw trajectories by means of a semantic enrichment process that gives a possible interpretation of discovered patterns in terms of movement behaviour is provided.
The 3W Model and Algebra for Unified Data Mining
53 Citations2000Theodore Johnson, Laks V. S. Lakshmanan +1 more
A unied model supporting all major mining and analysis tasks, consisting of three distinct worlds, corresponding to intensional and extensional dimensions, and to data sets, and an algebra, called the dimension algebra, for manipulating (intensional) dimensions, as well as operators that serve as "bridges" between the worlds.
International Journal of Data Warehousing and MiningA Query Language for Mobility Data Mining
26 Citations2011Roberto Trasarti, Fosca Giannotti +3 more
This paper examines a formal framework, and the associated implementation, for a data mining query language for mobility data, created as a result of a European-wide research project called GeoPKDD Geographic Privacy-Aware Knowledge Discovery and Delivery.
Advanced knowledge discovery on movement data with the GeoPKDD system
24 Citations2010Mirco Nanni, Roberto Trasarti +3 more
This paper presents an experiment on a real world scenario that demonstrates the strong analytical power of massive, raw trajectory data made available as a by-product of telecom services, in unveiling the complexity of urban mobility.
The DAEDALUS framework
23 Citations2008Riccardo Ortale, Ettore Ritacco +7 more
The core component of DAEDALUS is the MO-DMQL query language that extends SQL in two respects, namely a pattern definition operator and the capability to uniform manipulating both raw data and unveiled patterns.