LSD-AN EFFECTIVE LOCAL SPLIT DECOMPOSITION-BASED GRAPH COMPRESSION METHOD

MPhil Thesis Defence


Title: "LSD-AN EFFECTIVE LOCAL SPLIT DECOMPOSITION-BASED GRAPH COMPRESSION 
METHOD"

By

Mr. Yatao LI


Abstract

With the popular usage of graphs in many applications, such as social 
networks analysis and web graph mining, how to store the graphs 
effectively in a distributed environment is quite challenging and useful. 
The straightforward solution is to compress the graphs. However, in this 
paper, we argue that the compressed graphs must be able to handle atomic 
operations and real-time updates without decompressing the graph. 
Unfortunately, the traditional compression methods cannot fulfill these 
requirements. Thus, in this paper, we propose a novel and effective 
compression method to compress distributed large graphs. Specifically, we 
first select a set of central nodes and then start compressing the 
selected nodes's neighbourhood structure by graph labeled trees (GLT), 
which are universally effective for all graphs and self-descriptive so 
that no extra indices or dictionaries are involved. The extensive 
experiments verify the effectiveness and efficiency of the proposed 
solution.


Date:			Thursday, 21 August 2014

Time:			4:00pm - 6:00pm

Venue:			Room 3501
 			Lifts 25/26

Committee Members:	Dr. Lei Chen (Supervisor)
 			Dr. Ke Yi (Chairperson)
 			Dr. Pan Hui


**** ALL are Welcome ****