Given a string S over an alphabet of size $\sigma$, we consider practical implementations of extended compressed RAM on S, which supports access, replace, lnsert, and delete operations on S while maintaining S in compressed form. In this paper, we proposed two implementations where each of them is based on the compressed RAM of Jansson et al. [ICALP 2012], and Grossi et al. [ICALP 2013], respectively. Experimental results show that our implementations support the operations efficiently while keeping the space proportional to the entropy of the input during the updates.

We consider the problem of designing succinct encodings for some intersection graphs on a circle, which include graph classes such as circle graphs, k-polygon-circle graphs, circle-trapezoid graphs among others. More specifically, we first prove a general counting lower bound, which is of independent interest, for these intersection graph classes, and then present a uniform encoding approach that lets us obtain matching lower and upper bounds for their succinct representation.

Clique-width is a well-studied graph parameter owing to its use in understanding algorithmic tractability. In this paper we design a succinct data structure for graphs on$n$vertices whose clique-width is at most$k \leq \epsilon \sqrt{\log n / \log \log n}$for some constant$0<\epsilon<1$, along with supporting degree, adjacency, neighborhood queries efficiently. This resolves an open problem of Kamali (Algorithmica-2018).

We consider practical implementations of compressed bit vectors, which support rank and select operations on a given bit-string, while storing thebit-string in compressed form. Our approach relies on variable-to-fixed (V2F) encodings of the bit-string, an approach that has not yet been considered systematically for practical encodings of bit-vectors. This approach leadsto fast practical implementations with low redundancy (i.e., the space used by the bit vector in addition to the compressed representation of the bit-string),and is a flexible and promising solution to the problem of supporting rank and select on moderately compressible bit-strings, such as those frequently found in real-world applications.

Let ∑ be a finite, ordered alphabet, and consider a string x=χ1χ2... χn ∈ ∑n. A secondary index for x answers alphabet range queries of the form: Given a range [αl,αr] ⊆ ∑, return the set I[αl,αr] = {i |χi ∈ >[αl,αr]}. Secondary indexes are heavily used in relational databases and scientific data analysis. It is well-known that the obvious solution, storing a dictionary for the set ∪i{χi} with a position set associated with each character, does not always give optimal query time. In this paper we give the first theoretically optimal data structure for the secondary indexing problem. In the I/O model, the amount of data read when answering a query is within a constant factor of the minimum space needed to represent the set I[αl,αr], assuming that the size of internal memory is (|∑| lg n)δ blocks, for some constant δ > 0. The space usage of the data structure is O(nlg |∑|) bits in the worst case, and we further show how to bound the size of the data structure in terms of the 0th order entropy of x. We show how to support updates achieving various time-space trade-offs.