New version page

Discovering Spatio-Temporal Causal Interactions in Traffic Data Streams

This preview shows page 1-2-3 out of 9 pages.

View Full Document
View Full Document

End of preview. Want to read all 9 pages?

Upload your study docs or become a GradeBuddy member to access this document.

View Full Document
Unformatted text preview:

Discovering Spatio-Temporal Causal Interactionsin Traffic Data StreamsWei LiuUniversity of Sydney,Sydney, [email protected] ZhengMicrosoft Research Asia,Beijing, [email protected] ChawlaUniversity of Sydney,Sydney, [email protected] YuanUniversity of Science andTechnology of [email protected] XieMicrosoft Research Asia,Beijing, [email protected] detection of outliers in spatio-temporal traffic data is animportant research problem in the data mining and knowl-edge discovery community. However to the best of our knowl-edge, the discovery of relationships, especially causal inter-actions, among detected traffic outliers has not been inves-tigated before. In this paper we propose algorithms whichconstruct outlier causality trees based on temporal and spa-tial properties of detected outliers. Frequent substructuresof these causality trees reveal not only recurring interac-tions among spatio-temporal outliers, but potential flaws inthe design of existing traffic networks. The effectiveness andstrength of our algorithms are validated by experiments ona very large volume of real taxi trajectories in an urban roadnetwork.Categories and Subject DescriptorsH.2.8 [Database Applications]: Data miningGeneral TermsAlgorithmsKeywordsSpatio-temporal outliers; outlier causalities; frequent sub-structures; urban computing and planning;1. INTRODUCTIONThe increasing availability of location-acquisition tech-nologies including GPS and WIFI have resulted in hugevolumes of spatio-temporal data, especially in the form ofPermission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on serve rs or to redistribute to lists, requires prior specificpermission and/or a fee.KDD’11, August 21–24, 2011, San Diego, California, USA.Copyright 2011 ACM 978-1-4503-0813-7/11/08 ...$10.00.trajectories [2, 5, 7, 15, 14, 19, 17]. Unusual patterns of mov-ing objects’ trajectories generally reflect abnormal trafficstreams on road networks, which could be caused by aperi-odic events including celebrations, parades, large-scale busi-ness promotions, protests, traffic control and traffic jams.Therefore, the detection of outliers/anomalies from trajec-tory data can help in sensing abnormal events and plan fortheir impact on the smooth flow of traffic. In this study,we treat both known (planned) and unknown (unplanned)events that behave differently from daily network traffics asanomalies.Challenges and ContributionsIn order to successfully detect outliers and causal interac-tions among them, the following challenges need to be ad-dressed: (i) Heterogeneous traffic patterns: the traffic pat-terns on roads vary across days of a week and hours of a day.Different road segments have often distinct time-variant traf-fic patterns. It is difficult to use one model to detect outliersacross the road network at different time periods. (ii)Datasparseness and distribution skewness: even though we couldhave a large number of sensors (taxis) probing the traffic onroads, there are many roads that have only a small numberof samples given a large size of road networks in a major city.Moreover, a few road segments are traveled by thousands ofvehicles in a few hours, while some segments may be onlydriven on a few times in a day. These two properties to-gether result in unique challenges in detecting outliers fromtraffic data. (iii) Causality among outliers: we not only needto discover outliers from the traffic, but also infer causal re-lationships and interactions among them, especially giventhe large number of outliers that could be identified. So achallenge is how to detect the appearance, growth, disap-pearance and transformation of outliers by time (e.g., prop-agation of a traffic jam).In this paper we design several steps to address the abovechallenges and propose solutions to the problem of detect-ing spatio-temporal outliers and causal relationships amongthem from traffic data streams. We use contexts of roadnetworks in this study, however, algorithms proposed in thispaper can be generally applied to domains of networking [12,1010Figure 1: An example using traffic networks in the city of Beijing. Based on major roads in the traffic network, the entire city(subfigure (a)) is partitioned into regions (subfigure (b)). Trajectories of moving objects (such as a moving taxi shown by ablue trajectory in subfigure (c)) connect neighboring regions, based on which we create the notion of links (subfigure (d)).13] and climate change [18, 23, 8] etc. More specifically, thecontributions we make in this paper are:1. City-wide traffic modeling: we partition the urban areaof a city into regions using the framework of the city’sroad network. Then we build a region graph where anode is a region and a link captures the traffic flowamong two regions. We formulate the outlier detec-tion problem as identifying the most outlying “links”from the region graph in terms of the spatio-temporalproperties of a link.2. Outlier tree construction:weproposetheSTOTree al-gorithm based on both spatial and temporal propertiesof detected outliers (which are certain “links” in a timeframe) to construct outlier trees, which uncover causalrelationships among these outliers.3. Frequent outlier subtree discovery:weproposethefre-qentSubtree algorithm, inspired by association rulemining, which generates the most frequent sub-structure(subtree) from all discovered outlier trees. These fre-quent subtrees reveal recurrent abnormalities in thedata and suggest inherent problems in existing roadnetworks.The rest of the paper is structured as follows. In Section3 we introduce the overall framework of our model, includ-ing preliminary concepts and notations that we use in thispaper. In Section 4 we propose algorithms for discoveringspatio-temporal outliers and causal relationships. Exper-iments and their analysis are reported in Section 5. Weconclude in Section 6 with directions for future work.2. RELATED WORKTo the best of our knowledge this is the first paper thatproposes the problem of discovering casual relationships amongspatio-temporal outliers. However, there have been a num-ber of efforts on detecting only


Loading Unlocking...
Login

Join to view Discovering Spatio-Temporal Causal Interactions in Traffic Data Streams and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Discovering Spatio-Temporal Causal Interactions in Traffic Data Streams and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?