Succinct data structure

In computer science, a succinct data structure is a data structure which uses an amount of space that is "close" to the information-theoretic lower bound, but (unlike other compressed representations) still allows for efficient query operations. The concept was originally introduced by Jacobson ^[1] to encode bit vectors, (unlabeled) trees, and planar graphs. Unlike general lossless data compression algorithms, succinct data structures retain the ability to use them in-place, without decompressing them first. A related notion is that of a compressed data structure, insofar as the size of the stored or encoded data similarly depends upon the specific content of the data itself.

Suppose that ${\displaystyle Z}$ is the information-theoretical optimal number of bits needed to store some data. A representation of this data is called:

• implicit if it takes ${\displaystyle Z+O(1)}$ bits of space,
• succinct if it takes ${\displaystyle Z+o(Z)}$ bits of space, and
• compact if it takes ${\displaystyle O(Z)}$ bits of space.

For example, a data structure that uses ${\displaystyle 2Z}$ bits of storage is compact, ${\displaystyle Z+{\sqrt {Z}}}$ bits is succinct, ${\displaystyle Z+\lg Z}$ bits is also succinct, and ${\displaystyle Z+3}$ bits is implicit.

Implicit structures are thus usually reduced to storing information using some permutation of the input data; the most well-known example of this is the heap.

Succinct indexable dictionaries

Succinct indexable dictionaries, also called rank/select dictionaries, form the basis of a number of succinct representation techniques, including binary trees, ${\displaystyle k}$-ary trees and multisets, ^[2] as well as suffix trees and arrays. ^[3] The basic problem is to store a subset ${\displaystyle S}$ of a universe ${\displaystyle U=[0\dots n)=\{0,1,\dots ,n-1\}}$, usually represented as a bit array ${\displaystyle B[0\dots n)}$ where ${\displaystyle B[i]=1}$ iff ${\displaystyle i\in S.}$ An indexable dictionary supports the usual methods on dictionaries (queries, and insertions/deletions in the dynamic case) as well as the following operations:

• ${\displaystyle \mathbf {rank} _{q}(x)=|\{k\in [0\dots x]:B[k]=q\}|}$
• ${\displaystyle \mathbf {select} _{q}(x)=\min\{k\in [0\dots n):\mathbf {rank} _{q}(k)=x\}}$

for ${\displaystyle q\in \{0,1\}}$.

In other words, ${\displaystyle \mathbf {rank} _{q}(x)}$ returns the number of elements equal to ${\displaystyle q}$ up to position ${\displaystyle x}$ while ${\displaystyle \mathbf {select} _{q}(x)}$ returns the position of the ${\displaystyle x}$-th occurrence of ${\displaystyle q}$.

There is a simple representation ^[4] which uses ${\displaystyle n+o(n)}$ bits of storage space (the original bit array and an ${\displaystyle o(n)}$ auxiliary structure) and supports rank and select in constant time. It uses an idea similar to that for range-minimum queries; there are a constant number of recursions before stopping at a subproblem of a limited size. The bit array ${\displaystyle B}$ is partitioned into large blocks of size ${\displaystyle l=\lg ^{2}n}$ bits and small blocks of size ${\displaystyle s=\lg n/2}$ bits. For each large block, the rank of its first bit is stored in a separate table ${\displaystyle R_{l}[0\dots n/l)}$; each such entry takes ${\displaystyle \lg n}$ bits for a total of ${\displaystyle (n/l)\lg n=n/\lg n}$ bits of storage. Within a large block, another directory ${\displaystyle R_{s}[0\dots l/s)}$ stores the rank of each of the ${\displaystyle l/s=2\lg n}$ small blocks it contains. The difference here is that it only needs ${\displaystyle \lg l=\lg \lg ^{2}n=2\lg \lg n}$ bits for each entry, since only the differences from the rank of the first bit in the containing large block need to be stored. Thus, this table takes a total of ${\displaystyle (n/s)\lg l=4n\lg \lg n/\lg n}$ bits. A lookup table ${\displaystyle R_{p}}$ can then be used that stores the answer to every possible rank query on a bit string of length ${\displaystyle s}$ for ${\displaystyle i\in [0,s)}$; this requires ${\displaystyle 2^{s}s\lg s=O({\sqrt {n}}\lg n\lg \lg n)}$ bits of storage space. Thus, since each of these auxiliary tables take ${\displaystyle o(n)}$ space, this data structure supports rank queries in ${\displaystyle O(1)}$ time and ${\displaystyle n+o(n)}$ bits of space.

