特定のサブセットを持つセットの検索

StackOverflow https://stackoverflow.com/questions/494502

  •  20-08-2019
  •  | 
  •  

質問

私は物理学の大学院生で、数百ギガバイトのデータを並べ替え、要求されたときにそのデータのスライスを返すコードの作成に取り組んでいます。ここにトリックがあります。この種のデータを並べ替えたり検索したりするための良い方法を私は知りません。

私のデータは基本的に多数の数値のセットで構成されています。これらのセットには、1 から n までの数値を含めることができ (ただし、セットの 99.9% では、n は 15 未満です)、これらのセットは約 15 ～ 20 億個あります (残念ながら、このサイズでは総当たり検索は不可能です)。

k 個の要素を含むセットを指定し、指定されたサブセットを含む k+1 個以上の要素を含むすべてのセットが返されるようにする必要があります。

簡単な例:
データに次のセットがあるとします。
(1,2,3)
(1,2,3,4,5)
(4,5,6,7)
(1,3,8,9)
(5,8,11)

リクエスト (1,3) を与えるとしたら、次のセットが得られます。（1,2,3）、（1,2,3,4,5）、および（1,3,8,9）。
リクエスト (11) は次のセットを返します。(5、8、11)。
リクエスト (1,2,3) は次のセットを返します。(1,2,3) および (1,2,3,4,5)
リクエスト (50) はセットを返しません。

ここまででパターンは明らかになるはずです。この例と私のデータの主な違いは、私のデータ内のセットがより大きく、セットの各要素に使用される数値が 0 から 16383 (14 ビット) であり、さらに多くのセットがあることです。

大事なことであれば、私はこのプログラムを C++ で書いていますが、Java、C、アセンブリ、Fortran、Perl の知識もあります。

これを実現する方法について何か手がかりを持っている人はいますか?

編集：
いくつかの質問に答えて、いくつかのポイントを追加するには、次のようにします。

1.) データは変更されません。すべては 1 つの長い実行セットで行われました (それぞれ 2 つのギガ ファイルに分割されました)。

2.) 保管スペースについて。生データは約 250 GB を占めます。興味のない多くの無関係なメタデータを処理して削除した後は、(インデックスなしで) 保持するメタデータの量に応じて、36 ギガバイトから 48 ギガバイトまで削減できると推定しています。さらに、データの最初の処理で同じセットが十分に見つかった場合は、単にイベントを何度も繰り返すのではなく、繰り返しイベントのカウンターを追加することでデータをさらに圧縮できる可能性があります。

3.) 処理されたセット内の各数値には、実際には少なくとも 2 つの数値が含まれます。データ自体 (検出エネルギー) 用の 14 ビットとメタデータ (検出器番号) 用の 7 ビットです。したがって、数値ごとに少なくとも 3 バイトが必要になります。

4.) 私の「ただし、セットの 99.9% では n は 15 未満です」というコメントは誤解を招くものでした。データの一部を予備的に確認したところ、22 個もの数値を含むセットがあることがわかりましたが、中央値は 1 セットあたり 5 個の数値で、平均は 1 セットあたり 6 個の数値です。

5.) ファイルにポインタのインデックスを構築するというアイデアは気に入っていますが、複数の数値を含むリクエストの場合、セットを見つけるというかなり遅いタスク (少なくとも私は遅いと思います) が残されるため、少し不安です。リストに共通するすべてのポインタの検索、つまり、指定された数のセットの最大共通サブセットを見つけます。

6.) 利用可能なリソースに関しては、システム上に生データを保存した後、約 300 ギガのスペースを集めることができます (そのシステム上の割り当ての残り)。このシステムは、2 つのクアッド コア amd オプテロンと 16 ギガバイトの RAM を備えたデュアル プロセッサ サーバーです。

7.) はい、0 が発生する可能性があります。発生する場合はデータ収集システムのアーチファクトですが、発生する可能性があります。

役に立ちましたか？

解決 4

私は最近、単一の次元までの多次元データをマッピングする空間充填曲線を使用する方法を発見しました。一つは、その1Dのインデックスに基づいて、インデックスデータをすることができます。範囲クエリを容易に曲線を表すボックスと交差する曲線のセグメントを発見し、それらのセグメントを検索することによって行うことができる。

私はこの方法が原因で、それを見た後、インデックスは私が保存したかっデータ、ほとんど良いことと同じ大きさになり示唆されているように非常識なインデックスを作成するよりもはるかに優れていると信じています。この幾分より詳細な説明はで見つけることができます：

