Urban computing of route-oriented vehicles

Techniques for analyzing effectiveness of an urban area based on traffic patterns collected from route-oriented vehicles. A process collects sequences of global positioning system (GPS) points in logs and identifies geographical locations to represent the urban area where the route-oriented vehicles traveled. The process models traffic patterns by: partitioning the urban area into regions based at least in part on major roads, segmenting the GPS points from the logs into time slots, and identifying the GPS points associated with transporting a passenger in the route-oriented vehicles. The process models traffic patterns by projecting the identified GPS points onto the regions to construct transitions of the identified GPS points travelling between the regions. Then the process builds a matrix of the regions for each time slot in each day based on a number of the transitions. Each item in the matrix represents an effectiveness of a connection between two regions.

BACKGROUND

Ubiquitous computing is a model of human-computer interaction to integrate information processing into daily activities. For instance, ubiquitous computing includes multiple computational devices and systems operating simultaneously. Recently, ubiquitous computing is applied to urban areas, which includes physical movements and interpretations of social context. As a result, urban computing is emerging as a concept where every sensor, person, vehicle, building, and street in the urban areas may be used as a computing component for serving people and their towns or their cities.

Urban computing may be used for urban planning that integrates land-use planning and transportation planning to improve built, economic, and social environments of communities. Urbanization is increasing at a fast pace in developing countries. Meanwhile, urban reconstruction, renewal, and suburbanization are occurring in countries that have already been developed. However, there are opportunities for innovative technologies that may automatically and inconspicuously sense urban dynamics and provide crucial information to urban planners.

For instance, a large number of taxicabs transport passengers in urban areas. Some taxicabs may be equipped with sensors to record their location data to a centralized server at regular intervals. The taxicabs may be considered to be ubiquitous mobile sensors constantly probing the urban areas' traffic patterns. Thus, there is an increasing opportunity to utilize the location data of route-oriented vehicles.

SUMMARY

This disclosure describes analyzing effectiveness of an urban area based on traffic patterns collected from logs of route-oriented vehicles. In one aspect, a process collects sequences of global positioning system (GPS) points in the logs and identifies geographical locations to represent the urban area where the route-oriented vehicles traveled based on the logs. The process models traffic patterns in the urban area by: partitioning the urban area into regions based at least in part on major roads, segmenting the GPS points from the logs into time slots, and identifying the GPS points associated with transporting a passenger in the route-oriented vehicles. The process further models traffic patterns by projecting the identified GPS points onto the regions to construct transitions of the identified GPS points travelling between the regions. Then the process builds a matrix of the regions for each time slot in each day based on a number of the transitions. Each item in the matrix represents an effectiveness of connectivity between the regions.

In another aspect, an interface receives user input for an urban area to be evaluated for an efficiency of the planning of the urban area. An area computing application receives sequences of global positioning system (GPS) points from logs of route-oriented vehicles and creates a model of the traffic patterns in the urban area being selected based on the GPS points. The model identifies pairs of regions in the urban area having a set of transitions between them when travelling in the regions. The area computing application aggregates the transitions to associate each pair of regions with a volume of traffic between the pair of regions, expected travel speeds of the transitions, and a ratio between an actual travel distance and an Euclidan distance between centroids of each of the pair of regions. An identified pair of regions may require the route-oriented vehicles to take detours based on congested traffic when travelling between the identified pair of regions. Based on this evaluation, recommendations may be provided for converting streets to one way streets, adding more lanes to the streets, adding more roads, adding another subway line, adding a bus stop, adding a train stop, building a shopping area, and the like.

DETAILED DESCRIPTION

Overview

This disclosure describes evaluating effectiveness of an urban area based on information collected from the logs of the route-oriented vehicles. The route-oriented vehicles travel frequently in the urban area to pick up passengers and to drop the passengers off in their desired destinations. Typically, a majority of the route-oriented vehicles tend to be equipped with sensors, such as global positioning system (GPS) sensors, which enable the route-oriented vehicles to report their locations to a centralized server at regular intervals. For instance, the sensors may collect the GPS points at regular intervals, such as every one to two minutes, every two to five minutes, or may be set at shorter or longer intervals.

As a result, the route-oriented vehicles equipped with the sensors are constantly probing the urban areas' traffic patterns, such as traffic flow on the roads and city-wide travel patterns of people in the route-oriented vehicles. For instance, a large city may have approximately 67,000 route-oriented vehicles generating an average of 1.2 million trips per day with passengers in the route-oriented vehicles. The 1.2 million trips per day generated by the route-oriented vehicles tend to have an average of 1.2 passengers per trip. This number represents about 5% of total personal trips created by various transportation systems including buses, subways, private vehicles, and the route-oriented vehicles. Based on the 5% of total personal trips, the route-oriented vehicles represent actual traffic patterns on the roads in the urban area. As a result, a process may create a model to model traffic patterns and to connect the traffic flows between the regions in the urban area.

