# Multiset-Trie Data Structure
## 5 Experiments
### Experiment 2  
In Experiment 2, we demonstrate the performance of the unrestricted multiset-trie allowing _multisets_ to be inserted into the data structure. We set \(n\) to be 6 and retain \(\sigma=25\), as in Experiment 1. The mapping \(\phi\) does not have an influence on the results, since the input data are generated artificially with uniform distribution. The cardinality of \(M\) varies from 40,000 to 640,000 multisets. Thus, the calculated density \(d\) varies from \(1.4\times 10^{-15}\) to \(2.25\times 10^{-14}\). The density is much smaller than in Experiment 1, because now we allow multisets to be stored in the data structure, and according to the parameters \(n\) and \(\sigma\), the cardinality of \(N\) is \(6^{25}=2.84\times 10^{19}\).  
As we can see from the graphs in Figure 6a,b, the performance of the functions submsetExistence and supermsetExistence becomes worse as the density increases. In this case, the number \(|M|\) is slightly larger than in Experiment 1, but the density is very small. Consequently, multiset-trie becomes more sparse. Multisets in a sparse multiset-trie differ more, which leads to a larger number of visited nodes.  
The maxima for both functions vary from 7500 to 25,000 visited nodes. According to these maxima, at least 300-1000 multisets were checked in order to find a sub-multiset or super-multiset, which is from \(1.5\times 10^{-3}\) to \(7.5\times 10^{-3}\) of the entire multiset-trie and from \(1.1\times 10^{-17}\) to \(3.4\times 10^{-17}\) of the complete multiset-trie. The percentage of visited multisets with respect to \(|M|\) is larger than in Experiment 1. However, if one would compare the percentage of visited multisets with respect to the complete multiset-trie, then, in the case of Experiment 2, it is less by 10 orders than in Experiment 1.  
Figure 5: Exhaustive functions of Experiment 1. (**a**) getAllSubmsets; (**b**) getAllSupermsets.  
The peaks are shifted from the center to the left and right for SUMBSTExistence and SUPERSTEExistence, respectively. Such behavior was previously observed in Experiment 1. The explanation is the same: the input data have a uniform distribution, implying that the size of multisets in \(M\) is normally distributed. Because of the normal distribution of the size of multisets, the shift in the peak occurs as the density increases.  
It can also be observed that, as in the previous Experiment 1, both functions SUMBSTExistence and SUPERSTEExistence have similar worst-case performance.  
The functions GETALLSUbMSETS and GETALLSuperMSETS decrease their performance as the density increases (see Figure 6(a),b). This happens because the number of multisets increases as the density increases. Thus, there are more nodes that have to be visited in order to retrieve all sub- or super-multisets of some multiset. The maximum for both functions varies from \(0.9\times 10^{5}\) to \(1.5\times 10^{7}\) visited nodes. As was observed in Experiment 1, the maxima occur at opposite points. For the function GETALLSUbMSETS, it will always be at the largest size of the multiset, which is 125 in our case. Conversely, the maximum for GETALLSuperMSETS is at the smallest size of multiset, which is 0 (an empty set).  
The results of Experiment 1 show that the performance of functions SUMBSTExistence and SUPERSTEExistence increases as the density increases. However, we observe the opposite behavior in Experiment 2. We explain the reason for such a contradiction in the next Experiment 3.