Why "Search Nearby" is a Massive Headache
Problem that start everything
Why "Search Nearby" is a Massive Headache (and How Maps Actually Do It)
Imagine you’re stuck in Milan for 8 hours. You’re not going to rot in the airport, so you decide to walk. But as a dev, you immediately start overthinking the route from A to K.
If you were building the map app yourself, you’d hit a wall pretty fast. OpenStreetMap (OSM) has millions of nodes. If your app just loops through all 10 million nodes every time a user moves their thumb, you’re looking at O(n) complexity. That’s a few seconds of lag—which, in app terms, is basically an eternity.
The Fix: Don't Search, Just Filter
To get those sub-millisecond responses (O(logn+k)), you have to stop treating the world like a giant list and start treating it like a grid. It’s the same logic databases use to find records without scanning the whole drive.
1. Partition the Mess
Instead of one giant pile of data, you chop the map into regions. Think of it like a Quadtree. You take the whole city, split it into four quadrants, and if a quadrant is too crowded, you split that into four more.
2. The Hierarchy
Now you’ve got a tree. The "Root" is the whole city, and the "Leaves" are the actual street corners or cafes. This lets the algorithm "ignore" 99% of the map instantly. If you're in the North-West quadrant, the code doesn't even look at the South-East.
3. Find and Refine
This is the "cheat code" for speed. It's a two-step process:
The Filter: Find which "buckets" (quadrants) overlap with where you’re standing.
The Refine: Only check the handful of points inside those specific buckets.
Why this matters
The difference is night and day. Brute force is a linear slog that breaks as soon as you add more data. Spatial indexing is an "instant" look-up that handles 100 million points as easily as 10,000. It’s the difference between reading every book in a library to find a quote versus just checking the index at the back.
public class KDTree {
public static final int K = 2;
private Node root;
static class Node {
double[] point;
Node left;
Node right;
int axis;
Node(double[] point, int axis) {
this.point = point;
this.axis = axis;
}
}
public void build(List<double[]> data) {
if (data == null || data.isEmpty()) {
return;
}
// Create a copy to avoid mutating the caller's original data
List<double[]> dataCopy = new ArrayList<>(data);
root = buildRecursively(dataCopy, 0);
}
private Node buildRecursively(List<double[]> coordinates, int depth) {
if (coordinates.isEmpty()) {
return null;
}
int axis = depth % K;
// Sort the current independent list along the target axis
coordinates.sort(Comparator.comparingDouble(c -> c[axis]));
int median = coordinates.size() / 2;
Node node = new Node(coordinates.get(median), axis);
// Wrap subList in a new ArrayList to create independent lists for recursion.
// This prevents modifying the underlying view.
node.left = buildRecursively(new ArrayList<>(coordinates.subList(0, median)), depth + 1);
node.right = buildRecursively(new ArrayList<>(coordinates.subList(median + 1, coordinates.size())), depth + 1);
return node;
}
}