2010_IBISML01_Tsuda_public.pptx複合ソート法による高速な 全ペア類似度検索 津田 宏治 産総研ＣＢＲＣ / JST ERATO Collaboration with 田部井靖生、清水佳奈、伊東純一、 富井健太郎、杉山将、宇野毅明 17/06/2010 2 全ペア類似度検索 § 近傍グラフ § 半教師つき学習、スペクトラルクラスタリングなどで必要 § ε-近傍グラフの作成問題 § Find all pairs (i,j), i < j, that § 全ペアの距離を計算すると ε アウトライン § ソーティングによって、高速に全ペア類似度検索を行う方法「 複合ソート法」を提案 § ハミング距離に基づく全ペア類似度検索 § コサイン距離に基づく全ペア類似度検索 § 画像、シグナル § 応用例 17/06/2010 3 17/06/2010 4 ハミング距離がｄ以下のペア発見 複合ソート法 (Multiple Sorting
AAAS
