Several services today are annotated with points of interest (PoIs) such as "coffee shop", "park", etc. In this paper, we study the query where a user provides a set of relevant PoIs and wants to identify the optimal route covering these PoIs. Ideally, the route should be small in length so that the user can conveniently explore the PoIs. On the other hand, the route should cover as many of the input PoIs as possible. These conflicting requirements of the optimal route raise an intriguing question: how do you balance the importance of route length vs. PoI coverage? If the route is to be covered on foot, and it is raining, length is critical for convenience. On the other hand, if the weather conditions are good, or the user is equipped with a vehicle, coverage is more important. In essence, the relative importance depends on several latent factors and we solve this dilemma through skyline route queries. Skyline routes subsume the choice of the optimization function for a route since the optimal route for any rational user is necessarily a part of the skyline set. Our analysis reveals that the problem is NP-hard. We overcome this bottleneck by designing an algorithm called SkyRoute. SkyRoute drastically prunes the search space through a goal-directed search, which is further empowered by Lipschitz embedding, and provides up to 4 orders of magnitude speed-up over baseline techniques.

In this paper, we study the problem of mining temporally anomalous sub-trajectory patterns from an input trajectory in a scalable manner. Given the prevailing road conditions, a sub-trajectory is temporally anomalous if its travel time deviates significantly from the expected time. Mining these patterns requires us to delve into the sub-trajectory space, which is not scalable for real-time analytics. To overcome this scalability challenge, we design a technique called MANTRA. We study the properties unique to anomalous sub-trajectories and utilize them in MANTRA to iteratively refine the search space into a disjoint set of sub-trajectory islands. The expensive enumeration of all possible sub-trajectories is performed only on the islands to compute the answer set of maximal anomalous sub-trajectories. Extensive experiments on both real and synthetic datasets establish MANTRA as more than 3 orders of magnitude faster than baseline techniques. Moreover, through trajectory classification and segmentation, we demonstrate that the proposed model conforms to human intuition.