We present a succinct representation of convex polyominoes, i.e., polyominoes whose intersection with every horizontal or vertical line forms a single contiguous segment. Our data structure uses$1.2074 n+o(n)$bits, matching the information-theoretic lower bound up to lower-order terms. It supports the following positional queries in$\mathcal{O}(1)$time: given a cell index$c, \operatorname{pos}(c)$returns its coordinates, and given coordinates (x, y), cell(x, y) returns the index of the cell located at (x, y), if such a cell exists. These queries, in turn, can be used to support a wide range of other queries in constant time, including navigation (adjacency, neighborhood, degree), distance, and shortest-path queries.

We provide a compact data structure for representing polyominoes that supports neighborhood and visibility queries. Neighborhood queries concern reporting adjacent cells to a given cell, and visibility queries determine whether a straight line can be drawn within the polyomino that connects two specified cells. For an arbitrary small ϵ > 0, our data structure can encode a polyomino with n cells in (3 + ϵ)n + o(n) bits while supporting all queries in constant time. The space complexity can be improved to 3n + o(n), while supporting neighborhood queries in $\mathcal{O}(1)$ and visibility queries in $\mathcal{O}(t(n))$ for any arbitrary t(n) ∈ ω(1). Previous attempts at enumerating polyominoes have indicated that at least 2.00091n−o(n) bits are required to differentiate between distinct polyominoes, which shows our data structure is compact.In addition, we introduce a succinct data structure tailored for bar graphs, a specific subclass of polyominoes resembling histograms. We show that a bar graph comprising n cells can be encoded using n + o(n) bits, enabling constant-time query processing. Meanwhile, n − 1 bits are necessary to represent any bar graph, proving our data structure is succinct.

We provide a compact representation of polyominoes with n cells that supports navigation and visibility queries in constant time. Our oracle takes 3n +o(n) bits. Previous enumeration efforts indicate that at least 2.00091 n -o(n) bits (likely 2.021 n -o(n) bits) are required to distinguish polyominoes, hence confirming that our oracle is compact.

The notion of clique-width for graphs is a relatively new topic which has received attention in the past decade. A graph has bounded clique-width if it can be represented as an algebraic expression on a constant number of labels associated with its vertices. Many computationally hard problems can be solved in polynomial time for graphs with bounded clique-width. Interestingly also, many graph families that arise in practice have bounded clique-width. In this paper, we present compact navigation oracles for graphs with bounded clique-width. Our oracles answer adjacency and neighborhood queries in constant time using O(n) space (i.e., O(n) bits) for a graph of size n, and report the degree of each given vertex, also in constant time, using O(n lg lg n) bits.

Balanced graph partitioning is a fundamental problem that is receiving growing attention with the emergence of distributed graph-computing (DGC) frameworks. In these frameworks, the partitioning strategy plays an important role since it drives the communication cost and the workload balance among computing nodes, thereby affecting system performance. However, existing solutions only partially exploit a key characteristic of natural graphs commonly found in the real-world: their highly skewed power-law degree distributions. In this paper, we propose High-Degree (are) Replicated First (HDRF), a novel streaming vertex-cut graph partitioning algorithm that effectively exploits skewed degree distributions by explicitly taking into account vertex degree in the placement decision. We analytically and experimentally evaluate HDRF on both synthetic and real-world graphs and show that it outperforms all existing algorithms in partitioning quality.

Social networks are large graphs that require multiple graph database servers to store and manage them. Each database server hosts a graph partition with the objectives of bal-ancing server loads, reducing remote traversals (edge-cuts), and adapting the partitioning to changes in the structure of the graph in the face of changing workloads. To achieve these objectives, a dynamic repartitioning algorithm is re-quired to modify an existing partitioning to maintain good quality partitions while not imposing a significant overhead to the system. In this paper, we introduce a lightweight repartitioner, which dynamically modifies a partitioning us-ing a small amount of resources. In contrast to the exist-ing repartitioning algorithms, our lightweight repartitioner is efficient, making it suitable for use in a real system. We integrated our lightweight repartitioner into Hermes, which we designed as an extension of the open source Neo4j graph database system, to support workloads over partitioned graph data distributed over multiple servers. Using real-world social network data, we show that Hermes leverages the lightweight repartitioner to maintain high quality partitions and provides a 2 to 3 times performance improvement over the de-facto standard random hash-based partitioning. 1.

List update is a key step during the Burrows-Wheeler transform (BWT) compression. Previous work has shown that careful study of the list update step leads to better BWT compression. Surprisingly, the theoretical study of list update algorithms for compression has lagged behind its use in real practice. To be more precise, the standard model by Sleator and Tarjan for list update considers a 'linear cost-of-access' model while compression incurs a logarithmic cost of access, i.e. accessing item i in the list has cost Theta(i) in the standard model but Theta(log i) in compression applications. These models have been shown, in general, not to be equivalent. This paper has two contributions: (1) We give the first theoretical proof that the commonly used Move-To-Front (MTF) has good performance under the compression logarithmic cost-of-access model. This has long been known in practice but a formal proof under the logarithmic cost compression model was missing until now, (2) we further refine the online compression model to reflect its use under compression by applying the recently developed 'online algorithms with advice' model. This advice model was initially a purely theoretical construct in which the online algorithm has access to an all powerful oracle during the computation. We show that surprisingly, this seemingly unrealistic model can be used to produce better multi-pass compression algorithms. More precisely, we introduce an 'almost-online' list update algorithm, which we term BIB which results in a compression scheme which is superior to schemes using standard online algorithms, in particular those of MTF and TIMESTAMP. For example, for the files in the standard Canterbury Corpus, the compression ratio of the scheme that uses BIB is 33.66 on average, while the compression ratios for the schemes that use MTF and TIMESTAMP are respectively 34.25 and 36.30.

The List-Update Problem is a well studied online problem with direct applications in data compression. Although the model proposed by Sleator & Tarjan has become the standard in the field for the problem, its applicability in some domains, and in particular for compression purposes, has been questioned. In this paper, we focus on two alternative models for the problem that arguably have more practical significance than the standard model. We provide new algorithms for these models, and show that these algorithms outperform all classical algorithms under the discussed models. This is done via an empirical study of the performance of these algorithms on the reference data set for the list-update problem. The presented algorithms make use of the context-based strategies for compression, which have not been considered before in the context of the list-update problem and lead to improved compression algorithms. In addition, we study the adaptability of these algorithms to different measures of locality of reference and compressibility.