␣
␣
C2: Cache-Conscious Succinct Tries with Adaptive Unary Path Compression Kepan Zhang
Tiancheng Zhao
Helen Xu
Georgia Institute of Technology USA [email protected]
Georgia Institute of Technology USA [email protected]
Georgia Institute of Technology USA [email protected]
arXiv:2606.16104v1 [cs.DB] 15 Jun 2026
Abstract Succinct tries are powerful string dictionaries because of their low memory footprint and fast query performance. However, existing succinct trie implementations face two key challenges to spatial locality: 1) they incur unnecessary cache misses during queries, especially during trie navigation operations, and 2) they waste significant space when the data contains many unary paths. We propose C2 , a set of two techniques: C1 introduces a more cachefriendly layout for the bitvector underlying succinct tries, and C2 compresses redundant unary paths. We thoroughly redesign three state-of-the-art succinct tries: FST, CoCo-trie, and Marisa, producing C2 -FST, C2 -CoCo, and C2 -Marisa. Experiments on six diverse datasets show that the C1 optimization improves query performance by 1.58×, 1.12×, and 1.42×, respectively, compared to the original FST, CoCo-trie, and Marisa. Furthermore, the C2 optimization achieves a 1.3× smaller memory footprint on average. The succinct tries optimized with both aspects of C2 achieve better space-time tradeoffs than their original versions and other state-of-the-art succinct tries, while using significantly less space than non-succinct tries like ART and C-ART.
Keywords
Table 1: Average number of LLC misses per query on the two largest datasets. FST [44], CoCo-trie [12] and Marisa [42] are bitvector-based succinct tries, while CART [43] is a pointer-based compact trie. Tries prefixed with C2 - are our cache-optimized versions. Dataset
FST
C2 FST
CoCo’
C2 CoCo
Marisa
C2 Marisa
C-ART
wiki [41] log [18]
82 235
78 230
66 57
49 45
56 58
58 62
23 117
Table 2: Unary-path statistics for the two largest datasets. #Branch denotes the number of branching edges. Given a path length ℓ, we report the percentage of paths with lengths ℓ = 1, 1 < ℓ ≤ 3, and ℓ > 3. ℓ𝐴𝑉 𝐺 and ℓ𝑀𝐴𝑋 denote the average and maximum lengths of compressible unary paths. Dataset
# Branch
ℓ =1
1<ℓ ≤3
ℓ>3
ℓ𝐴𝑉 𝐺
ℓ𝑀𝐴𝑋
wiki [41] log [18]
467K 7,284K
15.5% 17.4%
0.4% 3.8%
84.1% 78.8%
271 65
8676 8196
succinct, tries, cache, optimization, path, compression
1
Introduction
Succinct data structures have become essential in applications like large-scale databases, graph processing, and text indexing, especially in memory-constrained scenarios [36]. They are stringdata representations that use close to the theoretical minimum number of bits while still supporting efficient queries [20, 30]. We focus on succinct tries [11, 12, 23, 42, 44], which match or exceed the performance of regular tries with orders of magnitude less memory. Succinct tries separate the trie topology from the string data, encoding the topology in a compact bitvector that uses only about 2 bits per node on average compared to at least 128 bits for two pointers in traditional tries [24]. Navigation requires auxiliary index operations (e.g., “rank” and “select”) on top of this bitvector. Challenges to locality. Existing bitvector-based succinct tries exhibit suboptimal locality in two respects: 1) the bitvector layout in the topology, and 2) the unary paths, or maximal trie paths of at least 2 nodes in which every node except the last has exactly one child, in the data. For example, in Figure 3, paths 0-1-4 (“ca”) and 0-2-5 (“su”) are internal unary paths, whereas path 7-14-18 (“ie”) is a suffix unary path. Sections 3 and 4 detail both challenges. Table 1 confirms locality challenges due to navigation operations across state-of-the-art succinct tries. For example, a child EDBT ’27, Lille (France) © 2026 Copyright held by the owner/author(s). Published on OpenProceedings.org under ISBN 978-3-89318-106-3, series ISSN 2367-2005. Distribution of this paper is permitted under the terms of the Creative Commons license CC-by-nc-nd 4.0.
navigation in Marisa [42] incurs at least 3 cache misses to access the topology bitvector compared to 1 in a pointer-based trie to follow the pointer. Additionally, practical datasets often include strings with long shared prefixes followed by diverse dangling suffixes, which naturally introduce large numbers of unary paths in trie-based representations. For example, collections of hyperlinks frequently share common prefixes such as “en.wikipedia.org/wiki/”, while differing only in their trailing titles. As a result, large portions of the trie structure degenerate into long chains of unary nodes. Without effective compression, unary paths can consume a dominant fraction of succinct-trie storage, increasing memory footprint and disrupting cache locality. For example, as shown in Table 2, the majority of suffix regions in realistic datasets consist of long, redundant unary chains in the two largest tested inputs. In the wiki dataset, 84.1% of all branch edges correspond to compressible unary paths, with an average compressible length of 271 characters and a maximum compressible length of over 8K characters. Similarly, the log dataset contains 78.8% compressible unary paths. Optimizing for locality in bitvector-based succinct tries. We introduce C2 , a set of techniques that improve locality in both the topology and the data of succinct tries. We target two operations: the existence query (checking whether a key exists) and the range query (returning a range of keys). The first “C” of C2 improves cache locality of the select index in succinct tries. We introduce the functional index, a novel select index layout that maps straightforwardly to bit positions, enabling both rank and select indexes to be inlined in the bit
Size (normalized to ART) Size (normalized to ART)
EDBT ’27, 6-9 April 2027, Lille (France)
Zhang et al.
WIKI (359 MB)
aggressiveness exposes further space-time tradeoffs. For example, on Marisa, increasing “recursion” for more compression yields 1.17× space savings, but 1.30× slower queries. • We integrate these techniques into three state-of-the-art succinct tries — FST [44], CoCo-trie [11, 12], and Marisa [42] — improving query performance on the whole (with both C1 and C2 optimizations) by 1.58×, 1.13×, and 1.42×, respectively.
0.4 0.3 0.2 1
1.2
1.4 1.6 1.8 LOG (586 MB)
2
2.2
1.5
1
0.5 0.5
FST C1 -CoCo C2 -Marisa PDT
1 1.5 2 2.5 Query latency (normalized to ART) C1 -FST C2 -CoCo Marisa-1 C-ART
C2 -FST Marisa C1 -Marisa-1
CoCo’ C1 -Marisa C2 -Marisa-1
Results summary. Overall, C2 -optimized tries improve cache locality and performance over their original counterparts with negligible (<4%) additional space overhead. C2 -FST achieves better space-time performance than FST on all datasets. C2 -CoCo outperforms CoCo’ by 1.13× in query latency and is 1.31× smaller in space, on average across the six datasets 1 . C2 -Marisa improves Marisa’s query performance by 1.42× with similar memory consumption, and is generally the strongest C2 index. Figure 1 shows the query latency and size of the different tries on the wiki and log datasets. C2 -Marisa dominates all other succinct tries on query latency with the lowest (or within a few percent of the lowest) space usage. ART and C-ART, two nonsuccinct tries, achieve lower query latency at the cost of higher space usage. These space-time improvements stem from the cache-locality gains of C2 , as demonstrated by the cache-miss counts in Table 1.
2 Figure 1: Space-time performance comparison on wiki [41] and log [18] (normalized to ART). We use FSST as the tail container in all C2 -tries. The prefixes "C1 -"/"C2 -" indicate different optimization strategies (bitvector redesign / bitvector redesign + unary path compression); the suffix "-1" means we enforce one recursion (see Section 5). Lower and to the left is better. sequence. Using the functional index, we cut random accesses to two per child navigation in LOUDS-based succinct tries, which include many state-of-the-art tries such as the FST [44], CoCotrie [11], and Marisa [42]. Table 1 and Section 5 show that this optimization reduces cache misses by 19% on average with at most 2% overall space overhead. The second “C” of C2 is an adaptive compression algorithm that gives any succinct trie access to compression in the “tail container,” which stores the remaining string suffixes at the end of trie paths. Building on “re-pair” [27] and “recursion” [42], two orthogonal techniques for path compression, we enable all tries to use both recursion and the Fast Static Symbol Table (FSST) [14], a lightweight scheme that achieves good compression ratios with fast build times. Although recursion and compressed tail containers appear in prior work, this is the first generalization of recursion across tail containers, exposing space-time tradeoffs for any succinct trie. Contributions. Our primary contributions are as follows: • We redesign the succinct-trie topology with a cache-conscious functional index that inlines both rank and select indexes, minimizing cache misses during trie navigation. • We propose an adaptive compression scheme that selects the best compression strategy per dataset to balance space and query performance. Our experiments indicate that the chosen strategy improves space efficiency by 1.3× on average with similar (within 1.05×) query performance compared to the original succinct trie versions. Furthermore, increasing compression
Preliminaries
We introduce the rank/select primitives on bitvectors and common succinct tree-encoding schemes, review four state-of-the-art succinct tries this paper builds upon, and summarize string compression schemes for the tail container.
2.1
Rank/Select Primitives
Bitvectors are a fundamental building block of many succinct data structures. Succinct tree navigation relies on the rank and select primitives of bitvectors, which are defined as follows: • rank𝑝 (i): return the number of pattern 𝑝’s in the first 𝑖 bits of the bitvector. • select𝑝 (i): return the end of the 𝑖-th occurrence of pattern 𝑝 in the bitvector. Different bitvectors support different patterns for rank and select. Common choices of 𝑝 include 1, 0 and 00. For example, rank1 (i) returns the number of occurrences of “1” in positions [0, i). Index structures for rank and select partition the bitvector into fixed-sized (e.g., 512-bit) basic blocks and store partial results so far for each block from left-to-right [45]. They also often include secondary indices on smaller fixed-size blocks within each basic block for higher granularity and better performance. These auxiliary structures reduce the worst-case cost of rank and select to 𝑂 (1) with minimal (typically about 5%) space overhead [15, 20–22, 31, 34, 40, 44, 45]. For the rank operation, the rank index stores samples, or exact accumulative ranks before each block (e.g., the number of 1s preceding each basic block), which enable fast exact responses to rank queries. Answering a rank𝑝 (i) query involves combining the accumulative rank before the target block with the (computed) rank in the remainder up to position i. For example, Figure 2 illustrates a worked example of a rank1 (12) query on a bitvector where the rank index is built 1 The original CoCo-trie was designed for prefix-only datasets and fails to build on
the original datasets. We implemented CoCo’ by integrating CoCo-trie’s topology with C2 -CoCo. Section 5 provides the full details and shows that CoCo and CoCo’ achieve almost identical performance and space usage on the prefix-only datasets.
EDBT ’27, 6-9 April 2027, Lille (France) 𝑟𝑎𝑛𝑘1 12 = 4 + 1 𝑟𝑎𝑛𝑘1 (0)
Rank Index
0
𝑠𝑒𝑙𝑒𝑐𝑡1 14 = 17 + 9 𝑠𝑒𝑙𝑒𝑐𝑡1 (0)
𝑟𝑎𝑛𝑘1 (16)
4 𝒓𝒂𝒏𝒌𝟏 (𝟖)
7
12 𝑟𝑎𝑛𝑘1 (24)
Select Index sample rate = 8
0
0
𝑠𝑒𝑙𝑒𝑐𝑡1 (16)
17
c
28 1
𝒔𝒆𝒍𝒆𝒄𝒕𝟏 (𝟖)
a
𝒃𝒍𝒐𝒄𝒌𝟏 . 𝒓𝒂𝒏𝒌𝟏 𝟒 = 𝟏
Bits
0110 0101 0010 0110 0111 1010 1011 1_ _ _ block size 8
4
r
t
bit 17
Figure 2: Examples of rank/select operations using the associated indices on top of a bitvector. with block size 8. First, we look up the result of rank1 (8) = 4 in 𝑂 (1) time in the rank index because position 8 is the start of the basic block containing 12. Second, we calculate the remaining instances of the pattern in the range 8 - 12 in the bitvector. The combined result of the first and second step is 4 + 1 = 5, which is rank1 (12). The select operation uses a select index similar to the aforementioned rank index, but select is more challenging than rank because a query may not know exactly which block is needed based on the input. For example, with 8-bit basic blocks, bit 12 is always in the second basic block, but the 12-th one bit might be in the 100-th basic block! To support the select operation, the select index precomputes and stores samples, or exact results of select queries at regular intervals (e.g., select𝑝 (0), select𝑝 (8), select𝑝 (16), . . . ). Answering a select query involves finding the closest index entry to the left of the desired select query, then scanning sequentially using that as a starting point. For example, Figure 2 illustrates a worked example of a select1 (14) query on a bitvector where the select index is built with block size 8. First, we look up the closest entry below, which is select1 (8) = 17, in 𝑂 (1) time. Therefore, we know that the result of select1 (14) must be to the right of select1 (8), so we scan left to right starting from position 17 in the bitvector until we have found 6 more bits (for 8 + 6 = 14 bits total). Succinct trie bitvector structure. BP, LOUDS, and DFUDS are three popular bitvector-based succinct tree-encoding schemes [10, 24]. They all use the topology bitvector to map each tree element (i.e., nodes, edges, internal nodes, leaf nodes) to a unique integer ID in the range of [0, 𝑛 −1], where 𝑛 is the number of such elements in the tree. Depending on the encoding scheme, the topology may support efficient tree operations (e.g., parent/child navigation) via bitvector operations (e.g., rank/select). Succinct trees encoded using these schemes can be converted to tries by storing data associated with each trie edge in a separate array, which is indexed using the edge IDs [12, 23, 42, 44]. Efficient bitvector operations require auxiliary data structures which separate the bitvector into two parts: the index, which accelerates bitvector operations, and the bit sequence, which stores the content of the bitvector (i.e. the trie topology). The index facilitates rank/select operations essential to succinct trie navigation.
2.2
LOUDS Encoding
Level-Order Unary Degree Sequence (LOUDS) is aclassical example of a bitvector-based succinct-tree encoding scheme [24]. Each tree node is encoded using the bit sequence 1𝑚 0 (i.e., 𝑚 1’s followed by a 0), where 𝑚 is the degree (i.e., the number of children) of the node. The encoding bits of each node are concatenated in level order to form the encoding bitvector bv of the entire tree. With this encoding, each 1 bit corresponds to
2
9
$
1110 10 10 110 110 110 110 110 0 0 110 0 0 0 10 0 0 0 0
3
i
r
5
6
c
m e p i
10 8
LOUDS
t
u
9 bits (select 6 more 1’s) bit 12
s
14 12 13
HasChild Louds
y
11
c
LOUDS-Sparse
7
e
111 1 1 11 00 10 00 10 00 0 100 1 1 10 10 10 10 10 10 1
15
Labels
cst a u ir rt cm ep iy $c e 16
17
18
Figure 3: LOUDS/LOUDS-Sparse encoding example. Stored keys: car, cat, suc, succ, sum, tie, tip, trie, try. a parent-to-child edge, whereas each 0 bit marks the end of a node. We say a position 𝑖 belongs to a node 𝑘 if bit 𝑖 is part of node 𝑘’s encoding. The LOUDS encoding efficiently supports the following tree operations: • NodeID(i) = bv.rank0 (i), the LOUDS ID of the node to which position 𝑖 belongs. • EdgeID(i) = bv.rank1 (i), the LOUDS ID of the edge at position 𝑖 (Requirement: bv[i] == 1). • LeafID(i) = bv.rank00 (i), the LOUDS ID of the leaf node to which position 𝑖 belongs. • InnerID(i) = NodeID(i) - LeafID(i), the LOUDS ID of the inner node to which position 𝑖 belongs. • Child(i) = bv.select0 (bv.rank1 (i+1)) + 1, the position of the child node connected to the edge at position 𝑖. • Parent(i) = bv.select1 (bv.rank0 (i)), the position of the parent of the node to which position 𝑖 belongs. As illustrated in Figure 3, encoding a trie using LOUDS involves the following steps: First, the topology of the trie is encoded using the LOUDS bitvector; Second, all the trie labels are concatenated in level order into a separate array. At query time, trie labels are uniquely indexed by edge IDs (because they are associated with trie edges), whereas keys are indexed by leaf IDs. Next, we will present an example of how to traverse a LOUDSencoded trie using the trie in Figure 3. Suppose we are navigating to the second child of the root (i.e., from node 0 to node 2). We need to follow the second edge of the root node, which is at position 1. From the aforementioned formula, Child(1) = bv.select0 (bv.rank1 (2))+1 = bv.select0 (2)+1 = 6. Indeed, if we look at the LOUDS bitvector in Figure 3, the second child of the root starts at position 6. Balanced Parentheses (BP) [24] and Depth-First Unary Degree Sequence (DFUDS) [10] are two popular alternatives to LOUDS with the same two-bits-per-node overhead, but they traverse the tree in different orders. Compared with LOUDS, they support a broader range of tree operations, including computing subtree sizes or counting the number of leaf nodes to the left/right of a specific node. However, their functionality comes at the cost of slower parent/child navigation compared to LOUDS due to their greater complexity.
2.3
State-of-the-art Succinct Tries
Fast Succinct Trie. The Fast Succinct Trie (FST) [44] is a static succinct trie that combines the benefits of LOUDS-Sparse and LOUDS-Dense by leveraging both formats in different levels of the trie. Specifically, FST encodes the top levels of the trie, where nodes tend to have more branches and are more likely to be
EDBT ’27, 6-9 April 2027, Lille (France)
ca
r
t
c$
Zhang et al.
ti
su cc
tr y$
che
mp
enc(ca su ti tr)
c
…
a
𝐼𝑛𝑛𝑒𝑟𝐼𝐷
Ptrs ptr2
ptr3
ptr4
enc([ie y$])
0
LOUDS: 10 110 110 110 0 0 IsLink: 0 01 11 11 Labels: c a Links: omp che mp are ute
ute
are
Encoding
LOUDS
ptr1
omp
a
m$ e p ie
11110 110 1110 110 110 000000000
ptr0
Patricia
c
Marisa 4
hc 3
1
2 0
Figure 4: An example of a CoCo-trie obtained by collapsing sub-tries surrounded by dashed boxes in Figure 3. queried, using LOUDS-Dense, a representation that is fast and space efficient for nodes with dense branches. The rest of the trie, which tends to be colder and of lower average degree, is encoded with the more compact LOUDS-Sparse. Due to space limitations, we omit the details of LOUDS-Dense, but we refer the reader to the original FST paper [44] for the full details. LOUDS-Sparse uses 2 bits to encode each trie edge. The HasChild bit of each edge indicates if this edge points to an internal node (1) or a leaf node (0). The Louds bit of each edge indicates if this edge points to the first child of current node (1) or not (0), which is used to determine node boundaries. These two sets of encoding bits are respectively concatenated in level order to form two bitvectors, HasChild and Louds. With LOUDSSparse, we have • Child(i) = Louds.select1 (HasChild.rank1 (i+1)+1). • Parent(i) = HasChild.select1 (Louds.rank1 (i+1)-1). • LeafID(i) = HasChild.rank0 (i). Let us consider how to perform trie navigation in a LOUDSsparse-encoded trie using the example in Figure 3. Suppose we are navigating again to the second child of the root (also at position 1). From above, Child(1) = Louds.select1 (HasChild.rank1 (2) +1) = Louds.select1 (3) = 4. Indeed, the second child of the root starts at position 4 in the Louds bitvector in the LOUDSSparse encoding. CoCo-Trie. The CoCo-trie [11, 12] is a recent state-of-the-art static succinct trie that achieves both low memory consumption and fast query performance. A CoCo-trie is constructed by first creating a regular trie 𝑇 and then adaptively selecting sub-tries of 𝑇 to collapse into macro-nodes. Keys in each collapsed macronode are transformed to an increasing sequence of integer codes which is then encoded using a select pool of succinct integer encoding algorithms. The optimal set of sub-tries to collapse is computed using a bottom-up dynamic-programming algorithm. Figure 4 illustrates the CoCo-trie encoding of the example trie in Figure 3. Since the CoCo-trie uses LOUDS encoding, its trie navigation is done through rank/select operations on the bitvector as described in Section 2.2. Marisa Trie. The Marisa trie [42] is a LOUDS-encoded Patricia trie [29] that contracts unary paths into single concatenated labels. Unlike Patricia, Marisa improves space efficiency by recursively storing unary paths in multiple tries. The upper subgraph of Figure 5 shows an example of Patricia, where unary paths are contracted into a single node. To convert the trie to LOUDS succinct form, two bitvectors are needed: the topology bitvector LOUDS (Section 2.2), and an additional bitvector
pm
e tu
ra 1
o
$ 2
3
4
Figure 5: Examples of Patricia (top) and Marisa (bottom) with one recursion. Keys stored: cache, camp, compare, compute. Unary paths in the first Marisa trie are stored in the second Marisa trie in reversed form: ehc, era, etu, pm, pmo. Links in the first Marisa trie are indicated using dashed arrows, and the numbers alongside them indicate their values (which in this example are leaf node IDs in the second Marisa trie). (IsLink) which indicates if each edge is a regular edge (0) or a contracted edge (1). Each contracted edge is uniquely indexed by a LinkID determined by a rank operation on the IsLink bitvector. The Links vector stores links, or references, to the concatenated labels on the contracted edge. For example, bit 3 in LOUDS corresponds to bit 2 in IsLink and link 0 in Links (“omp”). Marisa improves on Patricia by recursively storing unary paths in secondary tries. The recursion continues until the number of tries reaches a preset limit, at which point the outstanding unary paths are sorted, deduplicated and moved to a simple “sorted” tail container (Section 2.4). The lower subgraph of Figure 5 shows a worked example of a Marisa trie with one recursion. For readability, links between tries are expressed as leaf node IDs in this example. Because the second trie only needs to support random access but not lookup operations, the keys are stored in reversed form so that they can be efficiently retrieved by reading the labels on a bottom-up path. For example, to retrieve link 4’s corresponding key, we start from leaf 4 of the second trie, concatenate all the (reversed) labels on the leaf-to-root path (‘o’ and ‘mp’), and obtain ‘omp’. In practice, links are implemented as leaf node positions to avoid an additional select operation. Finally, to mitigate the cost of link tracing during lookups, Marisa uses a small piece of memory to cache frequently-taken paths. The number of recursions in Marisa exposes a space-time tradeoff, as more recursions further compress the data at the cost of degraded search performance and higher build times [4].
Path Decomposed Trie. The Path Decomposed Trie (PDT) [19, 23, 25] is a DFUDS-encoded succinct trie. A PDT is obtained by transforming a regular trie through path decomposition [38]: At each step, a root-to-leaf path is selected and contracted into a single node, and the subtrees dangling on the original path are converted to its child nodes. The procedure recurses on the dangling subtrees. The PDT achieves both significant memory reduction and competitive query performance by compressing the contracted paths with an approximate version of the re-pair text compression algorithm [16, 27], which we will summarize in the next subsection.
EDBT ’27, 6-9 April 2027, Lille (France)
overflow flag 32 31
Keys
Dict
replace
01
pair place repair
2 1 02
0 re 1 place 2 pair
Select Index
Sorted
𝑟𝑎𝑛𝑘1 (𝑥)
Text Compression Algorithms
Figure 6 presents a worked example of how to compress a set of strings with the sorted tail container, re-pair algorithm, and FSST. Next, we summarize these algorithms. Sorted tail container. The sorted tail container is the string container for the last Marisa trie on a recursion chain. It overlaps two keys if one is a suffix of the other, and is particularly space efficient for datasets with short and repetitive keys. To efficiently detect possibilities of overlapping, it needs to reverse and sort all keys. Once the strings have been sorted, construction takes linear time. The link array which is used to retrieve keys from the container should also preserve the original key ordering. Dictionary compression. Dictionary compression encodes common text patterns as small integer codes, exemplified by the famous LZW algorithm [26]. The mapping between patterns and integers is known as the dictionary, and finding a good dictionary is known to be a key challenge to such algorithms [14]. In our work, we focus on two related algorithms that support fast random access: re-pair [27] and FSST [14]. Exact and approximate re-pair. At a high level, the original re-pair algorithm [27] replaces the most frequently-occurring character pair with a new special character, proceeding in rounds. For example, using special characters 𝛼, 𝛽, 𝛾 and 𝛿, re-pair may compress the string aabbaabb as 𝛼bb𝛼bb (𝛼 = aa) in the first pass, 𝛼𝛽𝛼𝛽 (𝛽 = bb) in the second pass, 𝛾𝛾 (𝛾 = 𝛼𝛽) in the third pass and 𝛿 (𝛿 = 𝛾𝛾) in the fourth pass. The dictionary is expressed as a set of recursive rules of pairing, which can be flattened to support constant-time decoding [23], with a small space overhead. Prior work shows that re-pair compresses a sequence 𝑇 of length 𝑛 over an alphabet of size 𝜎 and 𝑘-th order entropy 𝐻𝑘 to 𝑂 (𝐻𝑘 ) bits. [32, 33]. In practice, the PDT uses an approximate version of the re-pair algorithm [16] that accelerates build time by orders of magnitude compared to exact re-pair by identifying and replacing the top 𝑘 most frequently-seen character pairs in each round, rather than one at a time. To our knowledge, there is no theoretical bound on how far the compression ratio of approximate re-pair is from exact re-pair’s, as it depends on the dataset. Fast Static Symbol Table. The Fast Static Symbol Table (FSST) [14] is similar to approximate re-pair, but optimizes for lightweight compression (with linear build times). Specifically, it restricts the size of the symbol table (i.e., the list of special characters for replacement) to 256 entries and expands the size of each replaced entry to substrings of 8 bytes (rather than two characters in the original approximate re-pair). FSST further optimizes for build time by first encoding a small sample (about 16KB) of the original dataset, and then using the resulting symbol
0
7
ℎ𝑒𝑎𝑑
𝑑𝑖𝑠𝑡
target falls in [𝑏𝑙𝑜𝑐𝑘ℎ𝑒𝑎𝑑 , 𝑏𝑙𝑜𝑐𝑘ℎ𝑒𝑎𝑑+𝑑𝑖𝑠𝑡 ] 32 31 0
block 𝑖
Blocks …
1 …
𝑠𝑝𝑖𝑙𝑙_𝑝𝑡𝑟
SPILL LIST precomputed results
𝑟𝑎𝑛𝑘
𝑟𝑎𝑛𝑘1 (𝐵 × 𝑖)
2.4
0
𝐵 bits
replace$repair$
Figure 6: Examples of re-pair, FSST and sorted tail containers. Re-pair and FSST are both dictionary encoding methods (denoted with Dict) that replaces common text patterns with small integer codes. The sorted tail container (denoted with Sorted) overlaps suffix keys.
…
bit 𝑥
Figure 7: Interleaving. Figure 8: Select index overflow. table to encode the entire dataset. FSST implements hardwarespecific optimizations, achieving extremely high compression and decompression throughput. In practice, FSST reduces the compression time by over an order of magnitude compared to approximate re-pair, while achieving similar compression ratios. However, no theoretical space bound has been proved for FSST.
3
The First “C”: Cache-conscious Bitvector Design
In this section, we present the first "C" of C2 : Cache-conscious bitvector design (denoted with C1 ). First, inspired by prior work [15, 21], we apply an array-of-structs reorganization to bitvectors to better exploit the access pattern of rank queries. Second, we eliminate cache misses from reading the select index using our novel functional index. Third, to handle both sparse and dense patterns, we further optimize the existing technique of overflowing select indexes and reduce cache misses by storing all data in-place. Finally, we apply the above techniques to three state-of-the-art LOUDS-based succinct tries [11, 42, 44]. We adopt two design principles: (1) optimization priority of cache > branch > arithmetic operations [45], and (2) trading space for performance. Since trie topologies are usually much smaller than trie labels, a small space overhead is worthwhile for increased query speed. Locality issues in bitvectors. The main challenge to locality during trie navigation arises from storing the index and bitvector separately [20, 22, 31, 34, 40, 44, 45], since both must be accessed during rank and select. Packing the rank index with the bit sequence improves locality for rank [15, 21], but the same approach does not work for select. In most cases, the input to rank maps linearly to a position in the bit sequence; the input to select, however, is often an intermediate value (e.g. the output of rank) with no straightforward mapping to a bit position.
3.1
Array-of-Struct Reordering
Most traditional bitvectors are organized in a struct-of-array manner. During rank queries, each query accesses the target block immediately after its rank index. To better exploit this locality, rank indexes can be interleaved, or stored in an arrayof-structs manner with the index and bitvector in one contiguous memory allocation, as illustrated in Figure 7. Similarly, for tries encoded with multiple bitvectors, we interleave blocks of different bitvectors that are often jointly accessed at nearby bit positions. For example, in LOUDS-Sparse, we pack the blocks of HasChild and LOUDS, as they are aligned with each other and are typically accessed together. Similarly, we can interleave secondary rank indexes [15, 20, 21, 40, 42]. We restrict the size of each rank index element to 32 bits for better space efficiency without loss of applicability to larger datasets. To support bitvectors larger than 232 bits, previous work
EDBT ’27, 6-9 April 2027, Lille (France)
Zhang et al.
Traditional
Cache Optimized
Rank
0
Rank
0
HasChild
11111 11001 00010 000
HasChild
11111 11001 00010 000
Select
7
Child
3
Louds
10011 10101 01010 101
Louds
10011 10101 01010 101
5
8
9
17
5
9
8
15
9
17
Figure 9: Functional index example for LOUDS-Sparse’s Child(x) = Louds.select1 (HasChild.rank1 (x + 1) + 1). The block size and the sampling rate for select (left) are both 5. The third row on the right (Child) caches the results of Child(x) at the start of block (i.e. Child(0), Child(5), etc.). shows how to first partition the data into connected sub-tries that individually fit in the size limit [7].
3.2
Functional Index
To improve spatial locality for select, we introduce the functional index that samples results of the navigation function (e.g., Child(x)) rather than intermediate select values. For example, to support child navigation in LOUDS (where Child(x) = select0 (rank1 (x+1))+1), we sample Child(x), instead of select0 (x), at regular intervals of 𝑥. Since the sampled function is monotonically non-decreasing, the sampling is unambiguous. We then interleave these samples with blocks for spatial locality. Other succinct trie operations (e.g., parent navigation) can be optimized using similar approaches. Figure 9 shows a worked example of computing Child(6) using traditional and functional indexes. An implementation using the traditional index first computes HasChild.rank1 (6+1)=7 (by accessing HasChild’s rank index and the HasChild bitvector) and then obtains Louds.select1 (7+1)=13 (by accessing Louds’ select index and the Louds bitvector itself), which easily incurs 4 cache misses. In contrast, using the cache-optimized functional index, we first access block 1 (which bit 6 falls into) and obtain HasChild.rank1 (6+1) = 7 (using block 1’s rank index). Then, we read block 1’s functional index for Child, which stores the value of Louds.select1 (5+1) = 9. Since we need to compute select1 (7+1), we select two more ones starting from bit 9 and end up at bit position 13. Assuming the two accessed blocks belong to different cache lines, we incur only two cache misses in total. In practice, since trie navigation operations are often executed in a pipelined manner (i.e., the output of one operation is immediately used as the input of the next operation), this optimization essentially cuts cache misses by 4× in long pipelines. Applicability beyond LOUDS. Although we develop and evaluate the functional index in the context of LOUDS-based tries, the core idea applies to any succinct-tree encoding whose navigation functions are monotonically non-decreasing compositions of rank and select. The key insight behind the functional index is that Child(x) is a function of the position x, not of an intermediate bitvector value, so sampling it at regular intervals of x aligns the index with the bit sequence and enables interleaving. This property holds in BP and DFUDS as well, since the navigation function’s input and output both increase monotonically with the traversal order of the encoding. In BP, child navigation reduces to a findclose operation (i.e., locating the matching close parens for an open parens),which is implemented via rank/select on the parenthesis bitvector.
The functional index directly applies because findclose(x) is monotonically non-decreasing in x, so it can be directly sampled at regular intervals of x and interleaved with the bit blocks. Similarly, DFUDS navigation starts with the Child(x, 1) operation, which returns the first child of the node at position x. This firstchild operation admits a functional index in the standard way, with subsequent siblings located by scanning forward.
3.3
Overflow of Select Index
So far, we have assumed that the probe distance within the target interval is small. But this is not always the case, especially for the CoCo-trie, which sometimes contains nodes with very large fanouts. For instance, when encoding the trec-terms [8] dataset in the original CoCo-trie paper, the first 600k bits of the CoCo-trie topology contain only 36 zero bits. With such extreme sparsity, regular searching algorithms would be too slow. A classic solution to this problem is to allow the select index to overflow [34, 40]. That is, the select index should detect regions with extremely low pattern density, and precompute every select result in those regions. Since the precomputed results do not fit in regular sample space, they are overflowed to a separate list, and the sample stores a pointer to the overflow list instead. Unfortunately, overflowing the select index disrupts locality because two adjacent samples are no longer guaranteed to form a bounding interval, as either of them can be overflowed. Therefore, after querying the sample, we must either use linear search or incur an additional cache miss to read the spill list. We resolve this issue by storing block indexes instead of exact bit positions in regular samples, as this frees up additional bits to store the size of the bounding interval (in blocks). The rank indexes in each block provide enough information to restore any lost precision at no cost of additional cache misses. For example, in Figure 9, block 1’s functional index for Child (i.e. Child(5)) points to block 1, which is equivalent to bit position 5 (instead of its original value 9 in Figure 9). Using the inlined rank index, we immediately restore HasChild.rank1 (5) = 5. Since Child(5) = Louds.select1 (7), we can reach position Child(5) (i.e., 9) by selecting two more ones. As shown in Figure 8, each sample occupies 32 bits, where bit 31 indicates whether the sample overflows. If bit 31 is false, then bits 7 to 30 (the 24-bit head, which means block size must be at least 256) point to the lower bounding block, whereas bits 0 to 6 (the 7-bit dist) store the length of the bounding interval (in blocks). If dist does not fit in 7 bits (i.e., the bounding interval is at least 128 blocks long), then bit 31 is set to true, and the sample is overflowed. The rest of the sample (the 31-bit spill_ptr) indexes into the centralized overflow list spill_list, where spill_list[spill_ptr + i] is the position of the 𝑖-th target pattern in the overflowing interval. We apply this optimization to both traditional select indexes and functional indexes with intermediate selects. We sketch why spill_ptr always fits in 31 bits. With block size 𝐵 = 256 and sample rate 𝑆 = 256, each overflowing interval has target pattern density at most 𝑆/128𝐵 = 1/128 (for select indexes) or 𝐵/128𝐵 = 1/128 (for functional indexes). Since the bitvector size does not exceed 232 , the size of spill_list would not exceed 232 /128 = 225 and hence always fits in 26 bits. Finally, we address the space overhead incurred by the spill list. Because each spilled interval contains at most 𝐵 = 256 bits, the density of ones is at least 256/(256× 128) = 1/128, and the
EDBT ’27, 6-9 April 2027, Lille (France)
1, the select1 index contains about 𝑆/2𝐵 elements, whereas the Child functional index contains 𝑆/𝐵 elements. □ Although functional indexes use more space compared to traditional select indexes, the overall space overhead is small relative to the index size and label data. For example, when 𝐵 = 256, the functional index takes 12.5% extra space relative to the bitvector size compared to the select index. Lemma 3.2. A child navigation takes at most 4 cache misses in all of the C1 -optimized tries in this paper.
Figure 10: Optimized bitvector layout. child: functional index for Child(x). parent: functional index for Parent(x). secondary1 : secondary index for rank1 . associated spill list occupies at most 32/128 = 25% of the bitvector size. For LOUDS-encoded tries, since only half of the bits are zeros, the bound can be reduced to 25% × 128/127/2 = 12.6%. For LOUDS-Sparse encoded tries, the functional index is sampled on only one of the two bitvectors, which also tightens the bound to 12.5%. Both upper bounds are reached only under extreme conditions where most trie edges are concentrated in a few large nodes, which is unlikely in practical datasets.
3.4
Applying the Rules
We apply the above optimizations to FST, CoCo-trie, and Marisa; Figure 10 shows the resulting bitvector layouts. The FST is encoded using LOUDS-Sparse and only needs to support existence query. We pack the blocks of HasChild and LOUDS (Section 3.1) and interleave bits with the rank1 (Section 3.1) and child (Sections 3.2 and 3.3) indexes. The CoCo-trie is encoded using standard LOUDS and supports top-down lookup, and therefore an ideal approach is to inline (primary and secondary) rank1 and rank00 indexes (Section 3.1) and the child (Section 3.2, Section 3.3) functional index. However, this adds a 192-bit space overhead to every 256-bit block, which is too expensive. Therefore, we switch to LOUDS-Sparse encoding which incurs less index overhead. The case with Marisa is more involved. First, we change the encoding scheme from LOUDS to LOUDS-Sparse, as this allows for better alignment. Then, we pack the blocks of HasChild, LOUDS and IsLink, as all three bitvectors are now edge-aligned and are typically accessed with high locality (Section 3.1). Finally, we interleave the bits with indexes for child and parent (Section 3.2, Section 3.3), and each bitvector’s rank1 (Section 3.1) indexes, as the Marisa trie needs to support both forward and reverse lookups. Theoretical analysis. The 𝐶 1 optimizations preserve asymptotic bounds on space and query complexity. The rank and select indexes are lower-order terms relative to the bitvector size [44]. Lemma 3.1. Given a bitvector of size 𝑆 and a block size of 𝐵, the 𝐶 1 optimizations incur at most 𝑆/2𝐵 additional space overhead. Proof. The size of the rank index in 𝐶 1 is unchanged and takes 32 bits per block. Since only half of the bits in a trie encoding are
Proof. Let C1 -CoCo, C1 -FST, and C1 -Marisa denote the CoCotrie, FST, and Marisa trie with the 𝐶 1 optimization as illustrated in Figure 10. As shown in Figure 10, C1 -CoCo, C1 -FST, and C1 Marisa have block sizes of 704, 704, and 1024 bits, respectively. Given a cache-line size of 64 bytes (512 bits), each block in the C1 -optimized succinct tries takes at most 2 cache lines. A child navigation with the functional index queries two blocks: the input block and the output block. □ Although the blocks in the C1 -optimized tries span 2 cache lines each, the second cache line in the block is prefetched and therefore incurs no additional cache misses. In contrast, the original succinct tries (e.g., CoCo, FST, and Marisa), are encoded using separate bitvectors, which take at least 3 random cache misses per block.
4
The Second “C”: Adaptive Unary-Path Compression
In this section, we address the space inefficiency incurred by unary paths (especially suffix unary paths) and introduce the second "C" of C2 : the adaptive unary-path Compression scheme (denoted with C2 ). The C2 optimization enables all tries to access unary-path compression in the data. Specifically, it combines Marisa’s recursion [42] with the Fast Static Symbol Table (FSST) [14] as the tail container. Furthermore, it adaptively chooses the number of levels of recursion for the Marisa trie based on per-dataset space savings. We evaluate C2 tries against baselines at the same recursion level; since CoCo-trie and FST originally lack recursion, C2 changes only their tail container. Locality issues in the data. Long unary paths increase topology size and waste space through redundant label sequences. Without proper compression, suffix paths can account for about 80% of succinct-trie space, as shown in Table 2. Prior work uses two orthogonal compression methods (detailed in Section 2): PDT [23] uses re-pair [27], while Marisa [42] uses recursion, as detailed in Section 2. Neither method dominates: on the log [18] dataset, recursion and re-pair achieve compression ratios of 16.4× and 7.5×, respectively; on xml [35], the ratios are 3.9× and 5.0×. Choice of tail container. Although Marisa originally uses a sorted tail container, recursion is agnostic to the tail container; more advanced containers such as approximate re-pair [23] and FSST [14] can improve both space and query time. We limit our C2 tries to the FSST tail container because it captures almost all (within 1.12×) of the compression benefits of approximate re-pair with 12.8×–21.6× faster build times. As shown in Table 6 in Section 5, choosing FSST as the tail container always achieves a better compression ratio (up to 1.3×) with minimal impact on the query time (.96-1.13×) over the sorted container.
EDBT ’27, 6-9 April 2027, Lille (France)
Zhang et al. lookup(cell) “cel” cas
𝐿𝑒𝑎𝑓𝐼𝐷
𝐼𝑠𝐿𝑖𝑛𝑘
cam
depth = 3 cr ce
Table 3: Datasets used in evaluation. All dataset sizes are expressed in MB. LCP means length of longest common prefix. Size* is the size of the prefix-only version of each dataset.
DICT
h, p, ll, ash
DICT
Figure 12: A C2 -CoCo suffix Figure 11: Suffix path com- path compression example. pression for C2 -FST and C2 - Stored keys: cash, camp, cell, crash. CoCo. Integration with succinct tries. First, we enable C1 -FST, C1 CoCo, and C1 -Marisa to access recursion and compressed tail containers. We focus the discussion on FST and CoCo, as these previously could not access unary-path compression. Figure 11 illustrates how we containerize the storage of suffix paths in FST. Specifically, each leaf node has an IsLink bit indicating whether its suffix path is moved to the next container. A suffix link at position 𝑖 can thus be uniquely identified by LinkId(i) = IsLink.rank1 (LeafID(i)). When a lookup operation reaches a leaf node, we follow the IsLink bitvector to check the remaining suffixes in the container (if any). The integration with C1 -CoCo is similar to C1 -FST, but CoCo requires special care for correctness: its encoding schemes support only exact lookup. Figure 12 shows the issue. When looking up the string “cell,” the CoCo-trie would search for “cel” in the root because the root node has depth 3. Since “cel” is not a key of the root, the lookup would fail, even if “cell” exists in the trie. Instead, we search for the lower bound of the target key rather than an exact match. If the lower bound is a prefix of the target key, we trace the link to check the remaining suffixes. Adaptive recursion depth. We enable all of the succinct tries studied in this paper to access unary-path compression, but focus on the case of the Marisa trie and show how to achieve better space-time tradeoffs by combining recursion with FSST. Using recursion in the other tries (FST and CoCo) trades query performance for space savings. Therefore, we limit non-Marisa tries to no recursion in our evaluation, but expose it as a user option for different space-time tradeoffs. We will include the data on the effect of recursion in non-Marisa tries in the full version. The original Marisa-trie exposes the maximum number of recursions as a parameter to the user, but offers no per-dataset guidance on the space-query tradeoff. As the original Marisa trie documentation notes [4] and Section 5 confirms, recursion has a serious negative impact on query performance, so we only want to continue recursion when the space reduction is significant. We adaptively select the number of recursion levels that achieve the best time-space tradeoff per dataset. To balance compression ratio against build/query time, we stop recursion when the space savings would be less than some 𝜖 = 0.1 (relative to trie size). However, the user can set 𝜖 to suit their use case. To efficiently determine the space usage at each level of recursion, we adopt FSST’s fast estimation scheme, encoding a subset of the data to approximate the compression ratio. In practice, this estimate is within 10% of the true compression ratio. Other locality optimizations. For the Marisa trie, compressed tail containers degrade lookup performance in nodes with many links. To address this issue, we store the branching label (i.e., the first label of each unary path) in the label vector, enabling in-place intra-node search accelerated by SIMD [23].
Name
Size
Size*
#Keys
Avg len
Avg LCP
words [17] url [13] dna [35] xml [35] log [18] wiki [41]
5 37 101 117 586 359
4 17 44 74 258 236
4.67E5 1.77E6 3.32E6 2.15E6 4.45E6 1.75E7
9 21 31 56 137 21
6 7 11 33 54 11
Description English words UK private domains DNA 31-mers dblp XML dump server access logs Wikipedia titles
To further improve locality, we store unary paths smaller than a link in-place, avoiding the index overhead of moving them to the next level. The number of bits needed to store a link depends on the size of the trie (i.e., if a trie has 𝑛 nodes, we need lg(𝑛) bits to store each link). Short unary paths may be further compressed by moving them to the next level, but the space savings is limited by the short path length relative to the link cost.
5
Experimental Evaluation
We evaluate three succinct tries optimized using C2 (C2 -FST, C2 CoCo, and C2 -Marisa) and compare them with eight state-of-theart tries: FST [44], Marisa [42], CoCo-trie [11, 12], PDT [23], ART [28], C-ART [43], c-trie++ [39], and z-fast trie [9]. The first four are bitvector-based succinct tries introduced in Section 2; ART is a well-established pointer-based dynamic trie, C-ART is the compact and static version of ART, and c-trie++/z-fast trie are high-performance dynamic tries. We compare all data structures on query performance, space usage, and build time. Summary. The C2 tries significantly outperform the original versions in both performance and space efficiency on most datasets. On average, C2 -FST, C2 -CoCo, and C2 -Marisa improve query performance/space usage by 1.58×/1.27×, 1.13×/1.31×, and 1.42×/1.30×, respectively (at equal recursion). These improvements stem from improved locality and fewer cache misses in both the index and the data. Applying C1 (the cache-conscious bitvector redesign in Section 3) reduces cache misses per query by 1.51× for FST and 1.26× for Marisa on large datasets. The bitvector redesign adds at most 4% space overhead. At equal recursion, C2 (the unary-path compression scheme in Section 4) improves query performance, space usage, or both over C1 alone.
5.1
Experimental Settings
Hardware. We ran the experiments on a server with an AMD EPYC 9555 64-Core Processor running at 3.2GHz. The server has 1007 GB of memory, a 3 MiB L1 data cache, a 2 MiB L1 instruction cache, a 64 MiB L2 cache, and a 256 MiB L3 cache. We ran the experiments with one thread. Implementation. We implement the three C2 tries (C2 -FST, C2 CoCo and C2 -Marisa) using C++17. We use the compressed string pool implementation of PDT [1] and the publicly-available implementation [3] of FSST [14] for the re-pair and FSST tail containers, respectively. We also use the sdsl [20, 37], ds2i [34] and sux [31] libraries for C2 -CoCo as in the original CoCo-trie [6]. For CoCo-trie [6], Marisa [4], PDT [1] and C-ART [2], we use their original implementations. We adopt the ART implementation in the C-ART codebase. For FST, we use an optimized third-party implementation [5] which compacts suffixes into a
EDBT ’27, 6-9 April 2027, Lille (France)
contiguous array, as this allows for fairer comparison with many unary suffix paths. Finally, we also evaluate c-trie++ [39] and z-fast trie [9], two state-of-the-art dynamic tries. All tested systems support existence queries, but out of the tested C2 tries, only FST supports an iterator for range queries. Therefore, we evaluate FST versus C2 -FST on range queries. In each experiment, we generate range queries with a start key and a length, or number of subsequent keys to return beginning from the start key. We vary the query lengths k between experiments and test k = 1, 10, . . . , 10000. The ART and C-ART implementations we use are designed as filters but not indexes and may return false positives. To support lossless queries, the original dataset must be replicated and may need to be checked when the filter returns positive results. We report space costs without the replicated dataset; query times include false-positive checks. Finally, as detailed in Section 5.2, we introduce CoCo’, a version of the CoCo-trie with an optimized build routine but the same bitvector design, because the open-source CoCo-trie does not build on large datasets. All code is compiled with g++ 10.3.0 at -O3. All implementations used in our experiments are publicly available at https://github.com/alexztc/C2. Parameter settings. For FST, we use the default setting with 𝑅 = 64. For CoCo-trie, CoCo’, and C2 -CoCo, we set 𝛼 = 5% for a good space-time balance. We do not enable LOUDS-Dense for C2 -FST as it provides no benefit. We use Marisa’s default cache size for both Marisa and C2 -Marisa, which is 1/512 of the key count. We set 𝜖 = .1 for all C2 tries. Datasets. Table 3 details the six datasets in our evaluation. These datasets span diverse sources, key lengths, prefix depths, and alphabet sizes. Furthermore, following the methodology from the CoCo-trie paper [12], we generate prefix-only versions of each dataset (denoted by dataset*) because CoCo originally used only prefixonly datasets. We compare the open-source CoCo implementation with our CoCo’ implementation on the prefix-only datasets. Experimental setup. We set up experiments as follows: First, each dataset is sorted and deduplicated. Second, we build the trie under test on the dataset and record the build time and memory usage. Finally, we query the trie using all keys in the dataset in random order and compute the average query latency. We omit negative-query latencies, as they are generally proportional to positive workloads [12]. We also measure the cache performance of queries in different tries on the log and wiki datasets by recording the number of cache misses using perf. All times are the average of three trials after one warm-up trial. Notation. We use Marisa-𝑖 to denote Marisa with 𝑖 levels of recursion. Furthermore, for a given trie X, we use C1 -X to denote X optimized with C1 (Section 3). We use C2 -X to denote X with both C1 and C2 . For example, C1 -FST is C1 -optimized FST with sorted tail container, whereas C2 -Marisa-1 is C1 -optimized Marisa with FSST tail container and one level of recursion.
5.2
Building C2 -CoCo on larger datasets
Since the original CoCo-trie implementation runs out of memory when building the larger prefix-only datasets, we implement an optimized build routine underneath C2 -CoCo to support all datasets. The original CoCo is built from a pointer-based uncompacted trie, which not only consumes excessive memory but also incurs significant cache misses when traversing each node’s
Table 4: Comparison of CoCo and CoCo′ (Query, in ns per query) and space usage (Size, in % of original dataset size) on the prefix-only datasets used in the original CoCo-trie evaluation. words*
url*
dna*
xml*
Trie
Query Size
Query Size
Query Size
Query Size
CoCo CoCo′
315 380
742 811
655 743
62.7% 54.8%
42.4% 32.3%
24.0% 1039 40.1% 1011
47.5% 29.6%
Table 5: Normalized build and query time (relative to C2 FST; lower is better) for different LOUDS-Sparse/Dense configurations of FST. FST-Sparse uses LOUDS-Sparse/LOUDSDense, while FST-Hybrid uses LOUDS-Sparse, both with a sorted tail container. C2 -FST uses the same bitvectors with the FSST tail container.
FST-Sparse FST-Hybrid C2 -FST-Sparse C2 -FST-Hybrid
words (0.47M keys)
log (4.45M keys)
Build
Query
Build
Query
7.73× 7.02× 5.31× 5.29×
3.50× 2.85× 1.52× 1.45×
2.30× 2.24× 1.53× 1.55×
2.73× 2.57× 1.82× 1.85×
descendants at different levels, a key operation of CoCo-trie’s optimization process. We optimize the builder by representing the uncompacted trie as C2 -FST, which significantly reduces cache misses because in LOUDS-Sparse representation each node’s descendants at the same level fall into contiguous memory. Our implementation reduces the build time of C2 -CoCo by up to 14× and uses orders of magnitude less memory during build than the original CoCo-trie. We introduce CoCo’: C2 -CoCo’s build routine with the original CoCo-trie bitvector, to isolate bitvector differences. We use CoCo’ as the CoCo-trie baseline for larger datasets. As shown in Table 4, on the prefix-only datasets that the original CoCo-trie can build on, CoCo-trie and CoCo’ have similar query latencies (within 100 ns). However, the original CoCo-trie suffers from poor performance and space usage on full datasets because it does not handle unary suffix paths. For example, on url, a relatively small dataset, the original CoCo-trie implementation requires more than 10 minutes and 60 GB of memory to build. Furthermore, it takes over 2000 ns/query and occupies nearly half as much memory as the original dataset, both the worst among all tested tries.
5.3
Ablation Study and Sensitivity Analysis
Figure 1 shows ablation results of C1 and C2 across configurations of FST, CoCo, and Marisa. Table 6 contains the full data for the different C2 configurations discussed in Sections 5.3 and 5.4. Effect of hybrid bitvector. Table 5 evaluates the effect of switching to LOUDS-Sparse in FST [44]. As mentioned in Section 2, the original FST introduced a hybrid bitvector with LOUDS-Sparse and LOUDS-Dense. We find that the hybrid bitvector improves the performance of both build and query in the baseline FST (with no special tail container). However, the effect is much smaller on C2 -FST with the FSST tail container, so we switch to the fully sparse version in the final C2 configuration.
EDBT ’27, 6-9 April 2027, Lille (France)
Zhang et al.
Table 6: Build time, query latency, and space usage on the datasets in Table 3. The prefixes C1 /C2 indicate that the C1 /C1 +C2 optimizations are applied. We fix the tail container to be FSST with the C2 optimization, but we report results with the sorted tail container for the ablation study on the C1 optimization. Marisa-1 means the Marisa trie with 1 recursion level. For Marisa, we show all data points before C2 stops recursion. For all other tries, the recursion level was set to 0 for a fair comparison. For each column, green cells highlight the best value and blue cells highlight the second-best value. Build (ns/key) Trie
Query (ns/key)
Size (% of original size)
words url
dna
xml
wiki
log
words url
dna
xml
wiki
log
words url
FST C1 -FST C2 -FST
309 90 101
691 1043 1068
802 1148 1114
1157 897 894
716 762 729
2139 2173 1821
403 228 227
610 404 404
844 562 561
1541 835 842
1424 1242 1258
4003 2197 2154
45.5% 35.5% 74.3% 39.2% 37.9% 39.5% 40.4% 39.8% 75.9% 39.7% 38.4% 40.4% 40.4% 36.0% 43.8% 28.8% 37.7% 24.4%
CoCo’ C1 -CoCo C2 -CoCo
790 758 771
1639 1595 1637
1875 1919 1852
1913 1949 1900
2114 2145 2074
7258 7562 7237
389 355 358
626 562 560
749 695 613
1027 907 898
1539 1320 1342
1597 1465 1448
51.5% 41.7% 73.2% 40.6% 43.7% 40.2% 45.8% 39.5% 70.7% 39.8% 41.4% 39.9% 45.8% 35.7% 38.5% 28.9% 40.7% 23.9%
Marisa C1 -Marisa C2 -Marisa Marisa-1 C1 -Marisa-1 C2 -Marisa-1
234 131 168 239 141 169
470 1046 1064 558 1229 1294
676 1175 1139 1002 2275 2369
712 991 933 945 1476 1473
521 865 799 599 1025 997
1270 2031 1613 1405 2209 1938
272 178 182 301 178 196
460 310 308 583 425 424
663 443 439 968 686 436
669 483 500 960 746 764
991 739 732 1244 967 979
1098 831 829 1538 1229 1306
33.3% 37.5% 37.5% 29.5% 37.5% 36.2%
PDT ART C-ART c-trie++ z-fast trie
624 73 119 401 447
1582 83 150 654 779
2947 76 179 365 989
4593 115 178 344 1587
2040 92 220 644 1168
3912 289 404 315 2531
356 132 148 217 541
560 347 401 495 1158
795 533 674 683 1394
841 728 750 915 2016
1022 713 810 716 1192
1138 1611 1758 1507 2838
33.7% 26.2% 28.4% 19.7% 30.1% 13.0% 346.8% 156.2% 115.0% 59.1% 165.7% 27.6% 155.0% 68.6% 53.8% 27.1% 77.5% 16.0% 1540.1%747.0% 513.5% 290.6% 788.5% 157.1% 1084.5%586.6% 400.2% 223.9% 546.6% 92.7%
Effect of cache-optimized bitvector design. First, we isolate the effect of C1 , the cache-optimized bitvector design. We perform the ablation study on the datasets in Table 3 (1) with the sorted tail container and no recursion to avoid confounding factors from path compression, and (2) with all branching labels stored out of place to suppress intra-node search effects, so that the remaining query-time difference is attributable to the bitvector layout alone. The ablation study in Table 6 shows that the C1 optimization improves query performance by 1.58×, 1.12×, and 1.42×, respectively, compared to the original FST, CoCo-trie, and Marisa. These trie-level gains compound directly from the per-operator speedups in Table 7, since every full lookup issues 𝑂 (depth) rank queries on the topology bitvector and a small constant number of select queries, each of which benefits from the co-located block metadata in our layout. The bitvector redesign has the least impact in the CoCo-trie because the query time in CoCo is dominated by the cost to read the encodings, and each CoCo macro-node already amortises several traversal steps over one bitvector access. However, FST and Marisa improve significantly because bitvector cache misses dominate query time: each rank query in their baselines incurs two cache misses — one for the block summary and one for the bit field — which our co-located layout collapses to a single line. Table 7 reports the effect of C1 on the fine-grained bitvector operations that make up succinct-trie navigation. The results demonstrate that C1 improves the performance of key rank-based operations such as leaf_id and internal_id by 1.2 − 7.1×. We observe similar trends for trie-specific operations, such as parent navigation in Marisa (1.76× on parent_pos) and child navigation across all three tries (1.3 − 2.8× on child_pos). The only operators where the baseline is faster are get and degree, which perform linear scans through bits and do not use rank and select; interleaving block metadata with the bit field slightly reduces the effective bit density per cache line on such scans. However, neither of these lie on the critical path of a full lookup or range
35.3% 36.4% 30.9% 22.0% 26.5% 26.3%
dna
xml
76.4% 75.4% 41.0% 34.3% 33.8% 41.0%
40.3% 39.5% 27.6% 25.2% 26.3% 21.5%
wiki
32.4% 34.4% 32.9% 25.1% 28.9% 28.3%
log
37.3% 36.4% 20.7% 28.6% 28.2% 14.7%
Table 7: Bitvector Operation Latency (ns) on XML Dataset (2.1M keys). Speedup = Baseline / C1 . Bold entries indicate where C1 outperforms the baseline. Trie
Operation
Baseline (ns)
C1 (ns)
Speedup
FST
get leaf_id degree child_pos
1.48 10.32 1.09 48.62
1.52 1.45 2.75 17.09
0.98× 7.13× 0.40× 2.84×
CoCo
get leaf_id internal_id degree child_pos
0.64 2.10 4.18 1.83 22.60
1.06 1.72 2.82 2.34 17.87
0.60× 1.23× 1.48× 0.78× 1.26×
Marisa
get link_id leaf_id child_pos parent_pos
0.98 8.20 9.00 30.31 28.68
1.48 1.23 1.38 16.62 16.29
0.66× 6.66× 6.53× 1.82× 1.76×
query, and both are invoked 𝑂 (1) times per query at sub-3-ns cost each, so the few nanoseconds lost are dwarfed by the tens of nanoseconds saved on every rank query. Effect of unary-path compression. Next, we evaluate the effect of the C2 compression scheme. Specifically, for all tries, we measure the effect of replacing the sorted tail container with FSST. Furthermore, we test different recursion levels to evaluate the space-time tradeoff exposed by more recursions. Replacing the sorted tail container with FSST improves space usage by 1.27×, 1.31×, and 1.30× over C1 -FST, C1 -CoCo, and C1 Marisa, respectively. The effect on query performance is minimal (1-1.05× on average). As shown in Figure 13, recursion levels 0 and 1 expose Paretooptimal space-time trade-offs. For example, on C2 -Marisa, on the log dataset, no recursion takes 829 ns/query, while one level of
EDBT ’27, 6-9 April 2027, Lille (France)
ρ=1
Latency (ns / query)
ρ=0
C 2-FST
ρ=2
C 2-CoCo
3000
C 2-Marisa
2000
1500
2000
1000 1000
1000 0
20
30
40
20
Size (% of original) words
500 30
40
10
Size (% of original) url
dna
xml
20
30
40
Size (% of original)
wiki
log
Figure 13: Space-latency Pareto frontier under recursion depths 𝜌 ∈ {0, 1, 2} for the three trie variants across all six datasets. recursion takes 1308 ns/query. On the other hand, the space usage improves from 20.7% to 14.7%. Similarly, on the wiki dataset, no recursion takes 732 ns/query compared to 979 ns/query with one level of recursion. For wiki, one level of recursion improves the space usage from 32.9% to 28.3%. The same pattern holds for C2 -FST and C2 -CoCo. On the log dataset, C2 -FST without recursion takes 2187 ns/query at 24.4% space, while one level of recursion takes 2502 ns/query at 20.1% space; on the same dataset, C2 -CoCo without recursion takes 1463 ns/query at 23.9% space, while one level of recursion takes 1745 ns/query at 19.6% space. The same trade also holds on wiki, xml, url, and dna: across our six datasets, the absolute space savings from recursion levels 0 to 1 range from 0 percentage points (e.g., words, whose avg. longest common prefix of 6 leaves no recursive sub-prefix structure to extract) to roughly 6 percentage points (log across all three variants), while the corresponding latency degradation stays below 1.5× in every cell. Beyond one level of recursion, further recursion’s space savings rarely justify the performance penalty. For example, if we continue to recurse C2 -Marisa-1 on log, the relative space usage improves by 1.6× (which corresponds to a 5.3 percentage point improvement relative to the original data size, from 14.7% to 9.4%), but the query latency degrades by 1.25× (from 1308 to 1593 ns/query); on xml, the same step yields no measurable further space improvement. In fact, log is the only dataset on which 𝜌=2 strictly Pareto-dominates 𝜌=1 across all three tries, owing to its 113-character average key length harbouring nested common prefixes that a second recursion round can still extract. We observe one further anomaly: on dna, C2 -Marisa is fully insensitive to recursion — its size remains at 41.1% of the original data and its latency varies by less than 1% across 𝜌 ∈ {0, 1, 2} — because its unary-path encoder already absorbs DNA’s uniquesuffix structure at 𝜌=0, leaving no inter-tail prefix redundancy for the adaptive cost-based recursive string-pool builder to exploit. Going forward, we limit the recursion level of C2 -FST and 2 C -CoCo to 0 to match the original designs. For C2 -Marisa, we use the recursion level prescribed by the adaptive compression scheme. We expose recursion as an option for space-constrained settings: dialling C2 -Marisa up to 𝜌=2 on long-key datasets like log trades a further 5 percentage points of space for a 1.25× query latency penalty, while on every other dataset the same dial yields at most one percentage point of additional space and is therefore Pareto-dominated by 𝜌=1.
5.4
Comparison to State-of-the-art Tries
We compare C2 tries with all baselines. Table 6 reports the full data and the configurations prescribed by the C2 , the adaptive compression algorithm. Existence queries. Among all tries, ART always has the best query performance at the cost of high space usage. Child navigation in ART simply requires following a pointer, while succinct tries must perform complex bitvector operations. Furthermore, C-ART [43] uses an internal-node organization that trades search performance for space savings over ART. Both c-trie++ and z-fast trie are slower than ART for queries while consuming significantly more space. Table 6 demonstrates that C2 does not affect the query-time gains from C1 across tries and datasets. Among the succinct tries, C2 -Marisa achieves the lowest query latency with a space usage within 1.2× of the best. On average, C2 -Marisa improves the query latency of the original Marisa by 1.42×. On words and url, C2 -Marisa-1’s space consumption is relatively high compared to Marisa-1 because in this case, the C2 scheme stores short unary paths in place rather than in the tail container (see Section 4). For example, on the words dataset, C2 -Marisa contains only about .3× as many links as Marisa. C2 -FST improves query latency/space usage by 1.58×/1.27× on average compared with FST. C2 -CoCo does not benefit as much from C1 as it incurs fewer bitvector operations, but still improves both space usage and query latency compared to CoCo’. Time-space tradeoff. We next examine query time and space usage. C2 improves space usage by 1.34× on average compared to their original versions. On average, with no recursion, switching from the sorted tail container to FSST reduces the space usage by 1.3× at the cost of a 1.05× query performance penalty and 1.1× higher build time across all tested succinct tries. Additionally, for Marisa, on the datasets where C2 prescribes one level of recursion, the recursion improves the space efficiency by 1.29× on average, but also incurs a query performance penalty of 1.43× compared to no recursions. Specifically, recursion turns out to be extremely effective on the highly redundant log dataset. For C2 -Marisa, one level of recursion reduces the space cost by 1.74×, but increases the query time by 1.7× compared to no recursions due to the presence of many recursive paths.
EDBT ’27, 6-9 April 2027, Lille (France)
1.17×
1.4 1.2 1.0
103
0.82×
0.8
3 × 104
Speedup
k = 100
FST
1.62×
1.6 1.5
2 × 104 1.36× 1.27×
104
1.4
1.26×
1.3
1.14×
1.2
1.13×
1.1
6 × 103
words
url
dna
xml
wiki
log
1.7
words
url
Dataset
dna
xml
wiki
log
Dataset
C 2-FST
Speedup
k = 10000
2.04×
2.2 2.0
2 × 106
1.8 1.56×
106
1.44×
1.6 1.41×
1.41×
1.4 6 × 105
1.17×
words
1.2 url
dna
xml
wiki
log
Speedup (FST / C 2-FST)
1.27×
1.24×
C 2-FST
FST
1.6
Latency (ns)
1.46×
Latency (ns)
Speedup
1.48×
Speedup (FST / C 2-FST)
k=1
Latency (ns)
C 2-FST
Speedup (FST / C 2-FST)
FST
Zhang et al.
1.0
Dataset
Figure 14: Range-query latency comparison between FST-baseline and C2 -FST across six datasets under different range widths 𝑘. Each subplot corresponds to a fixed range width. Bars report absolute latency (left axis), while the red line indicates the speedup of C2 -FST over the baseline (right axis). On words, url and wiki, C2 -Marisa-1 has higher space usage (by at most 1.19×) than Marisa-1 because of the space overhead of storing the branching labels in place (see Section 4). On the larger datasets (e.g., log), C2 -FST and C2 -CoCo are generally less competitive than C2 -Marisa in both query performance and compression ratio, due to their handling of internal unary paths. C2 -FST does not handle such paths at all, and C2 -CoCo does not address the data redundancy in such paths. Furthermore, unary paths that do not fit the machine word size will be fragmented in C2 -CoCo, impairing data locality. Range queries. Figure 14 shows that the C2 optimizations speed up range queries by 1.2 − 1.5× in FST, which was the only tested trie that natively supports successor queries. The locality improvements in C2 -FST carry over into range queries, where each next() step can be resolved from data in the packed 256-bit blocks, which are already in cache. In contrast, the original FST fetches the equivalent information from three separately heapallocated arrays, incurring up to three cache-line misses per step. The relative advantage of C2 -FST increases monotonically with range width, with speedups on all but one configuration (wiki with 𝑘 = 1). The wiki contains many diverse suffixes, so the FSST tail container in C2 -FST finds almost nothing to compress, as shown in Table 6. However, C2 -FST must incur additional indirections during traversal to check the is_link array and fetch the compressed suffix, while the original FST can do a direct comparison.
Build time. While modern static succinct tries excel at space efficiency and query latency, their build times are significantly worse (between 3.2-24.7×) than the build times of pointer-based tries such as ART and C-ART, especially on large datasets. Depending on the dataset, the C2 optimizations can increase the build time by about 2× due to the time it takes to compress the tail container. We chose FSST as the tail container to try to minimize build times compared to approximate re-pair, which can take another 2× longer, as shown in PDT’s build times. Furthermore, building is a one-time cost for succinct tries and can be amortized over many queries. Future work will parallelize the build phase of succinct tries.
6
Conclusion
This paper presents C2 , guidelines for transforming bitvectorbased succinct tries to more cache-friendly and compact versions. C2 includes two optimizations: C1 , the Cache-conscious bitvector design, and C2 , the adaptive unary-path Compression. Following C2 , we redesign three state-of-the-art succinct tries: FST, CoCo-trie, and Marisa. On average, the three C2 -optimized tries improve query time by 1.58×/1.13×/1.42×, respectively, while using 1.27×/1.31×/1.30× less space. Future work will 1) apply similar bitvector optimizations to DFUDS/BP tries, like PDT or the DFUDS variant of CoCo-trie, 2) theoretically bound the space usage of practically-efficient compression schemes such as approximate re-pair [23] and FSST [14], and 3) integrate other powerful text-compression algorithms, such as LZW [26], with succinct tries.
EDBT ’27, 6-9 April 2027, Lille (France)
References [1] 2011. Path Decomposed Tries. https://github.com/ot/path_decomposed_tries. [2] 2017. C-ART. https://github.com/efficient/fast-succinct-trie/tree/master/thirdparty/art. [3] 2020. FSST. https://github.com/cwida/fsst. [4] 2020. Marisa trie. https://github.com/s-yata/marisa-trie. [5] 2021. Fast Succinct Trie. https://github.com/kampersanda/fast_succinct_trie. [6] 2024. CoCo-trie. https://github.com/aboffa/CoCo-trie. [7] Christoph Anneser, Andreas Kipf, Harald Lang, Thomas Neumann, and Alfons Kemper. 2020. The Case for Hybrid Succinct Data Structures. In International Conference on Extending Database Technology. https://api.semanticscholar. org/CorpusID:214613429 [8] Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, and Sebastiano Vigna. 2008. Theory and practice of monotone minimal perfect hashing. ACM J. Exp. Algorithmics 16, Article 3.2 (Nov. 2008), 26 pages. doi:10.1145/1963190.2025378 [9] Djamal Belazzougui, Paolo Boldi, and Sebastiano Vigna. 2010. Dynamic z-fast tries. In International Symposium on String Processing and Information Retrieval. Springer, 159–172. [10] David Benoit, Erik D Demaine, J Ian Munro, Rajeev Raman, Venkatesh Raman, and S Srinivasa Rao. 2005. Representing trees of higher degree. Algorithmica 43 (2005), 275–292. [11] Antonio Boffa, Paolo Ferragina, Francesco Tosoni, and Giorgio Vinciguerra. 2022. Compressed String Dictionaries via Data-Aware Subtrie Compaction. In String Processing and Information Retrieval, Diego Arroyuelo and Barbara Poblete (Eds.). Springer International Publishing, Cham, 233–249. [12] Antonio Boffa, Paolo Ferragina, Francesco Tosoni, and Giorgio Vinciguerra. 2024. CoCo-trie: Data-aware compression and indexing of strings. Information Systems 120 (2024), 102316. doi:10.1016/j.is.2023.102316 [13] Paolo Boldi, Bruno Codenotti, Massimo Santini, and Sebastiano Vigna. 2004. UbiCrawler: A Scalable Fully Distributed Web Crawler. Software: Practice & Experience 34, 8 (2004), 711–726. [14] Peter Boncz, Thomas Neumann, and Viktor Leis. 2020. FSST: fast random access string compression. Proceedings of the VLDB Endowment 13, 12 (2020), 2649–2661. [15] ByteDance. 2019. Terark Bit Vector. https://github.com/bytedance/terarkzip/tree/dev.1.1/src/terark/succinct. [16] Francisco Claude and Gonzalo Navarro. 2010. Fast and Compact Web Graph Representations. ACM Trans. Web 4, 4, Article 16 (Sept. 2010), 31 pages. doi:10.1145/1841909.1841913 [17] dwyl. 2024. English Words. https://github.com/dwyl/english-words. [18] Elias Dabbas. 2024. Web Server Access Logs. https://www.kaggle.com/datasets/eliasdabbas/web-server-access-logs. [19] Paolo Ferragina, Roberto Grossi, Ankur Gupta, Rahul Shah, and Jeffrey Scott Vitter. 2008. On searching compressed string collections cache-obliviously. In PODS. Association for Computing Machinery, 181–190. doi:10.1145/1376916. 1376943 [20] Simon Gog, Timo Beller, Alistair Moffat, and Matthias Petri. 2014. From Theory to Practice: Plug and Play with Succinct Data Structures. In Experimental Algorithms, Joachim Gudmundsson and Jyrki Katajainen (Eds.). Springer International Publishing, Cham, 326–337. [21] Simon Gog and Matthias Petri. 2014. Optimized succinct data structures for massive data. Software: Practice and Experience 44, 11 (2014), 1287–1314. doi:10. 1002/spe.2198 arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1002/spe.2198 [22] Rodrigo González and Veli Mäkinen. 2005. Practical implementation of rank and select queries. In WEA. https://api.semanticscholar.org/CorpusID: 10701791 [23] Roberto Grossi and Giuseppe Ottaviano. 2015. Fast Compressed Tries through Path Decompositions. ACM J. Exp. Algorithmics 19, Article 3.4 (Jan. 2015), 20 pages. doi:10.1145/2656332 [24] Guy Jacobson. 1989. Space-efficient static trees and graphs. In 30th annual symposium on foundations of computer science. IEEE Computer Society, 549– 554.
[25] Shunsuke Kanda, Dominik Köppl, Yasuo Tabei, Kazuhiro Morita, and Masao Fuketa. 2020. Dynamic Path-decomposed Tries. ACM J. Exp. Algorithmics 25, Article 1.13 (Sept. 2020), 28 pages. doi:10.1145/3418033 [26] W. Kinsner and R.H. Greenfield. 1991. The Lempel-Ziv-Welch (LZW) data compression algorithm for packet radio. In WESCANEX. 225–229. doi:10.1109/ WESCAN.1991.160551 [27] N Jesper Larsson and Alistair Moffat. 2000. Off-line dictionary-based compression. Proc. IEEE 88, 11 (2000), 1722–1732. [28] Viktor Leis, Alfons Kemper, and Thomas Neumann. 2013. The adaptive radix tree: ARTful indexing for main-memory databases. In ICDE. 38–49. doi:10. 1109/ICDE.2013.6544812 [29] Donald R. Morrison. 1968. PATRICIA—Practical Algorithm To Retrieve Information Coded in Alphanumeric. J. ACM 15, 4 (Oct. 1968), 514–534. doi:10.1145/321479.321481 [30] J Ian Munro and S Srinivasa Rao. 2018. Succinct representation of data structures. In Handbook of Data Structures and Applications. Chapman and Hall/CRC, 595–610. [31] Gonzalo Navarro and Eliana Providel. 2012. Fast, small, simple rank/select on bitmaps. In Proceedings of the 11th International Conference on Experimental Algorithms (Bordeaux, France) (SEA’12). Springer-Verlag, Berlin, Heidelberg, 295–306. doi:10.1007/978-3-642-30850-5_26 [32] Gonzalo Navarro and Luís MS Russo. 2008. Re-pair Achieves High-Order Entropy.. In DCC. 537. [33] Carlos Ochoa and Gonzalo Navarro. 2018. RePair and all irreducible grammars are upper bounded by high-order empirical entropy. IEEE Transactions on Information Theory 65, 5 (2018), 3160–3164. [34] Giuseppe Ottaviano, Nicola Tonellotto, and Rossano Venturini. 2015. Optimal Space-time Tradeoffs for Inverted Indexes. In Proceedings of the Eighth ACM International Conference on Web Search and Data Mining (Shanghai, China) (WSDM ’15). Association for Computing Machinery, New York, NY, USA, 47–56. doi:10.1145/2684822.2685297 Corpus. 2024. The Text Collection. [35] Pizza&Chili https://pizzachili.dcc.uchile.cl/texts.html. [36] Tetsuo Shibuya. 2019. Application-Oriented Succinct Data Structures for Big Data. The Review of Socionetwork Strategies 13 (10 2019), 1–10. doi:10.1007/ s12626-019-00045-1 [37] simongog. 2013. SDSL-Lite. https://github.com/simongog/sdsl-lite.git. [38] Daniel D. Sleator and Robert Endre Tarjan. 1983. A data structure for dynamic trees. J. Comput. System Sci. 26, 3 (1983), 362–391. doi:10.1016/0022-0000(83) 90006-5 [39] Kazuya Tsuruta, Dominik Köppl, Shunsuke Kanda, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. 2022. c-trie++: A dynamic trie tailored for fast prefix searches. Information and Computation 285 (2022), 104794. [40] Sebastiano Vigna. 2008. Broadword Implementation of Rank/Select Queries. In the Proceedings of the 7th International Workshop on Experimental Algorithms, 154–168. doi:10.1007/978-3-540-68552-4_12 [41] Wikipedia. 2024. Wikipedia titles. https://dumps.wikimedia.org/enwiki/20241120/. [42] Susumu Yata. 2011. Dictionary compression by nesting prefix/patricia tries. In Proc. 17th Meeting of the Association for Natural Language. [43] Huanchen Zhang, David G. Andersen, Andrew Pavlo, Michael Kaminsky, Lin Ma, and Rui Shen. 2016. Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes. In SIGMOD. Association for Computing Machinery, 1567–1581. doi:10.1145/2882903.2915222 [44] Huanchen Zhang, Hyeontaek Lim, Viktor Leis, David G. Andersen, Michael Kaminsky, Kimberly Keeton, and Andrew Pavlo. 2018. SuRF: Practical Range Query Filtering with Fast Succinct Tries. In SIGMOD. 323–336. doi:10.1145/ 3183713.3196931 [45] Dong Zhou, David Andersen, and Michael Kaminsky. 2013. Space-Efficient, High-Performance Rank and Select Structures on Uncompressed Bit Sequences. In ESA. 151–163. doi:10.1007/978-3-642-38527-8_15