We enhance space efficient representations of two types of intersection graphs. We refine the data structure for path graphs of Balakrishnan et al. to give a succinct data structure of n log n + o(n log n) bits that supports adjacency test, degree and neighbourhood queries in $O\left( {\frac{{\log n}}{{\log \log n}}} \right)$ time (for neighbourhood queries, this is the amount of time for each neighbour reported). To achieve O(1) query times, we give a data structure using (3 + ε)n log n + o(n log n) bits for any constant ε > 0. Furthermore, we are able to support both the distance and shortest path queries on unweighted path graphs using (2 + ε)n log n+ o(n log n) bits in O(log n/ log log n) time (shortest path uses an additional O(1) time per vertex on the path). This is the first compact distance oracles for path graphs. Turning to chordal graphs, we enhance the succinct data structure of Munro and Wu to reduce all query times including performing adjacency test in O(1) time.

An interval graph is the intersection graph of intervals on the real line. We consider the problem of constructing space efficient data structures for two subclasses of interval graphs: those with maximum degree σ1and those with chromatic number at most σ2.We show that both bounded degree and bounded chromatic number interval graphs have a tight lower bound of n lg σi− o(n lg σi) bits (i = 1, 2). This improves the lower bound of Chakraborty and Jo from $\frac{1}{6}n\lg {\sigma _i} - O(n)$. For bounded chromatic number interval graphs, we give the first succinct data structure occupying n lg σ2+ O(n) bits that supports navigational operations and distance queries in O(σ2lgn) time. To match Chakraborty and Jo’s time complexity of O(lg lg σ2), which uses (σ2− 1)n+O(n) bits, we use 2nlgσ2+O(n) bits instead.

In the range α-majority query problem, we preprocess a given sequence S[1..n] for a fixed threshold α ∈ (0, 1], such that given a query range [i..j], the symbols that occur more than α (j-i+1) times in S[i..j] can be reported efficiently. We design the first compressed solution to this problem in dynamic settings. Our data structure represents S using nHko(nlg σ) bits for any k = o(log σ n), where σ is the alphabet size and Hkis the k-th order empirical entropy of S. It answers range α-majority queries in O((lg n)/(α lg lgn)) time, and supports insertions and deletions in O(lg n/α) amortized time. The best previous solution [1] has the same query and update times, but uses O(n) words.

TrWP is a text relatedness measure that computes semantic similarity between words and phrases utilizing aggregated statistics from the Google Web 1T 5-gram corpus. The phrase similarity computation in TrWP is costly in terms of both time and space, making the existing implementation of TrWP impractical for real-world usage. In this work, we present an in-memory computational framework for TrWP, which optimizes the corpus search using perfect hashing and minimizes the required memory cost using variable length encoding. Evaluated using the Google Web 1T 5-gram corpus, we demonstrate that the computational speed of our framework outperforms a file-based implementation by several orders of magnitude.

Summary form only given: We study compressed representations of web graphs. Among previous work, the solution by Hernandez and Navarro [1] supports more queries than alternative approaches, including in-neighbour queries, out-neighbour queries and a set of mining queries. Their main strategy is to extract dense subgraphs from the given graph, and encode them using succinct data structures such as wavelet trees. Previous experimental studies on wavelet trees, however, test performance using textual data, and more engineering work is needed for the data generated from web graphs.Our strategy is to use different implementations to encode bit vectors at different levels of the wavelet trees constructed for dense subgraphs, based on the observation that bit vectors at top levels are more compressible than the rest. These implementations are considered: RRR, practical implementations [2] of the structure by Raman et al. [3]; RLEG, a bit vector structure based on run-length and Elias gamma codes [4]; and Plain, an uncompressed representation with low overheads [5]. Two specific approaches are used to combine them: The first approach encodes bit vectors using RRR starting from the root of a wavelet tree, until a level for which Plain uses less space is reached. Then, starting from this level downwards, Plain is used to encode bit vectors. The second approach uses RLEG, RRR and Plain in a similar top-down fashion, and different tradeoffs can be achieved by using different block sizes for RLEG.We implemented these approaches with code from [1, 4] and the compact structures library libcds (http://recoded.cl/), to encode data sets from the WebGraph Framework project (http://webgraph.di.unimi.it/). We obtained a rich set of time/space tradeoffs that can not be achieved using a single bit vector structure for all levels. The following three tradeoffs are particularly interesting: A new encoding scheme that decreases the space cost of Hernandez and Navarro's structure by 9% to 19% (more than 13% for all but one graph), while only doubling query time; a new scheme that decreases the space cost by 4% to 12% (10% or more for most graphs), with roughly the same query time; and a new scheme that decreases the space cost and the query time by about 2% and 1%-9% (5% or more for most graphs), respectively.