Not logged in.
Quick Search - Contribution
Contribution Details
| Type | Conference or Workshop Paper |
| Scope | Discipline-based scholarship |
| Published in Proceedings | Yes |
| Title | Scalable computation of Isochrones with network expiration |
| Organization Unit | |
| Authors |
|
| Editors |
|
| Presentation Type | paper |
| Item Subtype | Original Work |
| Refereed | Yes |
| Status | Published in final form |
| Language |
|
| ISBN | 978-3-642-31235-9 |
| ISSN | 0302-9743 |
| Page Range | 526 - 543 |
| Event Title | 24th International Conference on Scientific and Statistical Database Management, SSDBM 2012 |
| Event Type | conference |
| Event Location | Chania, Crete, Greece |
| Event Start Date | June 25 - 2012 |
| Event End Date | June 27 - 2012 |
| Series Name | Lecture Notes in Computer Science |
| Number | 7338 |
| Place of Publication | Heidelberg |
| Publisher | Springer |
| Abstract Text | An isochrone in a spatial network is the possibly disconnected set of all locations from where a query point is reachable within a given time span and by a given arrival time. In this paper we propose an efficient and scalable evaluation algorithm, termed (MINEX), for the computation of isochrones in multimodal spatial networks with different transportation modes. The space complexity of MINEX is independent of the network size and its runtime is determined by the incremental loading of the relevant network portions. We show that MINEX is optimal in the sense that only those network portions are loaded that eventually will be part of the isochrone. To keep the memory requirements low, we eagerly expire the isochrone and only keep in memory the minimal set of expanded vertices that is necessary to avoid cyclic expansions. The concept of expired vertices reduces MINEX’s memory requirements from O(|Viso|) to O(|Viso|) for grid and O(1) for spider networks, respectively. We show that an isochrone does not contain sufficient information to identify expired vertices, and propose an efficient solution that counts for each vertex the outgoing edges that have not yet been traversed. A detailed empirical study confirms the analytical results on synthetic data and shows that for real-world data the memory requirements are very small indeed, which makes the algorithm scalable for large networks and isochrones. |
| Related URLs | |
| Digital Object Identifier | 10.1007/978-3-642-31235-9_35 |
| Other Identification Number | merlin-id:7421 |
| PDF File |
Download from ZORA
|
| Export |
BibTeX
EP3 XML (ZORA)
|