問題タブ [r-tree]

JSI RTree 実装https://github.com/aled/jsiを使用して、アプリケーションの地理的位置にインデックスを付けようとしています。約 700 万のエントリをロードしてから、contains メソッドを使用して、マサチューセッツ州とコネチカット州の境界ボックスを使用してクエリを実行します。返される結果は、実際にはそのバウンディング ボックスにはありません。これはユーザー エラーですか、それとも RTree 実装のバグですか?

ここに私のバウンディングボックスがあります:

Rectangle r = new Rectangle(-73.630F,43.185F,-69.675F,40.946F);

返された多くの間違った結果の 1 つがこれでした

「経度」: -74.24565887、「緯度」: 40.66231918

...しかし、それらの多くは箱からはるかに外れています。

インデックス内の ID を誤って間違ったデータにマッピングしていないことを確認しました。

最初のテストを行ったとき、インデックスに数十のポイントを追加し、バウンディング ボックスを使用してクエリを実行したところ、結果が正確であることがわかりました。だから私は困惑しています。うまくいけば、誰かが何かアドバイスをしてくれます。

これらはhttp://elki.dbs.ifi.lmu.de/ からの引用です:

「本質的に、抽象距離クエリをデータベースにバインドし、この距離の最近傍検索を取得します。この時点で、ELKI は自動的に最も適切な kNN クエリ クラスを選択します。距離関数に適切なインデックスが存在する場合 (すべてのインデックスがすべての距離を加速できるわけではありません!)、ここでは自動的に使用されます。"

「getKNNForDBID メソッドは、低速の線形スキャンに要約される可能性がありますが、データベースに適切なインデックスがある場合、インデックス クエリが使用されます。その後、アルゴリズムは O(nk log n) または O(nk) 時間で実行できます。」

問題は、どのような基準で ELKI がインデックス クエリを実行するかどうかを選択するかということです。

「データベースに適切なインデックスがある場合」とはどういう意味ですか?どうすればそれを保証できますか?

「run」メソッドの署名に関する別の無関係な質問ですが、1 つではなく 3 つの署名があるのはなぜですか? それらの違いは何ですか?また、使用する署名を決定する基準は何ですか?

特定のポイントを含む一連のポリゴンをすばやく見つけるにはどうすればよいですか?

POSTGisデータベースにポリゴンのコレクションがあります。Ruby側でRGeoを使用して、データベースとの間で情報を操作、保存、およびプルしています。

外部マシンからポイント (x 座標と y 座標) を受け取り、このポイントがどのポリゴン内にあるかを知る必要があります。パフォーマンス上の理由からメモリ内で実行する必要があるため、データベースを使用できません。

r-treeが必要かもしれないと思いますが、正確には書きたくありません。

RGeocontains?ポイントが対象のポリゴン内にあることを確認するために使用できる方法を提供しますが、チェックするポリゴンを知る必要があります。私は 1,000 個のポリゴンを持っていますが、線形検索を行うことは私のニーズに対して十分な時間効率ではありません。

5次元空間に約10 Kのポイントがあります。ポイントは空間 (0,0,0,0,0) および (100,100,100,100,100) にランダムに分布していると想定できます。明らかに、データセット全体を簡単にメモリに常駐させることができます。

k 最近傍のどちらのアルゴリズムがより高速に実行されるか、kd-tree または RTree を知りたいです。

私はこれら 2 つのアルゴリズムについて非常に高いレベルのアイデアを持っていますが、どちらがより速く実行されるのか、またその理由についてはわかりません。高速に実行できる他のアルゴリズムがあれば、その可能性を探る用意があります。可能であれば、アルゴリズムがより速く実行される理由を指定してください。

床のさまざまな場所にさまざまなセンサーが配置されている床があります。送信デバイスごとに、センサーがその読み取り値を検出する場合があります。1 つのフロアに 6 ～ 7 個のセンサーを配置することができ、特定の読み取り値が一部のセンサーでは検出されず、他のセンサーでは検出される可能性があります。

取得したすべての測定値について、床でのその測定値の位置を特定したいと思います。床を論理的にタイル (5 x 5 フィートの領域) に分割し、各センサー デバイスによって検出された各タイルでの理想的な読み取り値を見つけます (伝送パスロスの式に基づいて)。

各タイルの「N」センサー デバイスから事前に計算された読み取り値を、N 次元空間の点として使用しています。実際の読み取り値を取得すると、この読み取り値に最も近い値を見つけて、この読み取り値をその場所に割り当てます。

