Affiliations: Intelligent Data Analysis Research Group, Department of
Cybernetics, Czech Technical University in Prague, Prague, Czech Republic.
[email protected]; [email protected]
Note: [] Address for correspondence: Czech Technical University in
Prague, Technická 2, 166 27 Prague 6, Czech Republic
Abstract: We study runtime distributions of subsumption testing. On graph data
randomly sampled from two different generative models we observe a gradual
growth of the tails of the distributions as a function of the problem instance
location in the phase transition space. To avoid the heavy tails, we design a
randomized restarted subsumption testing algorithm RESUMER2. The algorithm is
complete in that it correctly decides both subsumption and non-subsumption in
finite time. A basic restarted strategy is augmented by allowing certain
communication between odd and even restarts without losing the exponential
runtime distribution decay guarantee resulting from mutual independence of
restart pairs. We empirically test RESUMER2 against the state-of-the-art
subsumption algorithm Django on generated graph data as well as on the
predictive toxicology challenge (PTC) data set. RESUMER2 performs comparably
with Django for relatively small examples (tens to hundreds of literals), while
for further growing example sizes, RESUMER2 becomes vastly superior.