To answer a query for ${\displaystyle \mathbf {rank} _{1}(x)}$ in constant time, a constant time algorithm computes:

• ${\displaystyle \mathbf {rank} _{1}(x)=R_{l}[\lfloor x/l\rfloor ]+R_{s}[\lfloor x/s\rfloor ]+R_{p}[x\lfloor x/s\rfloor ,x{\text{ mod }}s]}$

In practice, the lookup table ${\displaystyle R_{p}}$ can be replaced by bitwise operations and smaller tables that can be used to find the number of bits set in the small blocks. This is often beneficial, since succinct data structures find their uses in large data sets, in which case cache misses become much more frequent and the chances of the lookup table being evicted from closer CPU caches becomes higher. ^[5] Select queries can be easily supported by doing a binary search on the same auxiliary structure used for rank; however, this takes ${\displaystyle O(\lg n)}$ time in the worst case. A more complicated structure using ${\displaystyle 3n/\lg \lg n+O({\sqrt {n}}\lg n\lg \lg n)=o(n)}$ bits of additional storage can be used to support select in constant time. ^[6] In practice, many of these solutions have hidden constants in the ${\displaystyle O(\cdot )}$ notation which dominate before any asymptotic advantage becomes apparent; implementations using broadword operations and word-aligned blocks often perform better in practice. ^[7]

Entropy-compressed solutions

The ${\displaystyle n+o(n)}$ space approach can be improved by noting that there are ${\displaystyle \textstyle {\binom {n}{m}}}$ distinct ${\displaystyle m}$-subsets of ${\displaystyle [n)}$ (or binary strings of length ${\displaystyle n}$ with exactly ${\displaystyle m}$ 1’s), and thus ${\displaystyle \textstyle {\mathcal {B}}(m,n)=\lceil \lg {\binom {n}{m}}\rceil }$ is an information theoretic lower bound on the number of bits needed to store ${\displaystyle B}$. There is a succinct (static) dictionary which attains this bound, namely using ${\displaystyle {\mathcal {B}}(m,n)+o({\mathcal {B}}(m,n))}$ space. ^[8] This structure can be extended to support rank and select queries and takes ${\displaystyle {\mathcal {B}}(m,n)+O(m+n\lg \lg n/\lg n)}$ space. ^[2] Correct rank queries in this structure are however limited to elements contained in the set, analogous to how minimal perfect hashing functions work. This bound can be reduced to a space/time tradeoff by reducing the storage space of the dictionary to ${\displaystyle {\mathcal {B}}(m,n)+O(nt^{t}/\lg ^{t}n+n^{3/4})}$ with queries taking ${\displaystyle O(t)}$ time. ^[9]

It is also possible to construct a indexible dictionary supporting rank (but not select) that uses fewer than ${\displaystyle \textstyle {\mathcal {B}}(m,n)}$ bits. Such a dictionary is called a monotone minimal perfect hash function, and can be implemented using as few as ${\displaystyle O(m\log \log \log n)}$ bits. ^{[10] [11]}

Succinct hash tables

A succinct hash table, also known as a succinct unordered dictionary, is a data structure that stores ${\displaystyle m}$ keys from a universe ${\displaystyle \{0,1,\dots ,n-1\}}$ using space ${\displaystyle (1+o(1)){\mathcal {B}}(m,n)}$ bits, and while supporting membership queries in constant expected time. If a succinct hash table also supports insertions and deletions in constant expected time, then it is referred to as dynamic, and otherwise it is referred to as static.

