Suppose a new point could fit in several overlapping leaves of a similarity search tree. Checking every candidate may be expensive. A heuristic replaces that exhaustive choice with a practical rule: at each level, follow the child whose centroid is closest to the point. The rule is fast, but the chosen leaf need not be the best one. section 10.3.2
More generally, a heuristic guides a decision without establishing that it is optimal for every input. That trade-off matters when exact search is too slow or an answer must arrive before a deadline. It is not appropriate when a sub-optimal answer is unacceptable. Nor does every use of a heuristic make the overall result approximate: a rule can guide a search or improve a data structure’s running time. section 16.1.1 section 5.0
The useful rule depends on the decision being made:
- For SS-tree insertion, scan the current node’s children, compare their centroid distances, and descend through one child. This simplifies insertion and gives the stated one-path O(log_M n) search bound. The price can be a larger bounding envelope and more overlap. section 10.3.2 section 10.3.3
- For filtered nearest-neighbor search, first reject shops missing required items; then let an application-specific comparison rule help choose between eligible candidates. Keep that business rule separate from the search structure. section 11.2.2
- For A*, estimate the remaining cost to the goal and combine it with the cost already incurred. A zero heuristic yields Dijkstra’s algorithm when distance uses edge weights, or breadth-first search when every edge costs one. Keep estimate units compatible with edge costs. section 14.5 section 14.5.2
- For difficult optimization problems, generate candidate solutions and keep the best found. Randomly sampling graph embeddings, rejecting invalid ones, and counting edge intersections is one such heuristic; repeated samples still need not find the minimum. section 16.1.1 section 16.2.3
Figure 10.12 An example where the point Z, which will be inserted into the tree, is added to the closest leaf, S14, whose bounding envelope becomes larger as a result, and overlaps another existing leaf, S15, which could have held Z within its bounding envelope. In the bottom half, notice how S14’s centroid moves as a result of adding the new point to the sphere.
The insertion diagram shows the cost of a convenient local choice: the selected leaf expands to hold the new point and overlaps another leaf that already covered it. section 10.3.2
Choose a heuristic by testing both its running cost and the quality of its decisions. A single branch is cheaper to explore than every intersecting branch, but can worsen later searches. Random sampling is cheap per attempt and does not require a specially shaped cost function, yet can repeat candidates or miss good solutions in a huge search space. Clustering algorithms likewise seek locally optimal results rather than guaranteed global optima. section 10.3.2 section 16.2.3 section 12.1.2
