Compressing Graphs and Indexes with Recursive Graph Bisection
Authors: Laxman Dhulipala
Liked by:
Domains: Graph compression
Tags: KDD2016
Uploaded by: Maximimi
Upload date: 2019-02-14 17:02:35


Nice paper building on top of [the WebGraph framework]( and [Chierichetti et al.]( to compress graphs. ### Approximation guarantee I read: "our algorithm is inspired by a theoretical approach with provable guarantees on the final quality, and it is designed to directly optimize the resulting compression ratio.". I misunderstood initially, but the proposed algorithm actually does not have any provable approximation guarantee other than the $\log(n)$ one (which is also obtained by a random ordering of the nodes). Designing an algorithm with (a better) approximation guarantee for minimizing "MLogA", "MLogGapA" or "BiMLogA" seems to be a nice open problem. ### Objectives Is there any better objective than "MLogA", "MLogGapA" or "BiMLogA" to have a proxy of the compression obtained by the BV-framework? Is it possible to directly look for an ordering that minimizes the size of the output of BV compression algorithm?
Maximimi at 2019-02-14 17:31:54
Edited by Maximimi at 2019-02-15 14:35:57

Please consider to register or login to comment on the paper.