著者
伝住 周平 有村 博紀 定兼 邦彦
出版者
一般社団法人電子情報通信学会
雑誌
電子情報通信学会誌 = The journal of the Institute of Electronics, Information and Communication Engineers (ISSN:09135693)
巻号頁・発行日
vol.97, no.12, pp.1080-1085, 2014-12

大規模な文字列データの操作は,文字列処理の分野で最も重要な課題の一つである.本稿では,文字列集合をコンパクトに圧縮し様々な操作を可能とする系列二分決定グラフ(系列BDD,SeqBDD)を紹介し,関連するパターン照合技術について紹介する.この系列BDDは,文字列データに拡張したZDDの一種であるが,同時に,従来から自然言語処理や文字列処理分野で研究されてきたトライや,有限オートマトン,接尾辞グラフなどのテキスト索引のためのデータ構造とも密接な関連を持つ.これら既存のデータ構造との関係や,近年発展が著しい簡潔データ構造と関連した話題についても述べる.
著者
浅井 達哉 有村 博紀
出版者
一般社団法人電子情報通信学会
雑誌
電子情報通信学会論文誌. D-I, 情報・システム, I-情報処理 (ISSN:09151915)
巻号頁・発行日
vol.87, no.2, pp.79-96, 2004-02-01
被引用文献数
15 or 0

最近,ウェブページやXMLデータなどの半構造データに対するデークマイニングが注目を集めている.本論文では,半構造データマイニングにおける主要な技術の一つである,グラフ構造データからの部分構造パターン発見技法について,主に木パターンマイニングとグラフマイニングの観点から,近年の研究動向を紹介する.はじめに,半構造データマイニングの萌芽期の研究として,Subdue及び,GBI,Nestrovらのスキーマ発見,DehaspeらのWarmrを紹介する.次に,木パターンとグラフパターンのマイニングに関する現在の研究動向を概観する.木パターンの発見アルゴリズムとして,浅井らのFREQTとUNOT,ZakiのTreeMiner.安部らのOPTTなどを説明し,一般のグラフマイニングアルゴリズムとして,猪口らのAGMとYanらのgSpanなどを説明する.最後に,新しいデークマイニングの方向性を示すものとして,半構造データストリームからのマイニングアルゴリズムStreamTについて述べる.
著者
有村 博紀 宇野 毅明 湊 真一 平田 耕一 伊藤 公人 下薗 真一 喜田 拓也
出版者
北海道大学
雑誌
基盤研究(A)
巻号頁・発行日
2012-04-01 (Released:2013-05-15)

本研究では,実世界と情報世界が融合した巨大な情報空間から有用な知識を効率よくとりだすための大規模半構造マイニング技術の確立を目指す.とくに,大規模規模知識基盤形成システムのための基礎技術として,超高速半構造マイニングエンジンと,時空間情報を用いた半構造マイニング技術の研究開発,周辺技術として,確率的情報スキーマの導入と,知識連係技術と知識索引技術の研究開発を行った.開発した技術の実装と最適化によりプロトタイプシステムの構築を行った.
著者
金田 悠作 吉澤 真吾 湊 真一 有村 博紀 宮永 喜一
出版者
一般社団法人電子情報通信学会
雑誌
電子情報通信学会技術研究報告. VLD, VLSI設計技術 (ISSN:09135685)
巻号頁・発行日
vol.109, no.393, pp.131-136, 2010-01-19

本稿では,重要なデータストリーム処理問題の一つである正規表現パターン照合に対して,ビット並列型パターン照合手法に基づいた高速なハードウェア指向アルゴリズムを提案する.並列ビット分配と呼ぶ新しいビット並列手法を用いて,文字と,連接,和,Kleeneプラスから構成させる非消去的正規表現のクラスに対して,O(mdlogb+m|Σ|)前処理時間とO(mdlogb/w+m|Σ|/w)領域を用いて,O(mdlogb/w)領域の高速なアルゴリズムを与える.ここで,nは入力長を表わし,mとd,bは,それぞれ,パターンの長さと,深さ,最大戻り幅を,wは計算機のワード長,|Σ|はアルファベットの要素数を表わす.さらに,このアルゴリズムを用いて,回路の再構成を伴わずにパターンの変更を可能なハードウェア実装のアーキテクチャをしめす.
著者
有村 博紀 喜田 拓也
出版者
情報処理学会
雑誌
情報処理 (ISSN:04478053)
巻号頁・発行日
vol.46, no.1, pp.4-11, 2005-01-15
参考文献数
13
被引用文献数
6 or 0

