Quadtree Radius Search Lab (Interactive)
Radius-search a real quadtree and measure how pruning skips empty quadrants. Build a density-split quadtree and answer a radius query by visiting only intersecting quadrants versus a brute-force scan.
Yelp-style Proximity: A Real QuadTree Over 4,000 Places
Recursively split 2D space by density, then radius-search the quadrants that can actually intersect the circle.
- 1. Ka-Pow #956 · Cafe · ★4.80.10 km
- 2. Ka-Pow #3908 · Cafe · ★4.10.16 km
- 3. City Lights #1531 · Bookstore · ★3.70.16 km
- 4. Blue Bottle #2192 · Cafe · ★4.20.18 km
- 5. Page One #1774 · Gym · ★4.30.22 km
- 6. Blue Bottle #1240 · Cafe · ★3.40.24 km
Every quadrant subdivision is density-driven: a quadrant only splits past 8 places, so downtown Tokyo gets deep quads while empty ocean stays one cell. The alternative — geohash — queries the target cell plus its 8 neighbors because a circle straddles box edges; boundary artifacts cost a handful of extra candidates either way. Production keeps the spatial index in memory per shard (6.4 GB for 200M places at 32 B each) and hydrates names, ratings, and review counts from Redis only for the returned K IDs.
How It Works Under the Hood
Proximity search for places near me needs a spatial index, and the quadtree is the canonical one: recursively split 2D space into four quadrants and split a node only once it holds more than its capacity of points, so dense downtowns get deep subdivisions while empty ocean stays one cell. A radius query then prunes any quadrant whose nearest edge is farther than the radius, so the vast majority of places are never distance-checked — that pruning efficiency versus brute force is the whole point. Results come back sorted by true haversine distance, and full records hydrate from cache only for the returned K.
Core Architectural Principles
- A quadrant splits only past leaf capacity, so subdivision tracks real point density.
- Radius queries prune quadrants whose closest edge exceeds the radius, so most points are never checked.
- Pruning efficiency = 1 - points_checked / total_places; deeper trees raise it for small radii.
Explain the quadtree, or an R-tree or geohash alternative, as the in-memory spatial index and the two-phase candidate-then-refine pattern. Quantify why a brute-force distance pass over millions fails per query and how pruning collapses it toward logarithmic for selective radii. Discuss boundary expansion, category filtering, and keeping the tree in memory per shard with a hydrate-from-cache step for the K results.
A quadtree gives density-adaptive pruning but must be rebuilt or updated on inserts and struggles at coarse uniform distributions.