Title:  Incorporating Streaming and Approximate Techniques in Graph Processing  

Date: 27/07/2018

Time: 14h00

Location: Sala 0.17, Pavilhão Informática II, IST, Alameda 

Advisors: Professor Luís Veiga / Professor Alexandre Francisco

Abstract: This work highlights recent contributions in distributed systems addressing graph processing, targeting (but not restricted to) algorithms such as community detection and vertex centrality. The study is being conducted as part of a larger context of big data, dynamic graphs and the emerging roles of approximate and incremental computing. Experiments are being conducted with the aim of analyzing the performance of distributed graph processing approaches in light of different algorithms in this context.  The systems used in empirical evaluation were the result of a two-phase study: 1) a broad qualitative analysis of several graph processing systems and databases and a choice based on desirable features; 2) a more in-depth analysis of the APIs and features of some systems. Given the increasing dimension of data sets represented as graphs in the advent of big data, how far can one relax from exact to approximate computing? How may we reliably define and ensure controlled error bounds given the volatility of graphs such as those representing social networks? And to what extent can performance be gained with a trade-off in accuracy in distributed system graph-processing scenarios? Employing distributed systems, how may one scale-out methods of graph clustering (as an example of a relevant graph algorithm) to process large graphs while harnessing the computational power of distributed computing infrastructures (potentially in line with statistical and machine learning techniques)? How easy is it to adopt incremental solutions for the processing of dynamic graphs? Could we update existing graph processing results based solely on previous results and a given change, or set of changes, in the graph?Establishing a basis for solving these challenges would pave the way for greater performance and resource-efficiency in the analysis of many graph-based big data scenarios.