# Multiset-Trie Data Structure
## 5 Experiments
### Experiment 1  
This experiment shows the performance of multiset-trie being used for storing and retrieving _sets_ instead of _multisets_. We restrict multiset-trie in order to obtain a closer comparison with the _set-trie_ data structure [24]. In this case, we set the maximal node degree \(n\) to be 2 and \(\sigma\) to be 25. The mapping \(\phi\) does not have an influence in this particular experiment because the input data are generated artificially with uniform distribution. On average, the results will be the same for any \(\phi\), since all the multisets are equally likely to appear in \(M\). The parameter \(|M|\) varies from 10,000 sets up to 320,000 sets. According to the parameters \(n\) and \(\sigma\), the cardinality of \(N\) is \(33,554,432\approx 3.36\times 10^{7}\). Thus, the calculated density of the multiset-trie with respect to \(|M|\) varies from \(0.3\times 10^{-3}\) to \(9.5\times 10^{-3}\). The performance of the functions submsetExistence and supermsetExistence increases as the density increases (see Figure 4a,b). The results are as expected because the increase in the density increases the probability of finding a sub-multiset or super-multiset in multiset-trie, which leads to a lower number of visited nodes. The maxima are located between 175 and 375 for submsetExistence and between 175 and 350 for supermsetExistence. According to these maxima, we can deduce that at least 7-15 multisets were checked in order to find a sub-multiset or super-multiset, which is from \(0.02\times 10^{-3}\) to \(1.5\times 10^{-3}\) of the multiset-trie and from \(1.9\times 10^{-7}\) to \(4.5\times 10^{-7}\) of the complete multiset-trie. As the density increases, the peaks shift from the center to the left or to the right, for submsetExistence and supermsetExistence, respectively. The shifts are the consequence of the uniform distribution of sets in \(M\). Since every set has the same probability of appearing in \(M\), the distribution of set sizes in \(M\) is normal. Consequently, with the increase in the density of the multiset-trie, the number of sets in \(M\) with cardinality \(\frac{1}{2}\sigma\) will be larger than the number of sets with cardinality \(\frac{1}{2}\sigma\pm\epsilon\), for \(\frac{1}{2}\sigma>\epsilon>0\). Thus, the function submsetExistence needs to visit less nodes for test sets of size \(\frac{1}{2}\sigma\) than for test sets of size \(\frac{1}{2}\sigma\pm\epsilon\). The function decreases the multiplicity of some elements (in some cases, it skips them) in order to find the closest subset. Hence, the peak shifts to the left. Oppositely, the function supermsetExistence increases the multiplicity of some elements (in this  
Figure 4: Existence functions of Experiment 1. (a) submsetExistence; (b) supermsetExistence. case, adding new elements) in order to find the closest superset. Thus, the peak shifts to the right. Note that despite the peak shifts, both functions submsetExistence and supermesetExistence have approximately the same worst-case performance. The performance of the functions getAllSubmsets and getAllSupermsets decreases as the density increases (see Figure 5a,b). This happens because the number of multisets in multiset-trie increases, which means that any multiset in the data structure will have more sub- and super-multisets. The maxima for both functions vary from \(8.0\times 10^{4}\) to \(1.5\times 10^{6}\) visited nodes. We can notice that the local maxima for the functions getAllSubmsets and getAllSupermsets differ with respect to the length of input. The explanation is very simple. In order to find all sub-multisets of a small set, the function has to traverse a small part of the multiset-trie. As the size of a set increases, the part of a multiset-trie where all the sub-multisets of a given set are stored also increases. The opposite holds for the function getAllSupermsets.