Managing trajectories

Retrieval tasks

Description

The Data Management group has targeted points-based search where trajectories are returned based on their proximity to a set of query points; i.e., given a collection of trajectories and a set query points, the goal is to retrieve the top-k trajectories that pass as close as possible to all query points. We advanced the nearest-neighbor based state-of-the-art by proposing a novel and more efficient, spatial range-based approach. In addition, a practical variant of this points-based search was proposed, which additionally takes into account other qualitative characteristics of the searched trajectories, e.g., the temporal span. Besides one-time or snapshot search. our recent work also introduced continuous points-based trajectory search where the query is long-standing and the result set must be maintained whenever updates to the query parameters and/or the data, i.e., the trajectories, occur.

Publications

  • Shuyao Qi, Dimitris Sacharidis, Panagiotis Bouros and Nikos Mamoulis:
    Snapshot and Continuous Points- based Trajectory Search
    International Journal on Advances of Computer Science for Geographic Information Systems (GeoInformatica), Vol 21, No 4, October 2017
  • Shuyao Qi, Panagiotis Bouros, Dimitris Sacharidis and Nikos Mamoulis:
    Efficient Point-based Trajectory Search
    Proceedings of the 14th International Symposium on Spatial and Temporal Databases (SSTD), Hong Kong, China, August 26-28, 2015
    Received the Best Paper Award

 

Path finding

Description

This line of work is captured by Prof. Bouros' doctorate studies. Prof. Bouros addressed new challenges that arise in path-finding problems, given the availability of trajectory collections; in prarticulal, whether path queries traditionally targeting graphs can be posed on trajectory collections, and even more importantly, if the evaluation of these queries can be enhanced by the special characteristics of the trajectories. For instance, a trajectory can be seen as a set of precomputed answers. Under this perspective, a novel framework was proposed for evaluating path queries on large disk resident collections that are frequently updated by adding and removing trajectories. The thesis introduced two evaluation paradigms that enjoy the benefits of search algorithms (i.e., fast index maintenance) while utilizing transitivity information to terminate the search sooner. In addition, efficient indexing schemes and appropriate updating procedures were also introduced.

Another arising challenge is to formulate existing optimization problems (originally not targeting graphs) that involve trajectories, as path queries. For this purpose, Prof. Bouros considered collections which appear in logistics and transportation scenarios, and particularly, in the context of pickup and delivery services. A transportation request is defined as picking up an object (e.g., package, person, etc.) from one location and delivering it at another. Given a set of customer requests, a company offering such services constructs a collection of trajectories that will be followed by its vehicle fleet to pickup and deliver the objects. However, during the service hours, new ad-hoc requests arrive at arbitrary timestamps and thus, the company needs to update the existing vehicle trajectories in order to satisfy the new customers. Under this setup, Prof. Bouros introduced dynamic Pickup and Delivery with Transfers, modeled as a dynamic shortest path problem with two optimization criteria that capture the company’s and the customers’ viewpoint.

Publications