拡張擬似木パターンマッチング問題に対するビット並列アルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 2010-09-15
• タイトル: 拡張擬似木パターンマッチング問題に対するビット並列アルゴリズム
• タイトル / 言語: en
• タイトル: Bit-Parallel Algorithms for Extended Pseudo-tree Pattern Matching Problem
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 信州大学工学部
• 著者所属: 長野工業高等専門学校
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Shinshu University
• 著者所属(英): en
• 著者所属(英): Nagano National College of Technology
• 著者名: 山本, 博章; 宮嵜, 敬
• 著者名(英): Hiroaki, Yamamoto; Takashi, Miyazaki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では，無順序木に対し，拡張擬似木パターン照合問題という木パターン照合問題の一種について考える。一般に，木パターン照合問題とは，パターン木 P とターゲット木 T が与えられたとき，T の中で P に一致する部分をすべて見つける問題である。拡張擬似木パターン照合問題は，先祖・子孫関係のみに着目した問題である．この問題は XML データの検索において重要な役割を演じている．我々はこの問題に対し，文字列上のビット並列法を利用した効率的なアルゴリズムを与える。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we are concerned with a special case of the tree pattern matching problem for XML query evaluation, which is called extended pseudo-tree pattern matching problem. This problem focuses on only ancestor-descendant relationship. Then we show efficient bit-parallel algorithms for this pattern matching problem. Our algorithms runs faster than the existing algorithms for pattern trees of small size.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2010-AL-131, 号 4, p. 1-8, 発行日 2010-09-15
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会