Traffic data is collected via the GPS sensors in logs of the route-oriented vehicles. A process extracts trajectories, which are sequences of GPS points from the logs. The trajectories represent trips for the route-oriented vehicles and imply human knowledge from drivers of the route-oriented vehicles. For example, human knowledge may include driving conditions during rush hour, road constructions, direction turns, and the like.

While aspects of described techniques can be implemented in any number of different computing systems, environments, and/or configurations, implementations are described in the context of the following example computing environment.

ILLUSTRATIVE ENVIRONMENT

FIG. 1illustrates an example architectural environment100, in which an evaluation of an effectiveness of planning of an urban area may be determined on a computing device. The environment100includes an example computing device102, which is illustrated as a mobile device. The computing device102is configured to connect via one or more network(s)104to access a planning service106for a user108. It is noted that the computing device102may take a variety of forms, including, but not limited to, a portable handheld computing device (e.g., a personal digital assistant, a smart phone, a cellular phone), a personal navigation device, a laptop computer, a desktop computer, a portable media player, or any other device capable of connecting to one or more network(s)104to access the planning service106for the user108.

The network(s)104represents any type of communications network(s), including wire-based networks (e.g., cable), wireless networks (e.g., cellular, satellite), cellular telecommunications network(s), WiFi networks, and IP-based telecommunications network(s). The planning service106represents an urban planning service that may be operated as part of any number of online service providers, such as a search engine. In another implementation, the planning service106may be a map-based application stored in memory of the computing device102. Updates with GPS logs and trajectories may be sent for an area computing application that is stored on a mobile device.

In the illustrated example, the computing device102may include a user interface (UI)110that is presented on a display of the computing device102. The user interface110facilitates access to the planning service106that provides the evaluation of the planning of urban area(s). The user108also employs the UI110to submit a request for an urban area from the planning service106.

In one implementation, the UI110is a browser-based UI that presents a page received from the trajectory datasets of the route-oriented vehicles. The UI110shows trajectory datasets for “Year X” and “Year Y.” The UI110illustrates the datasets are collected from about 29,800 route-oriented vehicles in Year X and from about 32,400 route-oriented vehicles in Year Y. The UI100also illustrates the number of GPS points is approximately 978 million in Year X and approximately 1730 million in Year Y.

In the illustrated example, the planning service106is hosted on one or more area computing servers, such as area computing server(s)112(1),112(2), . . . ,112(S), accessible via the network(s)104. The area computing servers112(1)-(S) may be configured as plural independent servers, or as a collection of servers that are configured to perform larger scale functions accessible by the network(s)104. The area computing server(s)112may be administered or hosted by a network service provider that provides the planning service106to and from the computing device102.

The planning service106further includes an area computing application114that executes on one or more of the area computing servers112(1)-(S). The area computing application114provides the evaluation of the effectiveness of the urban area, which first includes collecting logs from the route-oriented vehicles. Data from the route-oriented vehicles are used as drivers are very familiar with urban roads and time-variant traffic flows on the urban roads. The drivers know the fastest routes, which are short and quick, but not necessarily the shortest in distance. Thus, the data of the route-oriented vehicles enhances the area computing application114by mining human knowledge, such as learning smart driving directions.

The area computing application114processes the global positioning system (GPS) logs from various types of route-oriented vehicles. Based on the logs collected, the area computing application114identifies geographical locations where the route-oriented vehicles have traveled to generate a map of the urban area. To better identify effective driving directions in the geographical locations, the area computing application114parses trajectories from the logs. The urban area may be further partitioned into multiple regions based at least on the major roads.

The trajectory datasets may be stored in a database116, which is then used to construct a model based at least in part on the traffic patterns of the route-oriented vehicles. The model involves associating each route-oriented vehicle trajectory to a corresponding region in the urban area. Details of constructing the model are described with reference toFIGS. 4-8.

As mentioned, the environment100may include the database116, which may be a separate server or may be a representative set of server112that is accessible via the network(s)104. The database116may store information, such as logs for one or more route-oriented vehicle(s)118, a sequence of global positioning system (GPS) points, trajectories archive, graphs, a matrix, models, other data, and the like.

The environment100shows a representation of the urban area120computed as a result of the GPS logs from the route-oriented vehicles118. The representation of the urban area120illustrates evaluations and recommendations performed by the area computing application114to the user108. For instance, at122is a recommendation for a subway line to decrease the traffic.

