In a cell-indexed nearby-places service, how do you answer 'the 10 nearest restaurants' correctly when the request gives no search radius?

seniorshould knowfreq 45%

answer

no radius means no fixed footprint
grow outward one band at a time
k candidates is not enough
what distance is fully covered?
cap, coarsen, or give up gracefully

basics

~20 s

Use an expanding ring search: scan the user's cell and then successive rings of neighbours, keeping the best k by exact distance, and stop only when the k-th best lies within the radius the scanned cells fully cover.

solid answer

~50 s

A k-nearest query has no fixed footprint: ten restaurants may sit within 200 m downtown or 30 km away in the countryside. So I start at a fine cell around the user, scan it, then add rings of neighbouring cells, keeping the k best candidates by exact distance. The subtle part is the stop condition: having k candidates is not enough, because a closer one may sit just outside the scanned area. I stop only when the k-th best distance is no greater than the covered radius, the distance from the user to the nearest unscanned cell, which after r rings is at least r times the cell's shorter side. To bound cost I cap the rings or distance, coarsen cells when rings grow, and flag partial results. With a tree index the same idea is a best-first search ordered by distance to each node's bounds.

A k-nearest query has no fixed footprint: ten restaurants may sit within 200 m downtown or 30 km away in the countryside. So I start at a fine cell around the user, scan it, then add rings of neighbouring cells, keeping the `k` best candidates by exact distance. The subtle part is the **stop condition**: having `k` candidates is not enough, because a closer one may sit just outside the scanned area. I stop only when the k-th best distance is no greater than the **covered radius**, the distance from the user to the nearest unscanned cell, which after `r` rings is at least `r` times the cell's shorter side. To bound cost I cap the rings or distance, coarsen cells when rings grow, and flag partial results. With a tree index the same idea is a best-first search ordered by distance to each node's bounds.

code

pseudocode · 11 lines

pseudocode

function kNearest(lat, lng, k, p, maxRings):
  centre = geohash(lat, lng, p)
  best = boundedMaxHeap(capacity = k)   // keeps k smallest distances
  for ring in 0..maxRings:
    for cell in cellsAtRing(centre, ring):
      for place in rangeScan(keyPrefix = cell):
        best.offer(place, haversineKm(lat, lng, place.lat, place.lng))
    coveredKm = ring * shorterSideKm(p, lat)
    if best.size() == k and best.maxDistance() <= coveredKm:
      return best.sortedAscending()      // exact answer
  return best.sortedAscending()          // best effort within maxRings

go deeper

for a junior

Recall that 'nearest ten' has no fixed distance, so the search starts small around the user and grows outward until it is sure.

for a middle

Explain rings of cells, a heap that keeps the best k, and why the search can only stop once the k-th result is inside the fully scanned distance.

for a senior

Demonstrate the covered-radius stop condition, the ring-0 trap and the cost guards: ring caps, coarsening, density-aware starts and a clear partial-result signal.

for a principal

Decide where exactness is worth paying for: exact kNN for small k, bounded best-effort for sparse regions, and cached coarse answers where product tolerance allows.

Radius queries versus k-nearest queries

Spatial indexes answer two different shapes of question:

Aspect	Radius query	k-nearest query
Request	all places within D km	the k closest places
Search footprint	fixed by D	depends on local density
Result count	varies with density	fixed at k (or fewer)
Cost bound	known in advance	unknown until search ends

A radius query can pick its cell precision from D up front. A k-nearest (kNN) query cannot: the answer might be 200 metres away downtown or 30 km away in farmland. Converting it into a radius query with a large guessed radius either wastes work in dense areas or fails in sparse ones.

Expanding ring search

On a grid of cells, whether geohash, quadtree path keys or any other cell scheme, the standard technique is to grow the search outward:

