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 this paper, we consider a variant of the color range reporting problem called color reporting with frequencies. Our goal is to pre-process a set of colored points into a data structure, so that given a query range Q, we can report all colors that appear in Q, along with their respective frequencies. In other words, for each reported color, we also output the number of times it occurs in Q. We describe an external-memory data structure that uses O(N(1+log^2D/log N)) words and answers one-dimensional queries in O(1 +K/B) I/Os, where N is the total number of points in the data structure, D is the total number of colors in the data structure, K is the number of reported colors, and B is the block size. Next we turn to an approximate version of this problem: report all colors sigma that appear in the query range; for every reported color, we provide a constant-factor approximation on its frequency. We consider color reporting with approximate frequencies in two dimensions. Our data structure uses O(N) space and answers two-dimensional queries in O(log_B N +log^*B + K/B) I/Os in the special case when the query range is bounded on two sides. As a corollary, we can also answer one-dimensional approximate queries within the same time and space bounds.

In the dynamic indexing problem, we must maintain a changing collection of text documents so that we can efficiently support insertions, deletions, and pattern matching queries. We are especially interested in developing efficient data structures that store and query the documents in compressed form. All previous compressed solutions to this problem rely on answering rank and select queries on a dynamic sequence of symbols. Because of the lower bound in [Fredman and Saks, 1989], answering rank queries presents a bottleneck in compressed dynamic indexing. In this paper we show how this lower bound can be circumvented using our new framework. We demonstrate that the gap between static and dynamic variants of the indexing problem can be almost closed. Our method is based on a novel framework for adding dynamism to static compressed data structures. Our framework also applies more generally to dynamizing other problems. We show, for example, how our framework can be applied to develop compressed representations of dynamic graphs and binary relations.

List update algorithms have been widely used as subroutines in compression schemas, most notably as part of Burrows-Wheeler compression. The Burrows-Wheeler transform (BWT), which is the basis of many state-of-the-art general purpose compressors applies a compression algorithm to a permuted version of the original text. List update algorithms are a common choice for this second stage of BWT-based compression. In this paper we perform an experimental comparison of various list update algorithms both as stand alone compression mechanisms and as a second stage of the BWT-based compression. Our experiments showMTF outperforms other list update algorithms in practice after BWT. This is consistent with the intuition that BWT increases locality of reference and the predicted result from the locality of reference model of Angelopoulos et al. [LATIN 2008]. Lastly, we observe that due to an often neglected difference in the cost models, good list update algorithms may be far from optimal for BWT compression and construct an explicit example of this phenomena. This is a fact that had yet to be supported theoretically in the literature.

We develop a method of representing binary search trees in an environment in which pointers and other structural information may be "lost" or "maliciously altered". Our fault tolerant representation permits any 2 field changes to be detected and any 1 to be corrected without significantly increasing to storage requirements of the binary tree. The detection and correction procedures applied to the entire tree require 0(n) time.Our discipline is also used to represent binary search trees with a single pointer per datum without altering the cost of searching or updating. While our scheme can be applied in conjunction with any underlying tree balancing scheme ([AVL], bounded balance [Nievergelt et al] etc), if no balancing scheme is employed, the trees we form will have significantly shorter search paths than those formed using the straightforward algorithm.