FIG. 2is a flowchart of an example process200showing high-level functions performed by the area computing application114. These processes are illustrated as logical flow graphs, each operation of which represents a sequence of operations that can be implemented in hardware, software, or a combination thereof. In the context of software, the operations represent computer-executable instructions stored on one or more computer-readable storage media that, when executed by one or more processors, perform the recited operations. Generally, computer-executable instructions include routines, programs, objects, components, data structures, and the like that perform particular functions or implement particular abstract data types. For discussion purposes, the processes are described with reference to the computing environment100shown inFIG. 1. However, the processes may be performed using different environments and devices. Moreover, the environments and devices described herein may be used to perform different processes.

For ease of understanding, the methods are delineated as separate steps represented as independent blocks in the figures. However, these separately delineated steps should not be construed as necessarily order dependent in their performance. The order in which the process is described is not intended to be construed as a limitation, and any number of the described process blocks maybe be combined in any order to implement the method, or an alternate method. Moreover, it is also possible for one or more of the provided steps to be omitted.

The area computing application114provides the evaluation of the urban area based on the log information collected from the route-oriented vehicles118. The process200may be divided into four phases, an initial phase to collect GPS points from logs of route-oriented vehicles202, a second phase to model traffic patterns and connectivity between the regions in the urban area based on the GPS points204, a third phase to identify a set of skylines from the model to represent a portion of the urban area206, and a fourth phase to evaluate the effectiveness of planning of the urban area208. All of the phases may be used in the environment ofFIG. 1, may be performed separately or in combination, and without any particular order.

The first phase is to collect the GPS points from the logs of the route-oriented vehicles202. For instance, the area computing application114collects the logs from various types of route-oriented vehicles118that transport passengers, including but not limited to taxicabs, limousines, and shuttles. These types of route-oriented vehicles118tend to focus on picking up and dropping off passengers in the urban area. The logs may be obtained from GPS sensors located on each of the route-oriented vehicles118. The logs are generally a collection of GPS points, which includes a date, a time, a longitude coordinate, and a latitude coordinate. Also, the GPS points associated with transporting passengers are selected for the evaluation, so the route-oriented vehicles118may include a weight sensor for each of the route-oriented vehicles118to detect passengers other than the driver, a weight sensor to determine an occupancy status in a passenger seat of the route-oriented vehicle118, an identifier for the driver to specify a passenger is present in the route-oriented vehicle118, and the like. From the logs, the geographical locations are identified in the urban area.

The second phase is to model traffic patterns and connectivity between the regions in the urban area based on the GPS points204. For example, the area computing application114models the traffic patterns by: partitioning the urban area into regions based at least in part on major roads, segmenting the GPS points from the logs into time slots, and identifying the GPS points associated with transporting a passenger in the route-oriented vehicles118. The area computing application114projects the GPS points onto the regions to identify pairs of regions having a set of transitions between them when travelling in the regions and builds a matrix for the regions.

The third phase is to identify a set of skylines from the model to represent a portion of the urban area206. The term skyline describes a graphical representation of the data. For instance, the set of skylines represents the GPS points with travel speeds and ratios of actual travel distance and an Euclidan distance between centroids of each of the pair of regions, which are less efficient than other GPS points. The area computing application114then identifies pairs of regions having small travel speeds and large ratios of the actual travel distance and the Euclidan distance between centroids of each of the pair of regions. The identified pairs of regions may require the route-oriented vehicles118to take detours based on congested traffic when travelling between the identified pairs of regions.

The fourth phase is to evaluate the effectiveness of planning of the urban area208. Based on this evaluation, the area computing application114may provide recommendations for building new roads, converting streets to one way streets, adding more lanes to existing roads, adding new roads, adding another subway line, adding a bus stop, adding a train stop, and the like. Details are discussed for collecting GPS points from logs of the route-oriented vehicles202with reference toFIG. 3; for modeling traffic patterns204with reference toFIGS. 4-8, for creating and mining skylines with reference toFIGS. 9-12, and for evaluating the effectiveness of planning of the urban area with reference toFIG. 13.

Collect GPS Points from Logs of Route-Oriented Vehicles

FIG. 3is a flowchart illustrating an example process for phase202(discussed at a high level above) of collecting the GPS points from the logs of the route-oriented vehicles118. The area computing application114may use the collected GPS logs from the centralized server or receive the GPS logs from the route-oriented vehicle companies. Drivers for the route-oriented vehicles118may be very familiar with the roads and time-variant traffic flows on the roads. To be effective and to make profit, the drivers for the route-oriented vehicles118tend to select a fastest route based on their knowledge. Along with their knowledge, the drivers consider other factors, such as traffic flows and signals, accidents, road constructions, direction turns, and the like. By directly following their routes that are well supported by the GPS logs, the knowledge of the drivers may be effectively used.

