Sammanfattning En matris M sägs vara k-anonym om för varje rad r i M det finns minst k − 1 andra rader i M som är identiska med r. NP-hard k-anonymity problemet frågar, med tanke på en n × m-matris M över ett fast alfabet och ett heltal s > 0, om M kan göras k-anonymous genom att undertrycka ( blanking out) på de flesta s poster. Som komplement till tidigare arbete introducerar vi två nya "datadrivna" parameteriseringar för k-anonymitet-antalet t i olika indatarader och antalet t av olika utdatarader-båda modelleringsaspekter av data homogenitet. Vi visar att k-Anonymity är fast-parameter dragbar för parametern t i Och att det är NPhard även för t ut = 2 och alfabetet storlek fyra. I synnerhet innebär vårt fastparameterfallbarhetsresultat att k-anonymiteten kan lösas i linjär tid när t in är konstant. Våra beräkningshårdhet resultat sträcker sig också till relaterade integritetsproblem p-Känslighet och -Mångfald, medan våra fasta-parameter dragbarhet resultat sträcker sig till p-Känslighet och användning av domän generalisering hierarkier, där posterna ersätts av mer allmänna data i stället för att helt undertryckas.
Till exempel blir problemet fast-parameter dragbar för parametern "antal olika indatarader" eller för parameterkombinationen "antal olika utdataradtyper" och "antal dämpningar" REF.
The effect of homogeneity on the computational complexity of combinatorial data anonymization
{'venue': 'Data Mining and Knowledge Discovery', 'journal': 'Data Mining and Knowledge Discovery', 'mag_field_of_study': ['Mathematics', 'Computer Science']}