Indexing Labeled Property Multidigraphs in Entropy Space, with Applications

The proliferation of online graph data - such as produced on social networks, citation networks, and online graph databases - calls for space-efficient graph indexing methods that support fast graph queries and graph analytics. Labeled property multidigraphs as a model of representing complicated graph data are widely used in practice. However, the fundamental problem of compressing and indexing labeled property multidigraphs has remained unsolved. In this paper, we focus on the static data case and propose a novel self-index, called CGraphIndex, to compress and index labeled property multidigraphs that for the first time achieves the high-order entropy space for multidigraph properties (the dominant term in practice) and the 1st-order graph entropy for multidigraph structures. A self-index actually encodes the original input and thus there is no need to store the input separately. CGraphIndex supports fundamental and navigational operations on the structures and on the properties in constant time, and supports fast property extraction on vertices and edges. Our experimental results on the large LDBC SNB benchmarks demonstrate that CGraphIndex outperforms the popular graph database systems (Community Editions), generally several times to orders of magnitude faster in query time and several times less in space usage for the compared interactive complex queries, business intelligence queries, as well as typical graph analytics BFS and PageRank.