Choose a starting precision, typically fine enough that the user's own cell is small.
Ring 0 is the user's own cell. Ring r is the square band of cells at Chebyshev distance r from it: 8 cells for ring 1, 16 for ring 2, 8r in general.
Scan each new ring's cells with prefix range scans, compute exact distances and keep the best k in a bounded max-heap.
After each ring, test the stop condition. If it fails, add the next ring.

The stop condition is the whole question

The tempting rule, 'stop once I have k candidates', is wrong. The user may stand a metre from the edge of their cell; the first cell may hold ten restaurants 400 m away while an eleventh sits 30 m away across the edge.

The correct rule uses the covered radius: the largest distance around the user that is guaranteed to lie entirely inside the scanned cells.

After ring 0 the covered radius is zero, because the user may stand on the cell edge.
After r rings it is at least r times the cell's shorter side at the user's latitude.
Stop when the heap holds k candidates and the k-th best distance is at most the covered radius. Anything unscanned is then farther than every kept result.

Note that an empty ring is not a reason to stop: if the k-th best is still beyond the covered radius, a later ring can still hold closer points.

Bounding cost

Rings grow quadratically: after r rings the block holds (2r+1) x (2r+1) cells, so 5 rings mean 121 range scans. Production systems add guards:

Coarsen instead of widening. After a few rings, restart at a shorter prefix; each character removed makes cells 32 times larger in area, so one 3x3 block covers far more ground.
Cap the search. Limit rings or set a maximum distance, and return fewer than k results with an explicit 'nothing within X km' indicator rather than scanning a continent.
Start from density. Pick the starting precision from a precomputed density map, so downtown queries start fine and rural ones start coarse.
Cache popular answers keyed by a coarse cell when results need not be exact per metre.

Best-first search in tree indexes

Tree-shaped indexes such as quadtrees and R-trees answer kNN with a best-first search:

Put the root in a priority queue keyed by the minimum possible distance from the user to the node's bounding rectangle.
Pop the closest entry. If it is a node, push its children with their own minimum distances; if it is a point, push it with its exact distance.
When a point is popped, it is the next-nearest result, because nothing left in the queue can be closer.
Stop after k points.

This is the same idea as the covered radius, expressed through bounding boxes: the queue's smallest key is a lower bound on everything not yet examined.

Pagination and consistency

A 'load more' button turns kNN into 'the next k after distance d'. Passing the last returned distance and ID as a cursor lets the next page resume the search with that distance as a lower bound, instead of recomputing and skipping the first page. For mostly static places, small inconsistencies between pages are usually acceptable.

What a strong answer contains

Why kNN has no fixed footprint.
Rings of cells with a bounded heap.
The covered-radius stop condition, including the ring-0 trap.
Cost guards: coarsening, caps and density-aware starts.
The best-first equivalent for tree indexes.

