Proximity-based services

Restaurants near me, drivers within two kilometres, friends nearby. The question is always the same: given a point and a radius, return the closest items, fast.

Crux: a normal index sorts along one line, and the map has two dimensions. Turn the map into cells that can be looked up by key, fetch the few cells around the point, then filter those candidates by exact distance.

The problem

A table with lat and lng columns and two ordinary indexes does not work well. An index on lat finds a whole horizontal band of the planet. An index on lng finds a vertical band. The database must intersect two huge sets to find a small square.

We need to skip most of the map without looking at it. Ask first:

• How many items are there? A thousand is different from a hundred million.
• Are they static (restaurants) or moving (drivers)? How often do they update?
• Is the query a radius, the nearest K, or inside a region?
• Is straight-line distance good enough, or does travel time matter?

Options, from simple to complex

Scan everything

Compute the distance to every item and sort. For a few thousand items, in memory, that is fast enough and needs no index. Say so. It is the right answer more often than people expect.

Geospatial index in your database

Many databases support spatial queries: PostGIS for PostgreSQL, geo types in Redis, geo queries in Elasticsearch, and similar features in MongoDB and others. Use this first for static data and moderate scale. You get radius and nearest-K queries without building the index yourself.

Under the hood: ways to cut the map into cells

• Geohash: encodes a point as a short string. Nearby points tend to share a prefix, so a prefix search on an ordinary index finds a cell. Each extra character makes the cell smaller (about 32 times smaller in area, since each character carries 5 bits). Easy to build on any key-value store or sorted index. Weakness: two points close together across a cell border can have very different hashes, so you must also query the neighbouring cells.
• Quadtree: recursively split any square that has too many points into four. Dense cities get small cells and empty areas stay large. It adapts to uneven density, which fixed grids do not. It usually lives in memory, and updating a tree on many servers is more work.
• S2 and H3: libraries that cover the globe with hierarchical cells (S2 from Google uses squares on a sphere, H3 from Uber uses hexagons). They give cell IDs at chosen sizes and can return the set of cells covering a circle. Good when you want to design it properly and not reinvent it.
• R-tree: a tree of nested bounding boxes, used inside spatial databases such as PostGIS (through its GiST index). You rarely build one yourself, but it is the answer when asked how the database does it.

You do not need to choose between these on the whiteboard. State the idea (cells, neighbours, filter) and pick one: geohash or a database index for simple cases, quadtree for uneven density, S2 or H3 if a library is allowed.

The query, step by step

• 1. Find the cell for the user's point at a size close to the search radius.
• 2. Add the neighbouring cells the circle overlaps (usually the eight around it).
• 3. Fetch the items stored under those cell keys. This is a small candidate set.
• 4. Compute exact distance to each, drop those outside the radius, sort, and return the top K.
• 5. If too few, widen to bigger cells and repeat.

Moving objects

Drivers move every few seconds, so writes dominate. A database that rewrites an index on each update will struggle at scale.

• Keep current positions in memory (Redis geo or a custom service), keyed by cell, with a short TTL so offline drivers expire.
• Update the cell only when a driver moves across a cell border, and send only occasional pings otherwise.
• Persist a history separately and asynchronously, if you need one. Current location and location history are different data with different needs.
• At large scale, shard by region or by cell so each server owns an area.

A worked example: restaurants within 2 km

Assumptions: 5 million restaurants worldwide, searched by users, with details changing rarely (all assumptions for the exercise).

• Size: 5 million entries at, say, 100 bytes each for id, position and a few fields is about 500 MB. That is small enough to keep the index in memory on one machine, or a few. This number follows from the assumptions and is not a fact about any real service.
• Static data, so we do not need a write-heavy design. Rebuild or update the index when a restaurant opens or closes.
• Design: a PostGIS or Elasticsearch geo index serves the radius query. Or store (geohash6, restaurant_id) rows and query the user's cell and its eight neighbours.
• Filter and rank: the candidates are filtered by exact distance, then by open now, cuisine, and rating. The distance step is cheap because the set is small.
• Dense downtown: a cell may hold thousands of restaurants. We can use a smaller cell size there, which is the quadtree idea.
• Scale reads with the usual ladder: a cache for popular searches (see scaling reads), and replicas of the index.

Contrast: a ride-hailing app has moving drivers, frequent updates, and a need for "closest available now". That calls for an in-memory, sharded location store, not a search index over static rows.

Choosing

• Under a few thousand items: scan.
• Static data, moderate size: the database's geospatial support.
• Huge or very hot: a purpose-built cell index (geohash, S2, H3) with caching and sharding.
• Uneven density: quadtree or adaptive cell sizes.
• Moving objects: in-memory store updated on cell changes, with TTL.

Deep dives interviewers use

Search with filters

"Open now, vegetarian, rated above 4, within 2 km." Two shapes work. Geo first: fetch candidates from the cells, then filter and rank in the application, which is fine when a cell holds hundreds of items. Filters first: a search engine that stores the position next to the attributes and applies both in one query, which wins when filters remove most items. Say which one fits the data you assumed.

A dense centre and an empty countryside

A fixed cell size is wrong in one of the two places. Adaptive cells (a quadtree, or choosing a cell level from how many items the area holds) fix it. For "nearest K" with unknown radius, start small and widen ring by ring until you have K candidates plus a margin, since the K-th nearest may lie in a ring beyond the first that held K items.

Scaling the index

• Shard by cell prefix or region, so a query touches few shards. Dense regions need more shards than sparse ones, so split by load and not by area.
• Shard by item ID spreads load evenly but every query fans out to all shards. Fine when each shard is small and fast.
• Replicate for reads, and cache popular areas (a tourist square at lunch) for a short time.

Moving items at volume

The write rate is drivers times pings per second. Cut it: send a ping only after a move beyond a threshold, batch pings from the same device, and update the index only when the cell changes. Keep the latest position with a TTL, and send history to a log for later use. Say whether a position that is a few seconds old is acceptable for matching (usually yes).

Privacy of location

Location is sensitive. Store the least precision you need, keep history only as long as the product requires, and show other users a coarse position. For legal questions about retaining or sharing location data, defer to Legal or Compliance.

Common mistakes

• Reaching for a geo index for a thousand items.
• Querying only the user's own cell, and missing the item just across the border.
• Fixed-size cells in a world of uneven density: one cell with a million items, others empty.
• Treating straight-line distance as travel time. Roads, rivers and traffic matter. Use the index to get candidates, then a routing service to rank the top few.
• Writing every driver ping to the primary database.
• Ignoring edge cases such as the date line and the poles. Say the library handles them.
• Quoting cell sizes from memory. Look them up in a table for the precision you choose, and do not state them unchecked.

Check yourself

• Why are two ordinary indexes on latitude and longitude a poor fit?
• Why must a query also look at neighbouring cells?
• What does a quadtree do that a fixed grid does not?
• How do you handle drivers who move every few seconds?
• When is a scan the right answer?
• Why rank candidates by road distance only after the index step?