3

次の 2 つのテーブルを含む SQLite データベースがあります。

Objects:
  object_id int,
  name varchar(50)

Values:
  key char(12),
  value int,
  object_id int

ご覧のとおり、各オブジェクトにはキーと値のペアのリストが含まれています。このリストには通常、10 ～ 60 のエントリが含まれます。(key, object_id) の組み合わせは、値テーブル内で一意です。

次に、ユーザーからキーと値のペアのリストを取得し、データベースで最も類似したオブジェクトを検索します。ユーザーが提供したオブジェクトは、ほとんどの場合、データベース内のオブジェクトと直接一致しません。

類似性とは、両方のオブジェクトのキーのリストがほぼ等しく、それらのキーの値が類似していることを意味します (ほとんどの場合、値も等しくありません)。リストは可変長にすることができます。

次のリストを検討してください。

A = { a: 10, b: 20, c: 30 }
B = { a: 11, c: 80, d: 90 }
C = { c: 70, d: 89, e: 40, f: 100 }
D = { c: 65, d: 80, e: 41 }

A と B の両方にキーaとcが含まれていますが、bとdはそのうちの 1 つにのみ含まれています。したがって、キーだけを見ると、類似度は 0.5 になります。A と D にはcのみが共通しており、 a、b、d、およびeは 1 つのリストにのみ含まれています。したがって、それらはあまり似ていません。

次のステップでは、一致するキーの値を探す必要があります。したがって、A と B の例では、キーaとcの値を比較する必要があります。aはよく似ていますが、 cはあまりよく一致しません。

そのような検索を SQLite で直接行うことは可能ですか? そうでない場合、検索を行うための最良の方法/アルゴリズムは何ですか? 検索はできるだけ高速にする必要がありますが、モバイル デバイスでこれを行っているため、計算能力やメモリを消費しすぎてはいけません。

このトピックに関するヘルプ、リンク、またはリソースをいただければ幸いです。

4

1 に答える 1

1

正しく取得できれば、すべてのレコードをユーザー入力からの固定レコードセットと比較する必要があります（たとえば、Values）=> O（n * m 1 * m 2） （n =オブジェクトの数、n * m 1 =値のレコード数、m 2 =ユーザー入力のキー）-m 1、2が定数係数の場合、基本的にO（n） ：

select
  v1.object_id,
  count(distinct v1.key) cnt_obj_keys,
  count(distinct v2.key) cnt_usr_keys, --replace with a constant from outside code
  count(case
          when v1.key = v2.key
          then 1
        end) cnt_similar_keys,
  count(case
          when v1.key = v2.key and v1.value = v2.value
          then 1
        end) cnt_similar_values
from values v1
cross join values_from_user v2
group by v1.object_id
;

次に、各オブジェクトの式、つまりO（n）を使用して、オブジェクトの並べ替えと最初のオブジェクトのフェッチに使用される未指定のインデックスを計算する必要がありxます。例：

order by
  cnt_similar_keys / (cnt_obj_keys + cnt_usr_keys - cnt_similar_keys),
  cnt_similar_values / cnt_similar_keys
于 2012-11-29T12:49:50.067 に答える