## Radius queries versus k-nearest queries Spatial indexes answer two different shapes of question: | Aspect | Radius query | k-nearest query | |---|---|---| | Request | all places within D km | the k closest places | | Search footprint | fixed by D | depends on local density | | Result count | varies with density | fixed at k (or fewer) | | Cost bound | known in advance | unknown until search ends | A radius query can pick its cell precision from D up front. A **k-nearest** (kNN) query cannot: the answer might be 200 metres away downtown or 30 km away in farmland. Converting it into a radius query with a large guessed radius either wastes work in dense areas or fails in sparse ones. ## Expanding ring search On a grid of cells, whether geohash, quadtree path keys or any other cell scheme, the standard technique is to grow the search outward: 1. Choose a starting precision, typically fine enough that the user's own cell is small. 2. **Ring 0** is the user's own cell. **Ring r** is the square band of cells at Chebyshev distance r from it: 8 cells for ring 1, 16 for ring 2, 8r in general. 3. Scan each new ring's cells with prefix range scans, compute exact distances and keep the best k in a bounded max-heap. 4. After each ring, test the **stop condition**. If it fails, add the next ring. ## The stop condition is the whole question The tempting rule, 'stop once I have k candidates', is wrong. The user may stand a metre from the edge of their cell; the first cell may hold ten restaurants 400 m away while an eleventh sits 30 m away across the edge. The correct rule uses the **covered radius**: the largest distance around the user that is guaranteed to lie entirely inside the scanned cells. - After ring 0 the covered radius is **zero**, because the user may stand on the cell edge. - After r rings it is at least **r times the cell's shorter side** at the user's latitude. - **Stop when** the heap holds k candidates **and** the k-th best distance is at most the covered radius. Anything unscanned is then farther than every kept result. Note that an **empty ring** is not a reason to stop: if the k-th best is still beyond the covered radius, a later ring can still hold closer points. ## Bounding cost Rings grow quadratically: after r rings the block holds (2r+1) x (2r+1) cells, so 5 rings mean 121 range scans. Production systems add guards: - **Coarsen instead of widening.** After a few rings, restart at a shorter prefix; each character removed makes cells 32 times larger in area, so one 3x3 block covers far more ground. - **Cap the search.** Limit rings or set a maximum distance, and return fewer than k results with an explicit 'nothing within X km' indicator rather than scanning a continent. - **Start from density.** Pick the starting precision from a precomputed density map, so downtown queries start fine and rural ones start coarse. - **Cache popular answers** keyed by a coarse cell when results need not be exact per metre. ## Best-first search in tree indexes Tree-shaped indexes such as quadtrees and **R-trees** answer kNN with a **best-first search**: 1. Put the root in a priority queue keyed by the **minimum possible distance** from the user to the node's bounding rectangle. 2. Pop the closest entry. If it is a node, push its children with their own minimum distances; if it is a point, push it with its exact distance. 3. When a point is popped, it is the next-nearest result, because nothing left in the queue can be closer. 4. Stop after k points. This is the same idea as the covered radius, expressed through bounding boxes: the queue's smallest key is a lower bound on everything not yet examined. ## Pagination and consistency A 'load more' button turns kNN into 'the next k after distance d'. Passing the last returned distance and ID as a cursor lets the next page resume the search with that distance as a lower bound, instead of recomputing and skipping the first page. For mostly static places, small inconsistencies between pages are usually acceptable. ## What a strong answer contains - Why kNN has no fixed footprint. - Rings of cells with a bounded heap. - The covered-radius stop condition, including the ring-0 trap. - Cost guards: coarsening, caps and density-aware starts. - The best-first equivalent for tree indexes.

How do you stop a k-nearest query from scanning a huge empty region?
Bound the search by a ring count or a maximum distance and return what was found, flagged as 'nothing else within X km'. Switch to coarser cells after a few rings so each step covers far more area for the same number of scans, and choose the starting precision from a density map so sparse regions start coarse.
Why does best-first search on a tree index return exact nearest neighbours?
Every queue entry is keyed by the minimum possible distance from the user to anything inside it. When a point reaches the front of the queue, every remaining node and point has a key at least as large, so nothing unexamined can be closer. Each popped point is therefore the next-nearest, and stopping after k points is exact.

saying these in an interview costs you the question

The first k candidates found are the k nearest
A k-nearest query is just a radius query with a big radius
An empty ring means no closer result can exist
Scanning the user's cell and its neighbours always suffices for k-nearest
A k-nearest search needs no bound on how far it expands

In a cell-indexed nearby-places service, how do you answer 'the 10 nearest restaurants' correctly when the request gives no search radius?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

Radius queries versus k-nearest queries

Expanding ring search

The stop condition is the whole question

Bounding cost

Best-first search in tree indexes

Pagination and consistency

What a strong answer contains

▾common follow-ups2 questions

▾red flags5 flags

Radius queries versus k-nearest queries

Expanding ring search

The stop condition is the whole question

Bounding cost

Best-first search in tree indexes

Pagination and consistency

What a strong answer contains

answer

go deeper