The area computing application114identifies the geographical locations from the logs to represent the urban area302. The geographical locations from the logs represent roads and streets where the route-oriented vehicles118have traveled as recorded in the logs.

It is possible to collect log information since a large number of the route-oriented vehicles118may be equipped with GPS sensors that automatically record a trajectory, which is a sequence of time-ordered GPS points. The trajectory may be represented by Tr. Each trajectory may include the sequence of GPS points represented as p1→p2→p3→ . . . →pn.

At304, the GPS sensors record timestamps, coordinates of locations, and status of occupancy of each route-oriented vehicle118for a GPS point. The status of occupancy may be determined by a weight sensor for each of the route-oriented vehicles118to detect passengers other than the driver, a weight sensor on seats to determine if passengers occupied the seats of the route-oriented vehicles118, an identifier of occupancy associated with fares indicating passenger(s) are present in the route-oriented vehicle118, and the like. For instance, the GPS point may contain a date, a time in a.m. or p.m., a longitude coordinate, a latitude coordinate, and the status of occupancy which may be collected with a low sampling rate every one-two minutes or every two-five minutes per point. Thus, the GPS point may be represented by p=(d, t, long, lat, o).

At306, the area computing application114may identify the GPS points from the trajectory datasets based on satisfying a criteria. For instance, the criteria may include certain dates in the year, specific times during rush hour, weekdays, and an occupied status indicating a passenger was being transported in the route-oriented vehicle118. In another implementation, the criteria may include summer months, specific times during rush hour, weekends, and the occupied status of the passenger in the route-oriented vehicles.

After the GPS points for the route-oriented vehicle logs have been collected, the area computing application114may store the trajectory datasets in the database116or archive the information308. The area computing application114uses the GPS points to create a model.

Model Traffic Patterns and Connectivity Between Regions Based on GPS Points

FIG. 4is a flowchart illustrating an example process for phase204(discussed at a high level above) of modeling traffic patterns and connectivity between the regions in the urban area based on the GPS points. The area computing application114partitions the urban area into regions represented by (r) based at least on using major roads402. The use of regions helps provide rich knowledge about people's living and travel conditions. Also any problems or flaws in the regions are reflected in both land-use and transportation planning. An example of partitioning the urban area will be discussed with reference toFIG. 5.

The area computing application114may separate the GPS points from the logs into time slots404. For instance, the area computing application114separates the GPS points into two groups, 1) weekdays and 2) weekends and/or holidays. Then the GPS points are further divided according to the time of day into time slots. It is commonly understood that the time of day for travelling on the roads may affect the speed of the route-oriented vehicles118. Traffic patterns are considerably different during rush hour on weekdays as compared to weekends. For example, the time of day may be grouped into three or four time slots that are different for weekends than weekends or holidays, as shown below.

The area computing application114identifies the GPS points associated with the passenger in the route-oriented vehicles406. When there are passengers associated with the GPS points, the trajectories represent actual trips along the roads and streets to desired destinations. Thus, this represents actual traffic congestion.

The area computing application114projects the identified GPS points to the urban area and constructs transitions between the regions408. A transition represented by (s) is generated between two regions if a GPS point represented as piis a first point in region 1, r1, and pjis a second point in region 2 r2(i<j). The transition (s) includes a departure time (pi, ti), an arrival time (pj, tj), a travel distance (d) and a travel speed (v). The travel distance (d) may be calculated with the following equation:
d(pi,pj)=Σi≦k<jDist(pk,pk+1)
where Dist(pk, pk+1) denotes the Euclidian distance between two consecutive GPS points.

The travel speed (v) may be calculated with the following equation:
v=d(pipj)/|pj·t−pi·t|
where t represents time. Examples of charts illustrating the speeds of the route-oriented vehicles118in certain hours of the day follow with reference toFIGS. 6A and 6B. Examples of the transitions constructed are shown inFIG. 7.

The area computing application114plots pairs of regions having a set of transitions between them410. For instance, the pairs of regions, region 1 and region 2, may be represented by r1→r2having the set of transitions between them. The area computing application114aggregates the transitions so each pair of regions is associated with the following features: (a) volume of traffic between the regions such as a count of transitions |S|, (b) expected travel speed(s) E(V) of the transitions, and (c) the ratio Θ between the expected actual travel distance E(D) and the Euclidian distance between the centroids of two regions, represented as CenDist(r1, r2).

The following equations are used to compute expected travel speed E(V), expected travel distance E(D), and ratio Θ, respectively.

