03-09-2016, 10:36 AM
1452270450-CustomizablePointofInterestQueriesinRoadNetworks.docx (Size: 19.96 KB / Downloads: 4)
Abstract
We present a unified framework for dealing with exact point-of-interest (POI) queries in dynamic continental road networks within interactive applications. We show that partition-based algorithms developed for point-to-point shortest path computations can be naturally extended to handle augmented queries such as finding the closest restaurant or the best post office to stop on the way home, always ranking POIs according to a user-defined cost function. Our solution allows different trade-offs between indexing effort (time and space) and query time. Our most flexible variant allows the road network to change frequently (to account for traffic information or personalized cost functions) and the set of POIs to be specified at query time. Even in this fully dynamic scenario, our solution is fast enough for interactive applications on continental road networks.
Existing System
• The Existing engineering community algorithm has developed methods to rank POIs according to driving times by augmenting hierarchical speedup techniques for point-to-point queries, such as contraction hierarchies (CH) or hub labels (HL).
• These speedup techniques divide the work into two phases. An offline pre-processing phase computes auxiliary data which is used during the online query phase to find the same path as Dijkstra’s algorithm, but much faster.
• Extensions of such methods to POI-related queries use the fact that we are looking for shortest paths only (between the source and a subset of the available POIs), and that any shortest path must pass through a restricted set of “important” nodes, or hubs.
• An indexing step can associate POI information with these hubs, allowing for quick queries.
• The classical acceleration technique for computing shortest paths in road networks has a long history, but it has often been dismissed as uncompetitive with state-of-the-art hierarchical methods.
• Disadvantages: These methods work reasonably well, but have major drawbacks, including nontrivial preprocessing effort and excessive space requirements. Most importantly, hierarchical methods are not robust to changes in the cost function: even small changes (such as setting a high cost for making a U-turn, i.e., turning into the opposite direction on the same road segment) can have a significant adverse effect on their performance.
Proposed System
• Our proposed algorithms that work in up to four phases, each potentially taking the outputs of previous phases as additional inputs.
• The first phase is metric-independent preprocessing, which takes as input only the graph topology.
• The second phase, customization, takes as input the metric (cost function) that defines the cost of each arc.
• The third phase, selection (or indexing), processes the set P of candidate POIs, given k.
Finally, the query phase takes as input a source s (and potentially a target t) and computes the best POIs among those in P. Some algorithms may conflate two or more phases into one.
System Requirements
Software Requirements
• Operating System : Windows 7
• Programming Package : Net Beans IDE 7.3.1
• Coding Language : JDK 1.7
• Database : Mysql
Hardware Requirements
• Processor Type : Pentium IV
• Speed : 2.4 GHZ
• RAM : 1 GB
• Hard disk : 80 GB
Modules
1) Graph Topology Formation
2) Metric-Independent Preprocessing
3) Customization
4) Queries
GRAPH TOPOLOGY FORMATION:
• A road network is usually modeled as a directed graph G =(V, A), where each vertex v is belong into V represents an intersection of the road network and each arc (v, w) is belong into A represents a road segment.
• A metric (or cost function) l : A --> N maps each arc to a positive length (or cost). For a more realistic model, we also take turn costs (and restrictions) into account.
• We think of each vertex v as having one entry point for each of its incoming arcs, and one exit point for each out-going arc.
• We extend the concept of metric by also associating a turn table T v to each vertex v.
METRIC-INDEPENDENT PREPROCESSING:
• The first phase is metric-independent preprocessing, which takes as input only the graph topology.
• Preprocessing takes as input an unweighted version of the input graph (its vertices and arcs), partitions it, and creates the topology of the over-lay graph.
• The preprocessing stage defines a multilevel overlay and builds auxiliary data structures. The preprocessing phase of CRP uses PUNCH, a graph-partitioning heuristic tailored to road networks, to create a multilevel partition.
• Given an unweighted graph and a bound U, PUNCH splits the graph into cells with at most U vertices while minimizing the number of arcs between cells. It first uses minimum s-t cut computations to identify natural cuts (such as bridges and mountain passes) that are common in road networks, and contracts all other edges; it then runs heavy heuristics on the shrunk graph.
• This results in partitions (for the original graph) with much fewer boundary vertices than grid partitions.
CUSTOMIZATION:
• During the customization stage, CRP computes the lengths of the shortcuts on the overlay.
• A shortcut (p, q) within a cell C represents the shortest path (restricted to C) between p and q.
• To process each cell, the customization phase must compute the distances between each entry point and each exit point.
QUERIES:
• We now show how to generalize the multilevel approach to deal with queries involving more than two endpoints (s and t).
• In particular, we consider generic one-to-many, many-to-many queries and finding closest POIs.