講演抄録/キーワード |
講演名 |
2013-04-24 10:35
マルチトラックデータ上の近似順列パターン照合と索引構造 大田裕之・○桂 敬史・成澤和志・篠原 歩(東北大) COMP2013-2 |
抄録 |
(和) |
複数の系列からなるデータをマルチトラックと呼び,マルチトラック上で,各系列の入れ替えを許して行うパターン照合を順列パターン照合と呼ぶ.
数値列で表されるトラック長$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 / / / / |
文献情報 |
信学技報, vol. 113, no. 14, COMP2013-2, pp. 9-16, 2013年4月. |
資料番号 |
COMP2013-2 |
発行日 |
2013-04-17 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2013-2 |