planning algorithms, and that cannot be derived by looking at just distance and edge speeds.
Driving patterns can be derived from the traffic database by using frequent pattern mining [1, 15, 23]. We can define a minimum support level, and go through the traffic database identifying frequent edges, and when we have access to in dividual vehicle data, longer frequent path segments can be mined. The problem with this approach is that a uniform minimum support level is difficult to define, and it may fil ter many important local roads, or may keep infrequently traveled highlevel roads.
We propose a frequent pattern mining method guided by the area and road hierarchies: Frequent edges are mined at the area level, using a minimum support relative to the traffic volume of each edge class in the area. This will allow us, for example, to distinguish support for edges at different levels of the road hierarchy.
With driving pattern mining, each edge (or path segment) in the road network can be marked as frequent or infre quent given a time interval and a set of driving conditions (d_{1}, ..., d_{k}). The pathfinding algorithm will use this infor mation to guide the search mostly through frequent edges, and only expand infrequent ones when absolutely necessary (e.g., usually at the start or end of a road when we may need to go into nearby neighborhoods).
6.
PRECOMPUTATION AND UPGRADES
In this section we will present two techniques aimed at improving the performance both in terms of run time and path accuracy of fastest path algorithms by the utilization of two techniques. The first is area level precomputation of stable paths in order to improve efficiency. The second is to upgrade certain small but very fast roads to a higher level in the road hierarchy in order to improve the accuracy (path duration vs. best possible path duration) of the algorithm.
6.1
Area level precomputation
Many fastest path algorithms rely on precomputing a small set of fastest paths in order to improve performance [19, 5, 26]. At one end of the spectrum we can use algorithms such as Floyd Warshall [9] that precompute the shortest path between every pair of nodes. In this case fastest path queries can be answered in O(1) lookups, but we need O(n^{2}) space for storing those pairs, and O(n^{3}) time for the initial computation. At the other end of the spectrum we can per form no precomputation and dynamically find the shortest path using an algorithm such as A∗ [16]. In between these two extremes we have several algorithms that do hierarchi cal decomposition of the original graph, and precompute a subset of paths that are helpful in connecting different areas in the graph [19, 5].
Most methods that do fastest path precomputation as sume that there is a unique path (or several but equally attractive, and thus undistinguishable) between any two nodes. When edge speed is a function of factors such as time, weather, or road conditions, the fastest path between two nodes may be different for different times and condi tions, e.g., it may differ when we leave at 8:00 am than at 10:00 am, or if we have to drive through icy roads or dry roads. In the presence of variable edge speeds, precomputed fastest paths need to be annotated with the set of conditions under which they are valid.
Definition 6.1. We say that fastest path p between nodes
799
(s, e) is conditionally stable for starting time interval t_{1}, t_{2} given condition c = (d_{1}, . . . , d_{n}), where each d_{i }is a value for factor D_{i }or the special value * to indicate any value for D_{i }is valid, if duration(p) is minimal among all possible paths between (s, e), when the starting time is between t_{1 }and t_{2}, and when condition (d_{1}, . . . , d_{n}) is forecasted for all edges along paths connecting s and e.
The benefit of precomputing a path between two nodes is proportional to the number of path queries for which the path can be used to speedup the fastest path algorithm. We can check two conditions to determine benefit. First, how many fastest path queries will go through nodes of the precomputed path. For example, precomputing the fastest path between two houses in an area has little value, as it will likely help a single query, while precomputing a path be tween two important intersections may benefit many queries. Second, how stable is the path, i.e., for how long, and for how many speed patterns is the path a fastest path. For example, precomputing a path that is valid only between 10:07am and 10:11am has less value than precomputing a path that applies for the entire rush hour interval, 8:00am

10:00am. A sensible strategy is thus to precompute high
benefit value paths.
A naive method to determine what paths to precompute would be to list every fastest path in the road network, un der every possible condition, and rank them according to benefit value. This strategy would yield optimal results but it is clearly unfeasible as the number of paths and condi tions to consider is enormous. We propose an area level precomputation strategy where we compute certain fastest paths only within the nodes inside the area. We first define a minimum level l_{m }in the area hierarchy at which path pre computation will be conducted. Within each area at level l_{m }we choose the set of nodes S_{p }of class l_{m }+ 1 (one level smaller than the borders of the area), and class l_{m}, and pre compute fastest paths between nodes in S_{p}. For this step, we guide our precomputation by the set of speed rules mined for the area, and limit the analysis paths involving edges with few speed rules. We can handle time intervals by using the algorithm presented in [20], which efficiently computes the set of fastest paths between two nodes for different time intervals.
6.2
Small road upgrades
The main assumption of hierarchical path finding algo rithms is that drivers take the largest road available in or der to reach their destination, and thus the search space for route finding can be significantly reduced. Our observation is that although this strategy is generally true, there is an important exception, if there is a small road that is faster than a large road, people will take it. For example, people driving to or from cities usually do it through highways, but during rush hour highways can become so congested that taking smaller roads yields shorter travel times. If we ig nore such cases we may incur significant error.
Our strategy in dealing with this problem will be to up grade certain edges inside an area if under some driving con ditions they have a significantly higher speed than the edges at the area borders under the same driving conditions. For the above example, we would upgrade the internal edges in the area where the city resides, to the level of highways but only for the driving condition of rush hour. This way we can still compute most routes considering only highways,