Data structure set-trie for storing and querying sets of sets
Iztok Savnik, FAMNIT, University of Primorska, Koper
Mikita Akulich, FAMNIT, University of Primorska, Koper
Matjaz Krnc, FAMNIT, University of Primorska, Koper
Riste Skrekovski, Faculty of Information Studies, Novo Mesto & FAMNIT, UP, Koper
Abstract
The data structure for storing sets of sets and the corresponding
set containment operations are an important tool in various fields,
such as datamining tools, object-relational databases, rule-based expert
systems, and AI planning systems.
We propose the data structure set-trie for storing sets of sets
which provides efficient algorithms for the set containment operations.
Mathematical and empirical study of the set-trie has been done.
The expected performance of the data structure is
analyzed by a probabilistic model, and
some relevant upper-bounds on its efficiency are determined.
The empirical study was designed to give insight into
the time-complexity space of the set containment operations.
The experimental results confirm the mathematical analysis.
Software
Data structure set-trie is implemented in Programming language C.
The source code can be dowloaded from here.
Data used in the experiments of the paper entitled
Data structure set-trie for storing and querying sets: a theoretical and empirical analysis
can be downloaded from here.
Publications
-
Data structure for set containment queries: theoretical and empirical analysis.
I.Savnik, M.Krnc, R.Skrekovski.
Submitted, 2016.
-
Index data structure for fast subset and superset queries.
I.Savnik.
CD-ARES, IFIP LNCS, 2013.
[pdf]
-
Bottom-up induction of functional dependencies from relations.
I. Savnik and P.A. Flach.
Proc. of KDD'93 Workshop: Knowledge Discovery form
Databases, AAAI Press, 1993, Washington, pp. 174-185.
[Postscript]
Last update: Fri Sep 2 12:04:04 CEST 2016