Data structure settrie 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, objectrelational databases, rulebased expert
systems, and AI planning systems.
We propose the data structure settrie for storing sets of sets
which provides efficient algorithms for the set containment operations.
Mathematical and empirical study of the settrie has been done.
The expected performance of the data structure is
analyzed by a probabilistic model, and
some relevant upperbounds on its efficiency are determined.
The empirical study was designed to give insight into
the timecomplexity space of the set containment operations.
The experimental results confirm the mathematical analysis.
Software
Data structure settrie 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 settrie 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.
CDARES, IFIP LNCS, 2013.
[pdf]

Bottomup 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. 174185.
[Postscript]
Last update: Fri Sep 2 12:04:04 CEST 2016