  Data mining services require accurate input data for their results to be
meaningful, but privacy concerns may influence users to provide spurious
information. To encourage users to provide correct inputs, we recently proposed
a data distortion scheme for association rule mining that simultaneously
provides both privacy to the user and accuracy in the mining results. However,
mining the distorted database can be orders of magnitude more time-consuming as
compared to mining the original database. In this paper, we address this issue
and demonstrate that by (a) generalizing the distortion process to perform
symbol-specific distortion, (b) appropriately choosing the distortion
parameters, and (c) applying a variety of optimizations in the reconstruction
process, runtime efficiencies that are well within an order of magnitude of
undistorted mining can be achieved.
