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: float score

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

message id_with_score {
  0: string id
  1: float 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 リストを返す。