TL;DR
This paper tackles the challenge of anonymizing transactional data, where each transaction is a set of items (like a shopping basket). They introduce "km-anonymity" to protect against adversaries with partial knowledge of a transaction and propose efficient generalization-based algorithms to achieve this, outperforming previous methods in scalability and effectiveness.
What Problem Does This Paper Address?
Publishing transactional data, such as customer purchase histories, poses a significant privacy risk. Even after removing direct identifiers, an adversary with partial knowledge of a transaction (e.g., seeing some items in a shopping bag) could potentially link it back to an individual and infer their entire purchase history. Existing privacy models, like k-anonymity for relational data, don't directly apply because transactional data is set-valued, has variable lengths, and lacks a clear distinction between quasi-identifiers and sensitive attributes. The authors introduce "km-anonymity" to address this: ensuring that any subset of m items from a transaction cannot uniquely identify it among a group of k transactions. This means an adversary with knowledge of up to m items must still be uncertain about which of the k transactions they are observing.
Methods
The core idea is to use generalization, transforming precise item names into more general categories (e.g., "skim milk" to "milk" to "dairy product"). This is achieved by defining generalization hierarchies for items. The paper proposes three main algorithms:
- Optimal Anonymization (OA): This algorithm explores all possible combinations of generalization rules to find the absolute best solution that satisfies km-anonymity with minimal information loss. However, its computational cost is prohibitively high for realistic datasets.
- Direct Anonymization (DA): A greedy heuristic that scans a specialized data structure called a count-tree to identify privacy breaches and then applies generalizations to fix them. It's more efficient than OA but still has high memory requirements.
- Apriori-based Anonymization (AA): The most scalable heuristic. It leverages the Apriori principle, iteratively building generalizations. It starts by addressing privacy breaches from adversaries with knowledge of 1 item, then 2, and so on, up to m. Crucially, generalizations made at earlier stages are used to prune the search space in later stages, significantly reducing computational cost and memory usage.
A key data structure used by the algorithms is the count-tree, which efficiently stores and retrieves the support (frequency) of itemsets, including generalized ones, to quickly check for privacy violations.
Datasets
The authors evaluated their algorithms on three real-world datasets:
- BMS-POS: Transaction logs from an electronics retailer.
- BMS-WebView-1 & BMS-WebView-2: Clickstream data from e-commerce websites.
Due to the computational demands of OA and DA, they also created smaller, synthetic datasets derived from BMS-WebView-2 by limiting the number of transactions and the item domain size to enable comparison with the optimal algorithm. They note that they did not have access to real-world generalization hierarchies and thus constructed artificial ones.
Key Insights and Ideas
- km-anonymity for Set-Valued Data: The introduction of km-anonymity is a novel and practical way to model privacy for transactional data, directly addressing the threat of adversaries with partial information.
- Generalization as the Key: Unlike suppression, generalization is shown to be an effective and scalable approach for anonymizing set-valued data, especially when combined with hierarchical item categories.
- The Power of Iterative Pruning (AA): The Apriori-based approach (AA) is a significant breakthrough in scalability. By building generalizations iteratively and using previous steps to prune the search space, it achieves near-optimal results with dramatically reduced computational cost and memory usage compared to exhaustive or simpler greedy methods.
- Scalability vs. Optimality Trade-off: The paper clearly demonstrates that while optimal solutions exist, practical applications require efficient heuristics like AA, which offer a good balance between privacy guarantees and computational feasibility.
Key Results
- AA's Superior Scalability: Experimental results show that AA significantly outperforms OA and DA in terms of execution time and memory requirements, especially as the database size, domain size, or the parameter m increases.
- Near-Optimal Information Loss: Despite being a heuristic, AA consistently achieves information loss very close to that of the optimal OA algorithm, indicating its effectiveness in preserving data utility.
- Performance Insensitivity to k: The computational cost and memory usage of AA were found to be largely insensitive to the parameter k (the number of transactions to be indistinguishable from), which is a desirable property.
- Impact of Hierarchy Depth (h): A deeper hierarchy (h) generally leads to better information loss but can increase computational cost. AA performs well across various hierarchy depths, though very shallow hierarchies can sometimes lead to trivial anonymization.
Limitations and Future Work
- Artificial Hierarchies: The authors acknowledge that they used artificial generalization hierarchies, and the performance might vary with real-world, domain-specific hierarchies.
- Future Work: The paper suggests extending the model to incorporate l-diversity concepts to handle sensitive attributes more robustly. They also plan to investigate local recoding techniques, which could potentially lead to even lower information loss.
Summary updated