5

(x,y)データセットを構成する64ビット整数のタプルのコレクションがあります。たとえば、これらのタプルは何兆もあります。地球上のどのマシンでも、データセットをメモリに保持することは不可能です。ただし、それらをディスクに保存することは非常に合理的です。

私はディスク上のストア（B +ツリー）を持っており、単一のディメンションでデータをすばやく同時にクエリできます。ただし、私のクエリの一部は両方のディメンションに依存しています。

クエリの例：

  • x与えられた値以上のタプルを見つけます
  • x可能な限り小さいタプルを見つけます。それyは、特定の値以上です。
  • x可能な限り小さいタプルを見つけます。それyは、特定の値以下です。
  • 保守操作を実行します（タプルを挿入し、タプルを削除します）

私が見つけた最善の策はZ階数曲線ですが、2次元データセットが与えられた場合にクエリを実行する方法を理解できないようです。

受け入れられない解決策には、データの順次スキャンが含まれます。これは遅すぎる可能性があります。

4

4 に答える 4

2

要件に最も適したデータ構造は、R ツリーとそのバリアント (R* ツリー、R+ ツリー、ヒルベルト R ツリー) であると思います。R-tree は B+-tree に似ていますが、多次元クエリも可能です。

他の関連するデータ構造は Priority Search Tree です。例 1 .. 3 のようなクエリには適していますが、頻繁な更新やディスク上のストアが必要な場合はあまり効率的ではありません。詳細については、この論文または本「Handbook of Data Structures and Applications」 (第 18.5 章) を参照してください。

于 2012-09-21T08:17:46.983 に答える
0

私は現在、多次元データ用の本質的に「積み上げられた」B+ ツリー (またはdが次元数であるd + ツリー) であるデータ構造の設計に取り組んでいます。私はそれがあなたのデータに完全に合うと信じており、あなたのユースケースのために特別に設計されています.

基本的な考え方は次のとおりです。

各次元は B+ ツリーであり、次の次元の B+ ツリーにリンクされています。通常、最初の次元を検索します。リーフに到達すると、次の次元に属する次の B+ ツリーのルートへのポインターが含まれます。x2 番目の B+ ツリーのすべてが同じ値に属します。

元の計画では、各ディメンションの一意の値とそのカウントのみを格納することでした。これは、非常に単純な圧縮アルゴリズム (それと呼べる場合) を採用しながら、データ セット全体を表現できるようにします。この「リンクされた」ディメンション スキームでは、B+ ツリーのスタックに単純に追加されるだけなので、追加のディメンションを後で追加できます。

2 つのディメンションの合計挿入/検索/削除時間は、次のようになります。

log b(card(x)) + log b(card(y))

ここで、bは各 B+ ツリーのベースであり、card(x)はx次元のカーディナリティです。

それが理にかなっていることを願っています。私はまだ実装に取り​​組んでいますが、アイデアを自由に使用したり、拡張したりしてください。

于 2013-01-28T03:21:51.533 に答える
0

Z オーダー カーブをクエリする方法がわからないということですか? ウィキペディアのページでは、範囲検索の方法について説明しています。

Z カーブは空間をネストされた長方形に分割し、キーの追加ビットごとに空間を半分に分割します。ポイントを検索するには:

Start with the largest rectangle that might contain your point.

    Recursively:

        Create a result set of rectangles    

    For each rectangle in your set        
        If the rectangle is a single point, you are done, it is what you are looking for.
        Otherwise, divide the rectangle in two (specify one additional bit of the z-curve)
            If both halves contain a point
                If one half is better 
                    Add that rectangle to your result set of rectangles
                Otherwise
                    Add both rectangles to your result set of rectangles
            Otherwise, only one half contains a point
                    Add that rectangle to your result set of rectangles

    Search your result set of rectangles

もちろん、最悪の場合のパフォーマンスは悪くなります。z オーダー インデックスの作成方法を変更することで調整できます。

于 2012-09-20T23:09:23.803 に答える
0

http://fallabs.com/tokyocabinet/

Tokyo Cabinet は、データベースを管理するためのルーチンのライブラリです。データベースはレコードを含む単純なデータ ファイルであり、各レコードはキーと値のペアです。すべてのキーと値は、可変長のシリアル バイトです。キーと値には、バイナリデータと文字列の両方を使用できます。データ テーブルやデータ型の概念はありません。レコードは、ハッシュ テーブル、B+ ツリー、または固定長配列で編成されます。

Tokyo CabinetはC言語で書かれており、C、Perl、Ruby、Java、LuaのAPIとして提供されています。Tokyo Cabinet は、C99 および POSIX に準拠した API を持つプラットフォームで利用できます。Tokyo Cabinet は、GNU Lesser General Public License の下でライセンスされているフリー ソフトウェアです。

埋め込むのは簡単ですか？

于 2013-09-16T04:16:57.073 に答える