REVersed Indexes $\approx$ VALues in Wavelet Trees
REVIVAL in Wavelet Trees

Data Compression constructs indexes to reduce the elementary size of original values, and therefore the storage cost is saved. Lower-bounded by Shannon ([5]), a fundamental limit to lossless data compression exists, which is known as the entropy rate. For decades, an extensive amount of efforts are paid on the potential breakthrough of this limit.

This work classifies prior work into two types. One is to improve the efficiency of lossless compression; and the other is to expand the functionalities of lossless compression. The latter is the focus in this work. Succinct Data Structures, originally formalized by Jacobson ([2]), are proposed to expand the functionalities of lossless compression. These data structures use an amount of space that is "close" to the entropy rate, while still retaining the functionality for efficient query operations. Therefore, queries on data can be directly performed on compression.

However, to perform any computation, it is still needed for decompression first in Succinct Data Structures. This work centers the focus on a particular Succinct Data Structure - Wavelet Tree ([1]). Wavelet Tree is used to store strings in compressed space. The definition of Wavelet Tree is achieved by recursively partitioning the alphabet (from the string) into pairs of subsets; the leaves correspond to individual symbols of the alphabet, and at each node a bitvector stores whether a symbol of the string belongs to one subset or the other.

This work first breaks the assumption of Wavelet Tree (or all lossless compression methods), by directly taking Leibniz Binary System ([3]) as the reference point (rather than character encoding such as ASCII codes). We find that: the encoding patterns of Leibniz Binary System ([3]) can be highly correlated with the formalization of Wavelet Tree ([1]), with only the bit reversal. Therefore we derive the discovery of Reversed Indexes $=$ Values, which is described in Section 1.1.1.

This work then rolls back to the formalization of Wavelet Tree (or all lossless compression methods), by refining the reference point back to the character encoding. We find that: the above approach can be generalized to character encoding, by (1) simply accounting for common subsequence(s) in bits; and (2) utilizing these subsequences as patterns, to recover indexes to values. We also discuss extensions to other scenarios (e.g., other data types). It is described in Section 1.1.2.

This work finally conjectures potential implications of the above ideas, by analyzing the benefits (and hypothesizing potential modifications to RAM model) for “Indexes $\approx$ Values" principle. This work considers two viewpoints by leveraging the classification from ([4]). We first view Wavelet Tree as a compression method, and the benefits can be directly derived. Then we view Wavelet Tree as a data structure, and the design space is discussed and we assume it deserves further investigations. It is described in Section 1.1.3.

In summary, the discovery of Reversed Indexes $\approx$ Values (REVIVAL) showcases the feasibility to bridge near-optimal lossless compression with the Leibniz Binary System, which makes the following three major contributions.

• •

  The bridge between near-optimal lossless compression and Leibniz Binary System enables Computation Directly on Compression.

• •

  The discovery expands the usability of Succinct Data Structures, and this delivers polymorphic functionalities within a single piece of the information.

• •

  The bridge motivates a revamp of RAM model to support the above idea, and demonstrates potential merits of fine-grained RAM operations.

When is a revival needed? When carelessness and unconcern keep the people asleep.

We first give an overview of the results in this work. Then we summarize the techniques developed in this work.

Wavelet Tree (WT) is a Succinct Data Structure, that can support $rank$ and $select$ operations efficiently, to store strings in compressed space ([1]).

We first introduce Reversed Indexes $=$ Values. We make the discovery by changing the reference point from character encoding into Leibniz Binary System ([3]).

With the strict definition of Reversed Indexes $=$ Values, we present a more general form called Reversed Indexes $\approx$ Values.

We discuss benefits from (and potential modifications to) RAM, so that we can support the usage of Reversed Indexes $\approx$ Values (and their potential variants). The key to support the polymorphic functionalities is to enable the retrieval of these values efficiently. We leverage Reversed Indexes $\approx$ Values as an example: based on the usage of WT, we analyze (and provide potential modifications) using RAM for Reversed Indexes $\approx$ Values. We first view WT as a compression method; and then we view WT as a data structure.

This work describes a discovery to bridge near-optimal lossless compression with Leibniz Binary System. It (1) makes Computation Directly on Compression feasible; and (2) enables polymorphic functionalities (i.e., efficient queries and computation) within a single piece of the information. This work also provides an initial analysis of the benefits from the method (and potentially other extensions), and suggests potential modifications. We conjecture that: with Reversed Indexes $\approx$ Values, everything old can be new now.