News

• Dr. Zheng is organizing the 2nd international conference on Urban Computing (UrbComp 2013). New!
• Dr. Zheng gave an keynote speech at the World Geospatial Developers Conferences (WGDC 2013).
• 2012.11.29. Dr. Yu Zheng gave an invited lecture on urban computing in Beijing urban planning institute. (Slides)
• 2012.9.17. Dr. Yu Zheng gave an invited lecture on "Urban Computing with City Dynamics" in Cornell University. (Slides)
• 2012.9.11. Dr. Yu Zheng gave an invited lecture on "Urban Computing with City Dynamics" in Carnegie Mellon University (CMU). (Slides)  
• 2012.4.10: Dr. Yu Zheng gave an invited talk about Urban Computing in MIT Media Lab. (see more)

____________________________________________________________________

Concept

With the rapid progress of urbanization and civilization on earth, urban computing is emerging as a concept where every sensor, device, person, vehicle, building, and street in the urban areas can be used as a component to probe city dynamics to further enable city-wide computing for serving people and their cities. Urban computing aims to enhance both human life and urban environment smartly through a recurrent process of sensing, mining, understanding, and improving. Urban computing also aims to deeply understand the nature and sciences behind the phenomenon occurring in urban spaces, using a variety of heterogeneous data sources, such as traffic flows, human mobility, geographic and map data, environment, energy consumption, populations, and economics, etc.

Recently, real-world data reflecting city dynamics becomes widely available, including, e.g., users’ mobile phone signal, GPS traces of vehicles and people, ticketing data in public transportation systems, user-generated content (like tweets, micro-blog, check-ins, photos), data from transportation sensor networks (camera and loop sensors) and environment sensor networks (temperature and air quality), as well as data from the Internet of Things. As a result, we are ready to carry out real urban computing activities that lead to better and smarter cities. By better sensing and understanding the city dynamics we are more likely to design effective strategies and intelligent systems for improving urban lives.

Urban computing is a research project in Microsoft Research Asia, led by a lead researcher Dr. Yu Zheng since March 2009. By analyzing and mining the city dynamics, a series of urban computing applications have been enabled as follows.

 __________________________________________________________________

Representative Research

1. Discovery regions of different functions 2. Large-Scale dynamice taxi ridesharing 3. Finding smart driving directions for end users  4. Glean the flawed urban planning in a city  5. A passenger-cabbie recommender system  6. Detecting anomalous events in a city 7. Constructing popular routes from check-ins

Discovering Region of Different Functions in a City Using Human Mobility and POIs

Goal: We propose a framework (titled DRoF) that Discovers Regions of different Functions, such as educational areas and business districts, in a city using both human mobility among regions and points of interests (POIs) located in a region. The results generated by our framework can benefit a variety of applications, including urban planning, location choosing for a business, and social recommendations.

Insight: We segment a city into disjointed regions according to major roads, such as highways and urban express ways. We infer the functions of each region using a topic-based inference model, which regards a region as a document, a function as a topic, categories of POIs (e.g., restaurants and shopping malls) as metadata (like authors, affiliations, and key words), and human mobility patterns (when people reach/leave a region and where people come from and leave for) as words. As a result, a region is represented by a distribution of functions, and a function is featured by a distribution of mobility patterns.

Publications:

[1] Jing Yuan, Yu Zheng, Xing Xie. Discovering regions of different functions in a city using human mobility and POIs. 18th SIGKDD conference on Knowledge Discovery and Data Mining (KDD 2012). 

_________________________________________________________________

Large-Scale Dynamic Taxi Ridesharing Service

Abstract: We present a large-scale taxi ridesharing service, which efficiently serves real-time requests sent by taxi users and generates ridesharing schedules that reduce the total travel distance significantly. We first propose a taxi searching algorithm using a spatio-temporal index to quickly retrieve candidate taxies that could satisfy a user query. A schedule allocation algorithm is then proposed to check each candidate taxi so as to insert the user’s trip into the schedule of the taxi. Our service can serve 40% additional taxi users while saving 15% travel distance over no ridesharing on average.

Publications:

