Research map / Learning theory and algorithms / Sample complexity
Practical Data-Dependent Metric Compression with Provable Guarantees
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 16 blocks instead of 1 (ablation) | QuadSketch · SIFT | bits per coordinate: 5.17 -> 2.795 | Helped |
| Vary the number of blocks (ablation) | QuadSketch · SIFT | accuracy: 0.719; 0.717; 0.722; 0.712; 0.712; 0.712; 0.713; 0.72 | No clear effect |
| Increase the number of blocks (ablation) | QuadSketch · SIFT | bits per coordinate: 5.17; 4.523; 4.02; 3.272; 2.795; 3.474; 4.032; 4.079 | Mixed |
| Increase the pruning parameter beyond 6 (ablation) | QuadSketch · SIFT | sketch size | No clear effect |
| Use QuadSketch rather than Product Quantization | metric compression on SIFT and MNIST · SIFT and MNIST | accuracy | Mixed |
| Use QuadSketch rather than Product Quantization | metric compression · NYC Taxi | accuracy | Helped |
| Use QuadSketch rather than Product Quantization | metric compression · Diagonal | accuracy | Helped |
| Use QuadSketch or Product Quantization rather than uniform scalar quantization | metric compression · SIFT, MNIST, NYC Taxi, and Diagonal | accuracy | Helped |
Closest papers by meaning
- Euclidean distance compression via deep random features (NeurIPS 2024 · similarity 0.86)
- MetricEmbedding: Accelerate Metric Nearness by Tropical Inner Product (ICML 2025 · similarity 0.85)
- Bridging Arbitrary and Tree Metrics via Differentiable Gromov Hyperbolicity (NeurIPS 2025 · similarity 0.83)
- Generalized Dimension Reduction Using Semi-Relaxed Gromov-Wasserstein Distance (AAAI 2025 · similarity 0.82)
- Euclidean Embedding of Data Using Local Distances (NeurIPS 2026 · similarity 0.82)
- Learning Distances from Data with Normalizing Flows and Score Matching (ICML 2025 · similarity 0.82)
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.