It has been recently claimed that human movement is 'highly predictable' with an upper bound of 93% predictability shown.

The interest in such upper limits is fueled by the vast array of applications that benefit from accurate prediction of an individual's future location. Examples include ubiquitous advertising, service provision and intelligent agents both virtual and physical. Knowing the theoretical limits of mobility predictors provides insight into human behaviour in general. However, it also enables designers of applications to understand and work around the constraints with which they are faced at specific spatiotemporal granularities, and provides researchers with additional insights into the design of effective prediction algorithms.

However, knowing an upper bound is only useful if it is relatively tight, i.e. it is close to the true limit of predictability.

In this work we reconsider the derivation of the upper bound to movement predictability and by considering real-world topological constraints we are able to achieve a tighter upper bound. Our results show that the upper bound is actually between 11-24% less than previously claimed.

Particularly at fine-grained spatial and temporal quantization, where a significant number of practical applications lie, these new (lower) upper limits raise serious questions about the use of location information alone for prediction, contributing more evidence that such prediction must integrate external variables in order to satisfy the prediction accuracy requirement of a significant number of pervasive computing (and other) applications.

Download the paper (pre-print) or get it from IEEE Xplore (published version).

An expanded proof to that presented as Appendix A.

The code can be found on GitHub in two parts:
1. GPU based Python Library and Python interface for calculating the Entropy Rate.
2. Python code for computing the upper bound on the limit of predictability using both the original method and the new method, including code for replicating the heatmaps from the published work.

The code has been tested on Ubuntu 13.10 x64 on a machine with a NVIDIA GeForce 580 graphics card and CUDA 5.5.
The code has the following dependencies:

Python, Numpy, Scipy and Boost.Python

Matlab (inc. the Parallel Toolbox)

mlabwrap

healpy

utm for python

Boost.NumPy

CUDA

[Optional] sqlite external interpreter

• Download and extract both the Predictability Upper Bound project and the Entropy Rate Estimator project from Github.

• Compile the Entropy Rate Estimator library using the instructions in the project readme and copy the library into the LoP folder as libEntropyCalc.so

• Download the Geolife data set. Once downloaded, extract to a working directory and update the paths in GeolifeSymbolisation.py

• Optional: Pre-build the database cache files by running "python GeolifeSymbolisation.py". This will take a significant amount of time as it builds the trajectory database from downloaded Geolife data set and pre-computes all required trajectory quantisations. If this is not done then it will be done on first run of the main code.

• Run "python GeolifeEntropyCalc.py". This computes the upper bounds for all spatiotemporal quantisations investigated in the paper and saves them to a CSV.

• Run "python Graphing.py". This plots the results as heatmaps.

Errors?