Research map / Learning theory and algorithms / Sample complexity
Local Density Estimation in High Dimensions
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 Count with sampling from nonzero Hamming-distance buckets instead of enumerating only distance-0 buckets | LSH-based density estimation · GloVe, Venice, Cake, and Book (0–60°) | relative error: within 20% vs higher than 50% | Helped |
| Add importance weighting to query-directed multi-probe (ablation) | Multi-Probe Count · GloVe, Venice, Cake, and Book (0–60°), 1000 inspected elements | relative error | Helped |
| Add importance weighting to query-directed multi-probe (ablation) | Multi-Probe Count · GloVe, Cake and Book (0–60°), 5000 inspected elements | relative error | Helped |
| Add importance weighting to query-directed multi-probe (ablation) | Multi-Probe Count · GloVe, Venice (0–60°), 5000 inspected elements and more than 10 tables | relative error: 1 or 2 percentage points | Mixed |
| Increase the LSH Count sampling Hamming threshold (ablation) | LSH Count · GloVe queries | inherent bias: under 10% | Helped |
| Increase the LSH Count sampling Hamming threshold (ablation) | LSH Count · GloVe queries | sample complexity | Hurt |
| Use Hamming thresholds farther from the query bucket (ablation) | LSH Count · GloVe queries | estimate quality | Hurt |
| Choose LSH Count rather than Multi-Probe Count | Local density estimation · GloVe, Venice (sparse neighborhood) | relative error | Hurt |
| Choose LSH Count rather than Multi-Probe Count | Local density estimation · GloVe, Book (dense neighborhood) | relative error | Helped |
| Choose LSH Count with a suitable Hamming threshold rather than Multi-Probe Count | Local density estimation · GloVe, Cake (medium-sized neighborhood) | relative error | Helped |
| Rank multi-probe buckets using target angles of 30°, 45°, or 60° (ablation) | Multi-Probe · GloVe queries | relative error | No clear effect |
Closest papers by meaning
- Learning to Hash Robustly, Guaranteed (ICML 2022 · similarity 0.88)
- S2JSD-LSH: A Locality-Sensitive Hashing Schema for Probability Distributions (AAAI 2017 · similarity 0.88)
- Locality-Sensitive Hashing for f-Divergences: Mutual Information Loss and Beyond (NeurIPS 2019 · similarity 0.86)
- Locality Sensitive Hashing for p-Exponential Kernels with Applications to Density Estimation (NeurIPS 2026 · similarity 0.86)
- Discovering Data Structures: Nearest Neighbor Search and Beyond (NeurIPS 2025 · similarity 0.84)
- KALAHash: Knowledge-Anchored Low-Resource Adaptation for Deep Hashing (AAAI 2025 · 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.