Research map / Learning theory and algorithms / Prediction and decision losses
Near Neighbor: Who is the Fairest of Them All?
Sariel Har-Peled, Sepideh Mahabadi
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (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 degree approximation instead of the standard bucket-sampling baselines | Fair near-neighbor sampling · MNIST | TV distance ratio vs. Optimal: 2.4 vs. 6.6 and 10 | Improved |
| Use degree approximation instead of the standard bucket-sampling baselines | Fair near-neighbor sampling · SIFT10K | TV distance ratio vs. Optimal: 1.4 vs. 6.1 and 9.7 | Improved |
| Use degree approximation instead of the standard bucket-sampling baselines | Fair near-neighbor sampling · GloVe | TV distance ratio vs. Optimal: 2.7 vs. 6.5 and 13.1 | Improved |
| Use degree approximation rather than exact degree computation | Fair near-neighbor sampling · MNIST, k=15, L=100 | runtime: twice faster | Improved |
| Use degree approximation rather than exact degree computation | Fair near-neighbor sampling · MNIST, L=300 | runtime: 4.3 times faster | Improved |
| Spend twice more queries on degree approximation (ablation) | Degree approximation · MNIST | TV distance ratio vs. Optimal: 2.4 to 1.6 | Improved |
| Spend three times more queries on degree approximation (ablation) | Degree approximation · MNIST | TV distance ratio vs. Optimal: to 1.2 | Improved |
| Spend four times more queries on degree approximation (ablation) | Degree approximation · MNIST | TV distance ratio vs. Optimal: to 1.05 | Improved |
| Spend twice more queries on degree approximation (ablation) | Degree approximation · SIFT10K | TV distance ratio vs. Optimal: 1.4 to 1.16 | Improved |
| Spend three times more queries on degree approximation (ablation) | Degree approximation · SIFT10K | TV distance ratio vs. Optimal: to 1.04 | Improved |
| Spend four times more queries on degree approximation (ablation) | Degree approximation · SIFT10K | TV distance ratio vs. Optimal: to 1.05 | Improved |
| Spend twice more queries on degree approximation (ablation) | Degree approximation · GloVe | TV distance ratio vs. Optimal: 2.7 to 1.47 | Improved |
Closest papers by meaning
- Graph-Based Algorithms for Diverse Similarity Search (ICML 2025 · similarity 0.85)
- Fast Diverse Nearest Neighbor Search (NeurIPS 2026 · similarity 0.85)
- Relative Error Fair Clustering in the Weak-Strong Oracle Model (ICML 2025 · similarity 0.83)
- Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits (NeurIPS 2024 · similarity 0.83)
- Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph (NeurIPS 2025 · similarity 0.83)
- Weighted distance nearest neighbor condensing (ICML 2024 · similarity 0.83)
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.
