Proximity Query Pattern and Neighbor Expansion

The Edge Problem
A point near a cell edge might be closer to points in adjacent cells than to points in its own cell. If you query only the center cell, you miss nearby points just across the boundary. A restaurant 100 meters away in a neighboring cell does not appear in results.
This is fundamental to all grid-based spatial indexing. The solution is neighbor expansion: query the target cell plus all 8 adjacent cells. This guarantees coverage of any circle that fits within the target cell.
Neighbor Expansion Algorithm
Given a geohash, compute its 8 neighbors: north, south, east, west, and the four diagonals. Each neighbor is a geohash of the same precision adjacent to the original. Query all 9 cells. Union the results. Post-filter by actual distance.
Computing neighbors requires understanding geohash structure. Moving east means incrementing longitude bits. Moving north means incrementing latitude bits. Libraries provide neighbor functions. For custom implementation, decode to lat/lon, offset by cell size, re-encode.
Query Radius vs Cell Size
If query radius exceeds cell size, expand to more neighbors. A 2 km radius query with 1 km cells needs the center plus at least the 8 immediate neighbors. For even larger radii, use coarser precision or expand to 25 cells (5x5 grid).
The trade-off is query count versus false positives. More cells mean more queries but fewer missed points. Fewer cells mean faster queries but potential gaps at edges. Post-filtering by exact distance catches any false positives from rectangular cells.
⚠️ Key Trade-off: Always post-filter results by actual distance. Geohash cells are rectangles, not circles. A point in a neighboring cell might be within your radius. A point in the same cell might be outside it. The geohash query is a coarse filter; distance calculation is the fine filter.

💡 Key Takeaways

✓Edge problem: nearby points in adjacent cells missed if only querying center cell

✓Neighbor expansion: query target cell plus 8 adjacent cells for coverage

✓Computing neighbors: increment or decrement longitude and latitude bits

✓Large radius queries need more neighbors or coarser precision

✓Always post-filter by actual distance; geohash cells are rectangles not circles

📌 Interview Tips

1Explain edge problem: a restaurant 50m away in the next cell is missed without neighbor expansion

2When implementing proximity search, always query 9 cells minimum: center plus 8 neighbors

3Emphasize post-filtering: geohash narrows candidates, Haversine formula determines actual matches

← Back to Geohashing Overview