Why space-partitioning trees fail in high dimension
ProofAdvanced⏱ 30 minRAGkd-treepruningconcentrationcurse
Problem
Show that under distance concentration, the pruning rule of a -d tree eliminates no cells, and determine the dimension at which the method degenerates to brute force as a function of .
Write a complete argument. Every inequality you use should be one you could state precisely.
Solution
Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.
Related problems
All problems| Solved | Problem | Field | Type | Difficulty | Time |
|---|---|---|---|---|---|
| Product quantisation budget arithmetic | RAG | Numerical | 30 min | ||
| Recall composes multiplicatively | RAG | Numerical | 15 min | ||
| Distance contrast and the failure of nearest neighbours | Classical ML | Proof | 30 min | ||
| From an exponential tail bound to almost sure convergence | Probability | Proof | 30 min | ||
| Simulate the measure of a spherical cap run | High-Dim Probability | Coding | 30 min |