Composable Core-sets for Diversity and Coverage Maximization

Summary: Constructs small composable core-sets for multiple diversity-maximization objectives in metric spaces, achieving approximation ratios that nearly match best offline algorithms up to constant factors. Applies to distributed/streaming/MapReduce nearest-neighbor and diversity search, and proves impossibility for max-coverage–based diversity. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1636
Venue: PODS
Year: 2014
Pagerank: 8.1682323e-05
Overall Rank: 2,756 | 80.85%
DOI: 10.1145/2594538.2594560

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,077	Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially	2019	VLDB	6.4634641e-05
5,888	MapReduce and Streaming Algorithms for Diversity Maximization in Metric Spaces of Bounded Doubling Dimension	2017	VLDB	5.2843653e-05
6,758	Better Sliding Window Algorithms to Maximize Subadditive and Diversity Objectives	2019	PODS	4.9335749e-05
7,083	RC-Index: Diversifying Answers to Range Queries	2018	VLDB	4.8331444e-05
8,921	Efficient Indexes for Diverse Top-k Range Queries	2020	PODS	4.4229886e-05
10,353	A Theoretical Framework for Distribution-Aware Dataset Search	2025	PODS	4.1905499e-05
10,365	Perfect Sampling in Turnstile Streams Beyond Small Moments	2025	PODS	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
398	Mergeable Summaries	2012	PODS	0.00024383201
1,204	Efficient Diversity-Aware Search	2011	SIGMOD	0.00013316893
1,606	Addressing Diverse User Preferences in SQL-Query-Result Navigation	2007	SIGMOD	0.00011175693
1,717	Max-Sum Diversification, Monotone Submodular Functions and Dynamic Updates	2012	PODS	0.00010768447

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,984	DisC Diversity: Result Diversification based on Dissimilarity and Coverage	2013	VLDB	9.8645751e-05
8,921	Efficient Indexes for Diverse Top-k Range Queries	2020	PODS	4.4229886e-05
8,521	Computing A Well-Representative Summary of Conjunctive Query Results	2024	PODS	4.4893996e-05
10,964	Faster Algorithms for Fair Max-Min Diversification in Rd	2024	SIGMOD	4.1905499e-05
5,064	Tight Space-Approximation Tradeoff for the Multi-Pass Streaming Set Cover Problem	2017	PODS	5.716891e-05
1,717	Max-Sum Diversification, Monotone Submodular Functions and Dynamic Updates	2012	PODS	0.00010768447
7,146	Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model	2019	PODS	4.8133378e-05
2,755	Towards Tight Bounds for the Streaming Set Cover Problem	2016	PODS	8.1694565e-05
9,753	Minimum Coresets for Maxima Representation of Multidimensional Data	2021	PODS	4.2856385e-05
5,888	MapReduce and Streaming Algorithms for Diversity Maximization in Metric Spaces of Bounded Doubling Dimension	2017	VLDB	5.2843653e-05