# Multiset-Trie Data Structure
## 5 Experiments  
This section contains the results of experiments that were performed on the multiset-trie data structure. In particular, we tested the functions submsetExistence, supermsetExistence, getAllSubmsets, and getAllSupermsets. We refer to the former two operations as the _existence operations_, and the later two as the _exhaustive operations_. The multiset-trie is implemented in the C\({}^{\star}\) programming language. The current implementation uses only the standard library of the C\({}^{\star}\)-14 version of the standard and has a command line interface [27]. The implementation of the program was optimized for testing, and, therefore, the program operates with files to process queries. After processing all the queries, the results are stored in files for further analysis. The current implementation of multiset-trie is not optimized for space consumption. A node in the multiset-trie is implemented as a record indicating the level of the tree that corresponds to a symbol from \(\Sigma\), and including an array of pointers to its children indexed by the multiplicities of the child symbols. The arrays have fixed length \(n\) from the interval \([0,n]\). Only some elements of an array may point to a child node, while others include a \(Null\) value. Figure 3: The ratio of “data overhead” derived from Figure 2, as the density \(p\) of our data structure increases. Unless we are in a very sparse setting, the trade-off in terms of space is small. Before we start, we will give a few definitions of the parameters that were varied throughout the experiments and discuss the experimental data that were used. Let \(M\) be a set of multisets inserted into multiset-trie and let \(n\) be the maximal node degree. Let \(N\) be the power multiset of \(\Sigma\), where the multiplicity of each element is bounded from above by \(n-1\). We define the _density_ of a multiset-trie to be the ratio \(\frac{|M|}{|N|}\), where \(|\cdot|\) denotes cardinality. The selected parameters of the data structure that were varied in the experiments were as follows:  
* \(\sigma\)--the cardinality of the alphabet \(\Sigma\);
* \(n\)--the maximal degree of a node, which explicitly defines the maximal multiplicity of elements in a multiset;
* \(\phi\)--mapping of letters from \(\Sigma\) into a set of consecutive integers;
* \(d\)--density of a multiset-trie. The cardinality of a power multiset \(N\) is equal to \(n^{\sigma}\), which means that density \(d\) of a multiset-trie depends on parameters \(|M|\), \(\sigma\) and \(n\). Because parameters \(\sigma\) and \(n\) are set when a multiset-trie is initialized, the parameter \(|M|\) was varied to change the density in the experiments. As we mentioned in Section 2, the mapping \(\phi\) determines the correspondence of letters to levels in multiset-trie, i.e., it defines the ordering of levels in multiset-trie. It is also true that \(\phi\) defines the ordering in multisets. In the following Sections 1-5, we will present the behavior of the multiset-trie data structure depending on the selected parameters, as well as the comparative benchmark of the multiset-trie against the B-tree implementation of Inverted Index. We start with experiments that were performed on artificially generated data in order to give a general picture of the multiset-trie's performance. In Experiment 1, a special case of the multiset-trie is considered. Only sets are allowed to be stored in the data structure, i.e., the maximally allowed multiplicity is set to 1. The performance is measured with respect to the density of the multiset-trie. Experiment 2 was an extension of the previous one. Here, we also measured the performance of the multiset-trie depending on its density. The difference was that the allowed multiplicity of an element was raised, i.e., the data structure was populated with multisets. Summarizing the tests of the performance depending on the density, we present Experiment 3. It shows the nonlinearity of the performance with respect to the density of the multiset-trie.