2

リレーショナルデータベースに保存されているテキストドキュメントの大規模な（300〜500k）コレクションがあるとします。各ドキュメントは、1つ以上（最大6つ）のカテゴリに属する​​ことができます。StumbleUponの動作のように、単一のエンティティが繰り返されないように、ユーザーが特定のカテゴリのドキュメントをランダムに選択できるようにする必要があります。

大量のユーザーとドキュメントを使用する低速のNOTINクエリを使用してこれを実装する方法が実際にはわかりません。そのため、この目的のためにカスタムデータ構造を実装する必要があるかもしれないと考えました。おそらく、私のニーズに適応する可能性のあるいくつかのアルゴリズムを説明する論文がすでにありますか？

現在、私は次のアプローチを検討しています。

  • データベースからすべてのエントリを読み取ります
  • このカテゴリに属する​​ドキュメントのIDから、カテゴリごとにリンクリストベースのインデックスを作成します。シャッフルする
  • 特定のユーザーが表示したすべてのエントリを含むブルームフィルターを作成します
  • イテレータを使用してインデックスをトラバースし、ブルームフィルタを使用してアイテムをランダムに選択し、表示されていないアイテムを選択します。
4

7 に答える 7

2

ユーザーがランダムなエントリを取得する方法によって異なります。

オプション1：

ユーザーがいくつかのエンティティをページングしていて、それらのいくつかの後で停止します。たとえば、ユーザーは現在のランダムなエンティティを見て、次のエンティティに移動し、それを読んで数回続けます。それだけです。次にこのユーザー (または別のユーザー) がこのカテゴリからエンティティを取得すると、既に表示されているエンティティは明確になり、既に表示されているエンティティを返すことができます。

そのオプションでは、既に表示されているエンティティ ID の (ハッシュ) セットを保存し、ユーザーがランダムなエンティティを要求するたびに、DB からランダムに選択し、まだセットにないかどうかを確認することをお勧めします。

セットが非常に小さく、データが非常に大きいため、既に表示された ID を取得する可能性は非常に低く、ほとんどの場合 O(1) かかります。

オプション 2:

ユーザーはエンティティでページングしており、表示されたエンティティはすべてのユーザー間で保存され、ユーザーがページにアクセスするたびに保存されます。その場合、おそらく各カテゴリのすべてのエンティティを使用し、表示されたすべてのエンティティを保存して、エンティティが表示されているかどうかを確認するには、しばらく時間がかかります。

そのオプションでは、このトピックのすべての ID を取得します。それらをシャッフルして、リンクされたリストに保存します。ランダムに表示されていないエンティティを取得する場合は、リストの先頭を取得して削除します (O(1))。

于 2012-07-16T08:29:10.730 に答える
2

ユーザーが見たエントリをテーブルを介して追跡する場合...これを試してください。mysql を使用するのは、それが私が考えることができる最も簡単な例だからですが、要点は明確なはずです。

「使用中」のリンクについて...

insert into viewed (userid, url_id) values ("jj", 123)

リンクを探していると...

select p.url_id
from pages p left join viewed v on v.url_id = p.url_id
where v.url_id is null
order by rand()
limit 1

これにより、データベースは先に進み、1 対 1 の結合を実行し、クエリを制限して、ユーザーがまだ見ていないエントリを 1 つだけ返すようにします。

ただの提案です。

編集: この 1 つの操作を実行することは可能ですが、URL がユーザーに正常に渡されるという保証はありません。

于 2012-07-21T00:48:59.637 に答える
1

私は過去に、Apache Luceneを使用してリレーショナルデータベースをドキュメント指向の形式にインデックス付けすることで、同様の問題を解決しました。これは最近のNoSQLサーバーの登場前であり、基本的に同じことですが、それでも有効な代替アプローチです。

textId（リレーショナルデータベースID）フィールドと複数値のcategoryIdおよびuserIdフィールドを使用して、テキストごとにLuceneドキュメントを作成します。categoryIdフィールドに適切に入力します。ユーザーがテキストを読むときは、ユーザーIDをuserIdフィールドに追加します。単純なクエリは、指定されたcategoryIdを持ち、指定されたuserIdを持たないドキュメントのセットを返します。ランダムに1つを選択して、それを表示します。

于 2012-07-19T11:20:05.800 に答える
1

Apache Cassandra のような nosql ソリューションを検討することをお勧めします。これらはあなたのニーズに理想的に合っているようです。新しい列をその場でテーブル (列ファミリー) に簡単に追加できる環境で必要なアルゴリズムを設計するには、多くの方法があり、データが非常にまばらなテーブルを優れたサポートを提供します。

編集：以下の多くの可能な解決策の1つ：

  1. カテゴリごとにCF（列ファミリー、つまりテーブル）を作成します（これらをオンザフライで作成するのは非常に簡単です）。
  2. カテゴリに属する​​ドキュメントごとに、各カテゴリ CF に行を追加します。
  3. ユーザーがドキュメントにヒットするたびに、名前付きの列を追加し、それを行に true に設定します。明らかに、このテーブルは数百万の列で巨大になり、おそらく非常にまばらに入力されますが、問題はありません。これを読むことは依然として一定の時間です。
  4. カテゴリ内のユーザーの新しいドキュメントを見つけるには、select * where == null の結果を選択するだけです。

Cassandra の「結果整合性」モデルを受け入れることができれば、一定時間の書き込みと読み取り、驚くべきスケーラビリティなどを得ることができます (つまり、ユーザーが重複したドキュメントを取得しないことはミッション クリティカルではありません)。

于 2012-07-17T15:21:43.027 に答える
1

特定の <user, category> ペアについて、表示されるドキュメントの数は、そのカテゴリで利用可能なドキュメントの総数に比べてかなり少ないと思います。

では、どのドキュメントが表示されたかを示すインデックス付きトリプル <user, category, document> を保存し、ランダムに選択されたドキュメントに関して楽観的なアプローチを取ることができますか? ほとんどの場合、ランダムに選択されたドキュメントはユーザーに読まれません。また、トリプルには索引が付けられているため、すぐに確認できます。

于 2012-07-16T08:30:04.893 に答える
1

私は疑似ランダムアプローチを選択します：

1.) 表示するカテゴリ内の要素の数を決定します (SELECT COUNT(*) WHERE ...)
2.) 範囲 1 ... count の乱数を選択します。
3.) 単一のドキュメントを選択します (SELECT * FROM ... WHERE [数えるときと同じ] ORDER BY [安定した順序を生成する]。使用されている SQL ダイアレクトに応じて、一部のみを取得するために使用できるさまざまな句があります。必要な結果セットの (MySQL LIMIT 句、SQLServer TOP 句など)

ドキュメントの数が多い場合、同じユーザーに同じドキュメントを 2 回提供する可能性はごくわずかです。上記のスキームを使用すると、状態情報を保存する必要はまったくありません。

于 2012-07-16T14:44:13.680 に答える
0
  1. X 選択を過ぎたユーザーを Cookie などに保存します。
  2. ユーザーの新しい基準で最後の選択をサーバーに返します
  3. ユーザーの最後の X 選択のメンバーでなくなるまで、基準を満たすテキストの 1 つをランダムに選択します。
  4. このテキストの選択を返し、最後の X 選択のリストを更新します。

X の最適な値を見つけるために実験しますが、たとえば 16 の X のようなものを念頭に置いていますか?

于 2012-07-20T21:52:33.233 に答える