E⁡(V)=∑si∈s⁢⁢si·vsE⁡(D)=∑sj∈s⁢⁢sj·dsθ=E⁡(D)/CenDist⁡(r1,r2)
where S is a collection of transitions between r1and r2. An example graph illustrating expected travel speed E(V), expected actual travel distance E(D), and ratio Θ is shown inFIG. 8.

The area computing application114builds a matrix of the regions for each time slot in each day based on the transitions412. For instance, an item in the matrix is a tuple, ai,j=<|S|, E(V), Θ>, denoting a number of transitions |S|, the expectation of travel speed E(V), and the ratio Θ between regions riand rj. In an implementation, there may be x weekdays and y weekends or holidays, 4x+3y matrices will be build using the schema of the time slots shown in Table I. The matrix M is shown below.

FIG. 5illustrates an example map of partitioning the urban area into regions based at least on using major roads402. For instance, a map of the urban area may be divided into disjoint regions, which includes: communities, neighborhoods, subdivisions, roads, streets, and the like. The roads facilitate transportation while the streets facilitate public interaction. The roads include but are not limited to highways and motorways. The streets include but are not limited to pedestrian streets, alleys, city-centre streets, and the like.

In implementations, the major roads500may be highlighted with a color or a heavy weight line, and referred to as a first zone that includes the top two communities. Meanwhile, the small roads502may be highlighted with another color or a medium weight line, and referred to a second zone that includes smaller areas, which are at a lower level than the first zone. Also, the streets504may be highlighted with yet another color or a small weight line, referred to as a third zone that includes smallest areas, and at a lower level than the first zone and the second zone.

Example Charts of GPS Points with Speed Versus Time of Day

FIGS. 6A and 6Billustrate example charts of separating the GPS points from the logs into time slots404for weekdays and weekends/holidays, respectively with their speeds. At600, the chart is for the GPS points collected during the weekdays. The speed602of the route-oriented vehicles118is shown in (km/h) and the time of day604is shown in hour-half increments starting with the hour at 06:00 until 22:30.

The average travel speed is shown at606. The average travel speed for the route-oriented vehicles118in chart600, from 7:00 am-10:30 am608(i.e., slot 1) is lower than that of the entire day. This is expected due to rush hour traffic as there are more vehicles on the roads during this time. Also, the average travel speed during 4:00 pm-7:30 pm610(i.e., slot 3) represents the evening rush hour when people are returning home.

The bottom chart612illustrates the speed of the route-oriented vehicles118and the time of day for weekends or holidays. For instance, the average travel speed is shown at614. As expected, the average travel speed for the weekdays is slightly slower than the average travel speed for the weekends or holidays.

The charts600,612illustrate in the same time slot, the traffic conditions and semantic meaning of people's travels are similar. The area computing application114explores the trajectories from different time slots to detect flaws in the urban planning. Finally, the time partition enables the area computing application114to evaluate temporal relationships between the results detected from continuous time slots to understand the flaws in the urban planning.

Construct Transitions Between Regions

FIG. 7illustrates an example process of projecting the GPS points onto the regions and constructing transitions between the regions408. The trajectory Tr1700traverses from point p0702in region r1704, to p1706in region r1704, to p2710in region r1704, and to p3712in region r3714. The top dark line represents a path716of the trajectory Tr1700. Also shown is a second trajectory Tr2718.

Turning to the diagram720below, the two trajectories Tr1700and Tr2718are shown with transitions formed between the regions. The first trajectory Tr1700traverses from r1→r3722to formulate a transition of r1→r3. The second trajectory Tr2718traverses from r1→r2→r3724to formulate three transitions of: r1→r2, r2→r3, and r1→r3. The second trajectory Tr2718discontinuously traverses two regions, r1→r3but formulates the transition between the two regions. Thus, the distance represented by (d) of this transition may be represented by: Σ4≦k<8DiSt(pk, pk+1) and the travel speed may be represented by d/(p8·t−p4·t).

FIG. 8illustrates pairs of regions having a set of transitions between them410. An example graph includes a count of transitions |S|800on z-axis, the expectation of travel speed E(V)802on y-axis, and the ratio Θ804on x-axis. The area computing application114plots pairs of regions from a time slot of 7:00 am-10:30 am for a weekday in the <|S|, E(V), Θ> space. A single dot located in the center806represents a pair of regions. The pair of regions is projected onto XZ space808and YZ space810. It is noted that Θ may have a value smaller than 1 as the route-oriented vehicles travel across two adjacent regions with a distance shorter than that between the two centroids.

