N個のオブジェクトのセットがあり、NxN距離行列を計算したいと思います。N個のオブジェクトのセットが非常に大きい場合があり、距離比較のサブセットのみを計算して、NxN距離行列の近似値を計算したいと思います。
誰かが私を完全距離行列の近似を計算する何かの方向に向けることができますか？私はいくつかのアイデアを念頭に置いていますが、車輪の再発明を避けたいと思います。
編集：アルゴリズムのタイプの例は、オブジェクトAとオブジェクトBの距離が非常に小さく、オブジェクトBとオブジェクトCの距離が非常に小さい場合、ある程度の距離が必要であるという事実を利用します。オブジェクトAとCの間の短い距離。
私はこれと同じ質問をして、Pythonコードを書くことになりました：
https://github.com/jpeterbaker/lazyDistance
README.mdは、三角不等式を使用して各距離の上限と下限を更新する方法を説明しています。
2次元空間での例のスクリプトとしてPythonファイルを実行するだけです。プロットされた線は、実際に計算された唯一の距離です。
私のバージョンでは、時間の節約は多数のオブジェクトを持つことではありません。私が書いたように、これはO（n ^ 4）アルゴリズムなので、オブジェクトの数が多い場合、すべての距離を計算するよりも実際には悪いです。しかし、私の方法では、オブジェクトの数が適度で、距離関数の計算に非常に費用がかかる場合に時間を節約できます。単一の距離測定よりも、複数のO（n ^ 2）操作を実行する方が高速であると想定しています。
nが大きい場合は、次に計算する距離を決定するためのより安価な方法を探すことができます（距離境界行列のn ^ 2エントリを使用した算術は含まれません）。また、このコードが更新するたびに、すべての2 * n^2境界を更新する必要がない場合もあります。
正直なところ、近似値をどれだけ近づけたいか、サブセットの大きさによって異なると思います。マトリックスがどのように見えるかを全体的に把握したい場合は、ランダムなサブセット（最大ノードと最小ノードを含む）に対して単純な線形補間を実行して、かなり正確な（tm）結果を得ることができます。
ここでの本当の秘訣は、ヒューリスティック（線形、2次などの補間）とサブセットサイズを把握することだと思います。また、さまざまなサブセットの距離行列を把握し、それらの行列を何らかの方法（線形、球面線形、立方体）で内挿することもできます。
最初のサンプルにもよりますが、「必要なものには十分です」と言うまでは、ヒューリスティックな試行錯誤です。
必要なソリューションは、グラフで一般的に見られるものと似ています。距離を見つけるためにすべてのペアの最短経路を使用できます。また、ジョンソンのアルゴリズムを確認することもできます。