Abstract We study succinct variants of B trees in the word RAM model that require $$s + o(s)$$ bits of space, where s is the number of bits essentially needed for storing keys and possibly other satellite values. Assuming that elements are sorted by keys (not necessarily in the order of their integer representations), our B trees support standard operations such as searching, insertion and deletion of elements. In some applications it is useful to associate a satellite value to each element, and to support aggregate operations such as computing the sum of values, the minimum/maximum value in a given range, or search operations based on those values. We propose a B tree representation storing n elements in $$s + \mathcal {O}(s / \lg n)$$ bits of space and supporting all mentioned operations in $$\mathcal {O}(\lg n)$$ time. Operations on integer-ordered keys and satellite values can be accelerated to $$\mathcal {O}(\lg n / \lg \lg n)$$ time if we use $$s + \mathcal {O}(s \lg \lg n / \lg n)$$ bits of space. The time is retained for special kind of aggregate functions that can be computed bit-parallel in constant time. For integer-ordered keys, we can also compress the space s to match compression measures using difference encoding of the keys while retaining the operational time complexities. For the last enhancement, we allow us to pre-compute tables of $$o(n)$$ bits.

Given a string T of length N, the goal of grammar compression is to construct a small context-free grammar generating only T. Among existing grammar compression methods, RePair (recursive paring) [Larsson and Moffat, 1999] is notable for achieving good compression ratios in practice. In this paper, we propose the first RePair algorithm working in compressed space, i.e., potentially o(N) space for highly compressible texts. The key idea is to give a new way to restructure an arbitrary (context-free) grammar S for T into RePair(T) in compressed space and time. We propose an algorithm for RePair(T) running in O(min(N, nm log N)) space and expected O(min(N, nm log N) m) time or O(min(N, nm log N) log log N) time, where n is the size of S and m is the number of variables in RePair(T). We implemented our O(min(N, nm log N) m)-time algorithm and show it can actually run in compressed space. We also present a new approach to reduce the peak memory usage of existing RePair algorithms combining with our algorithms, and show that the new approach outperforms, both in computation time and space, the most space efficient linear-time RePair implementation to date.

A grammar compression is a context-free grammar (CFG) deriving a single string deterministically. For an input string of length N over an alphabet of size sigma, the smallest CFG is O(log N)-approximable in the offline setting and O(log N log^* N)-approximable in the online setting. In addition, an information-theoretic lower bound for representing a CFG in Chomsky normal form of n variables is log (n!/n^sigma) + n + o(n) bits. Although there is an online grammar compression algorithm that directly computes the succinct encoding of its output CFG with O(log N log^* N) approximation guarantee, the problem of optimizing its working space has remained open. We propose a fully-online algorithm that requires the fewest bits of working space asymptotically equal to the lower bound in O(N log log n) compression time. In addition we propose several techniques to boost grammar compression and show their efficiency by computational experiments.

When we consider any applications that use large data continuously produced, it is necessary for the system developer to apply some fast method that migrates the data stream to the processors. Even if we consider the internal communications of a BigData processing system, applications that treat dataflow such as from a sensor system with tens of channels to a peripheral bus for interconnections among processing modules are currently facing a critical frequency problem to exchange data in the busses because the data size has become very large. One of the best solutions to improve the situation is to compress the exchanged data stream during the transfer in the interconnection among processing modules. However, the conventional compression mechanisms used by software solutions such as ZIP and LZW need to aggregate the compressed data and a table that includes the information for recovering the compressed data to the original one. This paper shows a novel compression mechanism based on the symbol pair matching that uses a coherent and static lookup table with a limited number of entries of the symbol pairs. Building a compression pipeline with multiple tables we can implement an effective data path of the stream-based compression with a reconfigurable and flexible compression ratio applying trained tables from the original data characteristics. This paper shows the algorithm design and an implementation example on an FPGA using the content addressable memory and reports the performance of the hardware.

1 Introduction By rapid progress of network and storage technologies, a huge amount of electronic data such as Web pages and XML data [23] has been available on intra and internet. These electronic data are heterogeneous collection of ill-structured data that have no rigid structures, and often called semi-structured data [1]. Hence, there have been increasing demands for automatic methods for extracting useful information, particularly, for discovering rules or patterns from large collections of semi-structured data, namely, semi-structured data mining [6, 11, 18, 19, 21, 25].