[1] Shuo Ma, Yu Zheng, Ouri Wolfson. T-Share: A Large-Scale Dynamic Taxi Ridesharing Service. IEEE International Conference on Data Engineering (ICDE 2013)  Best Paper Runner-up Award.

_________________________________________________________________

Constructing Popular Routes from User Check-in Data

Abstract: We present a Route Inference framework based on Collective Knowledge (RICK) to construct the popular routes from uncertain trajectories, e.g., a user's check-in sequence in FourSquare, geo-tagged photos in Flickr, or the migratory trails of a bird. Explicitly, given a location sequence and a time span, the RICK is able to construct the top-k routes which sequentially pass through the locations within the specified time span, by aggregating such uncertain trajectories in a mutual reinforcement way (i.e., uncertain + uncertain → certain). Our work can benefit trip planning, traffic management, and animal movement studies.

Publications:

[1] Ling-Yin Wei, Yu Zheng, Wen-Chih Peng, Constructing Popular Routes from Uncertain Trajectories. 18th SIGKDD conference on Knowledge Discovery and Data Mining (KDD 2012).

[2] Hechen Liu, Ling-Yin We, Yu Zheng, Markus Schneider, Wen-Chih Peng. Route Discovery from Mining Uncertain Trajectories. Demo Paper, in IEEE International Conference on Data Mining (ICDM 2011).

_________________________________________________________________

Smart Driving Directions Based on Taxi Trajectories

Goal: In this research, we aim to mine the time-dependent and practically quickest driving route for end users using GPS-equipped taxicabs traveling in a city.

Insight: The time that a driver traverses a route depends on three aspects: 1) The physical feature of a route, such as distance, the number of traffic lights and direction turns; 2) The time-dependent traffic flow on the route; 3) A user’s drive behavior. Thus, a good routing service should consider these three aspects (routes, traffic and drivers), which are far beyond the scope of the shortest path computing.

GPS-equipped taxis can be regarded as mobile sensors probing traffic flows on road surfaces, and taxi drivers are usually experienced in finding the fastest (quickest) route to a destination based on their knowledge. Consequently, the trajectories of taxicabs already have the knowledge of experienced drivers, physical routes and traffic conditions.

Publications

[1] Jing Yuan, Yu Zheng, et al. T-Drive: Driving Directions Based on Taxi Trajectories. In ACM SIGSPATIAL GIS 2010, The Best Paper Runner-Up Award.

[2] Jing Yuan, Yu Zheng, et al, T-Drive: Enhancing Driving Directions with Taxi Drivers' Intelligence. Transactions on Knowledge and Data Engineering (TKDE).

Media Reports

[1] Adding cabbie know-how to online maps, MIT Technology Review, 2010.11.6

[2] Follow that cab! Racing Google Maps on city streets, NewScientist, 2010.11.5

Further Research: Later, we expanded this research by considering the drive behavior and traffic prediction as well as other factors affecting driving, such as weather conditions. Specifically, we proposed a model incorporating day of the week, time of day, weather conditions, and individual driving strategies (both of the taxi drivers and of the end user for whom the route is being computed). Using this model, our system predicts the traffic conditions of a future time (when the computed route is actually driven) and performs a self-adaptive driving direction service for a particular user. This service gradually learns a user’s driving behavior from the user’s GPS logs and customizes the fastest route for the user. Refer to the following publication for details.

Publications

[1] Jing Yuan, Yu Zheng, et al. Driving with Knowledge from the Physical World. 17th SIGKDD conference on Knowledge Discovery and Data Mining (KDD 2011).

Media Reports

[1] "A driving route made just for you", MIT Technology Review, 2011.8.30.

__________________________________________________________________

Glean the problematic urban planning in a city

Abstract: Urban computing for city planning is one of the most significant applications in Ubiquitous computing. In this paper we detect flawed urban planning using the GPS trajectories of taxicabs traveling in urban areas. The detected results consist of 1) pairs of regions with salient traffic problems and 2) the linking structure as well as correlation among them. These results can evaluate the effectiveness of the carried out planning, such as a newly built road and subway lines in a city, and remind city planners of a problem that has not been recognized when they conceive future plans. We conduct our method using the trajectories generated by 30,000 taxis from March to May in 2009 and 2010 in Beijing, and evaluate our results with the real urban planning of Beijing.

