Definition
Plain language
A way of organizing points in space so you can quickly find which ones are near a given location.
As stated in the literature
A space-partitioning data structure for nearest-neighbor and range queries in low-to-moderate dimensions; one of the classical computational-geometry indexes too heavy for GPU-resident attention sparsification.
Also called: KD-trees
Why it matters: It speeds up nearest-neighbor searches in modest dimensions, though it's too heavy to run inside the tight constraints of GPU attention.
For example, given a city full of cafes, it lets you quickly find the few nearest one to where you're standing instead of checking every cafe.
Heard on the show
“Because computational geometry has theoretical answers — KD-trees, R-trees — but those are too heavy for the hardware they need to run on.”Episode 036 — Sparse Attention Was the Wrong Frame. Treat It as Geometry Instead.