Multiset-trie data structure - datasets
DOI10.5281/zenodo.7004689Zenodo7004689MaRDI QIDQ6699273FDOQ6699273
Dataset published at Zenodo repository.
Mikita Akulich, Riste Škrekovski, Matjaž Krnc, Iztok Savnik
Publication date: 17 August 2022
Copyright license: Creative Commons Attribution 4.0 International
We propose a new data structure multiset-trie 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 S and a multiset X. The multiset containment operations retrieve multisets from S that are either sub-multisets or super-multisets of X. 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.
This page was built for dataset: Multiset-trie data structure - datasets
