7

私は現在、ユーザーが属性 (年齢、身長、町、学歴など) に基づいて他のユーザーを検索できる Web サイトを開発しています。私は今、ユーザー プロファイル間にある種の評価を実装したいと考えています。評価は、指定された 2 つのプロファイル間の類似性に基づいて、独自のアルゴリズムを介して計算されます。たとえば、ユーザー A は、ユーザー B に対して 85、ユーザー C に対して 79 という評価「一致評価」を持っています。B と C の評価は 94 などです。

ユーザーは特定の属性を検索し、評価によって結果をフィルタリングできる必要があります。

評価はプロファイルごとに異なり、検索を行うユーザーにも依存するため、ユーザー テーブルに単純にフィールドを追加して ORDER BY を使用することはできません。これまでのところ、私は2つの解決策を思いつきました:

  • 私の最初の解決策は、考えられるすべてのユーザーの組み合わせの評価を計算し、それを別のテーブル (user1、user2、rating) に保存する、毎晩のバッチ ジョブを用意することでした。次に、このテーブルをユーザー テーブルと結合し、評価によって結果を並べ替えることができます。いくつかの計算を行った後、このソリューションはそれほどスケーリングしないことがわかりました。

    式 n * (n - 1) / 2 に基づいて、10 人のユーザーに対して 45 通りの組み合わせが可能です。1,000 人のユーザーの場合、突然 499,500 の評価の組み合わせを評価テーブルに挿入する必要があります。

  • 2 番目の解決策は、MySQL をそのままにして、アプリケーション内でオンザフライで評価を計算することでした。これもうまくスケーリングしません。検索で 100 件の結果のみが UI に返される必要があるとします (最高評価が一番上に表示されます)。10.000 人のユーザーがいて、ニューヨークに住んでいるすべてのユーザーを評価別に検索したい場合、ニューヨークに住んでいるすべてのユーザー (3.000 としましょう) をアプリにロードし、アルゴリズムを適用してからのみを返す必要があります。ユーザーへのトップ100。このようにして、DB から 2.900 の役に立たないユーザー オブジェクトをロードし、アルゴリズムで何もせずに CPU を浪費しました。

システムが数千ユーザーを超えてスケ​​ーリングするように、ユーザーが他のすべてのユーザーと個別の評価を持つことができるように、MySQL db または web アプリでこれを設計する方法はありますか?

4

3 に答える 3

3

すべてのユーザーを他のすべてのユーザーと照合する必要がある場合、アルゴリズムは O(N^2) です。

ある種の 1 次元の「メトリック」を利用できる場合は、各ユーザーを単一の合成値に関連付けることができます。しかし、それはむずかしく、不可能かもしれません。

ただし、できることは、プロファイルの変更が必要なユーザーを記録することです(マッチングの基になるパラメーターが変更されるたびに)。その時点で、それらのユーザーのみのテーブルをバッチ再計算できるため、O(N) で作業できます。10000 人のユーザーがいて、再計算が必要なユーザーが 10 人だけの場合、100,000,000 ではなく 100,000 レコードを調べる必要があります。

他の戦略は、比較される可能性が高いレコードに対してのみメインアルゴリズムを実行することです:あなたの例では、「同じ都市」です。または、レコードを更新する場合 (ただし、これには (user_1、user_2、ranking、last_calculated) を保存する必要があります)、ランキングの高いレコード、非常に古いレコード、または計算されていないレコードのみを再計算します。最も低いランクの一致は、変動するほど大きく変化する可能性は低いです。あっという間に頂上へ。

アップデート

問題は、 O(N^2) storage spaceで動作しています。

このスペースを減らす方法は？2つのアプローチが見られると思います。1 つは、マッチ テーブルにまったく情報を入力しないことです。「一致」関数は、厳密で急勾配であるほど意味があります。「良い一致」が 1 万あるということは、一致の意味がほとんどないことを意味します。そのため、User1 がいくつかの重要なデータを変更したときに、User1 の「ノー・ノー」一致の一部が「たぶん」ゾーンに戻った場合に備えて、まだ多くの再計算が必要になります。ただし、ユーザーごとにアクティブな一致のより小さなクリークを保持します。

ストレージは依然として 2 次的に増加しますが、急激ではありません。

もう 1 つの戦略は、一致を再計算することです。次に、どのユーザーが適切に一致する可能性が高いかをすばやく選択するための何らかの方法を開発する必要があります (したがって、JOIN によって取得される行の数を制限します)。マッチ; これには、User1 と User2 の間の一致を、DataUser1 のサブセットである DataUser2 の非常に単純な関数に書き換える必要があります (おそらく補助列を使用します)。

課題は、MySQL の機能を活用し、一部の計算を MySQL エンジンからオフロードすることです。

この目的のために、入力時に (したがって O(k) で) いくつかのデータを空間情報または文字列に「マッピング」し、レーベンシュタイン距離を使用することができます。

1 人のユーザーのストレージは増加しますが、2 次ではなく直線的に増加し、MySQLSPATIALインデックスは非常に効率的です。

于 2012-10-01T20:08:16.900 に答える
2

検索で上位 100 件のベスト マッチのみを返す必要がある場合は、それらを保存しないのはなぜでしょうか? とにかく結果の下端を検索したくないように聞こえるので、それらを計算しないでください。

そうすれば、ストレージ スペースは o(n^2) ではなく o(n) だけになり、更新もそうあるべきです。誰かが最初の 100 件を超えた一致を本当に見たい場合 (そしてあなたが許可したい場合) は、その時点でリアルタイムでクエリを実行するオプションがあります。

于 2012-10-01T20:31:37.857 に答える
0

@Iserniの言うことすべてに同意します。

Web アプリがあり、ユーザーが「ログイン」する必要がある場合、その時点でそのユーザーのランキングを作成し、それらを一時テーブル (または既存のテーブルの行) に格納する機会があるかもしれません。

計算に必要なすべてのデータがメモリに収まる場合、これは妥当な時間 (数秒) で機能します。データベース エンジンは、テーブル全体のスキャンを実行し、すべての評価を作成する必要があります。

これは、ログインしている 1 人のユーザーの場合はかなりうまく機能するはずです。. . しかし、たとえば 1 秒以内に多数のユーザーがログインしている場合、うまくスケーリングすることはできません。

ただし、基本的に、評価は適切にスケーリングされません。結果を得るには、すべてのユーザーとすべてのユーザーを比較する必要があります。これがバッチ (夜間) であろうとリアルタイム (誰かがクエリを持っているとき) であろうと、問題の性質は変わりません。大量のコンピューティング リソースを使用することになり、複数のユーザーが同時にリクエストを行うとボトルネックになります。

于 2012-10-01T20:29:25.273 に答える