Finding what is nearby: geohash, quadtree, H3/S2

Many apps ask "what is near me?" An interviewer asks: "Design 'restaurants near me'. How do you find the places within 3 km?" The question tests whether you can search by position. A normal index does not do this well.

A weak answer measures the distance to every place, or uses a plain index. A strong answer cuts the map into cells and gives each cell an ID. It searches the user's cell and the cells around it, and then checks the exact distance. It also says that fixed places and moving drivers need different plans.

At SDE-1 level you should explain the cell idea. At SDE-2 level you should pick a cell size and handle the cell edge. At SDE-3 level you should also compare geohash, quadtree, H3 and S2, and plan for moving drivers.

A position on Earth has two numbers. Latitude says how far north or south (from -90 to 90 degrees). Longitude says how far east or west (from -180 to 180 degrees). The question is: which places are within a radius R of a point? The distance is the shortest way along the Earth's surface. Road distance is different.

Measuring the distance to every place is slow when there are 200,000 places. A normal index does not fix this. A B-tree (lesson 20) keeps rows sorted by one value. An index on latitude finds a band between two latitudes. The band runs across the whole map, and the database must still check the longitude of every row in it. An index on (latitude, longitude) is sorted by latitude first, so it has the same problem. Some databases also have a special map index, for example PostGIS for Postgres. The cell idea below works in any database, and in memory.

Think of a street map book. The city is cut into numbered squares, such as "page 42, square C3". To find shops near you, you look in your own square and the squares next to it. The computer does the same. A cell is one square of a grid on the map. Each cell has a cell ID. Each place is stored with its cell ID, and that column has a normal index. A search has four steps:

1. Find the cell of the user.
2. Read the places in that cell and the 8 cells around it.
3. Compute the exact distance to each place. Cells only give candidates.
4. Keep the places within R, and sort them by distance.

Each side of a cell must be at least R long. Then a circle with radius R around a point in the middle cell cannot leave the 3 x 3 block of cells. A larger cell gives more candidates. A smaller cell means more cells to read.

Geohash

A geohash is a short text that names a cell. It is made by halving the map again and again. Is the point in the east half (1) or the west half (0) of longitudes -180 to 180? Then ask the same about latitude. Then longitude again, and so on. Each answer is one bit. Every 5 bits become one character from a set of 32 (the digits and the letters, without a, i, l and o).

Take a point in Indiranagar, Bengaluru: latitude 12.9784, longitude 77.6408. The first ten bits are 1100101100. The first five, 11001, are 25, which is the character t. The next five, 01100, are 12, which is d. With 8 characters the hash is tdr1yf8k.

Each new character makes the cell 32 times smaller. Here are the sizes near latitude 13 degrees. (The width shrinks as you move away from the equator.)

The prefix property is the important part. Every place inside the cell "tdr1y" has a hash that starts with "tdr1y". So a search for one cell is a search for a prefix. A sorted index finds it, because those values sit next to each other.

The reverse is not true. Two places can be very close and still have different prefixes, because a cell edge lies between them. This is the edge problem. The fix is the 3 x 3 block: always read the user's cell and its 8 neighbours. Libraries compute the neighbours. Their hashes can look very different.

Quadtree

A quadtree cuts the map into squares of different sizes. Start with one square for the whole map. If a square holds more than N places (for example 100), cut it into 4 equal squares. Repeat for each new square. The squares that are not cut any more are called leaves. Each leaf holds at most N places.

A busy city centre is cut many times, so it gets small squares. An empty area stays as one large square. To search, start at the top and go down only into squares that touch the search circle. A quadtree lives in the memory of a program, not in a normal index.

H3 and S2

H3 is a grid of hexagons. Uber made it, and it is open source. It has 16 sizes, called resolutions 0 to 15. Each cell has a 64-bit ID. A hexagon has 6 neighbours, all the same distance away. A square has 4 neighbours at one distance and 4 at its corners, farther away. So "all cells within 2 steps" is closer to a circle with hexagons.

S2 is an open-source library from Google. It puts the six faces of a cube on the sphere. It cuts each face into 4 squares, again and again, in 31 levels (0 to 30). Each cell has a 64-bit ID, and the ID tells which cell is its parent.

H3 and S2 give you the same thing as geohash: a cell ID that you store, index and search.

Fixed places and moving drivers

Fixed places, such as restaurants, change rarely. Save the cell ID when a place is added, and index it. Cache the answer of each cell for some minutes. A crowded area puts many places in one cell, so use smaller cells there. This is what a quadtree does. Spread the data over shards by city (lesson 43).

