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 {

// Let K be the number of dimensions (e.g., 2 for 2D space) public static final int K = 2; private Node root;

/** * Basic static Node class with left and right pointers. * Each node holds its coordinate point and the axis it was split on. */ static class Node { double[] point; Node left; Node right; int axis;

Node(double[] point, int axis) { this.point = point; this.axis = axis; } }

/** * Builds the KD-Tree from a list of coordinates. * Example OSM data way-points: {[1.0, 2.0], [8.0, 5.0], [5.0, 4.0]} */ public void build(List<double[]> data) { if (data == null || data.isEmpty()) { return; // Safety check for empty data } root = buildRecursively(data, 0); }

/** * Recursively constructs the tree by sorting and splitting at the median. */ private Node buildRecursively(List<double[]> coordinates, int depth) { // Base case: if the subset is empty, we've reached a leaf if (coordinates.isEmpty()) { return null; }

// Determine the axis to split on based on the current depth int axis = depth % K;

// Sort the coordinates along the current axis coordinates.sort(Comparator.comparingDouble(c -> c[axis]));

// Find the median element int median = coordinates.size() / 2;

// Create the node using the median point Node node = new Node(coordinates.get(median), axis);

// Recursively build the left and right subtrees // Passing depth + 1 ensures the next recursive call splits on the next axis node.left = buildRecursively(coordinates.subList(0, median), depth + 1); node.right = buildRecursively(coordinates.subList(median + 1, coordinates.size()), depth + 1);

return node; } }