Referring to the second trajectory Tr2718that was described inFIG. 7, the route-oriented vehicle118may have traveled through several other regions before finally reaching the destination of r3. However, the connectivity of the two regions may be represented by all the possible routes between them instead of the direct or fastest transitions. Often, the driver of the route-oriented vehicle118may have to reach a region through a roundabout route travelling through other regions to avoid traffic jams. Also, the discontinuous transitions do not bias the expected travel speed E(V)802and the ratio Θ804. The drivers of the route-oriented vehicles118tend to travel through an effective shortcut route between two regions rather than the roundabout route.

For instance, the driver of the route-oriented vehicle118intending to travel from r1to r3, tends to travel the shortcut route by travelling the trajectory path716. Thus, the number of discontinuous travel is a very small portion in the transition set. As a result, the expected travel speed E(V)802and the ratio Θ804are close to the real travel speed and ratio that people could travel from r1to r3. However, if the drivers of the route-oriented vehicles118have to reach the destination of r3by travelling through additional regions such as r2, which is indicative that the route directly connecting r1to r3is not very effective.

The graph of <|S|, E(V), Θ> represents the model of traffic patterns and the connectivity between two regions. Specifically, the ratio Θ804captures a geometry property of the connection between the pairs of regions. The pair or regions with a large ratio Θ804indicates drivers of the route-oriented vehicles118have to take a long detour when travelling from one region to another region. The count of transitions |S|800and the expected travel speed E(V)802represent features of the traffic. For instance, a large count of transitions |S|800and a small expected travel speed E(V)802imply there is congested traffic by the existing routes between the two regions. One of the purposes is to identify problem areas in the urban area. The area computing application114retrieves the pairs of regions with a large count of transitions |S|800, a small expected travel speed E(V)802, and a large ratio Θ804, which is indicative of flaws in the urban area.

Identify a Set of Skylines from the Model

FIG. 9illustrates an example graph from a third phase206(discussed at high level above) to identify a set of skylines from the model to represent a portion of the urban area. As previously mentioned, the area computing application114built a matrix of regions, M and now selects the pairs of regions having the number of transitions above an average from the matrix M. The area computing application114locates “a skyline set” represented by (L) from the selected region pairs according to the expected travel speed E(V)802and the ratio Θ804. A skyline is defined as points which are not dominated by any other points. For instance, a point dominates another point if the point is as good or better in all dimensions and better in at least one dimension than the another point.

An example process illustrates how the area computing application114determines when a first point dominates a second point if the first point is as good or better in all dimensions and better in at least one dimension than the second point. Points are shown in Table II along with expected travel speed E(V), and ratio Θ between the actual travel distance and the Euclidan distance between centroids of each of the pair of regions.

Table II indicates that point 2 dominates point 1 based on the lower E(V) value and higher ratio. Thus, point 1 is not included in the skyline. However, point 2 does not dominate point 3 as point 3 has a higher ratio, indicating point 3 is better than point 2. Also, points 5 and 8 are detected as not being dominated by other points and included in the skyline while points 4, 6, and 7 are dominated by other points.

FIG. 9further illustrates the expected travel speed E(V)802plotted along y-axis and the ratio Θ804plotted along x-axis. The dashed line900illustrates points representing the pair of regions900that have smaller expected travel speeds E(V)802and larger ratios Θ804than the other points902located in the skyline. Each tuple ai,j,L is not dominated by others, such as ap,qLM, in terms of the expected travel speed E(V)802and the ratio Θ804. There are not any pairs of regions ap, qL having smaller expected travel speed E(V)802and larger ratio Θ804than ai,jL.

FIG. 10illustrates example kinds of pairs of regions detected in the set of skylines. For instance, at1000, the pairs of regions in the set of skylines may have properties of a small expected travel speed E(V)802between a set of transitions and a small ratio Θ804between an actual travel distance of the set of transitions and an Euclidan distance between centroids of each of the pair of regions. The properties here indicate the pairs of regions are connected with some direct routes, while a capacity of these routes is not sufficient as compared to the existing traffic between the two regions. The properties here further indicate the drivers may have no other options but to take ineffective routes for travelling between the two regions.

In another instance at1002, the pairs of regions in the set of skylines may have properties of a small expected travel speed E(V)802between a set of transitions and a large ratio Θ804between an actual travel distance of the set of transitions and an Euclidan distance between centroids of each of the pair of regions. The properties here indicate drivers of the route oriented vehicles118have to take detours for travelling between two regions while these detours have congested traffic leading to a slow speed. This is one of the worst cases of the kinds of pairs of regions in the set of skylines.

In yet another instance at1004, the pairs of regions in the set of skylines may have properties of a large expected travel speed E(V)802between a set of transitions and a large ratio Θ804between an actual travel distance of the set of transitions and an Euclidan distance between centroids of each of the pair of regions. The properties here indicate that the drivers of the route-oriented vehicles118take detours such as highways, which are fast when travelling between two regions. Although the expected travel speed E(V)802is not slow, the long distance may cost the drivers and current passengers in the route-oriented vehicles more time and gas.

