Flash: Efficient, stable and optimal k-anonymity

K-anonymization is an important technique for the de-identification of sensitive datasets. In this paper, we briefly describe an implementation framework which has been carefully engineered to meet the needs of an important class of k-anonymity algorithms. We have implemented and evaluated two major well-known algorithms within this framework and show that it allows for highly efficient implementations. Regarding their runtime behaviour, we were able to closely reproduce the results from previous publications but also found some algorithmic limitations. Furthermore, we propose a new algorithm that achieves very good performance by implementing a novel strategy and exploiting different aspects of our implementation framework. In contrast to the current state-of-the-art, our algorithm offers algorithmic stability, with execution time being independent of the actual representation of the input data. Experiments with different real-world datasets show that our solution clearly outperforms the previous algorithms.