Spatio-Temporal Graph Data Analytics (eBook)
X, 100 Seiten
Springer International Publishing (Verlag)
978-3-319-67771-2 (ISBN)
This book highlights some of the unique aspects of spatio-temporal graph data from the perspectives of modeling and developing scalable algorithms. The authors discuss in the first part of this book, the semantic aspects of spatio-temporal graph data in two application domains, viz., urban transportation and social networks. Then the authors present representational models and data structures, which can effectively capture these semantics, while ensuring support for computationally scalable algorithms.
In the first part of the book, the authors describe algorithmic development issues in spatio-temporal graph data. These algorithms internally use the semantically rich data structures developed in the earlier part of this book. Finally, the authors introduce some upcoming spatio-temporal graph datasets, such as engine measurement data, and discuss some open research problems in the area.
This book will be useful as a secondary text for advanced-level students entering into relevant fields of computer science, such as transportation and urban planning. It may also be useful for researchers and practitioners in the field of navigational algorithms.
Preface 5
Acknowledgements 7
Contents 8
1 Introduction 10
1.1 Urban Road Networks 10
1.2 Social Networks 12
2 Fundamental Concepts for Spatio-Temporal Graphs 14
2.1 Road Network Datasets 14
2.1.1 Key Concepts in Road Network Datasets 15
2.1.2 Data-Collection vs Querying Reference Frame in Road Networks 17
2.2 Social Network Datasets 18
2.2.1 Key Concepts in Social Network Datasets 18
2.3 Conclusion 20
3 Representational Models for Spatio-Temporal Graphs 21
3.1 Models at Conceptual Level 21
3.1.1 Lagrangian Xgraphs 24
3.2 Data Structures for Algorithms 26
3.2.1 Temporal Digraphs 27
3.2.2 Temporal Digraphs for Holistic Properties and TurnDelays 29
3.3 Conclusion 31
4 Fastest Path for a Single Departure-Time 32
4.1 Problem Definition 32
4.1.1 Important Considerations 33
4.2 Dijkstra's Algorithm for the Fastest Path Problem 35
4.2.1 Latest Departure Path Problem 37
4.3 A* Search for the Fastest Path Problem 39
4.3.1 Using Lower Bound on Travel-Time 39
4.3.2 Using a Hierarchical Lower Bound on Travel-Time 40
4.4 Bi-directional Search for the Fastest Path Problem 43
4.5 Adapting Fastest Path Algorithm for Centrality Metrics 46
4.6 Conclusions 47
5 Advanced Concepts: Critical Time Point Based Approaches 49
5.1 Formal Problem Definition 51
5.2 Computational Structure of the ALSP Problem 52
5.3 Critical Time-Point Based ALSP Solver (CTAS) 54
5.3.1 CTAS Algorithm 54
5.3.2 Execution Trace 56
5.4 Correctness and Completeness CTAS Algorithm 58
5.5 Experimental Evaluation of CTAS 60
5.6 Conclusions 63
6 Advanced Concepts: Bi-Directional Search for Temporal Digraphs 64
6.1 Computational Structure of Temporal Bi-Directional Search 65
6.1.1 Forward Search Basic Concepts 66
6.1.2 Trace Search Basic Concepts 68
6.2 Temporal Bi-Directional Search for ALSP Problem 70
6.2.1 BD-CTAS Algorithm 73
6.3 Analytical Analysis of Temporal Bi-Directional Search 78
6.3.1 Correctness of BD-CTAS Algorithm 78
6.4 Conclusion 80
7 Knowledge Discovery: Temporal Disaggregation in Social Interaction Data 81
7.1 Basic Concepts and Problem Definition 82
7.2 Formation of Temporal Paths in TDSN 84
7.3 Community Identification in TDSNs 86
7.3.1 Approach for the Detection of Transient Communities 87
7.3.2 Running Example for Transient Community Detection 87
7.4 Node Influence Measures in TDSNs 89
7.4.1 Temporal Katz Centrality 89
7.5 Case Study on TDSN 90
7.5.1 Metric used for Experimentation 91
7.5.2 Experiment 1 92
7.5.3 Experiment 2 93
7.5.4 Experiment 3 94
7.6 Conclusion 95
8 Trend Topics: Engine Data Analytics 96
8.1 Statistically Significant Hot Route Discovery 96
8.1.1 Potential Next Steps 98
8.2 Conclusion 99
References 100
Erscheint lt. Verlag | 15.12.2017 |
---|---|
Zusatzinfo | X, 100 p. 61 illus., 30 illus. in color. |
Verlagsort | Cham |
Sprache | englisch |
Themenwelt | Mathematik / Informatik ► Informatik |
Technik | |
Wirtschaft | |
Schlagworte | Dynamic Social Networks • Geographic information science • Graph Algorithms • road navigation • road networks • shortest path algorithms • spatial databases • spatial networks • spatio-temporal networks • time-varying graphs • Transportation Networks • Urban Transportation |
ISBN-10 | 3-319-67771-3 / 3319677713 |
ISBN-13 | 978-3-319-67771-2 / 9783319677712 |
Haben Sie eine Frage zum Produkt? |
Größe: 3,2 MB
DRM: Digitales Wasserzeichen
Dieses eBook enthält ein digitales Wasserzeichen und ist damit für Sie personalisiert. Bei einer missbräuchlichen Weitergabe des eBooks an Dritte ist eine Rückverfolgung an die Quelle möglich.
Dateiformat: PDF (Portable Document Format)
Mit einem festen Seitenlayout eignet sich die PDF besonders für Fachbücher mit Spalten, Tabellen und Abbildungen. Eine PDF kann auf fast allen Geräten angezeigt werden, ist aber für kleine Displays (Smartphone, eReader) nur eingeschränkt geeignet.
Systemvoraussetzungen:
PC/Mac: Mit einem PC oder Mac können Sie dieses eBook lesen. Sie benötigen dafür einen PDF-Viewer - z.B. den Adobe Reader oder Adobe Digital Editions.
eReader: Dieses eBook kann mit (fast) allen eBook-Readern gelesen werden. Mit dem amazon-Kindle ist es aber nicht kompatibel.
Smartphone/Tablet: Egal ob Apple oder Android, dieses eBook können Sie lesen. Sie benötigen dafür einen PDF-Viewer - z.B. die kostenlose Adobe Digital Editions-App.
Zusätzliches Feature: Online Lesen
Dieses eBook können Sie zusätzlich zum Download auch online im Webbrowser lesen.
Buying eBooks from abroad
For tax law reasons we can sell eBooks just within Germany and Switzerland. Regrettably we cannot fulfill eBook-orders from other countries.
aus dem Bereich