Abstract-Mining trajectory data has been gaining significant interest in recent years. However, existing approaches to trajectory clustering are mainly based on density and Euclidean distance measures. We argue that when the utility of spatial clustering of mobile object trajectories is targeted at road network aware location based applications, density and Euclidean distance are no longer the effective measures. This is because traffic flows in a road network and the flow-based density characterization become important factors for finding interesting trajectory clusters of mobile objects travelling in road networks. In this paper, we propose NEAT−a road network aware approach for fast and effective clustering of spatial trajectories of mobile objects travelling in road networks. Our method takes into account the physical constraints of the road network, the network proximity and the traffic flows among consecutive road segments to organize trajectories into spatial clusters. The clusters discovered by NEAT are groups of sub-trajectories which describe both dense and highly continuous traffic flows of mobile objects. We perform extensive experiments with mobility traces generated using different scales of real road network maps. Our experimental results demonstrate that the NEAT approach is highly accurate and runs orders of magnitude faster than existing density-based trajectory clustering approaches. Location-based services (LBSs) and applications are a rapidly growing field due to the pervasive use of GPS receivers and WiFi or location sensing technology embedded in mobile devices (e.g. cellular phones, automobiles). With shipments of smartphones projected to grow from 295 million units in 2010 to 1.2 billion units in 2015 1 , LBS revenue is forecasted to reach an annual global total of $10.3 billion in 2015, up from $2.8 billion in 2010 2 . Ubiquitous GPS/WiFi-enabled mobile devices generate a huge amount of trajectory data, which are sequences of time-ordered locations of mobile objects. There has been a lot of work on collecting, storing, indexing and querying trajectories of mobile objects . We refer to the trajectories of mobile objects in a road network as MO trajectories. Clustering trajectories of these objects provides the most value and has a wide range of LBS applications. For example, the resulting clusters would help provide knowledge about traffic flows as well as dense areas in a road network. Such knowledge is very useful for applications in vehicular ad hoc network (VANET) [6] [7], traffic monitoring [8] , transportation planning [9] and location-based advertising [10] . We briefly present below two interesting application scenarios which show the usefulness of trajectory clustering and motivate us to study the
NEAT REF addresses this problem by introducing the flow-aware and road-network aware techniques to partition whole trajectories into sub-trajectories of interest and clusters the sub-trajectories using road-network distance and flow-based density measures.
NEAT: Road Network Aware Trajectory Clustering
2012 IEEE 32nd International Conference on Distributed Computing Systems
2012 IEEE 32nd International Conference on Distributed Computing Systems
Computer Science