City Research Online

Modeling Checkpoint-Based Movement with the Earth Mover's Distance

Duckham, M., van Kreveld, M., Purves, R. , Speckmann, B., Tao, Y., Verbeek, K. & Wood, J. (2016). Modeling Checkpoint-Based Movement with the Earth Mover's Distance. Geographic Information Science. GIScience 2016. Lecture Notes in Computer Science, 9927 L, pp. 225-239. doi: 10.1007/978-3-319-45738-3_15


Movement data comes in various forms, including trajectory data and checkpoint data. While trajectories give detailed information about the movement of individual entities, checkpoint data in its simplest form does not give identities, just counts at checkpoints. However, checkpoint data is of increasing interest since it is readily available due to privacy reasons and as a by-product of other data collection. In this paper we propose to use the Earth Mover’s Distance as a versatile tool to reconstruct individual movements or flow based on checkpoint counts at different times. We analyze the modeling possibilities and provide experiments that validate model predictions, based on coarse-grained aggregations of data about actual movements of couriers in London, UK. While we cannot expect to reconstruct precise individual movements from highly granular checkpoint data, the evaluation does show that the approach can generate meaningful estimates of object movements.

B. Speckmann and K. Verbeek are supported by the Netherlands Organisation for Scientific Research (NWO) under project nos. 639.023.208 and 639.021.541, respectively. This paper arose from work initiated at Dagstuhl seminar 12512 “Representation, analysis and visualization of moving objects”, December 2012. The authors gratefully acknowledge Schloss Dagstuhl for their support.

Publication Type: Article
Additional Information: The final publication is available at
Subjects: G Geography. Anthropology. Recreation > GA Mathematical geography. Cartography
Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Departments: School of Science & Technology > Computer Science > giCentre
School of Science & Technology > Computer Science
SWORD Depositor:
[thumbnail of emd-grid.pdf]
Text - Accepted Version
Download (3MB) | Preview


Add to AnyAdd to TwitterAdd to FacebookAdd to LinkedinAdd to PinterestAdd to Email


Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login