The area computing application114identifies the most salient pairs of regions that have flawed planning. The skyline is constructed from the pairs of regions having a large amount of traffic, as represented by the count of transitions |S|800that is above average. Thus, the skyline generated is based on many travels of passengers and each expected travel speed E(V)802, ratio Θ804is calculated based on a large number of observations.

FIG. 11illustrates an example process1100of formulating skyline graphs based on the pairs of regions connected from consecutive time slots. Shown along the left side are time periods of slot 1, slot 2, and slot 3 at1102. Table I. previously illustrated how the time slots correspond to different hours based on whether the day is a weekday or a weekend or holiday. Shown along the top are days, DAY 1, DAY 2, DAY 3 at1104.

The process1100identifies a skyline in each time slot1102of each day1104. For instance, two pairs or regions from two consecutive slots may be connected if the pairs of regions are spatially close to each other. For example, in DAY 1, the process1100connects the pairs of regions r1→r2from slot 1 at1106to r2→r8from slot 2 at1108since the two pairs of regions share a common node of r2and appear in the consecutive time slots of the same day. Also, for DAY 1, the process1100connects r4→r5from slot 1 at1110to r5→r7from slot 2 at1112. However, for DAY 1, the process1100does not connect r4→r5from slot 1 at1100to r8→r4from slot 3 at1114since the pairs of regions are not temporally close. The process1100then formulates a collection of skyline graphs (CG)1116.

The area computing application114mines frequent sub-graph patterns from the collection of skyline graphs across a certain number of days to avoid any false alter. In certain instances, the area computing application114may detect a pair of regions with effective connectivity as part of a skyline based on anomaly events, such as a traffic accident. The mining of frequent sub-graph patterns further provides deeper analysis of any flaws in the urban area.

The area computing application114mines the skyline patterns by utilizing different supports. The area computing application114calculates a support of a sub-graph pattern using the following equation:

support⁡(g)={G⁢g⊆G,CG}num⁢⁢of⁢⁢days
where g represents the sub-graph pattern, G is a skyline graph, and CG represents a collection of skyline graphs across multiple days. The denominator denotes the number of days that the dataset is analyzed over.

For example, the support of r4→r5is 1 since this transition appears in the skyline graphs of all three days while that of r3→r6is ⅔ since it only appears in DAY 2 and DAY 3. For a threshold 6, the area computing application114selects the support ≧δ. The patterns represent flaws present in the planning of the urban area, in which the patterns appear prominent and frequent.

FIG. 12illustrates examples of mined frequent skyline patterns at1200and1202. The area computing application114associates individual pairs of regions to determine any causalities and/or relationships among the regions to better understand how a problem may be derived. The area computing application114mines association rules among the patterns according to the following equations for support and confidence:

Support⁡(g1⇒g2)=g1⋃g2num⁢⁢of⁢⁢daysConfidence⁡(g1⇒g2)=g1⋃g2g1
where |g1∪g2| denotes the number of days that g1and g2both occurred and |g1| indicates the number of days having g1.

Two patterns may formulate an association rule, denoted as g1→g2, if the support of g1→g2≧δ and the confidence ≧Θ (i.e., a given threshold). For instance, at1200, the association rules illustrate (r4→r5) at1204→(r3→r6) at1206which includes a support of ⅔ and a confidence of ⅔. In yet another example, (r3→r6) at1206→(r4→r5) at1204which includes a support of and a confidence of 1.

The association rules may include two or more patterns. For instance, g1, g2→g3, where g3has a very high probability (conditioned by δ and Θ) to occur when g1and g2appear simultaneously. However, the sub-graph patterns may not be geospatially close to each other, revealing the causality and correlation between flawed planning without any relationship in the geographical spaces.

In an implementation, the planning service106presents the user interface110on the display of the computing device102, after the user108activates the planning service106. The user interface110gives the user108access to the area computing application114provided by the planning service106. The user input may be for a request for a particular urban area to evaluate flaws in the planning.

Once the planning service106receives the input or query from the user108, the planning service106accesses the model constructed from analysis of the logs of the route-oriented vehicles118. The construction of the model was previously described with reference toFIGS. 4-8.

FIG. 13is an example heat map1300as computed by the area computing application114and presented to the user108on the user interface110. As mentioned, the area computing application114from the planning service106may be provided by a network service provider, a web application, an application based on a live search map, an application stored in memory of a computing device, and the like.

