Efficient algorithms for clone items detection

14th USENIX Security Symposium

Raoul Medina ; Caroline Noyer ; Olivier Raynaud

Others  :  http://CEUR-WS.org/Vol-162/paper7.pdf
PID  :  50492

来源: CEUR

【 摘 要 】

This paper presents efficient algorithms for clone items detection in a binary relation. Best implementation of these algorithms has O(|J |.||M||) time complexity, with J corresponding to the set of items of the relation and ||M|| corresponding to the size of the relation. This re- sult improves the previous algorithm given in [3] which is O(|J |2.||M||). Clone items have been introduced by Medina and Nourine to explain why, sometimes, the number of rules of a minimum cover of a relation is exponential with the number of items of the relation.