The Trie Measure, Revisited

Consider the problem of encoding a set of integers $S\subseteq U=\{0,\mathrm{\dots },u-1\}$ (without loss of generality, we assume $u$ to be a power of two), so as to minimize the overall number of bits used to represent $S$. In their seminal work on data-aware measures, Gupta et al. [10] proposed and analyzed an encoding for sets of integers based on the idea of packing the integers (seen as strings of $\log u$ bits) into a binary trie: this allows to avoid storing multiple times shared prefixes among the encodings of the integers. The number of edges in such a trie is known as the trie measure of the set. See Figure 1 for an example.

Gupta et al. also showed that this measure approaches worst-case entropy on expectation when the integers are shifted by a uniformly-random quantity modulo $u$, i.e. when building the trie over the set $S+a≔\{x+a\mathrm{mod}u:x\in S\}$ for a uniform $a\in U$. See Figure 2.

In this paper, we revisit this problem in two natural directions: (1) we move from one set to a sequence of sets, and (2) we study more general prefix-free integer encodings. More formally, given $n$ subsets $S_1,\mathrm{\dots },S_n$ of $U$, having total cardinality $N={\sum }_{i=1}^n|S_i|$, we study the problem of finding a prefix-free encoding $\mathrm{enc}:U\to {\{0,1\}}^{+}$ minimizing the trie measure of these sets, i.e. the total number of edges in the $n$ binary tries ${𝒯}_1,\mathrm{\dots },{𝒯}_n$, where ${𝒯}_i$ is the trie packing the encoded integers $\{\mathrm{enc}(x):x\in S_i\}$. Solving the problem on set sequences finds applications in data structures for rank/select queries on set sequences – also known in the literature as degenerate strings – , an important toolbox in indexes for labeled graphs [8, 6, 5, 7]. Such applications stem from the recent work of Alanko et al. [1], who showed how to solve rank and select queries on set sequences with a data structure – the subset wavelet tree – implicitly encoding sets as tries. While [1] only considered the standard binary (balanced) encoding, their technique works for any prefix-free encoding. As a result, our work can directly be applied to optimize the space of their data structure. Another application is the offline set intersection problem where the goal to preprocess subsets of the universe, so that later given a set of indices of the sets, one can compute the intersection of the sets space-time efficiently. Arroyuelo and Castillo [2] presented an adaptive approach that uses a trie representation of sets and they showed that it can benefit from its space-efficient representation.

We begin by showing that finding the optimal such prefix-free encoding is equivalent to the following natural optimization problem: find the minimum-cost sequence of binary unions that merges $u$ given sets, where the cost of a union is the sum of the two sets’ cardinalities. As this problem was shown to be NP-hard by Ghosh et al. [9], we focus on particular (hopefully easier) families of encodings. We start by studying the shifted encoding of Gupta et al., who did not discuss the problem of finding the optimal value of $a\in U$ minimizing the corresponding trie measure. We describe an algorithm solving the problem in $O(u+N\log u)$ time. The algorithm is based on the fact that, under this encoding, the trie measure has a highly periodic sub-structure as a function of the shift $a$. We then remove the linear dependency on the universe size and achieve running time $O(N{\log }^{2}u)$ by storing this periodic structure with a DAG. $O(N\log u)$ running time is also possible by merging the two ideas, but for space constraints we will describe it in the extended version of this article. We also want to remark that the general prefix-free encoding problem is not only difficult to compute, but also it requires to store the ordering of the elements in addition to the trie representation. By a simple enumeration, it needs $O(N^{\prime }\log u)$ bits of space where $N^{\prime }$ is the cardinality of the union of the sets (i.e., the number of distinct elements over all sets). On the other hand, the shifted encoding only requires $O(\log u)$ bits since it is sufficient to store a single integer $a\in U$.

We then move to ordered encodings: here, the encoding must preserve lexicographically the order of the universe $U$ (i.e. the standard integer order). In this case, we show that the textbook solution of Knuth [12] based on dynamic programming, running in $O(N+u^3)$-time, can be adapted to our scenario. We observe that essentially the same solution allows also shifting the universe (like in the shifted encoding discussed above) at no additional cost. As a result, we obtain that the best shifted ordered encoding can be computed in $O(N+u^3)$-time as well. This encoding is never worse than the best shifted and the best ordered encodings.

We conclude our paper with an experimental evaluation of our algorithms on real datasets, showing how these encodings perform with respect to the worst and average-case scenario.

