Fast and Private Max-Sum Diversification
Cryptography and SecurityData Structures and Algorithms
Summary
The authors study how to pick a set of items that are both relevant and diverse from sensitive data while keeping the data private. They focus on a common method called max-sum diversification and create new algorithms that protect privacy using differential privacy techniques. Their methods work under different kinds of constraints and are almost as good as the best possible results. They also run faster than existing methods, including some that don't protect privacy. Tests on real datasets show their approach keeps results useful and is efficient even with strong privacy protections.
Authors
Ron Zadicario, Tova Milo
Abstract
Result diversification is crucial for generating informative, non-redundant data summaries and query outputs. Although its various formulations have been extensively studied across an array of data-driven disciplines, existing methods fail to address the privacy concerns that arise when the underlying data is sensitive. In this work, we initiate the study of result diversification under differential privacy, focusing on the max-sum diversification (MSD) problem, a widely adopted model with the objective of maximizing a linear combination of a submodular function, quantifying relevance, and the sum of pairwise distances between selected items, quantifying diversity. We propose differentially private algorithms for MSD under both cardinality and matroid constraints, achieving nearly optimal utility guarantees. At the same time, we design more efficient algorithms that maintain strong guarantees. Notably, the proposed algorithms are faster than existing non-private methods, making them appealing even in non-private settings. Experimental evaluations on real-world datasets demonstrate that the proposed approach achieves utility comparable to that of non-private baselines even under strong privacy guarantees, and significantly improves execution times for cardinality constraints.