Moving drivers send a new position every few seconds. An index would change on every update, and an answer is old after a few seconds. So keep drivers in memory, in two maps: the driver to its position and cell, and the cell to the set of drivers in it. A new position changes the cell sets only when the driver crosses a cell edge. Remove drivers that are silent for too long. Do not cache the answers.

SwadKart wants "restaurants within 3 km" for a user in Indiranagar.

Assumptions (made up to teach with, not real data):

• 200,000 restaurants are spread evenly over a region of 300 km x 300 km = 90,000 km². That is 200,000 / 90,000 = 2.22 per km². Real cities have crowds; this only compares the methods.
• The user is at latitude 12.9784 and longitude 77.6408. The restaurant positions are made up.

Step 1: how many rows must we check?

• The real answer: a circle of radius 3 km has area 3.14 x 3 x 3 = 28.3 km². That is 28.3 x 2.22 = about 63 restaurants.
• An index on latitude: a band of 6 km x 300 km = 1,800 km². That is 1,800 x 2.22 = 4,000 rows to check.
• Geohash with 5 characters: a cell is 4.76 km x 4.89 km, which is bigger than 3 km. Nine cells cover 9 x 4.76 x 4.89 = 209 km². That is 209 x 2.22 = about 465 rows. It is 4,000 / 465 = 8.6 times fewer than the band.
• Geohash with 6 characters: a short program counted 56 cells that touch the circle. Their area is 56 x 1.19 x 0.61 = 41 km², so about 90 rows. This is fewer rows, but 56 cells to read.

Step 2: the cells. The user is in the cell tdr1y. The 9 cells are tdr1t, tdr1v, tdr1w, tdr1x, tdr1y, tdr1z and, to the north, tdr4j, tdr4n and tdr4p. Note the "tdr4".

Place B has a different prefix, but it is close. Place C is in the user's cell, but it is too far. So we read 9 cells and check the real distance.

Step 3: the answer to the predict box. Take two points 44 m apart: 13.0076 and 13.0080 north, both at 77.6408 east. Their hashes are tdr1yz and tdr4nb. They lie on two sides of a cell edge, and a search for the prefix of one misses the other. So the answer is no. We search the user's cell and the 8 around it.

Step 4: quadtree. Cut a square when it holds more than 100 places.

• Evenly spread: 200,000 / 100 = 2,000 leaves are needed. The first power of 4 above that is 4 to the power of 6 = 4,096. So 6 cuts are needed, and a leaf is 300 / 2 to the power of 6 = 4.7 km wide.
• Assumption: 20,000 restaurants are in a centre of 10 km x 10 km, which is 200 per km². A square of 1.17 km holds about 274 (too many). A square of 0.59 km holds 0.59 x 0.59 x 200 = about 70 (enough). So the centre needs 9 cuts, and has squares of 0.59 km.

Step 5: moving drivers. Assumptions: 50,000 drivers online, each sends a position every 4 seconds, at 30 km per hour on average.

• Updates: 50,000 / 4 = 12,500 per second.
• A driver moves 30,000 m / 3,600 s x 4 s = 33 m between updates. A 6-character cell is 610 m high and 1,190 m wide. So few updates cross an edge. Assumption: 1 in 12. This is a high number: 33 / 610 + 33 / 1,190 = 0.082, and the real share is lower.
• Changes to the cell sets: 12,500 / 12 = about 1,042 per second. The other 11,458 only replace a position in memory.

• Cells solve a search by place with an ordinary index. In the example, about 465 rows to check instead of 4,000.
• They cost a 3 x 3 read and a distance check, because cells only give candidates. Small cells check fewer rows but read more cells (56 against 9).
• A quadtree solves uneven crowds (0.59 km squares in the centre). It costs a tree in memory.
• I would change it when places move often: then I keep them in memory by cell, not in an indexed table.

"The same prefix means near, so a different prefix means far." Only the first half is true. In the example, two places 44 m apart had the hashes tdr1yz and tdr4nb.

"I will put an index on latitude and one on longitude." A B-tree is sorted by one value. So a band of 1,800 km² (4,000 rows) is checked. The cells cover 209 km².

"The cell gives the answer, so I need no distance check." A cell only gives candidates. Place C was in the user's cell and 3.4 km away.

1. Why does a B-tree index on latitude and longitude fit a nearby search badly? What is the prefix property of a geohash? What is the edge problem and how do you fix it?
2. 120,000 shops are spread evenly over 200 km x 200 km. You search within 2 km. Cells are 3 km x 3 km. How many shops are in (a) the circle, (b) a latitude band of 4 km x 200 km, (c) the 3 x 3 block?
3. A team has 40,000 scooters that send a position every 5 seconds. They update a table that has an index on the geohash. The database is at 100% CPU. What do you suggest?