The main objective of this project is to develop methods and techniques for building, storing, processing and accessing TD-LSG. In addition, this project aims to develop a new software platform, open source and free, which can be used to build applications that rely on a TD-LSG. The research topics to be tackled during this project are :
- Build a TD-LSG using spatio-temporal or temporal traces
We aim at investigating methods and techniques for building a TD-LSG using temporal or spatiotemporal traces. These data will be used to compute the temporal functions that shall annotate the graph edges. In order to this computation we need: (1) to reconstruct trajectories from raw data, (2) to perform map-matching on trajectory data and (3) to compute the corresponding piecewise linear function for each road segment. The latter task will require particular linear regression methods which correctly capture time intervals with relevant changes in the temporal function.
2. Inter-linking and querying TD-LSG
Each transportation system is managed independently and uses a specific model. One problem is therefore integrating different networks corresponding to distinct transportation modes so as they can interoperate and be queried in a uniform way. In addition to ensuring interoperability, we are interested in enriching the integrated model with external data sources, which could be relevant linked data sources, information provided by social media, or dynamic information such as contextual data streams or events. We aim at linking/aligning ontologies with a TD-LSG in order to enrich it with external sources. Some research proposals have addressed the problem of interlinking spatio-temporal and semantic web data, but they are often dedicated to a specific application context, or the temporal dimension is not explicitly taken into account. Unlike these works, our aim is to provide a generic model suitable for TD-LSG to ensure network interoperability and to capture and exploit the temporal variability.
3. Storing and partitioning a distributed TD-LSG
We assume that the graphs we will manage are too large to be stored and processed in a centralized manner. So we need to develop methods and techniques for storing and partitioning large-scale graphs. However, no unique approach exists for partitioning graphs that will attend all kind of queries (e.g. KNN, Shortest Path, Page Rank, etc). An important question to be addressed is how to perform this partitioning taking into account the graph nodes/edges distribution and the types of queries to be performed over it. Another research question is how to take into account the space and time during partitioning.
4. Allowing Scalable Query Processing over a TD-LSG
Efficient query processing over a TD-LSG must rely on methods and techniques for processing large graphs. In this sense, we will investigate the recent strategies for processing large-scale graphs such as Pregel, Giraph, GraphLab and GPS. Clearly, such strategies are generic for any type of graph, however our focus of research will evaluate and propose specific techniques for processing TD-LSG.
5. Implement the TD-LSG Platform
We intend to build a framework for building applications that store graphs with time-dependent costs and process queries over them. Since static (non-time-dependent) graphs are a particular case of time-dependent graphs, this framework is also suitable for handling this kind of graph. Part of this framework has already been developed in the context of dissertations and theses developed at UFC. However, we intend with this project to accelerate its development aiming to create an open source platform, which will be an important contribution to the scientific community, as well as for the development of applications that depend on time-dependent networks.
TD-LSG Architecture
