Today, TripAdvisor held a tech talk in Columbia University. The topic is about k-d Tree implemented in TripAdvisor to efficiently search MASSIVE location tree.
Problem
Millions of locations, it's tough to perform Nearest Neighbor Search.
Solution
Using k-d tree to implement location tree.
It's a space-partitioning balanced binary tree. And k is the number of dimension.
k-d Tree
pseudocode
function kdtree (list of points pointList, int depth)
{
// Select axis based on depth so that axis cycles through all valid values
var int axis := depth mod k; // Sort point list and choose median as pivot element
select median by axis from pointList; // Create node and construct subtrees
var tree_node node;
node.location := median;
node.leftChild := kdtree(points in pointList before median, depth+1);
node.rightChild := kdtree(points in pointList after median, depth+1);
return node;
}