| 講演名 | 2017-05-12 集合間類似度を用いたストリームデータのtop-k類似検索に対する高速な厳密解アルゴリズム 山崎 智博(電通大), 古賀 久志(電通大), 戸田 貴久(電通大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | ストリームデータの類似検索は，正常/異常検出や情報推薦の基盤となる技術として注目されている．本研究では，データストリームの直近の要素集合をクエリとし，データベースから最も類似する$k$個のデータを検索する問題を取り扱う．本問題に対してはこれまで，現在の時刻で上位$k$位に入る可能性があるデータを過去に計算した類似度から決定し，それらに対してのみ類似度を計算する枝刈りによる厳密解アルゴリズムが提案されている．これに対して本研究では，既存手法より大幅に実行時間を短縮する高速な厳密解アルゴリズムを提案する．提案手法は，頻度を考慮した転置インデックスを用いて現在時刻と次の時刻で類似度が変わるデータを効率的に特定し，それらに対してのみ，類似度を更新することで類似度の計算回数を減らす．さらに，類似度も$O(1)$で更新することで処理時間を短縮する． |
| 抄録(英) | |
| キーワード(和) | ストリームデータ / 類似検索 / 転置インデックス |
| キーワード(英) | |
| 資料番号 | COMP2017-1 |
| 発行日 | 2017-05-05 (COMP) |
| 研究会情報 | |
| 研究会 | COMP / IPSJ-AL |
|---|---|
| 開催期間 | 2017/5/12(から2日開催) |
| 開催地（和） | 長崎県建設工業協同組合 |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | 伊藤 大雄(電通大) / 堀山 貴史(埼玉大) |
| 委員長氏名（英） | Hiro Ito(Univ. of Electro-Comm.) / 堀山 貴史(埼玉大) |
| 副委員長氏名（和） | 宇野 裕之(阪府大) |
| 副委員長氏名（英） | Yushi Uno(Osaka Pref. Univ.) |
| 幹事氏名（和） | 脊戸 和寿(成蹊大) / 斎藤 寿樹(九工大) / 岡本 吉央(電通大) / 川原 純(NAIST) / 河村 彰星(東大) |
| 幹事氏名（英） | Kazuhisa Seto(Seikei Univ.) / Toshiki Saito(Kyushu Inst. of Tech.) / 岡本 吉央(電通大) / 川原 純(NAIST) / 河村 彰星(東大) |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Theoretical Foundations of Computing / Special Interest Group on Algorithms |
|---|---|
| 本文の言語 | JPN-ONLY |
| タイトル（和） | 集合間類似度を用いたストリームデータのtop-k類似検索に対する高速な厳密解アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ストリームデータ |
| キーワード(2)（和/英） | 類似検索 |
| キーワード(3)（和/英） | 転置インデックス |
| 第 1 著者 氏名（和/英） | 山崎 智博 / Tomohiro Yamazaki |
| 第 1 著者 所属（和/英） | 電気通信大学(略称：電通大) The University of Electro-Communications(略称：UEC) |
| 第 2 著者 氏名（和/英） | 古賀 久志 / Hisashi Koga |
| 第 2 著者 所属（和/英） | 電気通信大学(略称：電通大) The University of Electro-Communications(略称：UEC) |
| 第 3 著者 氏名（和/英） | 戸田 貴久 / Takahisa Toda |
| 第 3 著者 所属（和/英） | 電気通信大学(略称：電通大) The University of Electro-Communications(略称：UEC) |
| 発表年月日 | 2017-05-12 |
| 資料番号 | COMP2017-1 |
| 巻番号（vol） | vol.117 |
| 号番号（no） | COMP-28 |
| ページ範囲 | pp.1-8(COMP), |
| ページ数 | 8 |
| 発行日 | 2017-05-05 (COMP) |