On the Necessity of Counterfeits and Deletions for Continuous Data Publishing

Continuous data publishing is the scenario where a dataset is published at different times, while it changes between publications through insertion of new tuples, reinsertions, deletions and updates of previously published tuples. Existing algorithms follow a similar structure, requiring in some cases the edition of the dataset in order to feasibly enforce the expected notion of privacy. The possible editions are insertion of synthetic tuples (counterfeits), deletion of part of the dataset, or edition of the sensitive values of a subset of the tuples. In this paper, we study when such operations are unavoidable and prove that the use of centroids as an alternative proposal to data deletion preserves the privacy of the state-of-the-art notions used in the literature.