Route discovery from mining uncertain trajectories

Moving objects in the physical world usually generate many uncertain trajectories for some reasons such as the consideration of energy consumption, leaving the route passing two consecutive sampling points unknown. While such trajectories imply rich knowledge about the mobility of moving objects, they are less useful individually. This paper introduces an online trip planning system that mines collective knowledge (i.e., most possible routes between given locations) from massive uncertain trajectories following a paradigm of "uncertain+uncertain?certain". This system first builds a routable graph from uncertain trajectories, and then answers a user's online query (a sequence of point locations) by searching top-κ routes on the graph. Two large-scale datasets consisting of "check-in" records from FourSquare and a trajectory dataset of taxis have been used to evaluate our system. As a result, our system provides a user with effective routes according to the user's query efficiently.