A lagrangian approach for storage of Spatio-Temporal Network datasets: A summary of results

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations

Abstract

Given a set of operators and a spatio-temporal network, the goal of the Storing Spatio-Temporal Networks (SSTN) problem is to produce an efficient data storage method that minimizes disk I/O access costs. Storing and accessing spatio-temporal networks is increasingly important in many societal applications such as transportation management and emergency planning. This problem is challenging due to strains on traditional adjacency list representations when storing temporal attribute values from the sizable increase in length of the time-series. Current approaches for the SSTN problem focus on orthogonal partitioning (e.g., snapshot, longitudinal, etc.), which may produce excessive I/O costs when performing traversal-based spatio-temporal network queries (e.g., route evaluation, arrival time prediction, etc) due to the desired nodes not being allocated to a common page. We propose a Lagrangian-Connectivity Partitioning (LCP) technique to efficiently store and access spatio-temporal networks that utilizes the interaction between nodes and edges in a network. Experimental evaluation using the Minneapolis, MN road network showed that LCP outperforms traditional orthogonal approaches.

Original languageEnglish (US)
Title of host publication18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2010
Pages212-221
Number of pages10
DOIs
StatePublished - Dec 31 2010
Event18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2010 - San Jose, CA, United States
Duration: Nov 2 2010Nov 5 2010

Publication series

NameGIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems

Other

Other18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2010
CountryUnited States
CitySan Jose, CA
Period11/2/1011/5/10

Keywords

  • File structure
  • Spatio-temporal databases
  • Spatio-temporal networks
  • Storage methods

Fingerprint Dive into the research topics of 'A lagrangian approach for storage of Spatio-Temporal Network datasets: A summary of results'. Together they form a unique fingerprint.

Cite this