Path-based Queries on Trajectory Data

Benjamin Bjerre Krogh, Nikos Pelekis, Yannis Theodoridis, Kristian Torp

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

27 Citations (Scopus)

Abstract

In traffic research, management, and planning a number of path-based analyses are heavily used, e.g., for computing turn-times, evaluating green waves, or studying traffic flow. These analyses require retrieving the trajectories that follow the full path being analyzed. Existing path queries cannot sufficiently support such path-based analyses because they retrieve all trajectories that touch any edge in the path. In this paper, we define and formalize the strict path query. This is a novel query type tailored to support path-based analysis, where trajectories must follow all edges in the path. To efficiently support strict path queries, we present a novel NETwork-constrained TRAjectory index (NETTRA). This index enables very efficient retrieval of trajectories that follow a specific path, i.e., strict path queries. NETTRA uses a new path encoding scheme that can determine if a trajectory follows a specific path by only retrieving data from the first and last edge in the path. To correctly answer strict path queries existing network-constrained trajectory indexes must retrieve data from all edges in the path. An extensive performance study of NETTRA using a very large real-world trajectory data set, consisting of 1.7 million trajectories (941 million GPS records) and a road network with 1.3 million edges, shows a speed-up of two orders of magnitude compared to state-of-the-art trajectory indexes.
Original languageEnglish
Title of host publicationSIGSPATIAL'14:Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems
Number of pages10
PublisherAssociation for Computing Machinery
Publication date4 Nov 2014
Pages341-350
ISBN (Print)978-1-4503-3131-9
DOIs
Publication statusPublished - 4 Nov 2014
Event22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2014) - Dallas, Texas, United States
Duration: 4 Nov 20147 Nov 2014

Conference

Conference22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2014)
CountryUnited States
CityDallas, Texas
Period04/11/201407/11/2014

Keywords

  • trajectories
  • network-constrained indexing
  • spatio-temporal indexing
  • analysis
  • performance

Fingerprint Dive into the research topics of 'Path-based Queries on Trajectory Data'. Together they form a unique fingerprint.

  • Prizes

    Best Paper Award

    Benjamin Bjerre Krogh (Recipient), Nikos Pelekis (Recipient), Torp, Kristian (Recipient) & Yannis Theodoridis (Recipient), 2014

    Prize: Conference prizes

    Cite this

    Krogh, B. B., Pelekis, N., Theodoridis, Y., & Torp, K. (2014). Path-based Queries on Trajectory Data. In SIGSPATIAL'14:Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (pp. 341-350). Association for Computing Machinery. https://doi.org/10.1145/2666310.2666413