# An Efficient Two-Level-Partitioning-Based Double Array and Its Parallelization
## 1 Introduction  
String storage and retrieval are fundamental operations in many fields, such as in search engine, natural language processing, and artificial intelligence applications. It is of great significance to improve the efficiency of these operations. Just as B\({}^{+}\)-Tree is the representative of database index for integer [1], trie is one of the most common structures for string storage and retrieval and is extensively used in artificial intelligence [2, 3], natural language processing [4], data mining [5], IP address searching [6, 7], string similarity joining [8, 9], and many other fields. For a detailed description of trie and its applications, we refer the reader to [10, 11] for more details. The storage and retrieval efficiency can be naturally improved by compressing common prefixes of strings into common paths. The traditional trie can either be a matrix form or a linked form [12]. The matrix form is efficient in retrieval speed but with a higher space overhead. Meanwhile, the linked form is efficient in space overheads, but its retrieval efficiency is relatively slow. Both of them are difficult to balance between retrieval performance and storage overheads. Many efforts have been devoted to address this problem, and various tries and corresponding optimizations have been proposed [13, 14, 15, 16, 17]. Among them, Level-Ordered Unary Degree Sequence (LOUDS) [18, 19] and double array (DA) [20] are the two mosteminent representatives. LOUDS is the most succinct trie to our best knowledge. It used bit strings to compress trie, which was extremely space-saving. However, retrieving in LOUDS was relatively time-consuming, because it requires expensive SELECT and RANK operations on generated bit strings. To improve the retrieval efficiency, the recent work, [PERSON] et al. [21], proposed Fast Succinct Trie (FST), which is a combination of LOUDS-SPARSE and LOUDS-DENSE. A fast bitmap-based LOUDS-DENSE is deployed in the upper-levels of a trie to enable fast and frequent access, and a space-efficient LOUDS-SPARSE is deployed in the lower-levels to decrease the space storage. Furthermore, FST introduces some other optimizations, e.g., lookup table and sampling, to speed up the SELECT and RANK operations, which makes FST both effective and succinct. Although FST has made a good trade-off between retrieval performance and storage overheads, its retrieval speed is still not fast because it still needs the SELECT and RANK operations to retrieve a child node of a specific node, which makes it not suit for frequently retrieval scenarios. DA [18] proposed by [PERSON], provides another way of making a good balance between retrieval performance and storage overheads. It compresses stored strings into two one-dimensional integer-arrays named BASE and CHECK. Retrieving a specific child node of a node is extremely fast, because only simple addition operations are needed. Considering the high retrieval efficiency of DA, many research efforts are devoted to further optimize this structure. [PERSON] et al. proposed a compact double array (CDA) [22], a statically constructed compressed double array. Unlike DA, CDA stores a character instead of an integer in CHECK to reduce the space overhead under the premise that each value in BASE is unique. [PERSON] et al. [12] presented a single array with multiple code (SAMC) which sets BASE[s] to \(s\) at first and then determines the content of CHECK in a depth manner. As BASE[s] equals \(s\), so BASE can be safely removed and thus storage spaces can be reduced. In double-array using linear functions (DALF) [23] proposed by [PERSON] et al., BASE is segmented and a linear function is designed for each segment to reduce the space overheads. [PERSON] et al. [24] introduced rearrangement methods to improve space efficiency as well as update time. Most of the aforementioned methods are devoted to reducing space overheads. However, the index construction efficiency has not been well studied.