IMPROVING PATH QUERY PERFORMANCE IN PGROUTING USING A MAP GENERALIZATION APPROACH

International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences

Sankepally, R. R.^1¹ 

[1] Lab for Spatial Informatics, International Institute of Information Technology, Gachibowli, Hyderabad, India^1

关键词: pgRouting;    Road Networks;    Skeletal Model;    Skeleton;    Shortest Path;    Map Generalization;    Zones;    Path Computation;   

DOI  :  10.5194/isprs-archives-XLII-4-W8-191-2018

学科分类：地球科学(综合)

来源: Copernicus Publications

【 摘 要 】

pgRouting library provides functions to compute shortest path between any two points of a road network which is of great demand and also a topic of interest in the field of GIS, graph theory and transportation. To compute path in a road network, pgRouting functions process the entire road network which is a major bottleneck when it comes to routing in large road networks leading to the requirement of large server resources. A reduction/compression in the input network that is to be processed for path computation would improve the performance of pgRouting. In this study a map generalization based network model is proposed which extracts a significantly smaller subset of the road network aka skeleton which further used to divide the network into zones, that shall be selectively used in path computation. This results in processing a much smaller part of the network to compute path between any two points leading to an overall improvement in query performance of pgRouting when computing path, especially on large road networks. As part of assessment of this approach and its applicability to large road networks, the paper presents an in-depth analysis of the trade-offs between deviation in computed path and the performance gain in terms of space and time on road networks of varying sizes and topology to get a better understanding for both providing a sound proof of the utility of the proposed method and also to show its implementability within the current model of pgRouting or any other routing platforms.

【 授权许可】

CC BY