research-article

Temporal Sampling Constraints for GeoSpatial Path Reconstruction in a Transportation Network

Authors:

Jane Macfarlane,

Bo XuAuthors Info & Claims

IWCTS'17: Proceedings of the 10th ACM SIGSPATIAL Workshop on Computational Transportation Science

Pages 1 - 6

https://doi.org/10.1145/3151547.3151548

Published: 07 November 2017 Publication History

Get Access

Abstract

In this paper, we address the problem of recovering traveled geospatial paths on a transportation network from time sampled location traces. Determining the proper sampling rate for path reconstruction has not traditionally been addressed ahead of the collection process. Instead various uncertainty models have been created and tuned to estimate possible geospatial paths from an existing set of location measurements. This paper suggests that the geospatial road density sets a fundamental constraint on the sampling frequency. The result shows that a sufficient sampling rate is determined by the maneuver that has the minimum possible travel time, which in turn is determined by maneuver length and speed limit. This is analogous to the Nyquist-Shannon Sampling Theorem for signal processing in that the sampling rate is determined by the highest frequency with which the signal changes its value; in our result the sampling rate is determined by the highest frequency with which a probe can change its route.

References

[1]

H. Cao, O. Wolfson, and G. Trajcevski. 2006. Spatio-Temporal Data Reduction with Deterministic Error Bounds. The VLDB Journal (September 2006), 15(3):211--228.

Digital Library

Google Scholar

[2]

L. Chen, Y. Tang, M. Lv, and G. Chen. 2015. Partition-based range query for uncertain trajectories in road networks. GeoInformatica (January 2015), 19:61--84.

Digital Library

Google Scholar

[3]

A. Civilis, C. S. Jensen, N. Nenortaite, and S. Pakalnis. 2004. Efficient tracking of moving objects with precision guarantees. MOBIQUITOUS (2004), 164--173.

Google Scholar

[4]

A. Civilis, C. S. Jensen, and S. Pakalnis. 2005. Techniques for efficient road-network-based tracking of moving objects. IEEE TKDE (2005), 17(5):19--26.

Digital Library

Google Scholar

[5]

D. Eppstein. 1999. Finding the k Shortest Paths. SIAM J. Comput. (April 1999), 652--673.

Digital Library

Google Scholar

[6]

J. Gudmundsson, J. Katajainen, D. Merrick, C. Ong, and T. Wolle. 2007. Compressing spatio-temporal trajectories. Proceedings of the 18th international conference on algorithms and computation (December 2007), 763--775.

Digital Library

Google Scholar

[7]

B. Kuijpers and W. Othman. 2009. Modeling uncertainty on road networks via space-time prisms. International Journal of GIS (September 2009), 1095--1117.

Google Scholar

[8]

R. Lange, F. Durr, and K. Rothermel. 2011. Efficient Real-time Trajectory Tracking. The VLDB Journal (October 2011), 20(5):671--694.

Digital Library

Google Scholar

[9]

I. S. Popa, K. Zeitouni, V. Oria, and A. Kharrat. 2015. Spatio-temporal compression of trajectories in road networks. Geoinformatica (2015), 19(1):117--145.

Digital Library

Google Scholar

[10]

G. Trajcevski, H. Cao, P. Scheuermann, O. Wolfson, and D. Vaccaro. 2006. On-line data reduction and the quality of history in moving objects databases. MobiDE (2006), 19--26.

Digital Library

Google Scholar

[11]

O. Wolfson, S. Chamberlain, S. Dao, L. Jiang, and G. Mendez. 1998. Cost and Imprecision in Modeling the Position of Moving Objects. Proceedings of the 14th International Conference on Data Engineering (February 1998), 588--596.

Digital Library

Google Scholar

[12]

O. Wolfson and Y. Yin. 2003. Accuracy and resource consumption in tracking and location prediction. SSTD '03 (2003), 325--343.

Google Scholar

[13]

K. Zheng, G. Trajcevski, X. Zhou, and P. Scheuermann. 2011. Probabilistic Range Queries for Uncertain Trajectories on Road Networks. EDBT (2011), (19):61--84.

Digital Library

Google Scholar

[14]

Y. Zheng and X. Zhou. 2011. Computing with spatial trajectories. Springer (2011).

Digital Library

Google Scholar

Cited By

View all

Werner TAhlers JBrinkhoff T(2023)About privacy on smart tachographs: Reconstructing car-driven routes based on speed measurementsProceedings of the 1st ACM SIGSPATIAL International Workshop on Geo-Privacy and Data Utility for Smart Societies10.1145/3615889.3628511(14-19)Online publication date: 13-Nov-2023
https://dl.acm.org/doi/10.1145/3615889.3628511

Index Terms

Temporal Sampling Constraints for GeoSpatial Path Reconstruction in a Transportation Network
1. Information systems
  1. Information systems applications
    1. Mobile information processing systems
    2. Spatial-temporal systems
      1. Global positioning systems
      2. Location based services

Recommendations

Analysis of adaptive sampling techniques for underwater vehicles

A critical problem in planning sampling paths for autonomous underwater vehicles (AUVs) is correctly balancing two issues. First, obtaining an accurate scalar field estimation and second, efficiently utilizing the stored energy capacity of the sampling ...
A new method for adaptive sequential sampling for learning and parameter estimation
ISMIS'11: Proceedings of the 19th international conference on Foundations of intelligent systems

Sampling is an important technique for parameter estimation and hypothesis testing widely used in statistical analysis, machine learning and knowledge discovery. In contrast to batch sampling methods in which the number of samples is known in advance, ...
Quickest path queries on transportation network
CATS '12: Proceedings of the Eighteenth Computing: The Australasian Theory Symposium - Volume 128

This paper considers the problem of finding a quickest path between two points in the Euclidean plane in the presence of a transportation network. A transportation network consists of a planar network where each road (edge) has an individual speed. A ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

IWCTS'17: Proceedings of the 10th ACM SIGSPATIAL Workshop on Computational Transportation Science

November 2017

46 pages

ISBN:9781450354912

DOI:10.1145/3151547

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 November 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

SIGSPATIAL'17

Sponsor:

SIGSPATIAL

SIGSPATIAL'17: 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

November 7 - 10, 2017

CA, Redondo Beach, USA

Acceptance Rates

Overall Acceptance Rate 42 of 57 submissions, 74%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
61
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)1

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Werner TAhlers JBrinkhoff T(2023)About privacy on smart tachographs: Reconstructing car-driven routes based on speed measurementsProceedings of the 1st ACM SIGSPATIAL International Workshop on Geo-Privacy and Data Utility for Smart Societies10.1145/3615889.3628511(14-19)Online publication date: 13-Nov-2023
https://dl.acm.org/doi/10.1145/3615889.3628511

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Analysis of adaptive sampling techniques for underwater vehicles

A new method for adaptive sequential sampling for learning and parameter estimation

Quickest path queries on transportation network