MapReduce and Streaming Algorithms for Diversity Maximization in Metric Spaces of Bounded Doubling Dimension

Summary: Streaming and MapReduce algorithms for diversity maximization in bounded-doubling metric spaces; core-sets enable space- and round-efficient approximations. Achieves (alpha+epsilon)-approximation, where alpha matches the best sequential poly-time linear-space ratio; demonstrated at scales up to billions of points. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11543
Venue: VLDB
Year: 2017
Pagerank: 5.2890537e-05
Overall Rank: 5,883 | 59.08%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 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
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

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
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
2,752	Composable Core-sets for Diversity and Coverage Maximization	2014	PODS	8.1742326e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,755	Better Sliding Window Algorithms to Maximize Subadditive and Diversity Objectives	2019	PODS	4.9383139e-05
2,480	Top-k Bounded Diversification	2012	SIGMOD	8.6899714e-05
7,480	Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms	2024	SIGMOD	4.7180617e-05
11,833	Streaming Algorithms for Robust Distinct Elements	2016	SIGMOD	4.1945683e-05
1,725	Max-Sum Diversification, Monotone Submodular Functions and Dynamic Updates	2012	PODS	0.00010748322
10,358	Robust Statistical Analysis on Streaming Data with Near-Duplicates in General Metric Spaces	2025	PODS	4.1945683e-05
9,772	Minimum Coresets for Maxima Representation of Multidimensional Data	2021	PODS	4.2856106e-05
10,961	Faster Algorithms for Fair Max-Min Diversification in Rd	2024	SIGMOD	4.1945683e-05
4,083	Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially	2019	VLDB	6.4638932e-05
2,752	Composable Core-sets for Diversity and Coverage Maximization	2014	PODS	8.1742326e-05