2

3〜20次元で50〜10000個のベクトルを格納したいと思います。最近傍問題をすばやく解決したり、最近傍問題を近似したりするために、ベクトルを格納する構造を知りたいです。ユークリッド、マンハッタン、マックス、および加重マンハッタンメトリックを使用します。

私は問題を読み始め、次元の数がベクトルの数よりもはるかに少ない場合、kd-treesがそれを行うことを発見しました（間違っている場合は訂正してください）。パフォーマンスは、深く劣線形になる可能性があります（O（log（n）））。

問題は、構造が非常に急速に変化することです。各ベクトルは、プログラムの過程で何千回も変化する可能性があります。さらに、ベクトルはおおよその位置やスケールを維持する必要はありません。構造全体がR^nを「移動」できます。

問題は、kdツリーの高性能を維持するために、時々リバランスを行う必要があるということです。この操作は、ツリー全体を再構築するのと同じくらいコストがかかる可能性があります。

急速に変化するkdツリーの問題を解決するにはどうすればよいですか？

4

1 に答える 1

2

さまざまなデータ構造で動作するアルゴリズムの償却分析を行う必要があります。結果は、使用している特定のデータ構造に対する操作の順序によって異なります。

Rツリーも見てみることをお勧めします。データ構造の更新がクエリよりも頻繁である場合、その構造の更新はかなりうまく機能する可能性があるため、静的グリッドを確認することもお勧めします。

データ構造の更新が頻繁に行われる場合は、変更のたびにデータ構造を更新する必要はなく、最初に古いものを使用してから、変更されたすべての要素を検索することをお勧めします。そうすれば、データ構造にバッチ変更を加えることができます。これは、もう少し効率的かもしれません。これは、償却分析でも回答できることの1つです。

また、多次元ツリーで利用可能な文献も参照する必要があります。データ構造やまだ考えていないものをより効率的に操作するための提案がきっと見つかります。しかし、私はまだ文学を推薦することはできません。

于 2013-01-04T07:18:25.253 に答える