Lagrangian Approaches to Storage of Spatio-Temporal Network Datasets

Kwang Soo Yang, Michael R. Evans, Venkata M.V. Gunturi, James M. Kang, Shashi Shekhar

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


Given a spatio-temporal network (STN) and a set of STN operations, the goal of the Storing Spatio-Temporal Networks (SSTN) problem is to produce an efficient method of storing STN data that minimizes disk I/O costs for given STN operations. The SSTN problem is important for many societal applications, such as surface and air transportation management systems. The problem is NP hard, and is challenging due to an inherently large data volume and novel semantics (e.g., Lagrangian reference frame). Related works rely on orthogonal partitioning approaches (e.g., snapshot and longitudinal) and incur excessive I/O costs when performing common STN queries. Our preliminary work proposed a non-orthogonal partitioning approach in which we optimized the LGetOneSuccessor() operation that retrieves a single successor for a given node on STN. In this paper, we provide a method to optimize the LGetAllSuccessors() operation, which retrieves all successors for a given node on a STN. This new approach uses the concept of a Lagrangian Family Set (LFS) to model data access patterns for STN queries. Experimental results using real-world road and flight traffic datasets demonstrate that the proposed approach outperforms prior work for LGetAllSuccessors() computation workloads.

Original languageEnglish (US)
Article number6529086
Pages (from-to)2222-2236
Number of pages15
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number9
StatePublished - Sep 1 2014

Bibliographical note

Publisher Copyright:
© 1989-2012 IEEE.


  • Combinatorial algorithms
  • Combinatorics
  • Data
  • Data Storage Representations
  • Data Structures
  • Database Management
  • Discrete Mathematics
  • Graphs and networks
  • Information Storage
  • Information Storage and Retrieval
  • Information Technology and Systems
  • Languages
  • Mathematics of Computing
  • Query languages
  • Spatial databases
  • Spatial databases and GIS
  • Storage/repositories
  • Systems
  • Temporal databases


Dive into the research topics of 'Lagrangian Approaches to Storage of Spatio-Temporal Network Datasets'. Together they form a unique fingerprint.

Cite this