大量の電子化データの流れであるデータストリームから,有用な情報を少ない資源で効率よく取り出すためのストリームマイニング技術を概観する.まず,データストリームの特徴と,データマイニングの目的について整理し,限定された計算資源を用いて無限に続くデータストリームからマイニングを行うためのシステムに要求される性質について議論する.次に,さまざまな要約データ構造とオンライン化技術についてまとめ,最近の研究のうち特色のあるものを紹介する.
著者
有村 博紀 喜田 拓也
出版者
情報処理学会
雑誌
情報処理 (ISSN:04478053)
巻号頁・発行日
vol.46, no.1, pp.4-11, 2005-01

大量の電子化データの流れであるデータストリームから,有用な情報を少ない資源で効率よく取り出すためのストリームマイニング技術を概観する.まず,データストリームの特徴と,データマイニングの目的について整理し,限定された計算資源を用いて無限に続くデータストリームからマイニングを行うためのシステムに要求される性質について議論する.次に,さまざまな要約データ構造とオンライン化技術についてまとめ,最近の研究のうち特色のあるものを紹介する.
著者
大濱 郁 喜田 拓也 有村 博紀 阿部 敏久
出版者
一般社団法人電子情報通信学会
雑誌
電子情報通信学会技術研究報告. IBISML, 情報論的学習理論と機械学習 (ISSN:09135685)
巻号頁・発行日
vol.110, no.476, pp.9-16, 2011-03-21

我々は,人間行動履歴の地理的クラスタリングについて議論する.本論文では,この問題を,二次元時系列データのセグメンテーション問題として定式化し,二つのクラスタリング手法,LS-linHMMとX-linHMMを提案する.前者のLS-linHMMは,線形制約付きHMMを用いたクラスタリングと情報量規準を用いたモデル選択を組み合わせ,クラスタ数の自動推定を行う.また,X-linHMMは,x-meansのアイデアを取り入れた2状態線形HMMによる階層的クラスタリングであり,LS-linHMMよりも高速なクラスタリングを実現している.今回,これらの手法を,GPSタグ付き写真コンテンツのクラスタリングに適用することを試みる.また,実データを用いた実験により,単純なx-meansよりも提案手法が効果的に動作することを確認した.
著者
安積 裕樹 川副 真治 安部 潤一郎 有村 博紀 有川 節夫
出版者
一般社団法人情報処理学会
雑誌
情報処理学会論文誌数理モデル化と応用(TOM) (ISSN:18827780)
巻号頁・発行日
vol.42, no.14, pp.14-24, 2001-12-15

本稿では,分散記憶型並列計算機上での効率の良い全文索引構築法について考察する.接尾辞配列は,最近提案された高機能全文索引であり,情報検索や遺伝子情報などに広い応用を持つ.本稿では,分散記憶型並列計算機上での効率の良い接尾辞配列構築法を提案する.Baeza-Yates-Gonnet-Sinder(BGS )アルゴリズムは,最も広く使われている外部記憶上の構築アルゴリズムである.このBGSアルゴリズムを並列化し,効率の良い並列構築アルゴリズムを与える.このアルゴリズムは,並列計算機時間と通信量に関して,BGS の最適な並列化になっており,従来からあるBGS の並列版のRiberio-Kitajima-Ziviani (RKZ )アルゴリズムに比べてより高速である.In this paper,we study efficient parallel construction of full-text indexing structures for large text data.The suffix array is a compact full-text indexing structure that is useful in information retrieval and bio-informatics.We propose an efficient parallel algorithm for constructing suffix arrays on distributed memory parallel computers.This algorithm is a parallel implementation of the well-known external memory algorithm,called Baeza-Yates-Gonnet-Sinder (BGS)algorithm.By theoretical analysis,we show that our algorithm runs more efficiently than Riberio-Kitajima-Ziviani (RKZ) algorithm,another parallel implementation of the BGS algorithm,in terms of parallel time and communication complexities.