Transcript ppt
Adaptive Fastest Path Computation on a Road Network : A Traffic Mining Approach Hector Gonzalez Jiawei Han Xiaolei Li Margaret Myslinska John Paul Sondag Department of Computer Science University of Illinois at Urbana-Champaign ---------------Presented by Dongmin Shin IDS Lab., SNU, Korea 2008.01.11. Index Overview Contribution Problem Definition Traffic Database Road Network Partitioning Traffic Mining Pre-computation and Upgrades Fastest Path Computation Experimental Evaluation Conclusion Center for E-Business Technology Copyright 2006 by CEBT Overview Problem of Previous System MapQuest, MapPoint, Google Maps a very simple model for road speeds – Constant speeds determined by their road class Not considering a multitude of other factors that are very important – – Driving patterns ex) Nice and quick route, not a high crime area, weather, etc.. Instead of modeling all such factors explicitly, mining historic traffic data and learning from the past driving behavior Speed patterns ex) the time of departure, weather conditions, whether you are qualified to drive on a car pool lane, etc.. Center for E-Business Technology Copyright 2006 by CEBT Term Definition Road network Speed pattern Driving pattern Edge forecast model F(edge_id, t) returns Query Center for E-Business Technology Copyright 2006 by CEBT Traffic Database Center for E-Business Technology Copyright 2006 by CEBT Road Network Partitioning Road networks are organized around a well-defined hierarchy of roads Center for E-Business Technology Copyright 2006 by CEBT Traffic Mining Speed pattern mining Multiple factors – Weather, time of day, vehicle class and road construction, etc.. Ex) if area = a1 and weather = icy and time = rush hour then speed = ¼ X base speed Center for E-Business Technology Copyright 2006 by CEBT Traffic Mining Driving pattern mining Frequent pattern mining 1. Define a minimum support level 2. Go thorough the traffic database identifying frequent edges 3. Individual vehicle data 4. Longer frequent path segments can be mined Problem of uniform minimum support level – May filter many important local reads or may keep infrequently traveled high-level roads – Using a minimum support relative to the traffic volume of each edge class in the area Center for E-Business Technology Copyright 2006 by CEBT Pre-computation and Upgrades Area level pre-computation May be different for different times and conditions – Need to be annotated with the set of conditions Two conditions to determine benefit – How many fastest path queries will go through nodes of the precomputed path – How stable is the path Apply limit to the area level Center for E-Business Technology Copyright 2006 by CEBT Pre-computation and Upgrades Small road upgrades Main assumption – Drivers take the largest road available An important exception – If there is a small road that is faster than a large road, people will take it Upgrade certain edges inside an area if under some driving conditions they have a significantly higher speed than the edges at the area borders under the same driving conditions Only when absolutely necessary Center for E-Business Technology Copyright 2006 by CEBT Fastest Path Computation Computed route has the following properties Supported by the historical driver behavior Go through the largest possible roads Account for all relevant factors affecting driving speed Before running, following components have been computed Road network has already been partitioned. Speed patterns have been mined. Driving patterns have been mined. Pre-computed a set of area-level fastest paths Upgraded internal roads Center for E-Business Technology Copyright 2006 by CEBT Fastest Path Computation Key concepts of the algorithm 1. For each path, keep g(n) the current cost and h(n) the expected cost 2. At each step, pick the node with lowest g(n) + h(n) value that is frequent 3. Using the area hierarchy tree T Ascending phase until reaching the lowest common ancestors Descending phase otherwise 4. In ascending phase, only consider lower-leveled or equalleveled neighbor In descending phase, otherwise 5. Whenever inserting a new path, update g(n) and h(n) Center for E-Business Technology Copyright 2006 by CEBT Fastest Path Computation Example In order to simplify, 1. Ignoring edge frequency 2. No pre-computed paths The lowest common ancestor Center for E-Business Technology Copyright 2006 by CEBT Fastest Path Computation Online path re-computation The predictor function F is used to estimate driving conditions throughout the entire trip – Initial estimate may be wrong – Ex) weather, road closure, accident In an online navigation system, – Applying the algorithm with a starting node changed to the current position Center for E-Business Technology Copyright 2006 by CEBT Experimental Evaluation Data Synthesis Varying in areas, speed conditions, vehicles, weather factors Three methods – A* : correctness baseline. Searching for all nodes – Hier : adaptive fastest path algorithm w/o pre-computation and upgrading – Adapt : adaptive fastest path algorithm proposed in this paper Center for E-Business Technology Copyright 2006 by CEBT Experimental Evaluation Query Length and Upgraded Paths Center for E-Business Technology Copyright 2006 by CEBT Experimental Evaluation Area Pre-computation Center for E-Business Technology Road Network Size Copyright 2006 by CEBT Contribution Road hierarchy-based partitioning Natural hierarchy to partition the network into semantically meaningful areas Essential for driving pattern mining and adaptive fastest path pre-computation Speed rule mining A set of concise rules In conditions c for edge e then speed factor = f Driving pattern mining Mining frequently traveled edges or edge-sequences Frequent path-segment at the area level Center for E-Business Technology Copyright 2006 by CEBT Contribution Adaptive pre-computation Pre-computing a subset of fastest paths in order to speedup path computation An area-level pre-computation strategy Road upgrading Support for some smaller roads should be upgraded People usually drive through the largest possible roads available Center for E-Business Technology Copyright 2006 by CEBT