car id 1 2 3 4 ...
path (edge id, start time, end time), . . .
, 1 0 , 1 5 ) ( e 2 , 1 5 , 2 3 ) ( e 7 , 2 3 , 2 9 ) , 2 0 , 2 9 ) ( e 1 , 2 9 , 3 , 9, 16)(e2, 16, 22) , 10, 11)(e2, 11, 17)(e8, 17, 20) 3 )
Table 2: Traffic Database
the form (edge id, start time, end time), where start time is the time when the car entered the edge, and end time is the time when the car exited the edge. For lack of space we do not show observed driving conditions at path stages.
In the above example we have that support(e1) = 3, support(e2) = 3, support(e7) = 1, etc.
ROAD NETWORK PARTITIONING
Road networks are organized around a well-defined hi- erarchy of roads. An example of a typical road hierarchy is the road network of the United States, where highways connect multiple large regions, interstate roads connect lo- cations within a region, multi-lane roads connect city areas, and small roads reach into individual houses. Information on road categories is available for both the Unites States where roads are classified into 4 levels, and for the Euro- pean Union where roads are classified at a higher level of detail into 13 levels. For our San Joaquin example in Figure 1, we draw roads at the two highest levels in bold, and all other roads in gray.
Most existing work on hierarchical shortest path algo- rithms assume that a partition of the road network is pro- vided, or that the partition can be generated by imposing a fixed grid over the network [18, 19]. Other approaches such as  use the idea of Highways to divide the graph, but their definition of Highway is graph theoretic, designed to preserve optimality of routes, and does not necessarily match the road size classification. We believe that the nat- ural partition induced by the road hierarchy itself can be used to divide the network into semantically meaningful ar- eas, with well defined driving and speed patterns. This idea can provide a significant speedup for fastest path queries when compared to arbitrary partitioning methods such as the grid-based one.
The partitioning process can first use the highest-level roads to divide the road network into large regions enclosed by such roads. Each large region can in turn be further sub- divided by using the next lower-level roads. This process can be recursively applied until an area contains only roads at the lowest level of the hierarchy, or until a threshold on the minimum number of nodes in an area is reached.
Definition 4.1. Given a road network G(V, E), with pre- defined edges classes class(e) for each edge e, the class of a node n denoted class(n), is defined as the biggest (lowest class number) of any incoming or outgoing edge to/from n.
The definition indicates that for an intersection of two highway segments with a small road (i.e., the entry point into the highway), the intersection will be at the level of the highway, not at the level of the small incoming road.
Definition 4.2. Given edges of class k, a partition P (k) o f a r o a d n e t w o r k G ( V , E ) d i v i d e s n o d e s i n t o a r e a s V k 1 , . . . , V k n , w i t h V = i V k i . A r e a s a r e d e fi n e d a s a l l s e t s o f s t r connected components after the removal of nodes with class(n) < k from G. A node n, with class(n) > k in strongly con- o n g l y n e c t e d c o m p o n e n t i , b e l o n g s t o a r e a V k i , a n d i t i s s a interior to the area. A node n, with class(n) ≤ k belongs to i d t o b e a l l a r e a s V k i s u c h t h a t t h e r e i s a n e d g e e , w i t h c l a s s ( e ) > k , c o n n e c t i n g n t o n a n d n ∈ V k i , s u c h n o d e s a r e border nodes of all the areas they connect to. s a i d t o b e
Given a road hierarchy with l levels, we can construct a hierarchy of areas as a tree of depth l − 1: The root node represents the entire road network, children of the root node represent the areas formed by partitioning the root using level-1 edges, the nodes in each area form a graph them- selves, and all the edges from E connecting two nodes in an area are said to belong to the area. A node at level-k results from the partition of its parent node using the edges of class k − 1. Notice that according to this convention, road class 1 is the largest, and road class l the smallest.
Figure 2: San Joaquin Partitioned Map
Figure 2 presents the partition of the road network for San Joaquin, CA. We have numbered each large area with two numbers a : b, a is the area number when roads of level 1 are used, and b is the subarea of a when roads of level 2 are used to subdivide a. We can see in the upper left corner that we have not marked individual areas, the reason is that there are quite a few strongly connected components in this region, and each has its own area, i.e., nodes inside each component cannot reach nodes in other components except by going through border nodes. We have marked one such component in the figure by encircling it with a dotted line to illustrate the point. As we can see the partition is quite natural. We also experimented with partitioning the entire road network for the San Francisco Bay Area, and for the complete state of Illinois among others (Figures not