The first dynamic succinct hash table was due to Raman and Rao in 2003. ^[12] In the case where ${\displaystyle n={\text{poly}}(m)}$, their solution uses space ${\displaystyle {\mathcal {B}}(m,n)+O(m\log \log m)}$ bits. Subsequently, it was shown that this space bound could be improved to ${\displaystyle {\mathcal {B}}(m,n)+O(m\log \log \log \cdots \log m)}$ bits for any constant number of logarithms ^[13] and a little after that this bound was also optimal. ^{[14] [15]} The latter solution supports all operations in worst-case constant time with high probability.

The first static succinct hash table was due to Pagh in 1999. ^{[16] [17]} In the case where ${\displaystyle n={\text{poly}}(m)}$, their solution uses space ${\displaystyle {\mathcal {B}}(m,n)+O(m(\log \log m)^{2}/\log m)}$ bits, and supports worst-case constant-time queries. This bound was subsequently improved to ${\displaystyle {\mathcal {B}}(m,n)+m/{\text{poly}}\log m}$ bits, ^[18] and then to ${\displaystyle {\mathcal {B}}(m,n)+{\text{poly}}\log m}$ bits. ^[19] Whereas the first two solutions ^{[17] [18]} support worst-case constant-time queries, the final one supports constant expected-time queries. ^[19] The final solution also requires access to a lookup table of size ${\displaystyle n^{\epsilon }}$, but this lookup table is independent of the set of elements being stored. ^[19]

Other examples

A string with an arbitrary length (Pascal string) takes Z + log(Z) space, and is thus succinct. If there is a maximum length – which is the case in practice, since 2³² = 4 GiB of data is a very long string, and 2⁶⁴ = 16 EiB of data is larger than any string in practice – then a string with a length is also implicit, taking Z + k space, where k is the number of data to represent the maximum length (e.g., 64 bits).

When a sequence of variable-length items (such as strings) needs to be encoded, there are various possibilities. A direct approach is to store a length and an item in each record – these can then be placed one after another. This allows efficient next, but not finding the kth item. An alternative is to place the items in order with a delimiter (e.g., null-terminated string). This uses a delimiter instead of a length, and is substantially slower, since the entire sequence must be scanned for delimiters. Both of these are space-efficient. An alternative approach is out-of-band separation: the items can simply be placed one after another, with no delimiters. Item bounds can then be stored as a sequence of length, or better, offsets into this sequence. Alternatively, a separate binary string consisting of 1s in the positions where an item begins, and 0s everywhere else is encoded along with it. Given this string, the ${\displaystyle select}$ function can quickly determine where each item begins, given its index. ^[20] This is compact but not succinct, as it takes 2Z space, which is O(Z).

Another example is the representation of a binary tree: an arbitrary binary tree on ${\displaystyle n}$ nodes can be represented in ${\displaystyle 2n+o(n)}$ bits while supporting a variety of operations on any node, which includes finding its parent, its left and right child, and returning the size of its subtree, each in constant time. The number of different binary trees on ${\displaystyle n}$ nodes is ${\displaystyle {\tbinom {2n}{n}}}$${\displaystyle /(n+1)}$. For large ${\displaystyle n}$, this is about ${\displaystyle 4^{n}}$; thus we need at least about ${\displaystyle \log _{2}(4^{n})=2n}$ bits to encode it. A succinct binary tree therefore would occupy only ${\displaystyle 2}$ bits per node.

See also

• Minimal perfect hash function
• Succinct Non-Interactive ARguments of Knowledge

References

