# Multiset-Trie Data Structure
## 5 Experiments
### Experiment 5  
In this experiment, we demonstrate the performance of the multiset-trie data structure compared to the Inverted Index based on the B-tree. Both data structures are implemented in the programming language C-, providing in this way an experimental setup for a fair comparison [27]. The Inverted Index is implemented using an idea from [23]. An inverted index structure consists of two parts: a dictionary and postings. In our case, a dictionary is implemented as an in-memory B-tree where keys are all distinct values from a domain represented by a set \(\Sigma\). The postings are represented by lists of multisets that contain a particular element from \(\Sigma\). Each list item in postings contains a cardinality of a multiset, which speeds up the containment queries. The experiment uses the input data for the construction of the given data structure and the test data for the execution of the operations on the given data structure. The input data comprise a set of randomly generated multisets used for the construction of a data structure. The test data include the set of multisets together with the operations that are evaluated. The input and test data were generated with respect to parameters \(\sigma\) and \(n\), as presented in Table 1. \begin{table}
\begin{tabular}{c c} \hline \hline \(\sigma\) & \(n\) \\ \hline
5 & 1 \\
30 & 1 \\
5 & 3 \\
15 & 3 \\
30 & 3 \\
10 & 10 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Configuration of \(\sigma\) and \(n\) in benchmark. Figure 9: Existence functions in Experiment 4. (**a**) submsetExistence; (**b**) supermsetExistence. We tested all three types of query on all of the configurations from Table 1, resulting in 18 experiments in total, i.e., 6 experiments per query type. In each experiment, we measured the average time consumed by the data structure to process the query. The results of the exact search, sub-multiset, and super-multiset search experiments are presented in Tables 2, 3 and 4, respectively. We can see that multiset-trie outperforms the Inverted Index in all of the experiments by up to four orders of magnitude. In an exact search, multiset-trie has to traverse only up to \(\sigma+1\) nodes to obtain a query result. It can be seen from the results that with the increase in \(\sigma\), the processing time for multiset-tire also increases. Multiplicity also affects the processing time; however, this happens passively. Multiplicity, or the degree of a node \(n\), defines the shape of multisets that are stored in multiset-trie. Thus, it affects the structure and density of the multiset-trie. As for the Inverted Index, all three operations must first fetch all postings for each particular element of a test multiset. Afterward, the intersection of postings is computed to answer the query. The operations use more processing time than a simple tree traversal, which we can see from the results. Postings are filtered on-the-fly to reduce the cost of the intersection. Implementations of the multiset containment operations for searching sub-multisets and super-multisets are similar in the case of the inverted file. The algorithm consists of the same steps. First, the postings are fetched for each element of the test multiset. Depending on the particular operation, postings are filtered on-the-fly. Finally, the union or the intersection of the filtered set of postings is computed. Note that the processing time increases with the size of the inverted index because of the increased sizes of postings. \begin{table}
\begin{tabular}{c c c c} \hline \hline \(\sigma\) & \(n\) & Multiset-Trie (\(\upmu\)s) & Inverted Index (\(\upmu\)s) \\ \hline
5 & 1 & 10.63 & 63,073.86 \\
30 & 1 & 14.65 & 449,251.68 \\
5 & 3 & 171.04 & 163,256.77 \\
15 & 3 & 43.42 & 425,733.80 \\
30 & 3 & 22.06 & 729,831.34 \\
10 & 10 & 58.32 & 373,784.81 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Super-multiset search.