Nearest Neighbor¶

詳細な仕様は IDL 定義を参照してください。
使用されているアルゴリズムの詳細についてはアルゴリズムを参照してください。

Configuration¶

設定は単体の JSON で与えられる。 JSON の各フィールドは以下のとおりである。

method

近傍探索に使用するアルゴリズムを指定する。以下のアルゴリズムを指定できる。

設定値	類似度尺度
`"lsh"`	コサイン類似度のLocality Sensitive Hashingを利用する。
`"minhash"`	MinHashを利用する。 [Ping2010]
`"euclid_lsh"`	コサイン類似度のLSHを用いてユークリッド距離での近傍探索を行う。

parameter

アルゴリズムに渡すパラメータを指定する。 method に応じて渡すパラメータは異なる。

共通

threads:

乱数生成や探索を行うスレッド数を指定する。この値を大きくすると、ハッシュ生成や探索において、データを分割しマルチスレッドで並列処理するためレイテンシが小さくなる。負の値を指定した場合は実行する環境の論理CPUコア数が利用される。実行環境の論理CPUコア数よりも大きい値を指定した場合、スレッドは論理CPUコア数分しか起動しないが、データは threads 数に分割され先に処理が終わったスレッドが処理する

本パラメータは0.9.0から利用できる。

本パラメータに値を設定したときの挙動は以下の通りである (Integer)

threads < 0
- threads に論理CPUコア数が設定され場合と同様の挙動になる
threads = 0
- threads に1を設定した場合と同様の挙動になる
1 <= threads <= 論理CPUコア数
- 指定した値のスレッド数の生成、データ分割が行われる
論理CPUコア数 < threads
- 論理CPUコア数分のスレッドが起動する。ただし、データは threads 数に分割される

なお、threads は後方互換性を確保するため省略可能である。省略した場合は従来と同様に1スレッドで動作する

lsh

hash_num:

ハッシュのビット数を指定する。大きくすると正確な値に近づく代わりに、多くのメモリを消費し、探索時間も増す。 (Integer)

値域: 1 <= hash_num

minhash

hash_num:

ハッシュのビット数を指定する。大きくすると正確な値に近づく代わりに、多くのメモリを消費し、探索時間も増す。 (Integer)

値域: 1 <= hash_num

euclid_lsh

hash_num:

ハッシュの個数を指定する。大きくすると正確な値に近づく代わりに、多くのメモリを消費し、探索時間も増す。 (Integer)

値域: 1 <= hash_num

converter: 特徴変換の設定を指定する。フォーマットはデータ変換で説明する。

例:

{
  "method": "lsh",
  "parameter" : {
    "hash_num" : 64
  },
  "converter" : {
    "string_filter_types": {},
    "string_filter_rules":[],
    "num_filter_types": {},
    "num_filter_rules": [],
    "string_types": {},
    "string_rules":[
      {"key" : "*", "type" : "str", "sample_weight":"bin", "global_weight" : "bin"}
    ],
    "num_types": {},
    "num_rules": [
      {"key" : "*", "type" : "num"}
    ]
  }
}

Data Structures¶

message id_with_score¶

スコア付きのデータIDを表す。

0: string id¶: データのIDを表す。

1: double score¶: IDに対して紐付かれた近傍性のスコアを表す。近傍性の値が大きいほど、よりお互いの近傍性が高いことを意味する。

message id_with_score {
  0: string id
  1: double score
}

Methods¶

service nearest_neighbor¶

bool set_row(0: string id, 1: datum d)¶

パラメータ:	id -- 行 ID d -- 行に対応する `datum`
戻り値:	モデルの更新に成功した場合 True

行 ID id のデータを d を利用して更新する。同じ id を持つ行が既に存在する場合は、その行が d で上書きされる。 recommender の場合と異なり差分更新ではない。更新操作を受け付けたサーバが当該行を持つサーバと同一であれば、操作は即時反映される。異なるサーバであれば、mix 後に反映される。

list<id_with_score> neighbor_row_from_id(0: string id, 1: uint size)¶

パラメータ:	id -- 近傍探索テーブル内の行を表す ID size -- 返す近傍点の個数
戻り値:	`id` で指定した近傍の id とその距離の値のリスト

指定した行 id に近い行とその距離のリストを (最大で) size 個返す。

list<id_with_score> neighbor_row_from_datum(0: datum query, 1: uint size)¶

パラメータ:	query -- 近傍探索の対象となる `datum` size -- 返す近傍点の個数
戻り値:	`query` の近傍の id とその距離の値のリスト

指定した query に近い datum を持つ行とその query との距離のリストを (最大で) size 個返す。

list<id_with_score> similar_row_from_id(0: string id, 1: uint ret_num)¶

パラメータ:	id -- 近傍探索テーブル内の行を表す ID ret_num -- 返す近傍点の個数
戻り値:	`id` で指定した近傍の id とその類似度の値のリスト

指定した行 id に近い行とその類似度のリストを (最大で) ret_num 個返す。

list<id_with_score> similar_row_from_datum(0: datum query, 1: uint ret_num)¶

パラメータ:	query -- 近傍探索の対象となる `datum` ret_num -- 返す近傍点の個数
戻り値:	`query` の近傍の id とその類似度の値のリスト

指定した query に近い datum を持つ行とその query との類似度のリストを (最大で) ret_num 個返す。

list<string> get_all_rows()¶

戻り値:	すべての行の ID リスト

すべての行の ID リストを返す。