Speaker:Pravithra Rajarathinam

Title: Graph Compression using heuristic based reordering

Abstract: Inverted index has been extensively used in Information retrieval systems for document related queries. We consider the generic case of graph storage using Inverted Index and compressing them using this format. Graph compression by reordering has been done using traversal and clustering based techniques. In generic methods, the graph is reordered to arrive at new identifiers for the vertices. The reordered graph is then encoded using an encoding format. The reordering to achieve maximal compression is a well known NP complete problem, the Optimal Linear Arrangement.

Our work focuses on the inverted index format, where each node has its corresponding list of neighbours. We propose a heuristic based graph reordering, using the property that the cost of each vertex is bound by its neighbour with largest vertex id. Consider, two vertices x and y with edges a and b respectively. If x>y and a>b, then cost of graph would come down, if the vertex id of x and y are interchanged. Further, experiments shows that using this heuristic helps in achieving compression rates on par with distributed methods but with reduced utilization of computation resources.