The heat map1300represents the flaws in the urban area based on detecting the frequent sub-graph patterns. The heat map1300includes frequency that a region has been detected as a flaw. For instance, a shape represents different frequency levels of flaws in the regions. In an implementation, a square represents a smallest level of frequency of flaws1302for the regions shown with the squares, while a circle represents a small level of frequency of flaws1304for the regions shown with the circles. Also, a star represents a middle level of frequency of flaws1306for the regions shown with the stars and a triangle represents a high level of frequency of flaws1308for the regions with the triangles. In another implementation, arrows may be used to indicate the direction of the transition from one region to another region.

Based on this evaluation of the heat map1300, the recommendations may include building new roads, widening existing roads, converting roads to one way streets, adding new roads, adding local businesses such as shopping malls in the regions outsourcing people (i.e., land-use planning), adding subways or bus routes in these regions.

Example Server Implementation

FIG. 14is a block diagram showing an example server112to be used for the planning service106and/or the area computing application114. The area computing server112may be configured as any suitable system capable of services, which includes, but is not limited to, implementing the planning service106for evaluating the planning of urban areas, such as provide the map of the urban area with flaws in the urban area due to traffic congestion, insufficient number of roads travelling through the regions, insufficient number of lanes on existing roads, insufficient land use, and the like. In one example configuration, the server112comprises at least one processor1400, a memory1402, and a communication connection(s)1404. The processor(s)1400may be implemented as appropriate in hardware, software, firmware, or combinations thereof. Software or firmware implementations of the processor(s)1400may include computer-executable or machine-executable instructions written in any suitable programming language to perform the various functions described.

Similar to that of computing environment100ofFIG. 1, memory1402may store program instructions that are loadable and executable on the processor(s)1400, as well as data generated during the execution of these programs. Depending on the configuration and type of computing device, memory1402may be volatile (such as random access memory (RAM)) and/or non-volatile (such as read-only memory (ROM), flash memory, etc.). Thus, memory1402includes volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information, such as computer-readable instructions, data structures, program modules, or other data.

The communication connection(s)1404may include access to a wide area network (WAN) module, a local area network module (e.g., WiFi), a personal area network module (e.g., Bluetooth), and/or any other suitable communication modules to allow the area computing server112to communicate over the network(s)104.

Turning to the contents of the memory1402in more detail, the memory1402may store an operating system1406, the planning service module106, the area computing application module114, and one or more applications1408for implementing all or a part of applications and/or services using the planning service106.

The one or more other applications1408may include an email application, online services, a calendar application, a navigation module, a game, and the like. The memory1402in this implementation may also include a model of traffic patterns and connectivity module1410and a skyline graph module1412.

The area computing application module114may perform the operations described with reference to the figures or in combination with the planning service module106, the model of traffic patterns and connectivity module1410, and the skyline graph module1412.

The server112may include the database116to store the collection of GPS logs, trajectories, graphs, routes, models, maps of urban areas, and the like. Alternatively, this information may be stored on other databases.

The server112may also include additional removable storage1414and/or non-removable storage1418including, but not limited to, magnetic storage, optical disks, and/or tape storage. The disk drives and their associated computer-readable media may provide non-volatile storage of computer readable instructions, data structures, program modules, and other data for the computing devices. In some implementations, the memory1402may include multiple different types of memory, such as static random access memory (SRAM), dynamic random access memory (DRAM), or ROM.

Computer-readable media includes, at least, two types of computer-readable media, namely computer storage media and communications media.

Computer storage media includes volatile and non-volatile, removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules, or other data. Computer storage media includes, but is not limited to, RAM, ROM, erasable programmable read-only memory (EEPROM), flash memory or other memory technology, compact disc read-only memory (CD-ROM), digital versatile disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other non-transmission medium that can be used to store information for access by a computing device.

In contrast, communication media may embody computer readable instructions, data structures, program modules, or other data in a modulated data signal, such as a carrier wave, or other transmission mechanism. As defined herein, computer storage media does not include communication media.

Various instructions, methods, techniques, applications, and modules described herein may be implemented as computer-executable instructions that are executable by one or more computers, servers, or computing devices. Generally, program modules include routines, programs, objects, components, data structures, etc. for performing particular tasks or implementing particular abstract data types. These program modules and the like may be executed as native code or may be downloaded and executed, such as in a virtual machine or other just-in-time compilation execution environment. The functionality of the program modules may be combined or distributed as desired in various implementations. An implementation of these modules and techniques may be stored on or transmitted across some form of computer-readable storage media.

The server112as described above may be implemented in various types of systems or networks. For example, the server may be a part of, including but is not limited to, a client-server system, a peer-to-peer computer network, a distributed network, an enterprise architecture, a local area network, a wide area network, a virtual private network, a storage area network, and the like.