Affiliations: EURISE – Université Jean Monnet de
Saint-Etienne 23, rue du Dr Paul Michelon, 42023 Saint-Etienne cedex 2, France.
amaury.habrard@univ-st-etienne.fr; marc.bernard@univ-st-etienne.fr;
marc.sebban@univ-st-etienne.fr
Note: [] Address for correspondence: EURISE – Université
Jean Monnet de Saint-Etienne, 23, rue du Dr Paul Michelon, 42023 Saint-Etienne
cedex 2, France
Abstract: In front of the large increase of the available amount of structured
data (such as XML documents), many algorithms have emerged for dealing with
tree-structured data. In this article, we present a probabilistic approach
which aims at a priori pruning noisy or irrelevant subtrees in a set of trees.
The originality of this approach, in comparison with classic data reduction
techniques, comes from the fact that only a part of a tree (i.e. a subtree) can
be deleted, rather than the whole tree itself. Our method is based on the use
of confidence intervals, on a partition of subtrees, computed according to a
given probability distribution. We propose an original approach to assess these
intervals on tree-structured data and we experimentally show its interest in
the presence of noise.
Keywords: data reduction, tree-structured data, noisy data, stochastic tree automata