ディメンションが考慮から削除される可能性がある、K 最近傍のバリアントがあるかどうかを知りたいです。これは、特定のセンサーが読み取り値を報告していない場合に特に役立ちます。kd-tree や R ツリーなどのアルゴリズムでは、ディメンションに重みを付けることは不可能であることを理解しています。ただし、最近傍を計算するときに次元を破棄できるかどうかを知りたいです。そのようなアルゴリズムはありますか？

編集：

私が知りたいのは、同じ R/kd ツリーを、各クエリの次元の重みが異なる場合に、異なるクエリで k 最も近い検索に使用できるかどうかです。次元の異なる重みごとに別のkdツリーを構築したくありません。

編集2：

カスタム距離関数を指定し、k 個の最近傍を検索できる Python のライブラリはありますか? 基本的に、クエリごとに異なるカスタム距離関数を使用したいと考えています。

私が抱えている問題は、長方形の中に長方形があることです。マップを考えてみてください。ただし、重要なポイントは次のとおりです。同様の密度を持つ長方形は、多くの場合、他の長方形と同様の寸法と x 軸上の同様の位置を共有しますが、これらの長方形間の距離は大きい場合がありますが、通常は小さい場合があります。x 軸上の位置または寸法が明らかに大きくずれている場合、それらは似ていません。

• 長方形は交差せず、小さな長方形は大きな長方形の中に完全に入っています。

• 長方形は、多くの場合、x 位置と寸法が類似しており (高さと幅が類似)、その中に小さな長方形があります。長方形自体は、それ自体のクラスターと見なされます。

• これらのクラスターから別のクラスターまでの距離が非常に大きい場合があります (島について考えてみてください)。多くの場合、これらのクラスターは、同じまたは類似の寸法と、同じまたは類似のサブ長方形の密度を共有します。その場合、2 つのクラスター間の距離に関係なく、同じクラスターの一部と見なす必要があります。

• 長方形の密度が高い (内部の長方形が小さい) ほど、近くに同じまたは類似の次元を共有する類似または同じ密度の長方形が存在する可能性が高くなります。

状況をより明確に説明する図を添付しました。

• 赤い境界線は、これらのグループが外れ値であり、クラスターの一部ではなく、無視されることを意味します。

• 青い境界線には多くのクラスターがあります (黒い実線の長方形を含む黒い境界線)。それらは、上記の基準 (同様の幅、同様の X 位置、同様の密度) により類似したクラスターのグループを形成します。基準 (類似の幅、類似の X 位置、類似の密度) により、右下隅に向かうクラスターでさえ、このグループの一部と見なされます。

• ターコイズの境界線には多くのクラスターがあります (黒い実線の長方形を含む黒い境界線)。ただし、これらのクラスターは、次元、x 位置、および密度が青い境界線のものとは異なります。それらは独自のグループと見なされます。

これまでのところ、DBSCAN などの密度クラスタリングは、ノイズ (外れ値) を考慮に入れているため完璧と思われますが、事前にクラスターの数を知る必要はありません。

ただし、クラスターを形成するために必要なポイントの最小数と距離のしきい値を定義する必要があります。これら 2 つを知らず、上記の問題によって異なる場合はどうなるでしょうか。

別の一見もっともらしい解決策は、階層的 (凝集) クラスタリング (r ツリー) ですが、それがクラスターであるかどうかを判断するには、ツリーの深さレベルのカットオフ ポイントを知る必要があるのではないかと心配しています。

デスクトップとアンドロイドの sqlite データベースで次のクエリを実行しています。

これがデータの構造です

これは、上記の Android での EXPLAIN QUERY の結果です。

そして、これはデスクトップの結果です

デスクトップ上の sqlite は apt-get を使用してインストールされ、Android 上のものはソースから次のオプションを使用してコンパイルされました。

android で sqlite がインデックスを使用しない理由は何でしょうか? 行 verid は両方のテーブルの PRIMARY KEY であるため、rtree のサブクエリで実行されるスキャンを除いて、スキャンは行われません。

現在のシナリオでは、数百万のレコードを追加する Rtree インスタンスがあり、作成に約 1 時間かかります。複数のマッパーを使用して複数の RTree を作成し、それらをレデューサーでマージして最終的な RTree を作成できるかどうか疑問に思っていましたか? 利用可能な特定のマージ Rtree 手法はありますか? これを解決するにはどうすればよいですか？どんな助けでも大歓迎ですか？