Hiding Sequences

The process of discovering relevant patterns holding in a database, was first indicated as a threat to database security by O' Leary in [20]. Since then, many different approaches for knowledge hiding have emerged over the years, mainly in the context of association rules and frequent itemsets mining. Following many real-world data and applications demands, in this paper we shift, the problem of knowledge hiding to contexts where both the data arid the extracted knowledge have a sequential structure. We provide problem statement, some theoretical issues including NP-hardness of the problem, a polynomial sanitization algorithm and an experimental evaluation. Finally we discuss possible extensions that will allow to use this work as a basic building block for more complex kinds of patterns and applications.

1. Introduction

Privacy preserving data mining, i.e., the study of data mining side-effects on privacy, has rapidly become a hot and lively research area [8], [20], [3], [27], which has seen the proliferation of many completely different approaches having different objectives, application contexts and using different techniques. The chronologically first approach in privacy preserving data mining was aimed at avoiding the identification of the original database rows (by means of data perturbation or obfuscation) while at the same time allowing the reconstruction of the data distribution at an aggregate level, and thus the production of valid mining models [3], [1], [10], [11], [23].