Partitioning road networks using density peak graphs: Efficiency vs. accuracy. (March 2017)

• Record Type: Journal Article
• Authors: Anwar, Tarique; Liu, Chengfei; Vu, Hai L.; Leckie, Christopher
• Is Part Of: Information systems. Volume 64(2017)
• Page Start: 22
• Page End: 40
• Publication Date: 2017-03
• Subjects: Spatial partitioning -- Road networks -- Spectral clustering -- Density peak graph; Database management -- Periodicals; Electronic data processing -- Periodicals; Bases de données -- Gestion -- Périodiques; Informatique -- Périodiques; Database management; Electronic data processing; Periodicals; 005.7
• DOI: 10.1016/j.is.2016.09.006
• Languages: English
• ISSNs: 0306-4379

Abstract

Abstract: Road traffic networks are rapidly growing in size with increasing complexities. To simplify their analysis in order to maintain smooth traffic, a large urban road network can be considered as a set of small sub-networks, which exhibit distinctive traffic flow patterns. In this paper, we propose a robust framework for spatial partitioning of large urban road networks based on traffic measures. For a given urban road network, we aim to identify the different sub-networks or partitions that exhibit homogeneous traffic patterns internally, but heterogeneous patterns to others externally. To this end, we develop a two-stage algorithm (referred asFaDSPa ) within our framework. It first transforms the large road graph into a well-structured and condensed density peak graph (DPG) via density based clustering and link aggregation using traffic density and adjacency connectivity, respectively. Thereafter we apply our spectral theory based graph cut (referred as α -Cut) to partition the DPG and obtain the different sub-networks. Thus the framework applies the locally distributed computations of density based clustering to improve efficiency and the centralized global computations of spectral clustering to improve accuracy. We perform extensive experiments on real as well as synthetic datasets, and compare its performance with that of an existing road network partitioning method. Our results show that the proposed method outperforms the existing normalized cut based method for small road networks and provides impressive results for much larger networks, where other methods may face serious problems of time and space complexities. Abstract : Highlights: An effective as well as efficient road network partitioning framework using both density and spectral based clustering. A fast density-based road network partitioning method FaDPa (extended to FaDPa+) is developed. Using FaDPa, a spectral based method FaDSPa is developed for partitioning small as well as large road networks. The complete derivation to optimize the α -Cut objective function (proposed in Anwar et al., EDBT 2014) is presented. Extensive experiments are conducted on real as well as synthetic datasets.