| 講演名 | 2013-04-24 マルチトラックデータ上の近似順列パターン照合と索引構造 大田 裕之, 桂 敬史, 成澤 和志, 篠原 歩, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 複数の系列からなるデータをマルチトラックと呼び,マルチトラック上で,各系列の入れ替えを許して行うパターン照合を順列パターン照合と呼ぶ.数値列で表されるトラック長n,トラック数Nのマルチトラックテキストに対し,トラック長m,トラック数Mのマルチトラックパターンが与えられたとき,トラック間のユークリッド距離が閾値以下のとき一致するとみなす近似順列パターン照合問題を考える.本論文では,近似順列パターン照合問題を高速に解くためのデータ構造であるLoFT,およびLoFTを用いた近似順列パターン照合問題に対する確率的パターン照合アルゴリズムを提案する.また,LoFTの性能および精度を実験的に評価する. |
| 抄録(英) | A multi-track data is a multi-set of sequences. The permuted pattern matching problem is, given a multi-track text and a multi-track pattern, to find positions that the pattern occurs. We consider the approximate permuted pattern matching problem on numeric multi-tracks with respect to the Euclidean distance. For the problem, we propose a new indexing structure called LoFT, and construct a probabilistic pattern matching algorithm utilizing LoFT. |
| キーワード(和) | 近似パターン照合 / マルチトラックデータ / 索引構造 / ハッシュ |
| キーワード(英) | approximate pattern matching / multi-track data / index structures / hashing |
| 資料番号 | COMP2013-2 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2013/4/17(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | マルチトラックデータ上の近似順列パターン照合と索引構造 |
| サブタイトル（和） | |
| タイトル（英） | Approximate Permuted Pattern Matching and Indexing Structure for Multi-Track Data |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 近似パターン照合 / approximate pattern matching |
| キーワード(2)（和/英） | マルチトラックデータ / multi-track data |
| キーワード(3)（和/英） | 索引構造 / index structures |
| キーワード(4)（和/英） | ハッシュ / hashing |
| 第 1 著者 氏名（和/英） | 大田 裕之 / Hiroyuki OTA |
| 第 1 著者 所属（和/英） | 東北大学大学院情報科学研究科 Graduate School of Information Science, Tohoku University |
| 第 2 著者 氏名（和/英） | 桂 敬史 / Takashi KATSURA |
| 第 2 著者 所属（和/英） | 東北大学大学院情報科学研究科 Graduate School of Information Science, Tohoku University |
| 第 3 著者 氏名（和/英） | 成澤 和志 / Kazuyuki NARISAWA |
| 第 3 著者 所属（和/英） | 東北大学大学院情報科学研究科 Graduate School of Information Science, Tohoku University |
| 第 4 著者 氏名（和/英） | 篠原 歩 / Ayumi SHINOHARA |
| 第 4 著者 所属（和/英） | 東北大学大学院情報科学研究科 Graduate School of Information Science, Tohoku University |
| 発表年月日 | 2013-04-24 |
| 資料番号 | COMP2013-2 |
| 巻番号（vol） | vol.113 |
| 号番号（no） | 14 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |