Find a warehouse for an order
A customer places an order. Which warehouse has the product in stock and is closest to the delivery address? Scanning every warehouse works, but a new customer address makes the previous distance calculations useless. With N warehouses, each request requires N new distance checks. An index can make repeated searches more practical. section 8.1 section 11.1
Similarity search finds objects in a large, multidimensional dataset using how similar they are to a query object. Nearest-neighbor search returns the closest point, or the closest N points; range search returns points within a specified distance or region. The query point need not belong to the dataset. For the geometric indexes described here, coordinates can represent locations or features such as price and rating, but the distance measure must be Euclidean. section 10.4 section 8.3
Start with the query, then choose an index suited to the data:
- A k-d tree partitions space with splitting planes. Search follows the side containing the query first, tracks the best distance found, then backtracks. It visits the other side when its distance to the split is smaller than the best distance: the nearest point could lie across that boundary. section 8.3 section 9.3.5
- An R-tree groups nearby points in bounding rectangles. During nearest-neighbor search, a branch can be pruned when its rectangle is farther away than the current best point. Its nearest-neighbor procedure is outlined rather than developed in detail. section 10.2.4
- An SS-tree uses bounding envelopes. Search can visit children in order of minimum possible distance to the query; an early good candidate lets it reject more distant branches. Points are checked at leaves, unlike in the k-d tree traversal. section 10.4.1
Listing 10.19 The nearestNeighbor method for SS-tree
function nearestNeighbor(node, target, (nnDist, nn)=(inf, null)) #1
if node.leaf then #2
for point in node.points do #3
dist ← distance(point, target) #4
if dist < nnDist then #5
(nnDist, nn) ← (dist, point) #5
else
sortedChildren ← sortNodesByDistance(node.children, target) #6
for child in sortedChildren do #7
if nodeDistance(child, target) < nnDist then #8
(nnDist, nn) ← nearestNeighbor(child, target, (nnDist, nn)) #9
return (nnDist, nn) #10
The SS-tree pseudocode shows the operational test: check distances at a leaf, but descend into an internal child only if its minimum distance can beat the current best. section 10.4.1
The closest point is not always the best business choice. A warehouse query may need a stock filter; it can retrieve several nearby candidates for later ranking or pass a comparison function that incorporates business rules. Keeping that policy separate from the spatial index makes the same search structure useful for different decisions. section 11.2 section 11.2.2
Match image colors
To reduce an image to 256 selected colors, store those colors as three-dimensional RGB points in a k-d tree or SS-tree. For each original pixel, find the nearest stored color and write its palette index. Choosing the 256 colors is a separate problem. section 11.4.1
Indexing is a trade-off, not a guarantee. A balanced k-d tree speeds up search in low- and medium-dimensional spaces, but nearest-neighbor search can still scan the whole tree in the worst case. Its cited amortized cost is O(2^k + log n) for n points of dimension k, with O(m) extra space when returning a constant number m of neighbors. High dimensions weaken pruning; frequent updates are another poor fit because k-d trees do not self-balance. Approximate queries offer another performance option when exact results are not required. section 9.3.7 section 9.4 section 10.4
