Research map / Learning theory and algorithms / Prediction and decision losses
Leveraging Sparsity for Efficient Submodular Data Summarization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LSH threshold/nearest-neighbor sparsification before lazy greedy | Facility location greedy · MovieLens | speedup at 99.9% of greedy value: 512 seconds -> less than 5 seconds (100x) | Helped |
| Use sparsified lazy greedy instead of stochastic greedy | Facility location on MovieLens · MovieLens | time to equivalent value: 125 seconds vs under 5 seconds (25x) | Helped |
| Use exact nearest neighbor sparsification | Facility location greedy · MovieLens | overlap with greedy set: 4x faster, perfect match | Helped |
| Use approximate (LSH) instead of exact nearest neighbors (ablation) | Sparsification · MovieLens | overlap with greedy set: 90% overlap, 50x faster vs 4x faster exact | Mixed |
| Use sparsification instead of stochastic greedy for overlap with greedy set | MovieLens summarization · MovieLens | overlap with greedy set: 90% vs 70% | Helped |
| Use sparsified Monte Carlo PPR instead of full PPR matrix greedy | Facility location on IMDb · IMDb graph | speedup: six hours -> under 10 minutes (36x), 99% of greedy | Helped |
| Use sparsified approach instead of sampling a subset of I with power-method PPR | Facility location on IMDb · IMDb graph | function value and greedy overlap vs runtime | Helped |
| Use facility location instead of plain PageRank for selecting actors | IMDb 57,000-vertex graph · IMDb | diversity of nationality | Helped |
Closest papers by meaning
- Data Summarization at Scale: A Two-Stage Submodular Approach (ICML 2018 · similarity 0.88)
- Learning Sparse Combinatorial Representations via Two-stage Submodular Maximization (ICML 2016 · similarity 0.87)
- Fast Constrained Submodular Maximization: Personalized Data Summarization (ICML 2016 · similarity 0.85)
- Online Summarization via Submodular and Convex Optimization (CVPR 2017 · similarity 0.85)
- Submodular Clustering beyond $1-1/e$ (NeurIPS 2026 · similarity 0.85)
- CSPG: Crossing Sparse Proximity Graphs for Approximate Nearest Neighbor Search (NeurIPS 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.