Computing Variable Length Paths on Graph Databases
Paths of fixed or variable length are a special case of graph patterns that enable graph databases perform operations with the same functionality as join queries in RDBMS but with much less complexity. Furthermore, variable length paths are also used to match hierarchical relationships. Despite their importance, many graph databases offer limited support for the computation of such queries. This project aims at exploring algorithms and indexing structures in order to support the efficient processing of variable length path queries on Neo4j. For more information click here.
Graph Query Processing on Relational Databases
Despite the recent development of various of NoSQL systems such as key-value stores and graph databases, relational databases still remain the most popular and widely used DBMS . However, the recent advances in the field of Big Data have demonstrated some of the inadequacies of RDBMS to efficiently support the storage and querying of new types of data such as documents or graphs. From graph data types in particular, various companies have already extended their RDBMS in order to support the storage of graph data and the execution of basic graph operations. Nevertheless, the support offered by RDBMS for graph-based queries and indexing is fairly limited. The extent to which RDBMS can support graph operations efficiently has yet to be studied in depth. In this context, this project aims at exploring existing approaches for graph query processing on RDBMS and implementing new methods to extend the support that RDBMS offer for graph queries and optimize the processing of key operations. For more information click here.
Network Data Analytics
Online Approximation of Graph Analytics
Recently, graph analytics have become an important aspect of multiple diverse applications. Despite the development of several graph processing systems, with the growing scale of real world graphs, the computation of entire graph analytics remains a challenging problem. As a result, the approximate computation of such analytics has attracted a lot of attention. One way to approximate analytics is to analyze the results of already submitted queries. In fact, the result of certain queries can be seen as an approximation to some analytics, e.g., the maximum distance between two nodes found by executing a large set of distance queries can be seen as an approximation to the diameter of the graph. Towards this end, this project aims at analyzing logs of queries submitted to some graph database over a period of time along with their results, and identifying a set of measures/analytics that can be approximated within a reasonable margin of error. For more information click here.
Highway Detection on Large Graphs
The concept of highways is very common on transportation networks. Highways are built in order to reduce traffic congestion in urban centers and allow drivers to travel fast and safe. In graph theory though, we can characterize any path segment of a graph as highway as long as it serves the aforementioned or similar purpose. While the concept of highways has been utilized by various approaches for efficient route planning and bottleneck detection, the actual detection of segments serving as highways in a graph with no prior information has attracted much less attention. To this end, this project aims at the development of efficient methods for analyzing large graphs and detecting path segments that have the same functionality as real-world highways.
Relative Reachability Analysis on Transportation Networks
Reachability analysis is an important concept for many applications of spatial network databases. For example, in urban planning it is important to assess how well a city is covered by various public services such as hospitals or schools. While there have been works that given a time-budget determine the area a user can reach, the reachability of a given mode of transport in comparison to other possible modes has yet to be studied in depth. This project aims at investigating the relative reachability of a given mode of transport, e.g. train+walking, in comparison to other modes, e.g., car+walking. We aim at answering queries of the type "Which points in the map can I reach faster by bus+walking than by car+walking?".