Inferring waypoints in the absence of knowledge of driving style

We present an algorithm for predicting intervals which contain waypoints from a GPS trace of a multi-part trip without having access to historical data about the driver or any other aggregated data sets. We assume the driver’s driving style is not known, but that it can be approximated by one of a set of cost preferences. The method uses a set of repeated forward and backward searches along the trace, where each of the searches represents one of the driving costs. We evaluate the algorithm empirically on multi-part trips on real route maps. The algorithm selects the results of the search with the fewest number of intervals and we achieve over 95% recall on estimating waypoints while the intervals cover less than 9% of the trace.