Browsing by Author "Wei, Ling-Yin"

Now showing 1 - 9 of 9

An incremental algorithm for clustering spatial data streams: exploring temporal locality
(2013-11-01)
Wei, Ling-Yin
;
Peng, Wen-Chih
;
資訊工程學系
;
Department of Computer Science
Clustering sensor data discovers useful information hidden in sensor networks. In sensor networks, a sensor has two types of attributes: a geographic attribute (i.e, its spatial location) and non-geographic attributes (e.g., sensed readings). Sensor data are periodically collected and viewed as spatial data streams, where a spatial data stream consists of a sequence of data points exhibiting attributes in both the geographic and non-geographic domains. Previous studies have developed a dual clustering problem for spatial data by considering similarity-connected relationships in both geographic and non-geographic domains. However, the clustering processes in stream environments are time-sensitive because of frequently updated sensor data. For sensor data, the readings from one sensor are similar for a period, and the readings refer to temporal locality features. Using the temporal locality features of the sensor data, this study proposes an incremental clustering (IC) algorithm to discover clusters efficiently. The IC algorithm comprises two phases: cluster prediction and cluster refinement. The first phase estimates the probability of two sensors belonging to a cluster from the previous clustering results. According to the estimation, a coarse clustering result is derived. The cluster refinement phase then refines the coarse result. This study evaluates the performance of the IC algorithm using synthetic and real datasets. Experimental results show that the IC algorithm outperforms exiting approaches confirming the scalability of the IC algorithm. In addition, the effect of temporal locality features on the IC algorithm is analyzed and thoroughly examined in the experiments.
Clustering Data Streams in Optimization and Geography Domains
(2009)
Wei, Ling-Yin
;
Peng, Wen-Chih
;
資訊工程學系
;
Department of Computer Science
In this paper, we formulate a dual clustering problem ill spatial data streams. A spatial data stream consists of data, points with attributes in the optimization and geography domains. We aim at partitioning these objects into disjoint clusters such that at each time window (1) objects in the same cluster satisfy the transitively r-connected relation in the optimization and geography domains, and (2) the number of clusters is as minimal as possible. We propose a Hierarchical-Based Clustering algorithm (HBC). Specifically, objects are represented as a graph structure, called RGraph, where each node represents an object and edges indicate their similarity relationships. In light of RGraph, algorithm HBC interatively merges clusters. Experimental results show the performance of the algorithm.
Discovering pattern-aware routes from trajectories
(2015-06-01)
Wei, Ling-Yin
;
Chang, Kai-Ping
;
Peng, Wen-Chih
;
交大名義發表
;
National Chiao Tung University
With the prevalence of GPS-equipped devices and navigation services, users can record and share their driving movements via trajectories. These trajectories reveal users\' driving behaviors for planning routes. In this paper, we propose a novel pattern-aware route discovery framework that considers users\' preferred routes. The proposed framework is comprised of two components: pattern-aware road map generation and route planning. In the first component, we mine significant road segments from historical trajectories, and generate a pattern-aware road map. We design a route score function that strikes a balance between user preference degrees and the length of the route. For the second component, given a source, a destination, and a user pre-defined value k, we intend to derive the top-k routes that consist of road segments from the source to the destination in the pattern-aware road map. To support on-line route planning in most navigation services, we propose a constrained breadth-first-search (CBFS) algorithm. We evaluate the performance of our framework using real trajectory data, and compare our framework with an existing approach in terms of effectiveness and efficiency. The experimental results demonstrate the effectiveness and efficiency of our proposed framework.
Exploring GPS Data for Traffic Status Estimation
(2009)
Chang, Yu-Ming
;
Wei, Ling-Yin
;
Lin, Chun-Shuo
;
Jung, Chen-Hen
;
Chen, I-Hung
Traffic status plays an important role in navigation systems. To estimate traffic status, expensive sensors are deployed, which is not cost efficient. In view of the growth of GPS navigation services, in this paper, we propose two algorithms to estimate traffic status of road segments in our CarWeb platform. To evaluate our proposed algorithms, we implement the proposed algorithms in our CarWeb platform that is used to collect GPS data points from cars. Extensive experiments are conducted on real datasets and experimental results indicate that our algorithms can provide desirable predictions of traffic status.
Exploring Pattern-Aware Travel Routes for Trajectory Search
(2013-06-01)
Wei, Ling-Yin
;
Peng, Wen-Chih
;
Lee, Wang-Chien
;
資訊工程學系
;
Department of Computer Science
With the popularity of positioning devices, Web 2.0 technology, and trip sharing services, many users are willing to log and share their trips on the Web. Thus, trip planning Web sites are able to provide some new services by inferring Regions-Of-Interest (ROIs) and recommending popular travel routes from trip trajectories. We argue that simply providing some travel routes consisting of popular ROIs to users is not sufficient. To tour around a wide geographical area, for example, a city, some users may prefer a trip to visit as many ROIs as possible, while others may like to stop by only a few ROIs for an in-depth visit. We refer to a trip fitting the former user group as an in-breadth trip and a trip suitable for the latter user group as an in-depth trip. Prior studies on trip planning have focused on mining ROIs and travel routes without considering these different preferences. In this article, given a spatial range and a user preference of depth/breadth specified by a user, we develop a Pattern-Aware Trajectory Search (PATS) framework to retrieve the top K trajectories passing through popular ROIs. PATS is novel because the returned travel trajectories, discovered from travel patterns hidden in trip trajectories, may represent the most valuable travel experiences of other travelers fitting the user's trip preference in terms of depth or breadth. The PATS framework comprises two components: travel behavior exploration and trajectory search. The travel behavior exploration component determines a set of ROIs along with their attractive scores by considering not only the popularity of the ROIs but also the travel sequential relationships among the ROIs. To capture the travel sequential relationships among ROIs and to derive their attractive scores, a user movement graph is constructed. For the trajectory search component of PATS, we formulate two trajectory score functions, the depth-trip score function and the breadth-trip score function, by taking into account the number of ROIs in a trajectory and their attractive scores. Accordingly, we propose an algorithm, namely, Bounded Trajectory Search (BTS), to efficiently retrieve the top K trajectories based on the two trajectory scores. The PATS framework is evaluated by experiments and user studies using a real dataset. The experimental results demonstrate the effectiveness and the efficiency of the proposed PATS framework.
Exploring Spatio-Temporal Features for Traffic Estimation on Road Networks
(2009)
Wei, Ling-Yin
;
Peng, Wen-Chih
;
Lin, Chun-Shuo
;
Jung, Chen-Hen
;
資訊工程學系
In this paper, given a query that indicates a query road segment and a query tune, we intend to accurately estimate the traffic status (i.e., the driving speed) on the query road segment at the query time from traffic databases. Note that a traffic behavior in the same tune usually reflects similar patterns (referring to the temporal feature); and nearby road segments have the similar traffic behaviors (referring to the spatial feature). By exploring the temporal and spatial features, more GPS data points are retrieved. In light of these GPS data retrieved, we exploit the weighted moving average approach to estimate traffic status on road networks. Experimental results show the effectiveness of our proposed algorithm.
Indexing spatial data in cloud data managements
(2014-12-01)
Wei, Ling-Yin
;
Hsu, Ya-Ting
;
Peng, Wen-Chih
;
Lee, Wang-Chien
;
資訊工程學系
With the proliferation of smart phones and location-based services, the amount of data with spatial information, referred to as spatial data, is dramatically increasing. Cloud computing plays an important role handling large-scale data analysis, and several cloud data managements (CDMs) have been developed for processing data. CDMs usually provide key-value storage, where each key is used to access its corresponding value. However, user-generated spatial data are usually distributed non-uniformly. In this paper, we present a novel key design based on an R+-tree (KR+-index) for retrieving skewed spatial data efficiently. In the experiments, we implement the KR+-index on Cassandra, and study its performance using spatial data. Experiments show that the KR+-index outperforms the-state-of-the-art methods. (C) 2013 Elsevier B.V. All rights reserved.
Mining temporal co-orientation pattern from spatio-temporal databases
(2007)
Wei, Ling-Yin
;
Shan, Man-Kwan
;
資訊工程學系
;
Department of Computer Science
A spatial co-orientation pattern refers to objects that frequently occur with the same spatial orientation, e.g. left, right, below, etc., among images. In this paper, we introduce temporal co-orientation pattern mining which is the problem of temporal aspects of spatial co-orientation patterns. A temporal co-orientation pattern represents how spatial co-orientation patterns change over time. Temporal co-orientation pattern mining is useful for discovering tactics from play sequences of sports video data, because the most tactic patterns of basketball competition are constituted of such spatial co-orientation patterns in time order. We propose the three-stage approach, which transforms the problem into sequential pattern mining, for mining temporal co-orientation patterns. We experimentally evaluate the performance of the proposed algorithm and analysis the effect of these stages.
Skyline Travel Routes: Exploring Skyline for Trip Planning
(2014-01-01)
Hsu, Wan-Ting
;
Wen, Yu-Ting
;
Wei, Ling-Yin
;
Peng, Wen-Chih
;
資訊工程學系
In this paper, given a spatial range Q and a set of query points specified by users, the goal of this paper is to return the travel routes that fulfill two requirements: 1.) travel routes should contain all those query points specified, and 2.) travel routes should be within the spatial range Q. Furthermore, we claim that each query point may have its proper visiting time. As such, the travel routes should go through these query points at their corresponding proper visiting time. To avoid some redundant information in the travel routes, we utilize the skyline concept to retrieve travel routes with more diversity. Specifically, in our paper, we consider some factors, such as the visiting time information of POIs and the set of query points, in retrieving travel routes. These factors could be mapped into dimensional spaces. Then, each travel route is viewed as a data point in the dimensional space. Thus, skyline data points (referred to as skyline travel routes) are returned as the query result. Skyline travel routes could provide more diversity in the query result of trip route recommendations. To evaluate our proposed methods, we conducted extensive experiments on real datasets. The experimental results show that skyline travel routes indeed provide more diversity in the query result. In addition, we evaluate the efficiency of retrieving skyline travel routes.