OPTIMIZING PATH QUERY PERFORMANCE: GRAPH CLUSTERING STRATEGIES

Many geographic information system (GIS) applications require path queries over transportation networks (TNs). Such networks, usually modeled as graphs composed of nodes and links and represented as link relations, can be very large and often need to be stored on secondary storage devices. Path query computation over such large persistent networks amount to high I/O costs due to having to repeatedly bring in links from the link relation from secondary storage into the main memory buffer to process. In this paper, a comparative experimental evaluation of alternative graph clustering solutions is presented to demonstrate their effectiveness in path query processing over TNs. A novel clustering technique, called spatial partition clustering (SPC), is developed that exploits unique properties of TNs such as spatial coordinates and high locality. Other promising candidates for clustering optimizations are identified from the literature and are then fine-tuned to optimize their I/O behavior for path query processing. An experimental evaluation of the performance of these graph-clustering techniques is performed that considers variations in parameters such as memory buffer size, length of the paths, locality, and out-degree. These experimental results are used as the foundation to establish guidelines to select the best clustering technique based on the type of networks. It was found that the SPC performs best for the highly interconnected city map; the hybrid approach for random graphs with high locality, and the 2-way partitioning based on the link weights for random graphs with no locality.

• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/issn/0968090X
• Corporate Authors:

  Elsevier

  The Boulevard, Langford Lane
  Kidlington, Oxford  United Kingdom  OX5 1GB
• Authors:
  • Huang, Y-W
  • Jing, N
  • Rundensteiner, E A
• Publication Date: 2000-2

Language

• English

Media Info

• Features: Figures; References;
• Pagination: p. 381-408
• Serial:
  • Transportation Research Part C: Emerging Technologies
  • Volume: 8
  • Issue Number: 1
  • Publisher: Elsevier
  • ISSN: 0968-090X
  • Serial URL: http://www.sciencedirect.com/science/journal/0968090X

Subject/Index Terms

• TRT Terms: Geographic information systems; Graph theory; Information processing; Network nodes; Optimization; Roads; Shortest path algorithms
• Uncontrolled Terms: Graph clustering strategies; Path queries; Transportation networks
• Subject Areas: Highways; Planning and Forecasting; I72: Traffic and Transport Planning;

Filing Info

• Accession Number: 00800334
• Record Type: Publication
• Files: TRIS, ATRI
• Created Date: Oct 5 2000 12:00AM