A bit-string is a finite sequence of bits, i.e., an element from ${\{0,1\}}^{\ast }$. We count indices from 1, so that for $\beta \in {\{0,1\}}^{+}$, $\beta [1]$ is the first element. With $\prec$ we denote the lexicographic order among bit-strings and with $|\cdot |$ we denote the length of bit-strings. For two strings $\alpha$ and $\beta$ of possibly different length, each not being a prefix of the other, we use $\oplus$ to denote the (non-commutative) operator defined as $\alpha \oplus \beta =\beta [j\mathrm{\dots }|\beta |]$, where $j-1$ is the length of the longest common prefix of $\alpha$ and $\beta$, i.e., $\alpha [i]=\beta [i]$ for and $\alpha [j]\ne \beta [j]$.

We denote with $U:=\{0,1,\mathrm{\dots },u-1\}$ the integer universe and we assume that $u$ is a power of two. Logarithms are in base 2, so $\log (x)$ indicates ${\log }_2(x)$. In particular, $\log u$ is an integer. Notation $[n]$ indicates the set $\{1,2,\mathrm{\dots },n\}$. For integers , we denote with $[\mathrm{\ell },r)$ an interval of integers $\{\mathrm{\ell },\mathrm{\ell }+1,\mathrm{\cdots },r-2,r-1\}$ and if $\mathrm{\ell }=r$, then $[\mathrm{\ell },r)=\mathrm{\varnothing }$ is the empty set. We use double curly braces $\{\{\mathrm{\dots }\}\}$ to represent multisets. Given a multiset $ℐ$ containing subsets of $U$ and an integer $a\in U$, the depth of $ℐ$ at position $a$ is defined as the number of elements of $ℐ$ that contain $a$. For integer $a,b$ and $p$ with $p\ge 1$, we say $a{\equiv }_{p}b$ if and only if $a\mathrm{mod}p=b\mathrm{mod}p$. For a predicate $P$, we use $\mathrm{𝟙}[P]$ to denote the indicator function that is 1 if $P$ holds and zero otherwise.

A prefix-free encoding of $U$ is a function $\mathrm{enc}:U\to {\{0,1\}}^{+}$ that satisfies that for no two distinct $x,y\in U$, it holds that $\mathrm{enc}(x)$ is a prefix of $\mathrm{enc}(y)$. For a set $S\subseteq U$, we let $\mathrm{enc}(S):=\{\mathrm{enc}(x):x\in S\}$ be the set of bitstrings obtained from encoding $S$ via $\mathrm{enc}$. We say that $\mathrm{enc}$ is ordered if and only if implies $\mathrm{enc}(x)\prec \mathrm{enc}(y)$ for all $x,y\in U$.

We study the following trie measure, generalized from the particular cases studied in [10]:

In this article we work, more generally, with sequences of sets. The above definitions generalize naturally:

Throughout the article, we will denote with $N={\sum }_{i=1}^n|S_i|$ the total cardinality of the input sets $S_1,\mathrm{\dots },S_n$. Definition 2 leads to the central problem explored in this paper, tackled in Sections 3 and 4: given a sequence $𝒮=⟨S_1,\mathrm{\dots },S_n⟩$ of $n$ subsets of $U$, find the encoding $\mathrm{enc}$ minimizing $\mathrm{trie}(\mathrm{enc}(𝒮))$, possibly focusing on particular sub-classes of prefix-free encodings.

A particularly interesting such sub-class, originally introduced by Gupta et al. [10], is that of shifted encodings:

We call $\mathrm{trie}(𝒮+a)$ the shifted trie measure. In Section 3 we study the problem of finding the value $a\in U$ minimizing $\mathrm{trie}(𝒮+a)$, a problem left open by Gupta et al. [10].

Given a sequence $𝒮=⟨S_1,\mathrm{\cdots },S_n⟩$ of $n$ subsets of $U$, in this section we study the problem of finding an optimal shift $a\in U$ that minimizes $\mathrm{trie}(𝒮+a)$. After finding a useful reformulation of $\mathrm{trie}(𝒮+a)$, we describe an algorithm for finding an optimal shift $a$. The algorithm is parameterized on an abstract data structure for integer sequences. Using a simple array, we obtain an $O(u+N\log u)$-time algorithm. A DAG-compressed segment tree, on the other hand, gives an $O(N{\log }^{2}u)$-time algorithm.

