tree 77958f81fcf2928dfe0d667ae65d4d9752dc1338
parent ea37c48ec001a65e83d209b3fd05ed3d257f655d
author Matthias Boehm <mboehm7@gmail.com> 1600103458 +0200
committer Matthias Boehm <mboehm7@gmail.com> 1600103472 +0200

[SYSTEMDS-2641] Improved slicefinder builtin (pruning, maxL constraint)

This patch improves the slice finding builtin function by a new
estimation of score upper bounds by solving for slice sizes in the
interval [minSup, ss] and incorporating the maximum tuple errors per
slices (also monotonically decreasing) into the score computation. The
tighter score upper bounds ultimately improve the pruning effectiveness.

However, there are still datasets where full enumeration is impossible
(e.g., dozens of correlated columns, whose subsets yield slices of very
large size). For such cases, we now also provide a maxL constraint where
users can specify to enumerate e.g., up to level 3 or 4 (conjunctions of
3/4 predicates). With this extension our slice finding algorithm can now
also handle such problematic datasets.

Finally, we had to modified the related tests (added column of expected
results) because the output schema of scores changes from a 3 to 4
column matrix.