Source-linked AI summary
Slicing: A New Approach to Privacy Preserving Data Publishing
Tiancheng Li, Ninghui Li, Jian Zhang, Ian Molloy
TL;DR
Existing anonymization methods face information loss, membership disclosure, and restrictive attribute separation. The paper introduces slicing, which partitions data vertically and horizontally while preserving selected correlations, and evaluates its privacy and utility benefits. Slicing is reported to preserve better utility than generalization, outperform bucketization in sensitive-attribute workloads, and support attribute- and membership-disclosure protection.
Problem
Generalization loses considerable information in high-dimensional data, while bucketization does not prevent membership disclosure and requires a clear separation between quasi-identifying and sensitive attributes.
Method
Slicing partitions attributes into correlation-based columns and tuples into buckets, then permutes values within columns to break cross-column links.
Results
Slicing preserves better utility than generalization, is more effective than bucketization in sensitive-attribute workloads, and supports attribute- and membership-disclosure protection.
Takeaways & Limitations
Slicing preserves correlations among highly correlated attributes, can handle high-dimensional data, and can include sensitive attributes with quasi-identifying attributes.
Takeaways & Limitations
The paper mainly focuses on tuple partitioning; the trade-off between column generalization and tuple partitioning is left for future work.
Abstract
from arXiv · showhide
Several anonymization techniques, such as generalization and bucketization, have been designed for privacy preserving microdata publishing. Recent work has shown that generalization loses considerable amount of information, especially for high-dimensional data. Bucketization, on the other hand, does not prevent membership disclosure and does not apply for data that do not have a clear separation between quasi-identifying attributes and sensitive attributes. In this paper, we present a novel technique called slicing, which partitions the data both horizontally and vertically. We show that slicing preserves better data utility than generalization and can be used for membership disclosure protection. Another important advantage of slicing is that it can handle high-dimensional data. We show how slicing can be used for attribute disclosure protection and develop an efficient algorithm for computing the sliced data that obey the l-diversity requirement. Our workload experiments confirm that slicing preserves better utility than generalization and is more effective than bucketization in workloads involving the sensitive attribute. Our experiments also demonstrate that slicing can be used to prevent membership disclosure.
1. INTRODUCTION
Slicing is introduced to address information loss, membership-disclosure risk, and restrictive attribute separation in existing anonymization methods. It partitions attributes and tuples to preserve useful correlations while supporting attribute- and membership-disclosure protection.
- Motivation of Slicing: Generalization loses considerable information in high-dimensional data, while bucketization permits membership disclosure and requires separating quasi-identifying and sensitive attributes.Bucketization also breaks correlations between quasi-identifying and sensitive attributes.
- Slicing Approach: Slicing partitions attributes vertically by correlation and tuples horizontally into buckets, then permutes values within each column.This breaks links across columns while retaining associations within correlated attribute groups.
- Slicing Approach: Slicing preserves highly correlated attribute associations while breaking associations between uncorrelated attributes that may be identifying.Unlike bucketization, slicing can group quasi-identifying attributes with a sensitive attribute and preserve their correlations.
- Privacy Intuition: A tuple generally matches multiple buckets because matching buckets may contain different tuples that collectively provide its column values.This ambiguity is the basis for protecting membership information.
- Contributions: The paper develops ℓ-diverse slicing and an efficient algorithm for attribute-disclosure protection, and explains how slicing protects membership disclosure.The algorithm partitions attributes, applies column generalization, and partitions tuples into buckets.
- Contributions: Workload experiments report better utility than generalization and greater effectiveness than bucketization in workloads involving the sensitive attribute.The paper also reports that slicing can outperform original data in some classification experiments and addresses bucketization’s membership-disclosure limitations.
2. SLICING
Slicing anonymizes microdata by partitioning attributes into correlated columns and tuples into buckets, then permuting values within columns. This preserves within-column correlations, supports high-dimensional data, and addresses limitations of generalization and bucketization.
- Slicing: Within each bucket, slicing randomly permutes values in each column to hide links between columns while preserving values within columns.In the example, correlated pairs such as Age–Sex and Zipcode–Disease remain grouped, while links across the two columns are hidden.
- Formalization of Slicing: Slicing partitions attributes into disjoint columns and tuples into disjoint buckets, vertically and horizontally partitioning the table.A slicing is formally defined by an attribute partition and a tuple partition; each attribute and tuple belongs to exactly one subset.
- Comparison with Generalization: Grouping correlated attributes together preserves their correlations, whereas one-attribute-per-column slicing preserves distributions but not attribute correlations.The paper states that a sliced table can encode the same amount of information as the original data for correlations between attributes in the same column.
- Slicing: Slicing reduces dimensionality by treating each column as a lower-dimensional sub-table while retaining links among sub-tables through shared buckets.This design is presented as an advantage for high-dimensional data.
- Comparison with Bucketization: Compared with bucketization, slicing can prevent membership disclosure and can operate without a clear separation between quasi-identifying and sensitive attributes.Bucketization is described as the special case with one sensitive-attribute column and one all-QI column; slicing may use more columns and can place QIs and sensitive attributes together.
- Comparison with Bucketization: Slicing preserves correlations involving sensitive attributes by allowing a column to contain both sensitive and quasi-identifying attributes.The paper gives Zipcode and Disease as an example of a same-column pair whose correlation remains available for workloads that use it.
3. ATTRIBUTE DISCLOSURE PROTECTION
The paper defines ℓ-diverse slicing to protect sensitive values by reasoning over all buckets that match a tuple’s column values. It combines bucket-membership probabilities with candidate sensitive-value distributions to bound inference risk.
- ℓ-Diverse Slicing: ℓ-diverse slicing is introduced to prevent attribute disclosure under the ℓ-diversity requirement.The paper defines a sliced table as ℓ-diverse when every tuple satisfies the requirement.
- Inference Procedure: An adversary first identifies a tuple’s matching buckets, namely buckets where every column contains the tuple’s corresponding value.A tuple may match multiple buckets because different tuples can collectively supply its column values.
- Computing p(t, s): The overall probability p(t, s) combines p(t, B) and p(s|t, B) using the law of total probability.The probabilities that t takes a sensitive value sum to 1 when t is in the data.
- Computing p(t, B): The probability p(t, B) that tuple t is in bucket B depends on the product of column-level matching degrees.If a column value is absent, the bucket cannot match; otherwise, independence makes possible candidate tuples equally likely.
- Computing p(s|t, B): Within a matching bucket, candidate sensitive values are those whose quasi-identifying values match t, and their distribution determines p(s|t, B).Candidate values include duplicates and are treated as equally possible without additional knowledge.
- Privacy Guarantee: From an ℓ-diverse sliced table, an adversary cannot correctly learn any individual’s sensitive value with probability greater than 1/ℓ.The same computed probabilities can also support other privacy measures such as t-closeness.
4. SLICING ALGORITHMS
Slicing computes an ℓ-diverse table by partitioning attributes into columns and tuples into buckets, preserving correlated attributes while supporting privacy requirements.
- The algorithm computes a sliced table with c columns that satisfies ℓ-diversity from microdata table T and parameters c and ℓ.
- Attribute partitioning: Attributes are clustered into columns using pairwise correlations, placing highly correlated attributes together to preserve their associations and reduce identification risks.
- Attribute partitioning: The mean-square contingency coefficient measures association between categorical attributes using marginal and joint occurrence fractions; continuous attributes are first discretized.
- Attribute partitioning: K-medoid clustering produces columns because attributes are data points without centroids, while remaining robust to outliers and order effects.
- Attribute partitioning: The sensitive column can be constrained to α attributes by selecting the QI attributes most correlated with sensitive attribute S.
- Column generalization: Column generalization can support membership protection by preventing unique column values, but it trades information loss against smaller buckets and better utility.
- Tuple partitioning: Tuple partitioning modifies Mondrian to split buckets only when the resulting sliced table satisfies ℓ-diversity, checked using matching-bucket statistics and candidate sensitive-value distributions.
5. MEMBERSHIP DISCLOSURE PROTECTION
The paper analyzes how anonymized data can reveal membership and argues that slicing obscures membership by creating matching buckets for many tuples outside the original data.
- Bucketization exposes membership because original QI values let an adversary infer whether an individual’s record appears in the published data.
- Membership protection requires tuples inside and outside the original data to have similar frequencies or matching-bucket patterns in the anonymized data.
- A fake tuple is outside the original data but matches at least one bucket in the sliced data; fake-tuple counts and matching-bucket similarity measure protection.
- A sliced bucket of size k across c columns can match up to k^c tuples, introducing as many as k^c − k tuples beyond its original members.
- These additional matching tuples make it uncertain whether a matching tuple belongs to the original data, and experiments empirically evaluate this protection.
6. EXPERIMENTS
The experiments evaluate slicing against generalization and bucketization for utility, attribute disclosure, and membership disclosure using Adult-derived datasets. Across workloads, slicing preserves sensitive-attribute utility better, while its fake tuples and matching buckets support membership-disclosure protection.
- Experimental setup: The experiments compare generalization, bucketization, and slicing using Mondrian and ℓ-diversity on Adult-derived datasets.The datasets include OCC-7 and OCC-15, with Occupation as the sensitive attribute.
- Attribute disclosure protection: Slicing outperforms generalization and bucketization when learning the sensitive attribute Occupation.This result is attributed to preserving correlations between Occupation and some quasi-identifying attributes.
- Attribute disclosure protection: Both bucketization and slicing perform much better than generalization when learning the QI attribute Education.Education remains grouped with other QI attributes, while sensitive-attribute correlations limit accuracy relative to the original data.
- Attribute disclosure protection: Increasing the number of slicing columns from c ∈ {2,3,5} decreases classification accuracy only slightly, and slicing remains better than generalization.When Occupation is the target, slicing also performs better than bucketization.
- Membership disclosure protection: Bucketization is vulnerable to membership disclosure because each OCC-7 and OCC-15 quasi-identifier combination occurs exactly once.An adversary can therefore determine membership by checking whether a quasi-identifier combination appears in the released data.
- Membership disclosure protection: 87936 fake tuples arise for OCC-7 with bucket size 100 and 2 columns, nearly twice the 45222 original tuples.The number of fake tuples increases with bucket size, helping hide original tuples.
- Membership disclosure protection: For OCC-7 with p = 100 and c = 2, 5325 fake tuples and 31452 original tuples have more than 20 matching buckets.The numbers become closer for larger p and c values, which provides better membership-disclosure protection.
7. RELATED WORK
Related work covers generalization, bucketization, marginal publication, differential privacy, δ-presence, and attribute-disclosure measures. Slicing is distinguished from these approaches by combining vertical and horizontal partitioning to retain selected correlations.
- Generalization and bucketization: Generalization replaces values with less-specific but semantically consistent values, using global, regional, or local recoding schemes.Regional recoding is also called multi-dimensional recoding.
- Generalization and bucketization: Bucketization partitions tuples into buckets and randomly permutes sensitive-attribute values separately from quasi-identifiers.It has also been used for anonymizing high-dimensional data.
- Marginal publication: Marginal publication releases correlations among subsets of attributes and can be viewed as slicing without horizontal partitioning.Unlike marginal publication, horizontal partitioning preserves correlations between different columns at the bucket level.
- Privacy measures: Membership-disclosure measures include differential privacy and δ-presence, while attribute-disclosure measures include ℓ-diversity and several related privacy notions.The paper uses ℓ-diversity for attribute-disclosure protection in slicing.
8. DISCUSSIONS AND FUTURE WORK
The discussion presents slicing as a utility-preserving approach that uses data characteristics while identifying open questions about overlapping columns, tuple grouping, and downstream data use. These directions expose privacy–utility and utility-preservation trade-offs requiring further study.
- Discussion: Slicing is presented as overcoming limitations of generalization and bucketization while preserving utility and protecting against attribute and membership disclosure.The experiments report better utility than generalization and greater effectiveness than bucketization in sensitive-attribute workloads.
- Discussion: The paper’s methodology analyzes data characteristics before anonymization so those characteristics can inform anonymization design.The authors specifically emphasize using attribute correlations in this design process.
- Future work: Overlapping slicing could duplicate attributes across columns and improve utility, but its privacy implications require careful study.The proposed example places Disease in both {Age, Sex, Disease} and {Zipcode, Disease}.
- Future work: Random grouping is not very effective for membership-disclosure protection, motivating more effective tuple-grouping algorithms.The paper leaves the design of such algorithms to future work.
- Future work: Slicing is identified as promising for high-dimensional data because it breaks uncorrelated associations while preserving highly correlated ones.The discussion gives transaction databases as a possible application.
- Future work: Randomly generating associations between column values may lose data utility, leaving the use of anonymized data an open problem.The authors identify designing data-mining tasks over anonymized data as another research direction.