Graph models and algorithms are ubiquitous of a large number of application domains, ranging from transportation to social networks, semantic web, or data mining. Our motivating application falls in the field of mobility analysis, though the approach aims to be more generic. Mobility applications are key for helping individuals, businesses and government agencies in managing traffic, public transportation, delivery logistics within the urban space. Such applications usually support services for route planning, detection of shortest paths, queries of nearest neighbors and others. A common characteristic of these applications is that they rely on a road network. Indeed, the nature of such networks are spatio-temporal. They need to represent space and spatial constraints to which the moving objects are submitted to. They also need to consider that the travel time on road networks depends directly on the traffic and that traffic patterns depend, in turn, not only in the region in question, but also the time of day. Therefore, the time a moving object takes to cross a path segment typically depends on its departure time. For example, on a same avenue in Fortaleza, Brazil, at 19:30 this avenue is completely congested and, thus, the time to cross it is longer than at 20:40, when the traffic is less intense.
(a) traffic at 19:10 (b) Traffic at 20:40
However, the majority of the solutions proposed to spatial queries on road networks fails to represent the reality in the sense that they do not consider the temporal dependence of road networks. They assume that these networks are static and the cost to traverse each edge is given by the length of this edge and, thus, it does not vary with time. This assumption is certainly not true on a real scenario, that is better represented by a time-dependent graph, which takes into consideration that the time one takes to traverse a road segment, typically depends on the departure time.
Some recent studies have included the temporal dependence to solve conventional spatial queries, such as k-nearest neighbors and shortest path queries. As in those works, we also consider this dependence to answer queries. More specifically, we assume that the network is modeled as a graph where the travel time along each edge is a function of the departure time. These functions give the travel time of an edge according to the time instant when one starts traversing this edge. However, processing queries in time-dependent graphs is challenging due to the space required to store these graphs is significantly larger than the space used to store the time independent ones, since it is necessary to keep, for each edge, the cost to traverse it for every time interval of a day. Furthermore, solutions for conventional queries in static graphs cannot be directly applied to solve the time-dependent problems. Particularly, it is no feasible to apply the well-known speed-up technique of bidirectional search that starts a search simultaneously from the source and the target, to solve the shortest path problem in a timedependent graph since the arrival time would have to be known in advance for such a procedure.
Despite of the efforts made so far, we know that some real world applications need to use large graphs, which could have millions of nodes and edges. In case of time-dependent graphs, the size of the graph may be increased by many orders of magnitude, depending on the time granularity. So, a part of querying challenges on time-dependent large-scale graphs (TD-LSG), we also envisage the problem of storing, processing and accessing large scale graphs in an efficient way. In this context, many research questions arises when dealing with such large time-dependent graphs such as:
- How to build a TD-LSG using spatio-temporal data or temporal traces in general?
- How to inter-link and enrich TD-LSG with semantic resources?
- How to allow scalable query processing over a TD-LSG?
- How to organize and maintain a TD-LSG in distributed architecture ?
The methodology to be adopted in this research project consists of the following steps:
- Understand and define precisely the problem to be tackled;
- Evaluate the state of the art related to the defined problems;
- Evaluate methods, techniques and tools for solving the problems outlined above;
- Develop new methods, techniques for solving these problems;
- Promote research missions to France and Rio in order to discuss specific problems and solutions;
- Prepare and publish the first results as technical reports and later in conferences and journals recognized by Qualis CAPES and CNRS;
- Prototype tools that implement the techniques and methods defined before;
- Realize seminars for disseminating results.
