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.1742326e-05
Overall Rank: 2,752 | 80.86%
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,083	Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially	2019	VLDB	6.4638932e-05
5,883	MapReduce and Streaming Algorithms for Diversity Maximization in Metric Spaces of Bounded Doubling Dimension	2017	VLDB	5.2890537e-05
6,755	Better Sliding Window Algorithms to Maximize Subadditive and Diversity Objectives	2019	PODS	4.9383139e-05
7,101	RC-Index: Diversifying Answers to Range Queries	2018	VLDB	4.8322751e-05
8,919	Efficient Indexes for Diverse Top-k Range Queries	2020	PODS	4.427232e-05
10,341	A Theoretical Framework for Distribution-Aware Dataset Search	2025	PODS	4.1945683e-05
10,353	Perfect Sampling in Turnstile Streams Beyond Small Moments	2025	PODS	4.1945683e-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
402	Mergeable Summaries	2012	PODS	0.00024196343
1,208	Efficient Diversity-Aware Search	2011	SIGMOD	0.00013275712
1,605	Addressing Diverse User Preferences in SQL-Query-Result Navigation	2007	SIGMOD	0.00011186762
1,725	Max-Sum Diversification, Monotone Submodular Functions and Dynamic Updates	2012	PODS	0.00010748322

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,000	DisC Diversity: Result Diversification based on Dissimilarity and Coverage	2013	VLDB	9.8229527e-05
8,919	Efficient Indexes for Diverse Top-k Range Queries	2020	PODS	4.427232e-05
10,927	Computing A Well-Representative Summary of Conjunctive Query Results	2024	PODS	4.1945683e-05
10,961	Faster Algorithms for Fair Max-Min Diversification in Rd	2024	SIGMOD	4.1945683e-05
5,066	Tight Space-Approximation Tradeoff for the Multi-Pass Streaming Set Cover Problem	2017	PODS	5.7223891e-05
1,725	Max-Sum Diversification, Monotone Submodular Functions and Dynamic Updates	2012	PODS	0.00010748322
7,145	Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model	2019	PODS	4.8179617e-05
2,749	Towards Tight Bounds for the Streaming Set Cover Problem	2016	PODS	8.1773535e-05
9,772	Minimum Coresets for Maxima Representation of Multidimensional Data	2021	PODS	4.2856106e-05
5,883	MapReduce and Streaming Algorithms for Diversity Maximization in Metric Spaces of Bounded Doubling Dimension	2017	VLDB	5.2890537e-05