Spatio-temporal Networks_ Modeling and Algorithms [George & Kim 2012-09-05].pdf

(1372 KB) Pobierz
SpringerBriefs in Computer Science
Series Editors
Stan Zdonik
Peng Ning
Shashi Shekhar
Jonathan Katz
Xindong Wu
Lakhmi C. Jain
David Padua
Xuemin Shen
Borko Furht
V. S. Subrahmanian
Martial Hebert
Katsushi Ikeuchi
Bruno Siciliano
For further volumes:
http://www.springer.com/series/10028
Betsy George Sangho Kim
•
Spatio-temporal Networks
Modeling and Algorithms
123
Betsy George
Oracle Inc.
Nashua, NH
USA
Sangho Kim
Esri
Redlands, CA
USA
ISSN 2191-5768
ISBN 978-1-4614-4917-1
DOI 10.1007/978-1-4614-4918-8
ISSN 2191-5776 (electronic)
ISBN 978-1-4614-4918-8 (eBook)
Springer New York Heidelberg Dordrecht London
Library of Congress Control Number: 2012943367
Ó
The Author(s) 2013
This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of
the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations,
recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or
information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar
methodology now known or hereafter developed. Exempted from this legal reservation are brief
excerpts in connection with reviews or scholarly analysis or material supplied specifically for the
purpose of being entered and executed on a computer system, for exclusive use by the purchaser of the
work. Duplication of this publication or parts thereof is permitted only under the provisions of
the Copyright Law of the Publisher’s location, in its current version, and permission for use must always
be obtained from Springer. Permissions for use may be obtained through RightsLink at the Copyright
Clearance Center. Violations are liable to prosecution under the respective Copyright Law.
The use of general descriptive names, registered names, trademarks, service marks, etc. in this
publication does not imply, even in the absence of a specific statement, that such names are exempt
from the relevant protective laws and regulations and therefore free for general use.
While the advice and information in this book are believed to be true and accurate at the date of
publication, neither the authors nor the editors nor the publisher can accept any legal responsibility for
any errors or omissions that may be made. The publisher makes no warranty, express or implied, with
respect to the material contained herein.
Printed on acid-free paper
Springer is part of Springer Science+Business Media (www.springer.com)
To the loving memory of my grandfather
for his unconditional love and relentless
encouragement!!
Betsy George
To my daughter Ellie and wife Taeeun
in appreciation of their patience and
understanding
Sangho Kim
Preface
Spatio-temporal networks are spatial networks whose topology and/or attributes
change with time. These are encountered in many critical areas of everyday life
such as transportation networks, electric power distribution grids, and social net-
works of mobile users. With the advances in technology, monitoring the temporal
changes of such networks is becoming increasingly easier. For example, the
increasing use of traffic sensors on transportation networks generates large
volumes of data such as congestion levels and it becomes important to incorporate
these data into data models and algorithms that deal with spatio-temporal
networks.
A spatio-temporal network (STN) typically consists a finite set of nodes with
location attributes, relationships between nodes (aka edges), and time-dependent
attributes associated with nodes and relationships. STN modeling and computa-
tions raise significant challenges. The model must meet the conflicting require-
ments of simplicity and adequate support for efficient algorithms. Another
challenge is to address the change in semantics of common graph operations such
as shortest path computation, when temporal dimension is added. For example,
shortest path between a start and an end location might be different at different
times of day. Also paradigms (e.g., dynamic programming) used in algorithm
design may be ineffective since their assumptions (e.g., stationary ranking of
candidates) may be violated by the dynamic nature of STNs.
In recent years, STNs have attracted considerable attention in reserach. New
representations have been proposed along with algorithms to perform key STN
operations, while accounting for their time dependence. Designing a STN database
would require the development of data models, query languages, indexing methods
to efficiently represent, query, store, and manage time-variant properties of the
network.
This book explores this design at conceptual, logical, and physical level.
Models used to represent STNs are explored and analyzed. STN operations with
emphasis on their altered semantics with addition of temporal dimension, are
addressed, illustrating the capability toward answering interesting questions. For
example, it is possible to answer queries such as, When is the best time to start so
vii

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin