3

特定のアルゴリズムを、RavenDB/CouchDB が使用する種類の map-reduce インデックス、つまり「事前計算済み」map-reduce に変換できるかどうかを確認しようとしています (つまり、インデックスは挿入時ではなく更新時に更新されます)。実際のクエリを実行します)。

カテゴリ別にグループ化された 50,000 の商品を扱う典型的なオンライン ストアがあるとします。すべての製品には、「[赤、丸、金属]」のような「属性値」のコレクションがあります。

ウェブサイトには非常に多くの製品があり、おそらく各カテゴリには多くのアイテムがあるため、ユーザーが現在表示している製品を「フィルタリング」する別の方法をユーザーに提供したいと考えています.

たとえば、カテゴリが「20 ドル未満」の場合、このカテゴリにはたくさんの製品があります。しかし、私たちのユーザーは、20 ドル未満の赤の製品だけを表示する必要があります。残念ながら、「20 ドル未満」カテゴリには「赤」というサブカテゴリはありません。

私たちのアルゴリズムは、製品の現在のリストを取得し、「興味深い」属性と属性値のリストを生成します。つまり、製品のリストが与えられると、次のように出力されます。

Color
   Red (40)
   Blue (32)
   Yellow (17)
Material
   Metal (37)
   Plastic (36)
   Wood (23)
Shape
   Square (56)
   Round (17)
   Cylinder (12)

この種のアルゴリズムは、RavenDB/CouchDB の map-reduce インデックスで何らかの方法で事前に計算できますか? そうでない場合は、なぜ正確に (将来その種のアルゴリズムを特定できるようにするため)、そうである場合はどのように?

C # 4.0 Visual Studio テスト ソリューションが利用可能で、潜在的なデータ構造とサンプル データを示し、map-reduce の実装を試してみることもできます (これは事前計算可能ではないようです)。

4

2 に答える 2

2

一般的なケース: CouchDB スタイルの map-reduce ビューを使用することは常に可能ですが、必ずしも実用的ではありません。

結局のところ、それはほとんどカウントベースの議論です: 500,000 製品のサブセットについて質問する必要がある場合、データベースは 2 500,000の異なる可能な質問のそれぞれに対して明確な回答を提供できなければなりません。それらのすべてに対して B ツリー リーフを発行する必要がある場合 (および、これらのクエリのほとんどに対する答えがゼロ、false、空のセット、または同様の null 値でない限り、データを発行する必要がある場合) は、法外な量のメモリが必要になります)。

CouchDB は、範囲クエリの存在を通じて、最初の小さな最適化を提供します (つまり、理想的なケースでは、N 2個の質問に答えるために、N 個の B ツリー リーフを使用できます)。ただし、あなたの例では、これは葉の数を 2 250,000まで減らすだけです (これは理論上の下限です)。

CouchDB は、キー プレフィックス クエリによる 2 つ目の小さな最適化を提供します。つまり、[A]、[A,B]、および [A,B,C] クエリを単一の [A,B,C] キーに圧縮できます。したがって、2 250,000 の可能性ではなく、「単なる」2 249,999にまで落ち込んでいます...

したがって、任意のサブセットの質問に答えるために放出戦略を考えることができますが、それは私たちの惑星で実際に利用できるよりも多くのストレージスペースを必要とします. 一般に、N 個の異なる質問に答えるには、少なくともsqrt(N/2)B ツリーの葉を発行する必要があるため、質問を数えて、葉の数の下限が許容できるかどうかを判断します。

カテゴリとサブカテゴリのみ: 製品の任意のリストをあきらめて、「属性 B と C でフィルター処理されたカテゴリ A の重要な属性を教えてください」という形式の質問のみを行うと、放出数は次のように減少します。

 AvgCategories * AvgAttr * 2 ^ (AvgAttr - 1) * 500,000

基本的に、製品ごと[Category,Attr,Attr,...]に、製品のすべてのカテゴリと製品の属性のすべての組み合わせのキーを発行しているため、カテゴリ + 属性でクエリを実行できます。商品ごとに平均して 1 つのカテゴリと 3 つの属性がある場合、これは約 600 万のエントリに相当し、かなり許容範囲内です。

于 2010-11-26T12:29:05.723 に答える
0

これは、CouchDB のようなものに実装するのは非常に簡単です。インデックスの map フェーズで、オブジェクトが持つ属性ごとに 1 つのキーと値のペアを出力します。値は単に「1」です。次に、reduce フェーズですべての入力値を合計し、合計を出力します。最終結果は、記述した形式のインデックスになります。

于 2010-11-25T23:29:24.023 に答える