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. c lass KDTree{ //lets k be the split dimension = 2 public static final int K = 2; // Basic Static class node with left and right pointer // and each node with its properties such as coordinates static class Node { double[] point; Node left, right; int axis; Node(double coordinates, int axis) { this.point = coordinates; this.axis = axis; } } // Lets First build our KD Tree lets say the data is like list of coordinates; just like in OSM data we have list of way-points {[1,2],[8,5],[5,4]} void build(List data){ root = buildRecursivley(data, 0); } Node buildRecursively(List cordinates,int depth){ // Since we are Insert axis wise, so first we need to sort the coordinates on axis basis // get the axis at which we are dividing int axis = depth % k ; // now lets sort on the axis basis coordinates.sort(Camparator.comparingDouble(c -> c[axis])); // now we have it in order based on the dimention int median = coordinates.size() / 2; // go and build the left part of the tree Node node = new Node(coordinate.get(median), axis); // go and build the right half of the tree node.left = buildRecursively(coordinates.subList(0,mid), axis+1); node.right = buildRecursively(coordinates.subList(mid+1,coordinates.size()),axis+1); return node; } }