Browsing by Author "Han, Jiawei"

Now showing 1 - 4 of 4

A Framework of Traveling Companion Discovery on Trajectory Data Streams
(2013-12-01)
Tang, Lu-An
;
Zheng, Yu
;
Yuan, Jing
;
Han, Jiawei
;
Leung, Alice
The advance of mobile technologies leads to huge volumes of spatio-temporal data collected in the form of trajectory data streams. In this study, we investigate the problem of discovering object groups that travel together (i.e., traveling companions) from trajectory data streams. Such technique has broad applications in the areas of scientific study, transportation management, and military surveillance. To discover traveling companions, the monitoring system should cluster the objects of each snapshot and intersect the clustering results to retrieve moving-together objects. Since both clustering and intersection steps involve high computational overhead, the key issue of companion discovery is to improve the efficiency of algorithms. We propose the models of closed companion candidates and smart intersection to accelerate data processing. A data structure termed traveling buddy is designed to facilitate scalable and flexible companion discovery from trajectory streams. The traveling buddies are microgroups of objects that are tightly bound together. By only storing the object relationships rather than their spatial coordinates, the buddies can be dynamically maintained along the trajectory stream with low cost. Based on traveling buddies, the system can discover companions without accessing the object details. In addition, we extend the proposed framework to discover companions on more complicated scenarios with spatial and temporal constraints, such as on the road network and battlefield. The proposed methods are evaluated with extensive experiments on both real and synthetic datasets. Experimental results show that our proposed buddy-based approach is an order of magnitude faster than the baselines and achieves higher accuracy in companion discovery.
Multidimensional Analysis of Atypical Events in Cyber-Physical Data
(2012)
Tang, Lu-An
;
Yu, Xiao
;
Kim, Sangkyum
;
Han, Jiawei
;
Peng, Wen-Chih
A Cyber-Physical System (CPS) integrates physical devices (e. g., sensors, cameras) with cyber components to form a situation-integrated analytical system that may respond intelligently to dynamic changes of the real-world situations. CPS claims many promising applications, such as traffic observation, battlefield surveillance and sensor-network-based monitoring. One important research topic in CPS is about the atypical event analysis, i.e., retrieving the events from a large amount of data and analyzing them with spatial, temporal and other multidimensional information. Many traditional approaches are not feasible for such analysis since they cannot describe the complex atypical events. In this study, we propose a new model of the atypical cluster to effectively represent such events and efficiently retrieve them from massive data. The micro-cluster is designed to summarize an individual event, and the macro-cluster is used to integrate the information from multiple events. To facilitate scalable, flexible and online analysis, the concept of significant cluster is defined and a guided clustering algorithm is proposed to retrieve significant clusters in an efficient manner. We conduct experiments on real datasets with the size of more than 50 GB. The results show that the proposed method can provide more accurate information with only 15% to 20% time cost of the baselines.
Multidimensional Sensor Data Analysis in Cyber-Physical System: An Atypical Cube Approach
(2012)
Tang, Lu-An
;
Yu, Xiao
;
Kim, Sangkyum
;
Han, Jiawei
;
Peng, Wen-Chih
Cyber-Physical System (CPS) is an integration of distributed sensor networks with computational devices. CPS claims many promising applications, such as traffic observation, battlefield surveillance, and sensor-network-based monitoring. One important topic in CPS research is about the atypical event analysis, that is, retrieving the events from massive sensor data and analyzing them with spatial, temporal, and other multidimensional information. Many traditional methods are not feasible for such analysis since they cannot describe the complex atypical events. In this paper, we propose a novel model of atypical cluster to effectively represent such events and efficiently retrieve them from massive data. The basic cluster is designed to summarize an individual event, and the macrocluster is used to integrate the information from multiple events. To facilitate scalable, flexible, and online analysis, the atypical cube is constructed, and a guided clustering algorithm is proposed to retrieve significant clusters in an efficient manner. We conduct experiments on real sensor datasets with the size of more than 50 GB; the results show that the proposed method can provide more accurate information with only 15% to 20% time cost of the baselines.
On Discovery of Traveling Companions from Streaming Trajectories
(2012)
Tang, Lu-An
;
Zheng, Yu
;
Yuan, Jing
;
Han, Jiawei
;
Leung, Alice
The advance of object tracking technologies leads to huge volumes of spatio-temporal data collected in the form of trajectory data stream. In this study, we investigate the problem of discovering object groups that travel together (i.e., traveling companions) from streaming trajectories. Such technique has broad applications in the areas of scientific study, transportation management and military surveillance. To discover traveling companions, the monitoring system should cluster the objects of each snapshot and intersect the clustering results to retrieve moving-together objects. Since both clustering and intersection steps involve high computational overhead, the key issue of companion discovery is to improve the efficiency of algorithms. We propose the models of closed companion candidates and smart intersection to accelerate data processing. A data structure termed traveling buddy is designed to facilitate scalable and flexible companion discovery from streaming trajectories. The traveling buddies are micro-groups of objects that are tightly bound together. By only storing the object relationships rather than their spatial coordinates, the buddies can be dynamically maintained along trajectory stream with low cost. Based on traveling buddies, the system can discover companions without accessing the object details. The proposed methods are evaluated with extensive experiments on both real and synthetic datasets. The buddy-based method is an order of magnitude faster than baselines. It also achieves higher precision and recall in companion discovery.