java - Rツリー実装Java

Question

私はここ数日、無制限の次元をサポートするR-Treeの安定した実装を探していました（20程度で十分です）。私はこのhttp://sourceforge.net/projects/jsi/しか見つけませんでしたが、2次元しかサポートしていません。

別のオプションは、区間木の多次元実装です。

たぶん私は私の問題にRツリーまたはインターバルツリーを使用するという考えに完全に間違っているので、私は問題を簡単に述べます、あなたはこれについてのあなたの考えを私に送ることができます。

私が解決する必要のある問題は、ある種の最近傍探索です。アンテナと部屋のセットがあり、アンテナごとに整数の間隔があります。例：アンテナ1、最小-92、最大-85。実際、それは部屋->アンテナのセット->アンテナの間隔として表すことができます。アイデアは、各部屋がアンテナの次元を超えて、間隔によって各次元でRツリーのボックスにまたがるというものでした。

Nアンテナと各アンテナの値を使用してクエリを取得すると、情報を部屋のクエリポイントとして表し、そのポイントに「最も近い」部屋を取得できます。

あなたが問題のアイデアと私のアイデアを手に入れたことを願っています。

Answer 1

個別のデータがある場合、Rツリーがひどく劣化する可能性があることに注意してください。最初に実際に見つける必要があるのは、適切なデータ表現です。次に、クエリがデータのサブセットで機能するかどうかをテストします。

R-Treeは、クエリを高速化するだけです。それらがそもそも機能しない場合、それは役に立ちません。最初にR-Treeを使用せずにアプローチをテストする必要があります。大量のデータ（たとえば、100.000オブジェクト）にヒットしない限り、メモリ内の線形スキャンは、特にコードとの統合が不十分なためにアダプターレイヤーが必要な場合に、Rツリーよりも簡単にパフォーマンスが向上します。

ここでの明らかなアプローチは、境界の長方形を使用し、それらを線形にスキャンすることです。それらが機能する場合は、MBRをRツリーに格納して、パフォーマンスを向上させることができます。ただし、線形スキャンで機能しない場合は、Rツリーでも機能しません（高速では機能しません）。

Answer 2

正確な問題が何であるかは完全にはわかりませんが、R ツリーまたはインターバル ツリーは 20 次元ではうまく機能しません。これは膨大な数の次元ではありませんが、次元の呪いが現れ始めるには十分な大きさです。

私が言いたいことを理解するために、角や端から離れたものを含め、箱のすべての隣人を見てみることを考えてみてください。20 次元の場合、3 ²⁰ - 1 または 3,486,784,400 個の隣接するボックスがあります。(各軸に沿って、隣接は -1 単位、0 単位、または +1 単位になる可能性がありますが、(0,0,0) は元のボックスを表しているため隣接ではありません。)

申し訳ありませんが、ブルートフォース検索を受け入れるか、問題をよりよく分析してより賢い解決策を考え出す必要があります。

Answer 3

多くの機能を提供していると思われる Java でのこの R*-Tree 実装を見つけました。

https://github.com/davidmoten/rtree

あなたはそれをチェックしたいかもしれません！

Answer 4

Java でのもう 1 つの優れた実装は ELKI: https://elki-project.github.io/です。