On mining closed sets in multi-relational data
Gemma C. Garriga, Roni Khardon, Luc De Raedt · Lirias (KU Leuven) · 2007
We investigate the problem of mining closed sets in multi-relational databases. Previous work in-troduced different semantics and associated algo-rithms for mining closed sets in multi-relational databases. However, insight into the implications of semantic choices and the relationships among them was still lacking. Our investigation shows that the semantic choices are important because they imply different properties, which in turn affect the range of algorithms that can mine for such sets. Of particular interest is the question whether the sem-inal LCM algorithm by Uno et al. can be upgraded towards multi-relational problems. LCM is attrac-tive since its run time is linear in the number of closed sets and it does not need to store outputs in order to avoid duplicates. We provide a posi-tive answer to this question for some of the seman-tic choices, and report on experiments that evaluate the scalability and applicability of the upgraded al-gorithm on benchmark problems. 1