http://www.ddj.com/184410998 の
そして、
http://www.dcs.bbk.ac.uk/~jkl/ publications.htmlする

他のヒント

あなたの問題は、検索エンジンが直面しているものと同じです。 「私はbajillion文書を持っている。私は言葉のこのセットが含まれているものを必要としています。」あなただけの、（非常に便利）整数の代わりの言葉、と小さめの書類を持っています。解決策は、転置インデックスです。 マニングらによる情報検索の入門（ですそのリンク）利用できる無料のオンラインは、非常に読みやすい、そしてこれを行う方法についての詳細の多くになります。

あなたはディスクスペースに代金をお支払いする必要があるとしているが、それは並列化することができ、インデックスが構築されると、タイミング要件を満たすのに十分な速以上である必要があります。

一貫したセット当たり15個の素子、及び20億セットで、0から16383のランダム分布を仮定すると、各要素は、約1.8Mのセットに現れます。あなたが検討している（そして、あなたは能力を持っていない）16384x〜1.8M（30Bエントリ、それぞれ4バイト）ルックアップテーブルを構築しますか？このようなテーブルを考えると、あなたは（1）を含有して設定するクエリを実行し、（17）および（5555）、その後、これらの3〜1.8M-要素リストの交差点を見つけることができます。

私の推測は以下の通りです。

各セットには名前、ID、またはアドレスがあるとします (セットが 20 億しかない場合は 4 バイトの数値で十分です)。

ここで、すべてのセットを一度実行して、次の出力ファイルを作成します。

  • 「1」を含むすべてのセットの ID を含むファイル
  • 「2」を含むすべてのセットの ID を含むファイル
  • 「3」を含むすべてのセットの ID を含むファイル
  • ...など...

セットごとに 16 のエントリがある場合、これらの 2^16 ファイルのそれぞれには、平均して 2^20 セットの ID が含まれることになります。各 ID が 4 バイトである場合、これには 2^38 バイト (256 GB) のストレージが必要になります。

リクエストを処理する前に、上記の作業を 1 回実行します。

リクエストを受信した場合は、これらのファイルを次のように使用します。

  • リクエスト内のいくつかの数字を確認してください
  • 対応するインデックス ファイルをいくつか開きます。
  • これらの両方のファイルに存在するすべてのセットのリストを取得します (各ファイルには 100 万の ID しかないため、これは難しくありません)。
  • これらのいくつかのセットのうちどれがリクエストの残りの部分を満たすかを確認します

私の推測では、上記のようにすると、インデックスの作成は（非常に）遅くなり、リクエストの処理は（非常に）速くなります。

考えられる検索値ごとに 1 つずつ、16383 個のインデックス ファイルを作成します。入力セット内の値ごとに、セットの先頭のファイル位置を対応するインデックス ファイルに書き込みます。各インデックス ファイルには、同じセットの同じ番号が含まれていることが重要です。これで、各インデックス ファイルはマスター ファイルへの昇順インデックスで構成されます。

検索するには、各検索値に対応するインデックス ファイルの読み取りを開始します。別のファイルから読み取ったインデックスよりも低いインデックスを読み取った場合は、そのインデックスを破棄して別のインデックスを読み取ります。すべてのファイルから同じインデックスを取得した場合、それは一致します。マスター ファイルからセットを取得し、各インデックス ファイルから新しいインデックスを読み取ります。いずれかのインデックス ファイルの最後に到達したら、作業は完了です。

値が均等に分散されている場合、各インデックス ファイルには入力セットの 1/16383 が含まれます。平均的な検索セットが 6 つの値で構成されている場合、元の入力の 6/16383 に対して線形パスを実行することになります。これはまだ O(n) ソリューションですが、n は少し小さくなりました。

追伸ゼロは不可能な結果値ですか、それとも本当に 1638 ですか?4 可能性は？

ブルートフォース + インデックス検索を含むアプローチの悪魔の代弁者を演じているだけです。

  1. セットの要素の min 、 max 、 no を使用してインデックスを作成します。
  2. 次に、max < max (検索対象のセット) および min > min (検索対象のセット) のセットを除外するブルート フォースを適用します。
  3. ブルート フォースでは、検索対象のセットの要素数より少ないセット全体の要素数も除外します。

実際の検索の 95% は、非常に小さいサブセットに対して総当たり攻撃を行うことになります。ちょっとした考え。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top