Given a static array of n totally ordered objects, the range minimum query problem is to build a data structure that allows us to answer efficiently subsequent on-line queries of the form “what is the position of a minimum element in the subarray ranging from i to j?”. We focus on two settings, where (1) the input array is available at query time, and (2) the input array is available only at construction time. In setting (1), we show new data structures (a) of size $\frac{2n}{c(n)}-\Theta\bigl(\frac{n\lg\lg n}{c(n)\lg n}\bigr)$ bits and query time $O(c(n))$ for any positive integer function $c(n)\in O\bigl(n^\varepsilon\bigr)$ for an arbitrary constant $0<\varepsilon<1$, or (b) with $O(nH_k)+o(n)$ bits and $O(1)$ query time, where $H_k$ denotes the empirical entropy of kth order of the input array. In setting (2), we give a data structure of size $2n+o(n)$ bits and query time $O(1)$. All data structures can be constructed in linear time and almost in-place.

The Range Minimum Query (RMQ) Problem is to preprocess an array A of length n in 0(n) time such that subsequent on-line queries asking for the position of a minimal element between two specified indices can be obtained in constant time. Several solutions to this problem have been proposed, starting with Berkman and Vishkin's linear-space solution [6], and leading to a succinct solution using only 2n + o(n) bits in addition to the input array [12]. The theoretical contribution of this article is to push this latter approach one step further and show that for compressible input arrays the RMQ-information can be compressed as well. In particular, we show that information for 0(l)-RMQs can be stored within the same entropy bounds that are achieved by the currently best schemes for storing A itself in compressed form, while still being able to access O(logn) contiguous bits in O(l) time [10]. Two such entropy- bounded schemes for 0(l)-RMQs are developed, each with its own practical advantage. We test these two methods extensively and compare them to three other schemes for RMQs: the currently best non-succinct solution [2], and two succinct approaches: Sadakane's 4n + o(n)-bit solution [22], and our own 2n + o(n)-bit solution. The results of this practical evaluation are (1) the practical space consumptions of the non-compressed schemes scale surprisingly well with their theoretical guarantees, and (2) for compressible input arrays our new compressed schemes can indeed reduce the space, with little or no slowdown in query time.

We present a method to mine strings that are frequent in one database and infrequent in another. The method uses suffix- and lcp-arrays that can be computed extremely fast and space efficiently, and further exhibit a good locality behavior. Experiments with several biologically relevant data sets show that our approach outperforms existing methods in terms of time and space.

Embeddings of various graph classes into hypercubes have been widely studied. Almost all these classes are regularly structured graphs such as meshes, complete trees or pyramids. In this paper, we present a general method for one-to-one embeddings of irregularly structured graphs into their optimal hypercubes, based on extended edge bisectors of graphs. An extended edge bisector is an edge bisector with the additional property that a certain subset of the vertices is distributed more or less evenly among the two halves of the bisected graph. The dilation and congestion of our embedding depends on the quality of the extended edge bisector. Moreover, if the extended bisection can be computed efficiently on the hypercube, then so can the embedding. Our embedding technique can also be applied to embeddings into hypercube-like topologies such as folded hypercubes, twisted cubes, crossed cubes, Möbius cubes, Fibonacci cubes or star graphs.