CSE Roadmap

Core tier · about 4 hours · 8 parts

Part 5 of 8 · 1 min read

Edge cases

Neighbours and widening.

Boundary issue 1. The reverse of the prefix rule is not true. Two places very close together can lie on opposite sides of the equator or the prime meridian, and have no shared prefix at all. The book gives a case in France, two towns 30 km apart whose geohashes share nothing. A query by prefix would miss them.

Boundary issue 2. Two places can share a long prefix and still be in different cells, if they sit at the edge of a cell. A user near the edge of a cell would miss places just across it.

The fix: search the user's cell and all its neighbouring cells. The neighbours' geohashes can be computed quickly. That means 1 + 8 = 9 cells. Then filter the results by true distance, to drop places outside the circle.

Too few results. Options: return only what is inside the radius, which is simple but may give too little; or widen the search. To widen with geohash, remove the last character, which gives a cell that is larger, and search it. Repeat if still too few.

A worked example (made up). A search at length 5 returns 3 places and the app wants at least 10. Dropping to length 4 widens the cell from about 4.9 × 4.9 km (24 km²) to about 39.1 × 19.5 km (762 km²), roughly 32 times larger. It will probably find enough, and then they are sorted by distance.

Read it as

A geohash cell is a box on a shelf. The box next to it may hold the nearest item. Always check the neighbouring boxes, then sort by real distance.

Check yourself: 1. Why can a prefix query miss close places? 2. How many cells are searched, and why? 3. How is a search widened?