4. Data Publishing: A Two-Stage Approach to Improving Algorithm Efficiency

While the strategy in previous chapter is theoretically superior to existing ones due to its independence of utility measures and privacy models, and its privacy guarantee under publicly-known algorithms, it incurs a high computational complexity. In this chapter, we study an efficient strategy for diversity preserving data publishing with publicly known algorithms (algorithms as side-channel). Our main observation is that a high computational complexity is usually incurred when an algorithm conflates the processes of privacy preservation and utility optimization. We then propose a novel privacy streamliner approach to decouple those two processes for improving algorithm efficiency. More specifically, we first identify a set of potential privacy-preserving solutions satisfying that an adversary’s knowledge about this set itself will not help him/her to violate the privacy property; we can then optimize utility within this set without worrying about privacy breaches since such an optimization is now simulatable by adversaries. To make our approach more concrete, we study it in the context of micro-data release with publicly known generalization algorithms. The analysis and experiments both confirm our algorithms to be more efficient than existing solutions.