Inferring waypoints using shortest paths

Daniel A. Desmond; Kenneth N. Brown

Inferring waypoints using shortest paths

Daniel A. Desmond
, Kenneth N. Brown

University College Cork

Research output: Contribution to journal › Article › peer-review

Abstract

We present a method for reconstructing intermediate destinations from a GPS trace of a multi-part trip, without access to aggregated statistics or datasets of previous traces. The method uses repeated forwards and backwards shortest-path searches. We evaluate the algorithm empirically on multi-part trips on real route maps. We show that the algorithm can achieve up to 97% recall, and that the algorithm degrades gracefully as the GPS traces become sparse and irregular.

Original language	English
Pages (from-to)	45-56
Number of pages	12
Journal	CEUR Workshop Proceedings
Volume	1751
Publication status	Published - 2016
Event	24th Irish Conference on Artificial Intelligence and Cognitive Science, AICS 2016 - Dublin, Ireland Duration: 20 Sep 2016 → 21 Sep 2016

Cite this

@article{caf377fd48cd4e58bb10c55cbe42eb7e,

title = "Inferring waypoints using shortest paths",

abstract = "We present a method for reconstructing intermediate destinations from a GPS trace of a multi-part trip, without access to aggregated statistics or datasets of previous traces. The method uses repeated forwards and backwards shortest-path searches. We evaluate the algorithm empirically on multi-part trips on real route maps. We show that the algorithm can achieve up to 97\% recall, and that the algorithm degrades gracefully as the GPS traces become sparse and irregular.",

author = "Desmond, \{Daniel A.\} and Brown, \{Kenneth N.\}",

note = "Publisher Copyright: {\textcopyright} 2016, CEUR-WS. All rights reserved.; 24th Irish Conference on Artificial Intelligence and Cognitive Science, AICS 2016 ; Conference date: 20-09-2016 Through 21-09-2016",

year = "2016",

language = "English",

volume = "1751",

pages = "45--56",

journal = "CEUR Workshop Proceedings",

issn = "1613-0073",

publisher = "CEUR-WS",

}

TY - JOUR

T1 - Inferring waypoints using shortest paths

AU - Desmond, Daniel A.

AU - Brown, Kenneth N.

PY - 2016

Y1 - 2016

N2 - We present a method for reconstructing intermediate destinations from a GPS trace of a multi-part trip, without access to aggregated statistics or datasets of previous traces. The method uses repeated forwards and backwards shortest-path searches. We evaluate the algorithm empirically on multi-part trips on real route maps. We show that the algorithm can achieve up to 97% recall, and that the algorithm degrades gracefully as the GPS traces become sparse and irregular.

AB - We present a method for reconstructing intermediate destinations from a GPS trace of a multi-part trip, without access to aggregated statistics or datasets of previous traces. The method uses repeated forwards and backwards shortest-path searches. We evaluate the algorithm empirically on multi-part trips on real route maps. We show that the algorithm can achieve up to 97% recall, and that the algorithm degrades gracefully as the GPS traces become sparse and irregular.

UR - https://www.scopus.com/pages/publications/85009366174

M3 - Article

AN - SCOPUS:85009366174

SN - 1613-0073

VL - 1751

SP - 45

EP - 56

JO - CEUR Workshop Proceedings

JF - CEUR Workshop Proceedings

T2 - 24th Irish Conference on Artificial Intelligence and Cognitive Science, AICS 2016

Y2 - 20 September 2016 through 21 September 2016

ER -

Inferring waypoints using shortest paths

Abstract

Other files and links

Fingerprint

Cite this