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:
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