Abstract
The rapid global migration of people towards urban areas is multiplying the traffic volume on urban road networks. As a result these networks are rapidly growing in size, in which different sub-networks exhibit distinctive traffic flow patterns. In this paper, we propose a scalable framework for traffic congestion-based spatial partitioning of large urban road networks. It aims to identify different sub-networks or partitions that exhibit homogeneous traffic congestion patterns internally, but heterogenous to others externally. To this end, we develop a two-stage procedure within our framework that first transforms the large road graph into a well-structured and condensed supergraph via clustering and link aggregation based on traffic density and adjacency connectivity, respectively. We then devise a spectral theory based novel graph cut (referred as α-Cut) to partition the supergraph and compare its performance with that of an existing method for partitioning urban networks. Our results show that the proposed method outperforms the normalized cut based existing method in all the performance evaluation metrics for small road networks and provides good results for much larger networks where other methods may face serious problems of time and space complexities.
Original language | English |
---|---|
Title of host publication | Advances in Database Technology - EDBT 2014 |
Subtitle of host publication | 17th International Conference on Extending Database Technology, Proceedings |
Publisher | OpenProceedings |
Pages | 343-354 |
Number of pages | 12 |
ISBN (Electronic) | 9783893180653 |
DOIs | |
Publication status | Published - 2014 |
Externally published | Yes |
Event | Extending Database Technology 2014 - Athens, Greece Duration: 24 Mar 2014 → 28 Mar 2014 Conference number: 17th https://openproceedings.org/html/pages/2014_edbt.html (Proceedings) |
Conference
Conference | Extending Database Technology 2014 |
---|---|
Abbreviated title | EDBT 2014 |
Country/Territory | Greece |
City | Athens |
Period | 24/03/14 → 28/03/14 |
Other | EDBT/ICDT 2014 Joint Conference March 24-28, 2014 - Athens, Greece EDBT: 17th International Conference on Extending Database Technology ICDT: 17th International Conference on Database Theory, |
Internet address |
|
Keywords
- Graph partitioning
- Road networks
- Spectral clustering