Approximate inverse frequent itemset mining: privacy, complexity, and approximation

In order to generate synthetic basket datasets for better benchmark testing, it is important to integrate characteristics from real-life databases into the synthetic basket datasets. The characteristics that could be used for this purpose include the frequent itemsets and association rules. The problem of generating synthetic basket datasets from frequent itemsets is generally referred to as inverse frequent itemset mining. In this paper, we show that the problem of approximate inverse frequent itemset mining is NP-complete. Then we propose and analyze an approximate algorithm for approximate inverse frequent itemset mining, and discuss privacy issues related to the synthetic basket dataset. In particular, we propose an approximate algorithm to determine the privacy leakage in a synthetic basket dataset.