1. Jacobson, G. J (1988). Succinct static data structures (Ph.D. thesis). Pittsburgh, PA: Carnegie Mellon University.
2. Raman, R.; V. Raman; S. S Rao (2002). "Succinct indexable dictionaries with applications to encoding k-ary trees and multisets". Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms. pp.  233–242. arXiv: 0705.0552 . CiteSeerX   10.1.1.246.3123 . doi:10.1145/1290672.1290680. ISBN   0-89871-513-X.
3. Sadakane, K.; R. Grossi (2006). "Squeezing succinct data structures into entropy bounds" (PDF). Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm. pp. 1230–1239. ISBN   0-89871-605-5. Archived from the original (PDF) on 2011-09-29.
4. Jacobson, G. (1 November 1989). Space-efficient static trees and graphs (PDF). 30th IEEE Symposium on Foundations of Computer Science. doi:10.1109/SFCS.1989.63533. Archived from the original (PDF) on 2016-03-12.
5. González, R.; S. Grabowski; V. Mäkinen; G. Navarro (2005). "Practical implementation of rank and select queries" (PDF). Poster Proceedings Volume of 4th Workshop on Efficient and Experimental Algorithms (WEA). pp. 27–38.
6. Clark, David (1996). Compact pat trees (PDF) (Ph.D. thesis). University of Waterloo.
7. Vigna, S. (2008). "Broadword Implementation of Rank/Select Queries" (PDF). Experimental Algorithms. Lecture Notes in Computer Science. Vol. 5038. pp. 154–168. CiteSeerX   10.1.1.649.8950 . doi:10.1007/978-3-540-68552-4_12. ISBN   978-3-540-68548-7. S2CID   13963489.
8. Brodnik, A.; J. I Munro (1999). "Membership in constant time and almost-minimum space" (PDF). SIAM J. Comput. 28 (5): 1627–1640. CiteSeerX   10.1.1.530.9223 . doi:10.1137/S0097539795294165.
9. Pătraşcu, M. (2008). "Succincter" (PDF). Foundations of Computer Science, 2008. FOCS'08. IEEE 49th Annual IEEE Symposium on. pp. 305–313.
10. Belazzougui, Djamal; Boldi, Paolo; Pagh, Rasmus; Vigna, Sebastiano (2009-01-04). "Monotone Minimal Perfect Hashing: Searching a Sorted Table with O(1) Accesses". Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics: 785–794. doi: 10.1137/1.9781611973068.86 . ISBN   978-0-89871-680-1.
11. Assadi, Sepehr; Farach-Colton, Martín; Kuszmaul, William (January 2023), "Tight Bounds for Monotone Minimal Perfect Hashing", Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Philadelphia, PA: Society for Industrial and Applied Mathematics, pp. 456–476, arXiv: 2207.10556 , doi:10.1137/1.9781611977554.ch20, ISBN   978-1-61197-755-4 , retrieved 2023-04-28
12. Raman, Rajeev; Rao, Satti Srinivasa (2003), "Succinct Dynamic Dictionaries and Trees", Automata, Languages and Programming, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 357–368, doi:10.1007/3-540-45061-0_30, ISBN   978-3-540-40493-4 , retrieved 2023-04-28
13. Bender, Michael A.; Farach-Colton, Martín; Kuszmaul, John; Kuszmaul, William; Liu, Mingmou (2022-06-09). "On the optimal time/Space tradeoff for hash tables". Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. New York, NY, USA: ACM. pp. 1284–1297. doi:10.1145/3519935.3519969. hdl:1721.1/146419. ISBN   9781450392648. S2CID   240354692.
14. Li, Tianxiao; Liang, Jingxun; Yu, Huacheng; Zhou, Renfei (2023). "Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries". ArXiv . arXiv: 2306.02253 .
15. Nadis, Steve (8 February 2024). "Scientists Find Optimal Balance of Data Storage and Time". Quanta Magazine .
16. Pagh, Rasmus (1998-01-28). "Low Redundancy in Dictionaries with O(1) Worst Case Lookup Time". BRICS Report Series. 5 (28). doi: 10.7146/brics.v5i28.19434 . ISSN   1601-5355.
17. Pagh, Rasmus (January 2001). "Low Redundancy in Static Dictionaries with Constant Query Time". SIAM Journal on Computing. 31 (2): 353–363. doi:10.1137/s0097539700369909. ISSN   0097-5397.
18. Patrascu, Mihai (October 2008). "Succincter". 2008 49th Annual IEEE Symposium on Foundations of Computer Science. IEEE. pp. 305–313. doi:10.1109/focs.2008.83. ISBN   978-0-7695-3436-7. S2CID   257721481.
19. Yu, Huacheng (2020-06-22). "Nearly optimal static Las Vegas succinct dictionary". Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. New York, NY, USA: ACM. pp. 1389–1401. arXiv: 1911.01348 . doi:10.1145/3357713.3384274. ISBN   9781450369794. S2CID   207780523.
20. Belazzougui, Djamal. "Hash, displace, and compress" (PDF).