Location Representation
A location is represented as two binary numbers, one for each axis, where every extra bit narrows the region the point lies in.
Two PIN codes that seemed close were separated by a train line with the crossing 2 kilometers away, so a PIN code does not measure distance.
A location-based database has two requirements:
- Measuring the distance between any two points, with uniform assignment and scalable granularity.
- Proximity: all the users within 10 kilometers of a point.
Latitude and longitude satisfy the first, with the Euclidean distance. They fail proximity, because checking every point in the database is too expensive.
A number with a fixed number of bits represents a range, and each bit is a step of a binary search. Of 64 bits, 32 go to the X axis and 32 to the Y axis. One bit from X and one from Y pick one of four quadrants.
Two points whose first 13 bits are the same are close. Two points on either side of a quadrant boundary are close, and their prefixes mismatch.
Data Structure - Quad Tree
A quad tree is like a binary search tree that works on two dimensions, so each node has four branches.
The root represents the whole world. Each child contains one-fourth of the region, a sub-region, and the tree is recursive.
20 points in a node are distributed among its children: 5 in the top right, 3 in the top left, 1 in the bottom left and 11 in the bottom right.
The depth is as far as the application requires. If cities are enough, all the users in Mumbai sit in one node. If a square of side one kilometer is enough, that square is the leaf node.
The more sensible way is to split only when required: a node is split into smaller pieces when the number of users in it exceeds a threshold, such as 10.
The worst case is skew. Mumbai has a huge population and a city in Iceland has very few users, so the tree goes very deep in one branch while the other branches are light.
Range Queries and Hilbert Curve
A Hilbert curve is a line squeezed into a 2D plane so that every point on the plane has a mapping on the line.
A range query on a 2D plane has no efficient algorithm. On a 1D line, segment trees and interval trees answer it in log n. So the plane is converted into a line that preserves the proximity information.
- The line is broken into four segments, 0, 1, 2 and 3, and each goes to one quadrant. Of the possible arrangements, the U shaped Hilbert curve loses the least proximity information.
- Each quadrant is recursively broken into four more, with the U shape rotated so that the line stays continuous.
- The recursion goes to any depth, so the curve fills the entire space.
Proximity is a plus or minus threshold on the line: 6 around a customer at position 29.
Setting the threshold is a problem. Position 18 is at a difference of 11 from 29 and is extremely close, and 40 is also 11 away and is very far.