Publications

[1] Yu Zheng, Yanchi Liu, Jing Yuan, Xing Xie, Urban Computing with Taxicabs, 13th ACM International Conference on Ubiquitous Computing (UbiComp 2011), Beijing, China, Sep. 2011. The best paper nominee.

[2] A technical report describing the map segmentation and trajectory projection details.

Media Reports

[1] "Taxicab data helps ease traffic". Future of Technology on MSNBC.com. 2011.9.30

[2] "GPS Data on Beijing Cabs Reveals the Cause of the Traffic Jams". MIT Technology Review, 2011.9.27. Featured on the first page.

[3] "Urban computing based on taxicabs". Reported by ACM TechNews. 2011.9.27

____________________________________________________________________

A Passenger-Cabbie Recommender System

Abstract: We present a recommender for taxi drivers and people expecting to take a taxi, using the knowledge of 1) passengers’ mobility patterns and 2) taxi drivers’ pick-up behaviors learned from the GPS trajectories of taxicabs. First, this recommender provides taxi drivers with some locations (and the routes to these locations), towards which they are more likely to pick up passengers quickly (during the routes or at the parking places) and maximize the profit. Second, it recommends people with some locations (within a walking distance) where they can easily find vacant taxis. In our method, we propose a parking place detection algorithm and learn the above knowledge (represented by probabilities) from trajectories. Then, we feed the knowledge into a probabilistic model which estimates the profit of a parking place for a particular driver based on where and when the driver requests for the recommendation. We validate our recommender using trajectories generated by 12,000 taxis in 110 days.

An internal website showcasing this application

Publications

[1] Jing Yuan, Yu Zheng, Liuhang Zhang, Xing Xie. Where to Find My Next Passenger? , 13th ACM International Conference on Ubiquitous Computing (UbiComp 2011).

[2] Nicholas Jing Yuan, Yu Zheng, Liuhang Zhang, Xing Xie. T-Finder: A Recommender System for Finding Passengers and Vacant Taxis. accepted by IEEE Transactions on Knowledge and Data Engineering (TKDE).

____________________________________________________________________

Detecting Anomalous Events in a City

Abstract: We detect anomalies in a city according to the taxi trajectories. The anomaly could be caused by unexpected or sudden accidents, such as traffic control, protests, concerts, parades, celebrations, and large-scale sale promotion. In many cases, the anomaly occurs before the corresponding accident actually happens. If detecting the unusual mobility pattern of people in this region in advance, we can solve the problem early and avoid the happening of the tragedy.

Publications

[1] Wei Liu, Yu Zheng, Sanjay Chawla, Jing Yuan and Xing Xie. Discovering Spatio-Temporal Causal Interactions in Traffic Data Streams. In KDD 2011.

[2] Linsey Xiaolin Pang, Sanjay Chawla, Wei Liu, and Yu Zheng. On Mining Anomalous Patterns in Road Traffic Streams. In the 7th International Conference on Advanced Data Mining and Applications (ADMA 2011). The best paper award

[3] Sanjay Chawla, Yu Zheng, and Jiafeng Hu. Inferring the root cause in road traffic anomalies, IEEE International Conference on Data Mining (ICDM 2012).

___________________________________________________________________

Some Released Datasets

[1] T-Drive Taxi Trajectroies: This is a sample of T-Drive taxi trajectory dataset which was generated by over 10,000 taxis in a period of one week in Beijing.

[2] GeoLife Trajectory Dataset: This is a GPS trajectory dataset collected in (Microsoft Research Asia) GeoLife project by 167 users in a period of over two years (from April 2007 to Dec. 2010). This trajectory dataset can be used for many research theme, such as mobility pattern mining, user activity recognition, location-based social networks, location privacy, and location recommendation.

___________________________________________________________________

Slide Decks

A slide deck for a 20-minute presentation

A slide deck for a 1-hour presentation

A slide deck for a 3-hour tutorial

___________________________________________________________________

Related People

Yu Zheng, Project Lead, Lead Researcher

Jing Yuan, Associate Researcher 2

Xing Xie, Lead researcher