To compute the optimal ordered encoding, we employ the equivalent problem formulation of Section 2.1. For any $x\in U$, let $A_x=\{i\in [n]:x\in S_i\}$. Recall that we can assume, w.l.o.g., that $A_x\ne \mathrm{\varnothing }$ for all $x\in U$ and $S_i\ne \mathrm{\varnothing }$ for all $i\in [n]$. Our goal is to find the binary tree $T$ with leaves $0,\mathrm{\dots },u-1$ (in this order) minimizing $c(T):={\sum }_{v\in T\setminus \{r(T)\}}|{\bigcup }_{x\in L(T_v)}{A}_x|$. For a binary tree $T$, let $T_{\mathrm{\ell }}$ and $T_r$ be the left and right sub-tree of the root of $T$, respectively. We show that the dynamic programming solution of Knuth [12] can be applied to our scenario. Consider the following alternative cost function: $d(T):=\left|{\bigcup }_{x\in L(T)}{A}_x\right|+d(T_{\mathrm{\ell }})+d(T_r)$. The (recursive) function $d(T)$ is related to $c(T)$ by the following equality: $c(T)=d(T)-|{\bigcup }_{x\in L(T)}{A}_x|$. It is not hard to turn the definition of $d(T)$ into a set of dynamic programming formulas computing both the best tree $T$ and its cost $d(T)$ by creating, for every , a variable $d_{x,y}$ whose final value will be ${\min }_{T^{\prime }}d(T^{\prime })$ (where $T^{\prime }$ runs over all trees such that $L(T^{\prime })=\{x,x+1,\mathrm{\dots },y\}$), and a pre-computed constant $a_{x,y}=\left|{\bigcup }_{t=x}^y{A}_t\right|$. Given the constants $a_{x,y}$, the following set of dynamic programming formulas finds (bottom up, i.e., by increasing $y-x$) the value $c(T)=d(T)-|{\bigcup }_{x\in L(T)}{A}_x|=d_{0,u-1}-a_{0,u-1}$ for the optimal tree $T$ and, by standard backtracking, the tree $T$ itself:

The optimal tree’s topology can be retrieved by backtracking: if $L(T^{\prime })=\{x,x+1,\mathrm{\dots },y\}$, then the number of leaves in $T_{\mathrm{\ell }}^{\prime }$ is equal to (we start from the root of $T$ with $x=0$ and $y=u-1$). Below, we show how to compute constants $a_{x,y}$ in $O(N+u^2)$ time. Since the above formulas can be evaluated bottom-up (i.e. by increasing $y-x$) in $O(u^3)$ time²²2In his work [12], Knuth shows how to evalutate these recursive formulas to $O(u^2)$ time. In the simpler case considered in his article (corresponding to our problem with pairwise-disjoint $A_0,\mathrm{\dots },A_{u-1}$), one can bound so that the overall cost of looking for all those optimal values of $z$ amortizes to $u^2$. Unfortunately, in our scenario we haven’t been able to prove that the same technique can still be applied., the overall running time of the algorithm is $O(N+u^3)$.

We now show how to compute efficiently the constants $a_{x,y}$. We describe an overview of the algorithm (see Algorithm 2 for the pseudocode). We add to the sequence two sets $A_{-1}=A_u=[n]$, respectively at the beginning and end: the new sequence becomes $A_{-1},A_0,\mathrm{\dots },A_{u-1},A_u$. The main idea behind the algorithm is to initially compute inside $a_{x,y}$ the number of elements from $[n]$ that are missing from $\left|{\bigcup }_{t=i}^j{A}_t\right|$. Then, the substitution $a_{x,y}\leftarrow n-a_{x,y}$ will yield the final result.

We initialize $a_{x,y}\leftarrow 0$ for all $0\le x,y\le u$. Let $A_{x+1},A_{x+2},\mathrm{\dots },A_{y-1}$ be a maximal contiguous subsequence of sets not containing a given $i\in [n]$, that is, (i) $i\notin A_{x^{\prime }}$ for all $x^{\prime }=x+1,x+2,\mathrm{\dots },y-1$, (ii) $i\in A_x$, and (iii) $i\in A_y$. Then, $i\notin \left|{\bigcup }_{t=x^{\prime }}^{y^{\prime }}{A}_t\right|$ for every $i\le x^{\prime }\le y^{\prime }\le y$. Imagine then adding one unit to $a_{x^{\prime },y^{\prime }}$ for all $(x^{\prime },y^{\prime })\in [x+1,y-1]\times [x+1,y-1]$. Clearly, if we can achieve this for every $i\in [n]$ and every such maximal contiguous subsequence of sets not containing $i$, at the end each $a_{x,y}$ will contain precisely the value $n-\left|{\bigcup }_{t=x}^y{A}_t\right|$. The issue is, of course, that adding one unit to $a_{x^{\prime },y^{\prime }}$ for all , costs time $O(xy)$ if done naively. The crucial observation is that this task can actually be performed in constant time using (bidimensional) partial sums: see Figure 7 for an example. Ultimately, this trick allows us computing all $a_{x,y}$ in the claimed $O(N+u^2)$ running time.