# An Efficient Two-Level-Partitioning-Based Double Array and Its Parallelization
## 3 TLP-Based Partitioned DAs  
### Tlp  
Two strings may lead to collisions when they are inserted into a DA, so it is not practical inserting them into a DA simultaneously. To construct DA in parallel, we need to divide a dataset into partitions and build multiple independent small DAs in parallel. As mentioned above, BP and BP_PLA are not suitable or less efficient in parallel environments due to the difficulties in keeping prefix integrity and load balancing together. To this end, this paper proposes a bottom-up two-level partitioning (TLP) framework to achieve a better balance between these two characteristics. TLP firstly divides a dataset \(D\) into \(m\) discrete lower-level partitions (\(LP\)) (\(L=\{LP_{1},LP_{2},\dots,LP_{m}\}\)) based on the first character of strings in \(D\). Each \(LP\) is a first-character partition (all strings with the same first character in \(D\) constitute a first-character partition). \(\left|LP_{j}\right|\) is used to represent the number of strings in \(LP_{j}\). This can ensure the prefix integrity within each \(LP\). Secondly, TLP uniquely assigns each \(LP\) to an upper-level partition (\(UP\)), eventually merging \(m\)_LPs_ into \(n\)_UPs_ (\(U=\{UP_{1},UP_{2},\dots,UP_{n}\}\)). Similarly, \(\left|UP_{i}\right|=\sum_{LP_{j}\in UP_{i}}\left|LP_{j}\right|\) is used to represent the number of strings in \(UP_{i}\). A brief structure of TLP is shown in Figure 4.  
Merging \(m\)_LPs_ into \(n\)_UPs_ is non-trivial. Intuitively, there are \(n^{m}\) different merging strategies. Different merging strategies lead to different load balancing performances. Thus, choosing the best merging strategy to obtain the best load balancing is a key to TLP. For easy explanation, we give the definition of Partition Range (PR) as follows:  
**Definition 1**. : _Given \(U=\{UP_{1},UP_{2},\dots,UP_{n}\}\), the PR of \(U\) is defined as \(R_{u}=max(U)-min(U)\), where \(max(U)\) and \(min(U)\) represent the maximum and minimum number of strings of each \(UP\) in \(U\), respectively._  
Figure 4: A brief structure of two-level partition (TLP). Figure 3: Balanced Partition with Partition Line Adjustment (BP_PLA). PR can be used to measure load balancing of a partition strategy. To obtain the optimal load balancing performance, the optimal \(LP\) merging is defined as follows:  
**Definition 2**. : _Optimal LP Merging (OLM): Given \(L=\{LP_{1},LP_{2},\ldots,LP_{m}\}\), each LP in \(L\) is uniquely assigned to an UP, thus merging UP into \(n\) disjoint Ups \(U=\{UP_{1},UP_{2},\ldots,UP_{n}\}\) while keeping \(R_{u}\) to be minimum._  
OLM is essentially a multi-way number partitioning problem [29; 30], which is proved to be an NPC problem, solving it in limited time is key to TLP. Based on the analysis above, this paper proposes a Min-Heap based Greedy Merging algorithm (MH_GMerge) to quickly find an approximate optimal merging strategy. The basic idea of MH_GMerge is as follows:  
1. sort \(m\)\(LP_{5}\) to be merged in descending order of the number of strings;
2. given the partition parameter \(n\), build a min-heap for the first \(n\)\(LP_{5}\) in \(L\), and set the corresponding \(UP\) partition No. (UPN) of the \(n\)\(LP_{5}\) to 1, 2, 3,..., \(n\), accordingly;
3. process the subsequent \(m\)-\(n\)\(LP_{5}\) in order until all \(LP_{5}\) have been processed. For \(LP_{j}\), assign its UPN to UPN of the heap top \(H_{t}\) and execute \(\big{|}H_{t}|=\)\(|H_{t}|+\)\(|LP_{j}\big{|}\), where \(|H_{t}|\) means the number of strings in all \(LP_{5}\) related to \(H_{t}\). At last, we readjust the heap to min-heap. The number of elements in the created min-heap is always \(n\) and there is no need to actually load the subsequent \(m\)-\(n\)\(LP_{5}\) into the heap, which makes MH_GMerge very fast. The completed MH-GMerge algorithm is shown in Algorithm 1. Algorithm 1. Min-Heap based Greedy Merging (MH-GMerge) algorithm. ```
//Input: L, a set of m LPs \(n\), number of partitions //Output: PQT, partition query table 1. L \(\leftarrow\) sort L by number of strings in descending order 2.