Local, succinct, and semi-distributed graph representations

This project is part of a 4 year Dual PhD degree programme between the National Tsing Hua University (NTHU) in Taiwan and the University of Liverpool in England. As Part of the NTHU-UoL Dual PhD Award students are in the unique position of being able to gain 2 PhD awards at the end of their degree from two internationally recognised world leading Universities. As well as benefiting from a rich cultural experience. Students can draw on large scale national facilities of both countries and create a worldwide network of contacts across 2 continents.

Aims and objectives:

The goal of the project is to develop a novel approach of semi-distributed graph representations and design compact representations for graph classes of practical and theoretical importance as well as efficient algorithms over such representations for important graph problems.

Background:

Climate change is profoundly affecting nearly all aspects of life on earth, including human societies, economies, and health. Various human activities are responsible for significant greenhouse gas emissions, including data centers and other sources of large-scale computation [3].

This fact together with the rapid growth of electronic data sets and computing time required for processing of these data sets demand efficient methods of computation and utilization of memory.

Networks or graphs are a convenient way of representing complex data in modern applications (e. g. Web graph, Facebook network, Google’s Knowledge Graph, Protein–Protein Interaction Network, cattle movement networks, etc.), and efficient storage and processing of graph data is an important issue in such applications.

The classical way to represent graphs is via adjacency matrices or adjacency lists. Such representations assume that the data structure representing a graph is stored in memory and accessed when certain queries are performed on the graph.

One way to optimize memory usage is to design succinct data structures. Research on succinct data structures has led to optimal-space data structures for many types of data [1], significantly extending the size of data sets that can be analyzed efficiently on commodity hardware.

Another way to tackle the problem of storing large data is to distribute data over several storage devices. This approach requires distributed methods of computation and special representations are an integral part of such computations.

A type of representation that is particularly suitable for efficient distributed graph storage is a local graph representation. In such representations, graph vertices are assigned labels in such a way that target queries (e. g. adjacency or distance) can be inferred only from the labels of the involved vertices.

The most basic local representation is an adjacency labeling scheme, where every vertex of a graph is assigned a label such that adjacency of two vertices can be decided only from the labels assigned to these two vertices. One of the main goals of such representations is to minimize the size of the labels. A very recent breakthrough result [2] showed that not every graph class admits an optimal-size adjacency labeling scheme. This poses the important fundamental open problem to characterize graph classes that admit optimal-size adjacency labeling schemes.

The main goal of this project is to develop a novel approach of semi-distributed graph representations as a unified framework for global (classical, centralized) and local (distributed) graph representations [4]. In a semi-distributed graph representation, a graph is represented by a small amount of global information plus local vertex labels in such a way that target queries can be efficiently answered only using the global information and the local labels of the query vertices.

For academic enquires please contact  Viktor Zamaraev (viktor.zamaraev@liverpool.co.uk) or Chung-Shou Liao (csliao@ie.nthu.edu.tw) or Sebastian Wild (sebastian.wild@liverpool.ac.uk)

For enquires on the application process or to find out more about the Dual programme please contact spspgr@liverpool.ac.uk

To apply for this opportunity please visit: https://www.liverpool.ac.uk/study/postgraduate-research/how-to-apply/ When applying please ensure you Quote the supervisor & project title you wish to apply for and note ‘NTHU-UoL Dual Scholarship’ when asked for details of how plan to finance your studies.