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.

MOTIVATION: Pangenome indexing is a critical supporting technology in biological sequence analysis such as read alignment applications. The need to accurately identify billions of small sequencing fragments carrying sequencing errors and genomic variants drives the development of scalable and efficient pangenome indexing approach. RESULTS: We propose a new wavelet tree-based approach, called Panaln, for indexing pangenome and introduce a batch computation approach for fast count query over Panaln. We present a simple and effective seeding strategy and develop a pangenome program that uses the seed-and-extend paradigm for read alignment. Experimental results on simulated and real data demonstrate that Panaln uses significantly less space for the compared pangenome methods with generally higher accuracy. We provide a scalable index construction by representing pangenome with a linear model. Additionally, Panaln brings enhanced accuracy compared to the popular single reference methods. AVAILABILITY AND IMPLEMENTATION: Package: https://anaconda.org/bioconda/panaln and source code: https://github.com/Lilu-guo/Panaln.