セットから最も近い要素を効率的に検索するためのデータ構造

Question

tl; dr MathematicaのNearestのようなものは、どのように効率的に実装できますか？

Mathematicaは（、彼らは数字ことができn次元空間、文字列などの座標）「もの」のリストを取るNearestと呼ばれる機能を有しており、NearestFunctionオブジェクトを返します。このオブジェクトは、xに適用すると、ある距離メトリックでxに最も近いリスト要素を返します。距離メトリックは、パラメータとしてNearestに渡すことができます。デフォルトでは、数値データの場合はユークリッド距離を使用し、文字列の場合はある程度の編集距離を使用します。

---

例（これがうまくいけば問題はより明確になります）：

nf = Nearest[{92, 64, 26, 89, 39, 19, 66, 58, 65, 39}];

nf[50]は58、50に最も近い要素を返します。 nf[50, 2]は、最も近い2つの要素である{58, 39}を返します。

---

質問：この機能を実装するための効率的な方法は何ですか？ NearestFunctionは内部的にどのようなデータ構造ですか？さまざまな種類のデータに最も近い要素を計算するために可能な限り複雑なのは何ですか？

数値を並べ替えてバイナリ検索を実行すると便利ですが、Nearestは多次元データと任意の距離関数で動作しますので、より一般的なものを使用していると思います。しかし、特定の種類のデータ/距離関数に特化していることが判明すれば、私は驚くことはありません。

Answer 1

適切に動作する距離関数のために、これ専用に最適化された多くのデータ構造があります。多次元データの場合、k-d tree（および他のbinary space partitioning trees）は、通常、サブライン時間で優れたnearest-neighbor searchesを与えることができます。最寄りの検索をサポートする方法で、一部のメトリックスペースにポイントを格納するように最適化されたツリー構造のmetric treesを調べることもできます。特定のメトリック空間（ユークリッド距離、編集距離など）に応じて、異なるデータ構造が多かれ少なかれ適切かもしれません。

動作に制限がない任意の距離関数（たとえば、三角不等式などでさえも）では、距離関数はすべての点で無限大である可能性があるため、線形探索が最良ですセット内の1つの特定の点を除く点。

希望すると便利です。

Answer 2

これはデータとメトリックによって異なります。ここをクリックしてください：Nearest Neighbour Search