Browsing by Author "Hung, Chih-Chieh"

Now showing 1 - 9 of 9

A regression-based approach for mining user movement patterns from random sample data
(2011-01-01)
Hung, Chih-Chieh
;
Peng, Wen-Chih
;
資訊工程學系
;
Department of Computer Science
Mobile computing systems usually express a user movement trajectory as a sequence of areas that capture the user movement trace. Given a set of user movement trajectories, user movement patterns refer to the sequences of areas through which a user frequently travels. In an attempt to obtain user movement patterns for mobile applications, prior studies explore the problem of mining user movement patterns from the movement logs of mobile users. These movement logs generate a data record whenever a mobile user crosses base station coverage areas. However, this type of movement log does not exist in the system and thus generates extra overheads. By exploiting an existing log, namely, call detail records, this article proposes a Regression-based approach for mining User Movement Patterns (abbreviated as RUMP). This approach views call detail records as random sample trajectory data, and thus, user movement patterns are represented as movement functions in this article. We propose algorithm LS (standing for Large Sequence) to extract the call detail records that capture frequent user movement behaviors. By exploring the spatio-temporal locality of continuous movements (i.e., a mobile user is likely to be in nearby areas if the time interval between consecutive calls is small), we develop algorithm TC (standing for Time Clustering) to cluster call detail records. Then, by utilizing regression analysis, we develop algorithm MF (standing for Movement Function) to derive movement functions. Experimental studies involving both synthetic and real datasets show that RUMP is able to derive user movement functions close to the frequent movement behaviors of mobile users. (C) 2010 Elsevier B.V. All rights reserved.
A storage management for mining object moving patterns in object tracking sensor networks
(2006)
Hung, Chih-Chieh
;
Peng, Wen-Chih
;
資訊工程學系
;
Department of Computer Science
One promising application of sensor networks is object tracking. Because the movements of the tracked objects usually show repeating patterns, we propose a heterogeneous tracking model, referred to as HTM, to efficiently mine object moving patterns and track objects. To ensure the quality of moving patterns, we develop a storage management to facilitate mining object moving patterns. Specifically, we explore load-balance feature to store more moving data for mining moving patterns. Once a storage of a cluster head is occupied by moving data, we devise a replacement strategy to replace the less informative patterns. Simulation results show that HTM with storage management is able not only to increase the accuracy of predition but also to save more energy in tracking objects.
A Velocity-Preserving Trajectory Simplification Approach
(2016-01-01)
Lin, Chih-Yu
;
Hung, Chih-Chieh
;
Lei, Po-Ruey
;
交大名義發表
;
National Chiao Tung University
By the rise of mobile devices, trajectory data could be easily collected and used in several applications, like destination prediction, public transportation optimization, and travel route recommendation. However, due to the spatio-temporal nature, raw trajectory data usually contain redundant movement information. This observation motivates the trajectory simplification approaches which discard some points with preserving some specific features, such as position features, direction features, and so on. Most of existing simplifications ignore the importance of velocity features. This paper proposes an adaptive trajectory approaches while taking the velocity feature into account. Specifically, the Adaptive Trajectory Simplification (ATS) algorithm is proposed, which not only preserves the position feature, but the velocity feature from the given trajectories. ATS algorithm groups the velocity values into several intervals, which are used to partition trajectories into velocity-preserving segments. The simplified trajectory could be derived by applying the position-preserving simplification approach on each segment, where the threshold in a position-preserving approach could be determined without manual setting. Extensive experiments are conducted by using a real trajectory dataset in Porto. The experimental results show ATS algorithm could simplify trajectories effectively while preserving the velocity feature and the position feature at the same time.
Clustering and aggregating clues of trajectories for mining trajectory patterns and routes
(2015-04-01)
Hung, Chih-Chieh
;
Peng, Wen-Chih
;
Lee, Wang-Chien
;
交大名義發表
;
National Chiao Tung University
In this paper, we propose a new trajectory pattern mining framework, namely Clustering and Aggregating Clues of Trajectories (CACT), for discovering trajectory routes that represent the frequent movement behaviors of a user. In addition to spatial and temporal biases, we observe that trajectories contain silent durations, i.e., the time durations when no data points are available to describe the movements of users, which bring many challenging issues to trajectory pattern mining. We claim that a movement behavior would leave some clues in its various sampled/observed trajectories. These clues may be extracted from spatially and temporally co-located data points from the observed trajectories. Based on this observation, we propose clue-aware trajectory similarity to measure the clues between two trajectories. Accordingly, we further propose the clue-aware trajectory clustering algorithm to cluster similar trajectories into groups to capture the movement behaviors of the user. Finally, we devise the clue-aware trajectory aggregation algorithm to aggregate trajectories in the same group to derive the corresponding trajectory pattern and route. We validate our ideas and evaluate the proposed CACT framework by experiments using both synthetic and real datasets. The experimental results show that CACT is more effective in discovering trajectory patterns than the state-of-the-art techniques for mining trajectory patterns.
Energy-Aware Set-Covering Approaches for Approximate Data Collection in Wireless Sensor Networks
(2012-11-01)
Hung, Chih-Chieh
;
Peng, Wen-Chih
;
Lee, Wang-Chien
;
資訊工程學系
;
Department of Computer Science
To conserve energy, sensor nodes with similar readings can be grouped such that readings from only the representative nodes within the groups need to be reported. However, efficiently identifying sensor groups and their representative nodes is a very challenging task. In this paper, we propose a centralized algorithm to determine a set of representative nodes with high energy levels and wide data coverage ranges. Here, the data coverage range of a sensor node is considered to be the set of sensor nodes that have reading behaviors very close to the particular sensor node. To further reduce the extra cost incurred in messages for selection of representative nodes, a distributed algorithm is developed. Furthermore, maintenance mechanisms are proposed to dynamically select alternative representative nodes when the original representative nodes run low on energy, or cannot capture spatial correlation within their respective data coverage ranges. Using experimental studies on both synthesis and real data sets, our proposed algorithms are shown to effectively and efficiently provide approximate data collection while prolonging the network lifetime.
Exploring Sequential Probability Tree for Movement-Based Community Discovery
(2014-11-01)
Zhu, Wen-Yuan
;
Peng, Wen-Chih
;
Hung, Chih-Chieh
;
Lei, Po-Ruey
;
Chen, Ling-Jyh
In this paper, we tackle the problem of discovering movement-based communities of users, where users in the same community have similar movement behaviors. Note that the identification of movement-based communities is beneficial to location-based services and trajectory recommendation services. Specifically, we propose a framework to mine movement-based communities which consists of three phases: 1) constructing trajectory profiles of users, 2) deriving similarity between trajectory profiles, and 3) discovering movement-based communities. In the first phase, we design a data structure, called the Sequential Probability tree (SP-tree), as a user trajectory profile. SP-trees not only derive sequential patterns, but also indicate transition probabilities of movements. Moreover, we propose two algorithms: BF (standing for breadth-first) and DF (standing for depth-first) to construct SP-tree structures as user profiles. To measure the similarity values among users\' trajectory profiles, we further develop a similarity function that takes SP-tree information into account. In light of the similarity values derived, we formulate an objective function to evaluate the quality of communities. According to the objective function derived, we propose a greedy algorithm Geo-Cluster to effectively derive communities. To evaluate our proposed algorithms, we have conducted comprehensive experiments on two real data sets. The experimental results show that our proposed framework can effectively discover movement-based user communities.
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.
Optimizing in-network aggregate queries in wireless sensor networks for energy saving
(2011-07-01)
Hung, Chih-Chieh
;
Peng, Wen-Chih
;
資訊工程學系
;
Department of Computer Science
This study proposes a method of in-network aggregate query processing to reduce the number of messages incurred in a wireless sensor network. When aggregate queries are issued to the resource-constrained wireless sensor network, it is important to efficiently perform these queries. Given a set of multiple aggregate queries, the proposed approach shares intermediate results among queries to reduce the number of messages. When the sink receives multiple queries, it should be propagated these queries to a wireless sensor network via existing routing protocols. The sink could obtain the corresponding topology of queries and views each query as a query tree. With a set of query trees collected at the sink, it is necessary to determine a set of backbones that share intermediate results with other query trees (called non-backbones). First, it is necessary to formulate the objective cost function for backbones and non-backbones. Using this objective cost function, it is possible to derive a reduction graph that reveals possible cases of sharing intermediate results among query trees. Using the reduction graph, this study first proposes a heuristic algorithm BM (standing for Backbone Mapping). This study also develops algorithm OOB (standing for Obtaining Optimal Backbones) that exploits a branch-and-bound strategy to obtain the optimal solution efficiently. This study tests the performance of these algorithms on both synthesis and real datasets. Experimental results show that by sharing the intermediate results, the BM and OOB algorithms significantly reduce the total number of messages incurred by multiple aggregate queries, thereby extending the lifetime of sensor networks. (C) 2011 Elsevier B.V. All rights reserved.
PTGF: Public Transport General Framework for Identifying Transport Modes Based on Cellular Data
(2019-01-01)
Gou, Xiaochuan
;
Hung, Chih-Chieh
;
Li, Guanyao
;
Peng, Wen-Chih
;
交大名義發表
Public transportation is beating heart of a city. Understanding how citizens utilize public transportation can be used to optimize many applications such as traffic planning, crowd flow prediction and location-based marketing. However, obtaining how citizens used transportation is not a trivial task. It is almost not possible to ask citizens to report their exact location and their transportation mode; moreover, there are usually various public transportation that move along the similar paths. These increase challenges to identify people's transport modes. To address these issues, this paper proposes Public Transport General Framework (PTGF) to identify people's transport modes by their cellular data in both offline and online manners. Regarding the offline phase, given historical cellular data of people and urban transportation networks, PTGF derives cellular data into trajectories, to match each trajectory to public transportation networks to find the most possible transport modes for sub-trajectories of a trajectory. In the online phase, given streaming trajectories, PTGF identifies the transport modes of each location by a LSTM which are trained by historical trajectories with transport modes annotated in the offline phase. Extensive experiments are conducted by using both synthetic and real datasets. The experimental results show that the accuracy of PTGF in offline phase around 80% and that in online phase F1-score around 0.7, which could prove that the effectiveness of the proposed framework PTGF.