Spatio-temporal Networks
Preface
Acknowledgments
Contents
1 Spatio-temporal Networks: An Introduction
1.1 Spatio-temporal Networks
1.2 Application Domain
1.3 Background Information
2 Time Aggregated Graph: A Model for Spatio-temporal Networks
2.1 Modeling Spatio-temporal Networks
2.1.1 Illustrative Application Domains
2.1.2 Broad Computer Science Challenges
2.2 Basic Concepts
2.2.1 The Conceptual Model
2.2.2 A Logical Data Model
2.2.3 Physical Data Model
2.3 Evaluation and Validation
2.3.1 Representational Comparison: Time Aggregated Graphs Versus Existing Models
2.3.2 Comparison of Storage Costs with Time Expanded Networks
2.4 Summary
3 Shortest Path Algorithms for a Fixed Start Time
3.1 Introduction
3.1.1 Broad Challenges
3.2 Basic Concepts
3.2.1 Classification of Shortest Path Algorithms
3.2.2 Algorithmic Challenges
3.3 Shortest Path Computation for Fixed Start Time
3.3.1 Shortest Path Algorithm for Fixed Start Time in a FIFO Network (SP-TAG)
3.3.2 A Formulation of Shortest Path Algorithm for a Fixed Start Time in a FIFO Network (SP-TAG)
3.4 Shortest Path Algorithm for a Given Start Time in a Non-FIFO Network (NF-SP-TAG)
3.5 Experimental Analysis
3.5.1 Experiment Design
3.5.2 Experimental Results and Analysis
3.6 Summary
4 Best Start Time Journeys
4.1 Introduction
4.2 Basic Concepts
4.2.1 The Conceptual Model
4.2.2 Basic Design Space of Shortest Path Algorithms
4.2.3 Algorithmic Challenges
4.3 Time Iterative SP-TAG (TI_SP-TAG) Algorithm for FIFO Networks
4.4 Best Start Time Shortest Path Algorithms for Non-FIFO Networks
4.4.1 Best Start Time Shortest Path (BEST) Algorithm (Label Correcting Approach)
4.4.2 Best Start Time Algorithm Using ATST (CP-NF-BEST Algorithm)
4.5 Experimental Analysis
4.5.1 Experiment Design
4.5.2 Experimental Results and Analysis
4.6 Summary
5 Spatio-temporal Network Application
5.1 Multimodal Transportation Networks
5.1.1 Modeling Multimodal Networks
5.1.2 Time Aggregated Graph Representation
5.1.3 Routing in Multimodal Networks
5.2 Modeling Sensor Networks
5.2.1 Hotspot Detection
References