Multiset-trie data structure - datasets

We propose a new data structure <em>multiset-trie</em> that is designed for storing and efficiently processing a set of multisets. Moreover, multiset-trie can operate on a set of sets without efficiency loss. The multiset-trie is a search tree with properties similar to those of a trie. It implements all standard search tree operations together with the multiset containment operations such as sub-multiset and super-multiset. Suppose we have a set of multisets <em>S</em> and a multiset <em>X</em>. The multiset containment operations retrieve multisets from <em>S</em> that are either sub-multisets or super-multisets of <em>X</em>. We present the mathematical analysis of a multiset-trie that gives the time complexity of the algorithms and the space complexity of the data structure. Further, the empirical analysis of the data structure is implemented in a series of experiments. The experiments illuminate the time complexity space of the multiset containment operations. For reproducability reasons we publish the datasets used in our experiments, in this repository.