Optimizing path query performance: Graph clustering strategies

Abstract

Path queries over transportation networks are operations required by many Geographic Information Systems applications. Such networks, typically modeled as graphs composed of nodes and links and represented as link relations, can be very large and hence often need to be stored on secondary storage devices. Path query computation over such large persistent networks amounts 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 for processing. This paper is the first to present a comparative experimental evaluation of alternative graph clustering solutions in order to show their effectiveness in path query processing over transportation networks. Clustering optimization is attractive because it does not incur any run-time cost, requires no auxiliary data structures, and is complimentary to many of the existing solutions on path query processing. In this paper, we develop a novel clustering technique, called spatial partition clustering (SPC), that exploits unique properties of transportation networks such as spatial coordinates and high locality. We identify other promising candidates for clustering optimizations from the literature, such as two-way partitioning and approximate topological clustering. We fine-tune them to optimize their I/O behavior for path query processing. Our experimental evaluation of the performance of these graph clustering techniques using an actual city road network as well as randomly generated graphs considers variations in parameters such as memory buffer size, length of the paths, locality, and out-degree. Our experimental results are the foundation for establishing guidelines to select the best clustering technique based on the type of networks. We find that our SPC performs the best for the highly interconnected city map; the hybrid approach for random graphs with high locality; and the two-way partitioning based on link weights for random graphs with no locality. (C) 2000 Elsevier Science Ltd. All rights reserved.