Euler histogram tree: A spatial data structure for aggregate range queries on vehicle trajectories

Hairuo Xie, Egemen Tanin, Lars Kulik, Peter I Scheuermann, Goce Trajcevski, Maryam Fanaeepour

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

5 Scopus citations

Abstract

This work addresses the problem of aggregation of trajectories data. Specifically, we propose a tree-based data structure for counting vehicle trajectories by mapping them into a set of spatial histograms with different granularities. We also present an approach for processing spatio-temporal range queries by aggregating the histograms in the query rectangles. The proposed methodology can be used for preserving the privacy of vehicle drivers by maintaining aggregated trajectory data. In addition, as we show, it can be used to handle the well-known distinct counting problem. Experimental results show that the new data structure achieves a high level of accuracy in query results and consistently outperforms the leading histogram-based approach.

Original languageEnglish (US)
Title of host publicationIWCTS 2014 - Proceedings of the 7th ACM SIGSPATIAL International Workshop on Computational Transportation Science
EditorsXin Chen
PublisherAssociation for Computing Machinery, Inc
Pages18-24
Number of pages7
ISBN (Electronic)9781450331388
DOIs
StatePublished - Nov 4 2014
Event7th ACM SIGSPATIAL International Workshop on Computational Transportation Science, IWCTS 2014 - Dallas, United States
Duration: Nov 4 2014 → …

Publication series

NameIWCTS 2014 - Proceedings of the 7th ACM SIGSPATIAL International Workshop on Computational Transportation Science

Other

Other7th ACM SIGSPATIAL International Workshop on Computational Transportation Science, IWCTS 2014
CountryUnited States
CityDallas
Period11/4/14 → …

Keywords

  • Aggregate query
  • Hierarchical data structure
  • Spatial histogram

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Networks and Communications
  • Transportation
  • Computer Science Applications

Fingerprint Dive into the research topics of 'Euler histogram tree: A spatial data structure for aggregate range queries on vehicle trajectories'. Together they form a unique fingerprint.

Cite this