0

私は現在、データ解析プログラムに取り組んでいる核物理学の大学院生です。データは数十億の多次元ポイントで構成されています。

とにかく、空間充填曲線を使用して複数の次元を単一の次元にマップし、B + ツリーを使用してデータのページにインデックスを付けています。各ページには、一定の最大ポイント数があります。

元のファイルから生データ (数百ギガ) を読み取り、前処理してインデックスを作成するときに、個々のポイントをページに挿入する必要があります。明らかに、単純にメモリに保存してからディスクにダンプするにはページが多すぎます。だから私の質問はこれです：ページが最大サイズに達して分割する必要があるときにデータの再シャッフルが最小限になるように、ページをディスクに書き込むための良い戦略は何ですか.

コメントに基づいて、これを少し減らします。

順序付けされたレコードを含むファイルがあります。これらのレコードはファイルに挿入されていますが、これらのレコードが多すぎて、単純にメモリ内でこれを行ってからファイルに書き込むことができません。レコードを挿入するときに必要な再シャッフルの量を最小限に抑えるには、どの戦略を使用する必要がありますか?

これが何らかの意味を成している場合は、これに対する解決策をいただければ幸いです。

編集：
データは多次元空間の点です。基本的に整数のリスト。これらの整数はそれぞれ 2 バイトですが、各整数にはさらに 2 バイトのメタデータが関連付けられています。したがって、座標ごとに 4 バイトで、座標は 3 から 20 の間です。したがって、基本的にデータは、各チャンクが 12 ～ 100 バイトの数十億のチャンクで構成されます。(明らかに、4 次元のポイントは、抽出されると 5 次元のポイントとは別のファイルに配置されます)。

この記事で説明したものと同様の手法を使用しています: http://www.ddj.com/184410998

編集2：ここでこの質問をしたことを少し後悔しているので、正式に取り消されたと考えてください。しかし、これが私が既製の製品を使用しない理由です。私のデータは、3 次元から 22 次元までの範囲のポイントです。各ポイントを単なるリストと考えると、これらの数字と同じリストに表示されたすべての数字として、ポイントをクエリする方法を考えることができます。以下は、次元が低い (そして通常よりもデータ ポイントがはるかに少ない) 例です。

Queries:
511
1021
237, 661
1021, 1047
511, 237, 1047

Responses:
237, 661, 1021, 237, 1021, 661, 1047, 1021
237, 661, 511, 511, 237, 511, 661, 1047
511, 1021, 1047
511, 661
_

したがって、これはほとんどのデータベース プログラムにとって難しい小さな問題ですが、これをうまく処理できるプログラムがいくつか存在することは知っています。

しかし、問題はさらに複雑になります。すべての座標が同じというわけではありません。多くの場合、ガンマ球だけで実行するため、各座標はガンマ線エネルギーを表します。しかし、ガンマスフィアまたはマイクロボールと呼ばれる検出システムに中性子検出器を挿入する場合もあれば、ガンマスフィアで生成された核種がフラグメント質量分析器に送られる場合もあります。これらすべておよびその他の検出システムは、単独で、またはガンマスフィアと組み合わせて使用​​できます。残念ながら、ほとんどの場合、上記と同様の方法でこの追加データを選択できるようにしたいと考えています。したがって、座標にはさまざまな意味があります。ガンマスフィアに加えてマイクロボールがあれば、方程式 x + y = n の正の解と同じ数の方法で n 次元のイベントを構成できます。さらに、各座標には関連付けられたメタデータがあります。したがって、私が示した各数値には、少なくとも 2 つの追加の数値が関連付けられています。1 つ目はイベントを検出した検出器の検出器番号、2 つ目は特定のガンマ線が何回発生したかを表す効率値です。 (実際に検出される検出器に入るガンマ線のパーセンテージは、検出器とエネルギーによって変化するため)。

既製のデータベース ソリューションで、膨大な量のカスタマイズを行わなくても、これらすべてのことを同時に実行できるとは思えません。そのために費やされた時間は、一般的ではなく、私自身の解決策を書くことに費やされたほうがよいと私は信じています。一般性が失われるため、どのデータベース コードに対しても削除関数を実装する必要はありません。また、さまざまなタイプの座標をゲートするためのセカンダリ インデックスを作成する必要もありません (1 つのセットだけで、各ポイントを 1 回だけ効果的にカウントします)。等

4

3 に答える 3

1

まず、商用および無料のデータベースが提供するものを確認する必要があると思います。それらは高速範囲検索を実行し (適切なインデックスが与えられた場合)、メモリとディスクへのページの読み取り/書き込みを効率的に管理するように設計されています。

それができない場合は、Binary Space Partition ( BSP ) ツリーの変種の 1 つを見てください。

于 2009-07-28T00:38:43.433 に答える
0

私は自分で答えを思いつきました。ページを分割する必要があるときにイベントがページに挿入されると、ファイルの最後に新しいページが作成されます。元のページのイベントの半分がそのページに移動されます。これにより、ページがソートされないままになり、高速検索メカニズムがいくらか無効になります。

ただし、最初の 1 回の大きなラッシュ (おそらく数日続く) でのみデータベースに書き込むため、書き込み後に少し余分な時間を費やしてページを調べ、すべてが構築された後に並べ替えることができます。この部分は、ページのインデックスに使用される B+ ツリーの性質により、実際には非常に簡単です。B ツリーの左端のリーフ ノードから始めて、最初のページを読み取って最終ファイルの最初に配置し、次に 2 番目のページを読み取って 2 番目に配置する、というように続きます。

このようにして、挿入の最後にすべてのページがファイル内でソートされ、多次元リクエストを 1 次元インデックスにマップするために使用している方法が、ディスクからデータを読み取るときに効率的かつ迅速に機能するようになります。

于 2009-09-11T01:53:38.633 に答える
0

したがって、最初の側面は、スレッド化されたアプリケーションでこれを実行して、より迅速に処理することです。データのチャンクを実行可能なセクションに分割します。それは私が考えるように導きます...

最初は Lucene を使用することを提案するつもりでしたが、これは実際にはHadoopで処理する必要があるように思えます。これは、この種の作業のために作成されました (そのためのインフラストラクチャがあると仮定します)。

私は間違いなくデータベースでこれを行いません。

データのインデックス作成とドキュメントへのデータ ポイントの埋め込みについて話しているときに、Hadoop を実装するためのインフラストラクチャ、知識、または時間がない場合は、最初の考えに戻って Lucene を使用する必要があります。実際にそのようにデータにインデックスを付け、データポイントを「ドキュメント」（オブジェクト）構造を使用して（私が考える数値範囲で）インデックスに直接保存することができます。

于 2009-07-28T00:29:22.387 に答える