Page 50 - Fister jr., Iztok, and Andrej Brodnik (eds.). StuCoSReC. Proceedings of the 2017 4th Student Computer Science Research Conference. Koper: University of Primorska Press, 2017

pectively. Let a node u be a parent node of a node v.
Suppose that a child node v is not Null and has a label cj.
Then the path u → v represents a symbol φ−1(i) ∈ Σ with
multiplicity j. Such a transition u → v is called a path of
length 1 and is allowed if and only if a node v is not Null
and u is a parent node of a node v.
We define a complete path to be the path of length σ in a
multiset-trie with the end points at root node (the 1st level)
and LL. Thus, a multiset m is inserted into a multiset-trie
if and only if there exists a complete path in a multiset-
trie that corresponds to m. Note that every complete path
in a multiset-trie is unique. Therefore, the multisets that
share a common prefix in a multiset-trie can have a common
path of length at most σ − 1. Thus, any multiset m that is
composed of symbols from Σ with maximum multiplicity not
greater than n − 1 can be represented by a complete path in
a multiset-trie.
Let us have an example of a multiset-trie data structure,
where σ = 2, Σ = I = {1, 2}, n = 3 and the mapping φ is
an identity mapping. The figure 1 presents an example of
the multiset-trie, where Null children are omitted. Let a pair
Figure 1: Example of multiset-trie structure.
(Li, cj) represents a node with label cj at a level Li. The pair tions getAllSubmsets and getAllSupermsets are based
(L1, cj) is equivalent to (L1, root), for every j. According to
the figure 1 we can extract inserted multisets as follows:
(L1, root) → (L2, c0) → (LL, c0) ≡ {10, 20} = ∅
(L1, root) → (L2, c0) → (LL, c2) ≡ {10, 22} = {2, 2}
(L1, root) → (L2, c1) → (LL, c2) ≡ {11, 22} = {1, 2, 2}
(L1, root) → (L2, c2) → (LL, c2) ≡ {12, 22} = {1, 1, 2, 2}
where ek represents an element e with multiplicity k.
2.2 Operations
Basic tree operations. The procedure insert(M, m) in-
serts a new instance m of type Multiset into multiset-trie M.
If the complete path already exists, then procedure leaves
the structure unchanged. Otherwise it extends partially ex-
isting or creates a new complete path. The procedure does
not return any result.
The function search(M, m) checks if the complete path
corresponding to a given multiset m exists in the structure
M. The function returns true if the multiset m exists in M,
and returns false otherwise.
The function delete(M, m) searches for the complete path
that corresponds to m in order to remove it. If the path can
not be found, the function immediately returns false. During
search, the function collects additional data about common
StuCoSReC Proceedings of the 2017 4th Student Computer Science Research Conference 50
Ljubljana, Slovenia, 11 October
prefixes. When search is completed, the function removes
the branch preserving common prefixes, and returns true.
Sub- and super-multiset existence. The submsetExis-
tence(M, m) function checks if there exists a multiset x in
M, that satisfies the condition x ⊆ m. The function starts
with searching for an exact match x = m in M, since m ⊆ m
by definition of submultiset inclusion. If an exact match is
not found in M, the function uses multiset-trie to find the
closest (the largest) submultiset of m in M by decreasing
multiplicity of elements in m. At every level the function
tries to proceed with the largest possible multiplicity of an
element that is provided by m. However, when the function
reaches some level where it meets a Null node and can not
go further using path provided by m, it decreases the mul-
tiplicity of an element that corresponds to a current level.
Thus, the function can decrease multiplicity of an element
or eventually skip it in order to find the closest x ⊆ m.
The function supermsetExistence(M, m) checks if there
exists supermultiset x of a given multiset m in M. By anal-
ogy to the function submsetExistence, the function su-
permsetExistence starts by searching for an exact match
x = m in M. If an exact match is not found in M, the func-
tion searches for the closest (the smallest) supermultiset x of
m in M, in this case, by increasing multiplicity of elements
in m.
Get all sub- and super-multisets. The algorithms for func-
entirely on algorithms for submsetExistence and supermse-
tExistence functions that do not terminate on the first
existing sub/supermultiset, but store the results and con-
tinue procedure until all existing sub/supermultisets in M
are found and stored.
2.3 Analysis of the multiset-trie
By the design of the multiset-trie, it is easy to see that the
functions search, delete and the procedure insert have
complexity of O(σ). Because σ is defined when the structure
is initialized and does not depend on the user input after-
wards, the asymptotic complexity of the functions search,
delete and the procedure insert is O(1). Nonetheless, in
the general case the complexity is O(σ).
In what follows, we focus on analysis of the more involved
functions which correspond to a multiset-containment queries:
submsetExistence, supermsetExistence, getAllSubm-
sets and getAllSupermsets.
Mathematical model. We start with the basics of our math-
ematical model. Let Σ be an alphabet of cardinality σ, such
that Σ = {1, 2, . . . , σ}. Define N to be the power multiset
of Σ with respect to n, where n is the maximal degree of
a node in multiset-trie. Thus, the number of multisets in a
complete multiset-trie is |N | = nσ. Let M be a collection of
multisets inserted into multiset-trie M. Our model assumes
that all the inserted multisets from M are chosen with the
same probability p from N, for some p ∈ (0, 1).