Sampling big trajectory data

Yanhua Li, Chi Yin Chow, Ke Deng, Mingxuan Yuan, Jia Zeng, Jia Dong Zhang, Qiang Yang, Zhi Li Zhang

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

9 Scopus citations

Abstract

The increasing prevalence of sensors and mobile devices has led to an explosive increase of the scale of spatio-temporal data in the form of trajectories. A trajectory aggregate query, as a fundamental functionality for measuring trajectory data, aims to retrieve the statistics of trajectories passing a user-specified spatiotemporal region. A large-scale spatio-temporal database with big disk-resident data takes very long time to produce exact answers to such queries. Hence, approximate query processing with a guaranteed error bound is a promising solution in many scenarios with stringent response-time requirements. In this paper, we study the problem of approximate query processing for trajectory aggregate queries. We show that it boils down to the distinct value estimation problem, which has been proven to be very hard with powerful negative results given that no index is built. By utilizing the well-established spatio-temporal index and introducing an inverted index to trajectory data, we are able to design random index sampling (RIS) algorithm to estimate the answers with a guaranteed error bound. To further improve system scalability, we extend RIS algorithm to concurrent random index sampling (CRIS) algorithm to process a number of trajectory aggregate queries arriving concurrently with overlapping spatio-temporal query regions. To demonstrate the efficacy and efficiency of our sampling and estimation methods, we applied them in a real large-scale user trajectory database collected from a cellular service provider in China. Our extensive evaluation results indicate that both RIS and CRIS outperform exhaustive search for single and concurrent trajectory aggregate queries by two orders of magnitude in terms of the query processing time, while preserving a relative error ratio lower than 10%, with only 1% search cost of the exhaustive search method.

Original languageEnglish (US)
Title of host publicationCIKM 2015 - Proceedings of the 24th ACM International Conference on Information and Knowledge Management
PublisherAssociation for Computing Machinery
Pages941-950
Number of pages10
ISBN (Electronic)9781450337946
DOIs
StatePublished - Oct 17 2015
Event24th ACM International Conference on Information and Knowledge Management, CIKM 2015 - Melbourne, Australia
Duration: Oct 19 2015Oct 23 2015

Publication series

NameInternational Conference on Information and Knowledge Management, Proceedings
Volume19-23-Oct-2015

Other

Other24th ACM International Conference on Information and Knowledge Management, CIKM 2015
CountryAustralia
CityMelbourne
Period10/19/1510/23/15

Keywords

  • Approximate query processing
  • Sampling
  • Spatio-temporal databases
  • Trajectory aggregate query

Fingerprint Dive into the research topics of 'Sampling big trajectory data'. Together they form a unique fingerprint.

  • Cite this

    Li, Y., Chow, C. Y., Deng, K., Yuan, M., Zeng, J., Zhang, J. D., Yang, Q., & Zhang, Z. L. (2015). Sampling big trajectory data. In CIKM 2015 - Proceedings of the 24th ACM International Conference on Information and Knowledge Management (pp. 941-950). (International Conference on Information and Knowledge Management, Proceedings; Vol. 19-23-Oct-2015). Association for Computing Machinery. https://doi.org/10.1145/2806416.2806422