# Multiset-Trie Data Structure
## 1 Introduction  
A multiset is a collection of elements that can have more than one instance. As in the case of ordinary sets, the ordering of the elements in multisets is not relevant. For example, multisets \(\{1,1,2\}\) and \(\{1,2,1\}\) represent the same multiset. Multisets appear in a wide variety of domains and applications [1]. The index structures for storing sets of multisets were studied in the area of object-relational database systems to store, compress and query multiset-valued attributes efficiently [2; 3; 4; 5]. The need to efficiently manage multisets also appears in information retrieval [6; 7; 8], where texts are represented as multisets. In data mining, sets are often used to represent and efficiently search hypotheses in the knowledge discovery process [9; 10]. In the area of expert systems, multisets are used for the representation and querying of the preconditions of rules [11]. Finally, in recent internet applications, the efficient representations and searches of multisets (such as user requests and object features) have become essential [12; 13; 14] for data cleaning, information integration, community mining, and entity resolution. In this paper, we address the problems of storing, indexing, and querying the sets of multisets. In particular, we deal with the design of an index data structure that provides an efficient implementation of the multiset containment queries. Let \(S\) be an index storing a set of multisets. For a given input multiset \(m\), a _containment query_ searches for either sub-multisets or super-multisets of \(m\) in \(S\). Existent indexes for storing a set of multisets are rooted in search trees [15]. The elements of a search tree can be accessed through keys. This approach is efficient for checking the membership of individual multisets \(m\) in \(S\). However, it is not as efficient for containment queries. The search based on the containment relation requires access to the collections \(C\subseteq S\) of multisets that are related for a multiset \(m\) either by a sub-multiset or a super-multiset relationship. The existing solutions to the implementation of the containment queries use the inverted indexes [6; 7; 16; 17; 18; 19], the signature trees [16; 20; 21; 22], and the B+ trees [19; 23]. These solutions provide a key-value look-up, where a key is an element of a multiset and a value is a corresponding multiset. The containment operations require multiple key-value index accesses and also the additional processing of partial results such as the intersection or union of multisets. To improve the efficiency of containment operations, we propose a data structure, _multiset-trie_, that is designed for storing and processing a finite bounded set of multisets. A multiset-trie generalizes the _set-trie_ data structure proposed by [PERSON] [1; 24], which was designed for the storage and processing of a finite bounded set of sets. The set-trie is an extension of a trie data structure to provide, besides the fast search and retrieval of sets, also the efficient implementation of the set containment operation. The set-trie is also a form of the binomial tree [15]. Multiset-trie provides a space-efficient representation of a set of multisets and efficient multiset containment operations. As in the case of set-trie, the ordering of the elements in multiset-trie is not relevant for the representation of multisets. As a consequence, the efficiency of the multiset containment operations is obtained by selecting the _specific_ ordering of multiset elements. This ordering can be exploited for the efficient search in a multiset-trie. The multiset-trie is an \(n\)-ary tree data structure. Each multiset in a multiset-trie is represented by a path from the root to a leaf node. Multiset elements are symbols from an alphabet. Each symbol from the alphabet is represented by a node at a certain level of the multiset-trie. The node stores the multiplicity of an element in a multiset. A multiset-trie is also a kind of search tree.