Frequent Itemsets Hiding: A Performance Evaluation Framework

Abstract

Sensitive knowledge hiding is an essential requirement to prevent disclosure of any sensitive knowledge holding in shared databases. The security of a database may be risked when it is made public as is: because the data mining tools are so sophisticated that the sensitive knowledge can easily be surfaced by receivers. This gives rise to a sanitization process which transforms the original database into another database, the released one, which does not hold the sensitive knowledge but can substitute the original otherwise. In case the sensitive knowledge is of the form frequent itemsets, the resulting concrete problem is called frequent itemsets hiding. A number of algorithms, exploiting different approaches and techniques, for frequent itemsets hiding problem is proposed in the literature. Since finding optimal solutions is NP-Hard, algorithms resort to certain heuristics having different levels of sophistication, complexity, efficiency and effectiveness. This paper presents an evaluation framework which implements recent algorithms belonging to different approaches and a set of metrics to gauge the performance and problem difficulties. The current work also presents an experimental study and its results where four algorithms and seven datasets are involved. Our results indicate that data distortion levels and runtime requirements are quite high, especially for difficult problem instances. Our conclusion is that there are new rooms for more sophisticated and tuneable (w.r.t. effectiveness/efficiency tradeoff) algorithms.