寓話
測絵隊は、毎回全境を測量しなくて済む索引台を建てた
国境測量隊は毎年、数十万枚の地形サンプル図を処理する。新しい地形報告が来るたびに、古い規則ではそれを以前のすべての報告と一つずつ照合し、類似の丘陵、河谷、隘口がないか確認する。
報告書は積み上がるばかりで、一度の照合は茶一杯の時間から半日へと変わった。前線は結果を待ちわび、後方はまだ古い図をめくっていた。隊長は人員を増やせと言い、こうして測量室に二十人が座り、それぞれが図を一束抱えて比べ合った。
さらに厄介なのは、新しい報告が正確な一致を求めないことが多い点だった。指揮官は問う：「この林に似た地形は近くにあるか？」数十メートル違っても構わない、おおよそ似ていればよい。しかし逐一照合する方法は正確な距離で計算するため、古い図ごとに全量計算を走らせる必要があった。
隊の若い測量員が数値分析をしたことがあった。彼は、全領域比較が遅いのは単一計算が重いからではなく、毎回すべての旧レポートを再読み込みして再ソートしているからだと気づいた。旧レポートを地形特徴ごとに索引化しておけば、新しいクエリが来たときは索引の中で最も近いクラスタを探すだけで済む。
彼はまず一種の圧縮符号化で各旧報告書の地形特徴を短いコードに圧縮し、次に符号の類似度で報告書を異なるバケツに分けた。照会時には、まず新しい報告書の符号を計算し、対応するバケツを見つけ、そのバケツの中だけで比較する。バケツの外は見なくてよい。
最初のバージョンはバケット分けだけで、精度はまあまあでしたが、時々境界付近のレポートを見落としました。彼はさらに層を追加しました：同じバケット内の比較に加えて、隣接するバケットも見るようにしました。隣接バケット内のレポートも十分に近い可能性があり、単にエンコード時にちょうど境界線付近に乗っているだけなのです。
彼はさらに圧縮符号化を極限まで高めた。各報告書の地形特徴を数百個の数値から数十個の数値に圧縮し、検索時にはまず圧縮コードを比較し、圧縮コードが近い少数の報告書だけを完全に解凍して照合する。
後にこの索引台はいつでも呼び出せるツールボックスになった。隊は圧縮精度とバケットの粗さを自分で選べ、精度、速度、メモリの間で調整でき、毎回報告書を最初から読む必要はない。測量隊長はついに全量比較の規則を撤廃した。比較の本質はすべてを見ることを保証することではなく、最小の労力で最も適切な数点を見つけることだ。後に測量隊はこの索引台を新兵に教えた。新兵が最も犯しやすい誤りは、速さを唯一の目標としてバケットを粗くしすぎ、似た谷を見落とすこと、または精度を唯一の目標としてバケットを細かくしすぎ、遅い旧来の検索に戻ることだ。隊長は戦況に応じて調整するよう求めた。急報はまず速さ、国境の選地はより正確さを。索引の良し悪しは、速度、空間、誤差の間の取捨選択にかかっている。