NATO Advanced Study Institute on Mining Massive Data Sets for Security

Approximation algorithms for k-anonymity and privacy preservation in query logs

author: Aris Gionis, Yahoo! Research Barcelona

Description

The talk (i) reviews a number of topics related to the concept of kanonymity, (ii) discusses two information-theoretic measures for capturing the amount of information that is lost during the anonymization process, (iii) presents approximation algorithms for the k-anonymization problem and (iv) discusses topics of privacy preservation on query logs.

You might be experiencing some problems with Your Video player.

*Slides*
0:00	Approximation algorithms for k-anonymity and privacy preservation in query logs
1:36	Outline
3:31	Privacy preservation
5:12	How to preserve privacy?
6:55	k-anonymity
8:01	k-anonymity — motivating example (1)
9:49	k-anonymity — motivating example (2)
11:53	k-anonymity — motivating example (3)
12:43	k-anonymity — motivating example (4)
13:09	k-anonymity — motivating example (5)
14:13	k-anonymity — motivating example (6)
14:51	k-anonymity
16:15	k-anonymity issues
16:55	k-anonymity operations
17:46	k-anonymity generalization operation
19:27	How to apply the generalization operation?
23:20	SDG vs. CBG
25:03	Some notation (1)
26:08	Some notation (2)
28:17	Measures of information loss (1)
30:04	Measures of information loss (2)
31:42	Entropy-based measures of information-loss
34:54	Example – how accurate is the entropy measure
39:47	Non monotonicity
41:32	Rectification of non monotonicity
43:07	Hardness results and approximation algorithms (1)
45:34	Hardness results and approximation algorithms (2)
46:58	The forest algorithm
52:16	New results and the entropy measures
54:01	k-anonymity algorithm for the entropy measure (1)
56:30	k-anonymity algorithm for the entropy measure (2)
58:01	Summary (so far)
90:46	Privacy preservation in query logs (1)
93:14	Privacy preservation in query logs (2)
94:10	Trade-off between utility and privacy
96:03	The AOL query-log release
98:24	A typical query log
100:12	Anonymizing query logs (1)
102:22	Anonymizing query logs (2)
103:12	Online elimination of infrequent queries (1)
106:04	Online elimination of infrequent queries (2)
106:48	Split personality
108:48	More on anonymizing query logs: negative results
112:22	Summary
112:55	References (1)
112:58	References (2)
113:01	References (3)

Lecture rating

People found this lecture:
Worth seeing
because it is:
Valuable and informative
Well presented
Easily understandable
Acceptably recorded
You need to login to cast your vote.

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.