Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper addresses the challenge of result diversification in sensitive data contexts by introducing differentially private algorithms for the max-sum diversification (MSD) problem. The authors achieve nearly optimal utility while ensuring privacy, and their methods outperform existing non-private algorithms in terms of execution speed. Experimental results confirm that their approach maintains comparable utility to non-private baselines, even under stringent privacy constraints, which is critical for data-driven applications requiring both relevance and diversity.
Achieving faster execution times and strong privacy guarantees, this work reveals that you can have both utility and confidentiality in result diversification.
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.