喜田 拓也

J-GLOBALへ         更新日: 18/10/01 16:37
 
アバター
研究者氏名
喜田 拓也
 
キダ タクヤ
URL
http://www-ikn.ist.hokudai.ac.jp/~kida/
所属
北海道大学
部署
大学院情報科学研究科 コンピュータサイエンス専攻 知識ソフトウェア科学講座
職名
准教授
学位
博士(情報科学)(九州大学)
科研費研究者番号
70343316
ORCID ID
0000-0003-1666-3303

プロフィール

2001 九州大学大学院システム情報科学研究科博士後期課程修了,博士(情報科
学).2001 九州大学附属図書館,研究開発室専任講師. 2004年より現職.テキストアルゴリズムおよび情報検索技術に関する研究に従事.特に,パターンマッチングとデータ圧縮のアルゴリズムを専門とする.情報処理学会正会員.電子情報通信学会正会員.日本データベース学会正会員.

研究分野

 
 

経歴

 
2004年4月
 - 
現在
北海道大学 准教授
 
2007年
 - 
2011年
北海道大学 大学院・情報科学研究科 准教授
 
2001年10月
 - 
2004年3月
九州大学附属図書館 研究開発室 講師
 
2000年1月
 - 
2001年9月
日本学術振興会 特別研究員
 

学歴

 
1999年4月
 - 
2001年9月
九州大学 システム情報科学研究科 情報理学専攻 博士課程
 
1997年4月
 - 
1999年3月
九州大学 システム情報科学研究科 情報理学専攻 修士課程
 
 
 - 
1997年3月
九州大学 理学部 物理学科
 

委員歴

 
2016年4月
 - 
現在
情報処理学会  アルゴリズム研究(SIGAL) 運営委員
 
2015年4月
 - 
現在
情報処理学会  情報基礎とアクセス技術研究(IFAT) 運営委員
 
2016年
 - 
2017年
The 20th International Conference on Discovery Science (DS 2017), Kyoto.  PC co-chair
 
2006年
 - 
2006年
1st Int'l Workshop on Data Mining and Statistical Science (DMSS-2006), Sapporo.  program committee
 
2015年6月
 - 
2016年6月
人工知能学会  2016年度全国大会 プログラム委員
 
2013年10月
 - 
2014年9月
FIT2014  研究会担当委員 兼 A分野責任者
 
2012年4月
 - 
2014年3月
情報処理学会  アルゴリズム研究会(SIGAL) 幹事
 
2009年4月
 - 
2013年3月
情報処理学会  TOD編集委員
 
2010年4月
 - 
2011年3月
情報処理学会  アルゴリズム研究会(SIGAL) 運営委員
 
2006年4月
 - 
2008年3月
人工知能学会  人工知能基本問題研究会(FPAI) 幹事
 

受賞

 
2001年
情報処理学会 創立40周年記念論文賞 受賞
 

論文

 
Iku Ohama,Takuya Kida,Hiroki Arimura
Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017   2578-2584   2017年   [査読有り]
Iku Ohama,Issei Sato,Takuya Kida,Hiroki Arimura
Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA   396-404   2017年   [査読有り]
Iku Ohama,Hiromi Iida,Takuya Kida,Hiroki Arimura
IEICE Transactions   99-D(4) 1139-1152   2016年   [査読有り]
Takuya Masaki,Takuya Kida
2016 Data Compression Conference, DCC 2016, Snowbird, UT, USA, March 30 - April 1, 2016   349-358   2016年   [査読有り]
Iku Ohama,Takuya Kida,Hiroki Arimura
Proceedings of the 2015 SIAM International Conference on Data Mining, Vancouver, BC, Canada, April 30 - May 2, 2015   819-827   2015年   [査読有り]
Satoshi Yoshida,Takuya Kida
J. Discrete Algorithms   32 75-86   2015年   [査読有り]
高田怜, 喜田拓也
日本データベース学会和文論文誌   13-J(1) 86-91   2014年10月
Kei Sekine,Hirohito Sasakawa,Satoshi Yoshida,Takuya Kida
Data Compression Conference, DCC 2014, Snowbird, UT, USA, 26-28 March, 2014   425   2014年   [査読有り]
Satoshi Yoshida,Hirohito Sasakawa,Kei Sekine,Takuya Kida
Data Compression Conference, DCC 2014, Snowbird, UT, USA, 26-28 March, 2014   436   2014年   [査読有り]
A Variable-length-to-fixed-length Coding Method Using a Re-Pair Algorithm
6(4) 17-23   2013年9月   [査読有り]
Kei Sekine,Hirohito Sasakawa,Satoshi Yoshida,Takuya Kida
2013 Data Compression Conference, DCC 2013, Snowbird, UT, USA, March 20-22, 2013   518   2013年   [査読有り]
Satoshi Yoshida,Takuya Kida
2013 Data Compression Conference, DCC 2013, Snowbird, UT, USA, March 20-22, 2013   532   2013年   [査読有り]
Iku Ohama,Hiromi Iida,Takuya Kida,Hiroki Arimura
Advances in Knowledge Discovery and Data Mining, 17th Pacific-Asia Conference, PAKDD 2013, Gold Coast, Australia, April 14-17, 2013, Proceedings, Part II   147-159   2013年   [査読有り]
Satoshi Yoshida,Takashi Uemura,Takuya Kida,Tatsuya Asai,Seishi Okamoto
Journal of Information Processing   20(1) 238-249   2012年   [査読有り]
人工知能学会論文誌   26(1) 297-306   2011年
Satoshi Yoshida,Takuya Kida
In Proc. Data Compression Conference 2011   to appear   2011年   [査読有り]
Jumpei Fujikawa,Takuya Kida,Takashi Katoh
In Proc. of IEEE International Conference on Granular Computing (GrC2011)   199-202   2011年   [査読有り]
喜田 拓也
電子情報通信学会論文誌. D, 情報・システム   93(6) 733-741   2010年6月
本論文では,VF符号で圧縮されたテキスト上でのパターン照合アルゴリズムについて論じる.ここで扱うVF符号とは,テキストを分節木によって可変長の部分文字列に分割し,固定長の符号語を割り当てる形式の符号化手法である.圧縮照合問題の形式的枠組みであるCollage systemを用いれば,VF符号上でKMP型の汎用的なアルゴリズムを組織的に導出でき,O(m^2+D)時間・領域の前処理の後, O(n+R)時間で圧縮テキストを走査できる.ここで, m, n, R, Dはそれぞれ,パターン長,テキスト...
喜田拓也
電子情報通信学会論文誌 D   J93-D(6) 733-741   2010年6月
Satoshi Yoshida,Takuya Kida
Proc. Data Compression Conference 2010   0-228   2010年   [査読有り]
UEMURA Takashi, YOSHIDA Satoshi, KIDA Takuya, ASAI Tatsuya, OKAMOTO Seishi
Proc. of the 17th Symposium on String Processing and Information Retrieval(SPIRE2010)   6393 179-184   2010年   [査読有り]
喜田 拓也
日本データベース学会論文誌   8(1) 125-130   2009年6月
本論文では,刈り込み接尾辞木を用いた新たな可変情報源系列固定長符号化(VF符号化)の手法を提案する.この符号化手法は,頻度情報に基づいて刈り込んだ接尾辞木を文節木として用いてVF符号化する.VF符号は,すべての符号語が等長であるという工学的に好ましい性質があり,圧縮パターン照合などへの重要な応用がある.実験の結果,提案符号は,自然言語文書などに対して約41%の圧縮率を達成しており,良く知られているHuffman符号や,古典的なVF符号であるTunstall符号よりも圧縮性能が良いことがわか...
Takuya Kida
In Proc. Data Compression Conference 2009   449   2009年   [査読有り]
Hideyuki Ohtani,Takuya Kida,Takeaki Uno,Hiroki Arimura
Proc. of The 3rd International Conference on Ubiquitous Information Management and Communication (ICUIMC 2009)   471-479   2009年   [査読有り]
Hiroshi Sakamoto,Shirou Maruyama,Takuya Kida,Shinichi Shimozono
IEICE Trans. on Information and Systems   E92-D(2) 158-165   2009年   [査読有り]
上村卓史, 喜田拓也, 有村博紀
情報処理学会論文誌トランザクション(CD-ROM)   2008(1) VOL.1NO.1,49-60   2008年11月
上村 卓史, 喜田 拓也, 有村 博紀
情報処理学会論文誌. データベース   1(1) 49-60   2008年6月
インターネットからの効率的な情報収集においてウェブブラウザの果たす役割は大きい.しかし,膨大な文書の検索および閲覧はユーザにとっていまだ大きな負担である.本論文では,情報収集の補助を目的として,ユーザが閲覧するウェブページからのキーワード抽出という問題について考察する.ここでのキーワードとは,任意の単語の連結(単語Nグラム)である.このため,接尾辞木をもとにした,任意の単語Nグラムを線形領域で表すデータ構造である単語Nグラム木を提案し,これを利用した高速な抽出アルゴリズムを与える.また,抽...
上村卓史, 喜田拓也, 有村博紀
電子情報通信学会論文誌   Vol.J91-D(No.03) 595-607   2008年3月
上村 卓史, 喜田 拓也, 有村 博紀
電子情報通信学会論文誌. D, 情報・システム   91(3) 595-607   2008年3月
プロパティ付きテキストとは,長さηのテキストに,補助情報としてテキスト上の互いにオーバラップを許した区間の集合(プロパティという)が付加された構造化文書の一種であり,アノテーション付きの系列データの形式的なモデルとなっている.このプロパティ付きテキストへの全文テキスト索引として,Amirら(CPM2006)は,プロパティ接尾辞木を提案した.これは,プロパティの各区間に含まれるすべての部分文字列を格納する索引構造であり,遺伝子情報や,ビデオストリーム,メタデータ付き時系列データなどへの応用が...
Takuya Kida,Tomoya Saito,Hiroki Arimura
Proc. the First International Workshop on Algorithms for Large-Scale Information Processing in Knowledge Discovery (ALSIP2008)   5-16   2008年   [査読有り]
Proceedings of The Third IEEE International Workshop on Databases for Next-Generation Researchers (SWOD'07)   13-18   2007年
上村 卓史, 喜田 拓也, 有村 博紀
情報科学技術レターズ   5(0) 5-8   2006年8月
Proceedings of Dagstuhl Workshop on Federation over the Web   LNAI3847 25-39   2006年
喜田 拓也, 南 俊朗
日本データベース学会letters   4(2) 61-64   2005年9月
多くの図書館において所蔵文献の検索にはOPAC(Online Public Access Catalog)が用いられている.しかしながら,歴史の長い図書館では古い資料の書誌データが電子化されないままであり,そのような資料はOPACで検索することができない.すなわち,利用者は図書目録カードが入った引出しの前まで出向き,カードを一枚一枚めくりながら目的の資料を探さなければならない.このような状況を打開する手段として,図書目録カードのすべてを画像データ化し,Web上でカードを閲覧できるシステムを...
Takuya Kida
Federation over the Web - International Workshop, Dagstuhl Castle, Germany, May 1-6, 2005. Revised Selected Papers   25-39   2005年   [査読有り]
Hiroshi Sakamoto,Takuya Kida,Shinichi Shimozono
Proceedings of The Eleventh Symposium on String Processing and Information Retrieval (SPIRE2004)   Lecture Notes in Computer Science 3246 218-229   2004年   [査読有り]
Pattern Matching with Taxonomic Information
Proceedings of The Asia Information Retrieval Symposium (AIRS2004)   265-268   2004年
Takuya Kida,Tetsuya Matsumoto,Yusuke Shibata,Masayuki Takeda,Ayumi Shinohara,Setsuo Arikawa
Theor. Comput. Sci.   298(1) 253-272   2003年   [査読有り]
Masayuki Takeda,Satoru Miyamoto,Takuya Kida,Ayumi Shinohara,Shuichi Fukamachi,Takeshi Shinohara,Setsuo Arikawa
String Processing and Information Retrieval, 9th International Symposium, SPIRE 2002, Lisbon, Portugal, September 11-13, 2002, Proceedings   170-186   2002年   [査読有り]
Takuya Kida,Tetsuya Matsumoto,Masayuki Takeda,Ayumi Shinohara,Setsuo Arikawa
Combinatorial Pattern Matching, 12th Annual Symposium, CPM 2001 Jerusalem, Israel, July 1-4, 2001 Proceedings   193-206   2001年   [査読有り]
Gonzalo Navarro,Takuya Kida,Masayuki Takeda,Ayumi Shinohara,Setsuo Arikawa
Data Compression Conference, DCC 2001, Snowbird, Utah, USA, March 27-29, 2001.   459-468   2001年   [査読有り]
Yusuke Shibata,Takuya Kida,Shuichi Fukamachi,Masayuki Takeda,Ayumi Shinohara,Takeshi Shinohara,Setsuo Arikawa
Algorithms and Complexity, 4th Italian Conference, CIAC 2000, Rome, Italy, March 2000, Proceedings   306-315   2000年   [査読有り]
Tetsuya Matsumoto,Takuya Kida,Masayuki Takeda,Ayumi Shinohara,Setsuo Arikawa
Seventh International Symposium on String Processing and Information Retrieval, SPIRE 2000, A Coruña, Spain, September 27-29, 2000   221-228   2000年   [査読有り]
Takuya Kida,Masayuki Takeda,Ayumi Shinohara,Setsuo Arikawa
Combinatorial Pattern Matching, 10th Annual Symposium, CPM 99, Warwick University, UK, July 22-24, 1999, Proceedings   1-13   1999年   [査読有り]
Kouichi Tamari,Mayumi Yamasaki,Takuya Kida,Masayuki Takeda,Tomoko Fukuda,Ichiro Nanri
Discovery Science, Second International Conference, DS '99, Tokyo, Japan, December, 1999, Proceedings   128-138   1999年   [査読有り]
Takuya Kida,Yusuke Shibata,Masayuki Takeda,Ayumi Shinohara,Setsuo Arikawa
Sixth International Symposium on String Processing and Information Retrieval and Fifth International Workshop on Groupware, SPIRE/CRIWG 1999, Cancun, Mexico, September 21-24, 1999   89-96   1999年   [査読有り]
Takuya Kida,Masayuki Takeda,Ayumi Shinohara,Masamichi Miyazaki,Setsuo Arikawa
Data Compression Conference, DCC 1998, Snowbird, Utah, USA, March 30 - April 1, 1998.   103-112   1998年   [査読有り]

Misc

 
Isamu Furuya,Takuya Kida
CoRR   abs/1706.10061    2017年   [査読有り]
古谷勇, 喜田拓也
情報処理学会研究報告(Web)   2017(AL-162) Vol.2017‐AL‐162,No.1,1‐8 (WEB ONLY)   2017年3月
小笠原 智明, 今井 浩, 喜田 拓也
電子情報通信学会技術研究報告 = IEICE technical report : 信学技報   116(211) 29-35   2016年9月
栗田和宏, 和佐州洋, 喜田拓也, 有村博紀
情報処理学会研究報告(Web)   2016(AL-157) VOL.2016‐AL‐157,NO.10 (WEB ONLY)   2016年2月
新井野昴, 喜田拓也
情報処理学会研究報告(Web)   2016(MUS-110) Vol.2016‐MUS‐110,No.5,1‐6 (WEB ONLY)   2016年2月
正木拓也, 喜田拓也
情報処理学会研究報告(Web)   2015(AL-154) VOL.2015-AL-154,NO.2 (WEB ONLY)   2015年9月
正木 拓也, 喜田 拓也
電子情報通信学会技術研究報告 = IEICE technical report : 信学技報   115(84) 37-43   2015年6月
喜田拓也, 高田怜
研究報告音楽情報科学(MUS)   2014(11) 1-8   2014年11月
本稿では,大規模な楽曲データベースに対し,楽曲の一部をクエリとして,そのクエリを含む楽曲を高速に検索する手法について論じる.ここで,データベースとクエリは共に,楽曲の音声音響信号から抽出された何らかの特徴ベクトルの系列として表現されているものとする.提案する手法では,データベースに含まれる大量の高次元特徴ベクトルを,アルファベット分割の考え方を用いて複数本の文字列データとしてとらえ,任意長の部分文字列に対する厳密一致検索が可能な索引構造を用いて保存する.楽曲の検索は,クエリからサンプリング...
正木拓也, 笹川裕人, 喜田拓也
情報処理学会研究報告(Web)   2014(AL-149) VOL.2014-AL-149,NO.5 (WEB ONLY)-5   2014年9月
入力テキストを単語毎に符号化する End-Tagged Dense 符号 (ETDC) は,バイト単位の可変長符号を用いる,符号語の抽出が容易な検索向きのデータ圧縮法である.本稿では,単語毎に分かち書きされていないテキストに対して ETDC で符号化する手法を提案した.提案手法は,テキストに対して文法圧縮の一つである Re-Pair アルゴリズムを利用した分かち書きを行い,その後に ETDC で符号化を行う.その際,Re-Pair アルゴリズムの再帰処理において,後段の ETDC の符号化...
正木 拓也, 笹川 裕人, 喜田 拓也
情報科学技術フォーラム講演論文集   13(1) 67-68   2014年8月
笹川裕人, 関根渓, 吉田諭史, 喜田拓也
情報処理学会研究報告. AL, アルゴリズム研究会報告   2014(8) 1-5   2014年6月
本稿では,可変長-固定長符号(VF符号)により符号化された圧縮テキストに対する,高速な部分文字列抽出法を提案する.提案手法では,圧縮テキストに対して,符号語の境界に対応する元テキストの位置を格納した簡潔索引を付加することで,圧縮テキストから部分文字列を抽出する問題を平均 O(N/n+l) 時間で解く.ここで,N と,n,l は,それぞれ元テキスト長,圧縮テキスト長,抽出する部分文字列長である.計算機実験では,提案手法を Re-Pair-VF アルゴリズム上で実装し,高速に部分文字列抽出問題...
寺島 裕貴, 喜田 拓也
電子情報通信学会技術研究報告 = IEICE technical report : 信学技報   113(493) 247-252   2014年3月
画像分類に広く用いられる特徴量としてLocal Binary Pattern (LBP)がある.これは.通常3×3の局所領域から画素値を元に算出された256個のパターンの頻度を記述したヒストグラムを特徴量とする局所特徴量である.本稿では,このLBPの考えを元に,画像の輝度による勾配情報をパターン化した特徴量を提案する.本稿で提案する特徴量は,3×3の局所領域の中から4点を選択し,それらの点が有する勾配強度と勾配方向の情報の組み合わせを256個のパターンで表す.テクスチャ画像,及び顔画像にお...
高田怜, 喜田拓也
情報処理学会研究報告. [音楽情報科学]   2013(7) 1-6   2013年8月
楽曲信号の検索には,音楽指紋が用いられることが多い.音楽指紋とは,楽曲の特徴をとらえつつ,楽曲信号を非常に小さいビット列へと変換したものである.したがって,精度良く高速に楽曲検索を行うためには,適切な音楽指紋の設計が重要となる.本稿では,異なる歌唱者によって歌われた同じ伴奏の楽曲信号からデータベース中の原曲を検索する問題について議論する.この問題のためにいくつか異なる音楽指紋を比較し,それらの検索精度への影響について調査を行う.
三浦亮, 寺島裕貴, 喜田拓也
情報処理学会研究報告. [音楽情報科学]   2013(30) 1-6   2013年8月
近年,膨大な数の楽曲を個人がインターネットを介して利用できるようになった.なおも増加し続ける楽曲データを効率よく管理し検索する上で,楽曲の構造理解は重要な役割を担っている.たとえば,ポピュラー音楽には,イントロ,コーラス (サビ),ブリッジといった音楽的に意味の有る構造が存在しており,これを自動的に抽出することで高度な楽曲鑑賞や管理を行うことができる.本稿では,楽曲信号を入力として音楽的に意味の有る構造の境界を見つける問題について議論する.楽曲構造の解析は,楽曲信号に対する自己相似性行列上...
関根 渓, 笹川 裕人, 吉田 諭史, 喜田 拓也
電子情報通信学会技術研究報告 : 信学技報   112(346) 47-52   2012年12月
The Re-Pair algorithm proposed by Larsson and Moffat in 1999 is a simple grammar-based com-pression method that achieves an extremely high compression ratio. However, Re-Pair is an offline and very space consuming algorithm. Thus, to apply it to a...
大濱 郁, 飯田 裕美, 喜田 拓也, 有村 博紀
電子情報通信学会技術研究報告. IBISML, 情報論的学習理論と機械学習   111(480) 1-8   2012年3月
本稿では,関係の有無の持つ意味が非対称であり,関係を生成する機会に個体差があるような関係データを分析するための,新しい生成モデルを提案する.提案するモデルでは,各オブジェクトに対して他オブジェクトとの遭遇しやすさを表すパラメータが組み込まれている.そして,サブセットクラスタリングのアイデアに基づき,オブジェクト同士が遭遇した時は,クラスタ固有の分布から,遭遇しなかった場合は,全データで共通の分布から関係が生成される.そのため,購買履歴のようにリンクと非リンクのもつ意味が非対称であり,オブジ...
吉田 諭史, 喜田 拓也
情報処理学会研究報告. データベース・システム研究会報告   2011(14) 1-6   2011年7月
本稿では,VF 符号における辞書データ構造を訓練することで VF 符号の性能を向上させる方法について論じる.ここで議論する VF 符号とは,分節木と呼ばれる木構造を用いて入力テキストを可変長のブロックに分割し,各ブロックに固定長の符号語を割り当てることでテキスト圧縮を達成する情報源符号化方法である.VF 符号の圧縮率は分節木によって決定されるが,入力テキストに対して最適な分節木を構築することは NP 困難であることが知られている.そのため,最適に近い分節木を構築するために,入力テキストを繰...
大濱 郁, 喜田 拓也, 有村 博紀, 阿部 敏久
電子情報通信学会技術研究報告. IBISML, 情報論的学習理論と機械学習   110(476) 9-16   2011年3月
我々は,人間行動履歴の地理的クラスタリングについて議論する.本論文では,この問題を,二次元時系列データのセグメンテーション問題として定式化し,二つのクラスタリング手法,LS-linHMMとX-linHMMを提案する.前者のLS-linHMMは,線形制約付きHMMを用いたクラスタリングと情報量規準を用いたモデル選択を組み合わせ,クラスタ数の自動推定を行う.また,X-linHMMは,x-meansのアイデアを取り入れた2状態線形HMMによる階層的クラスタリングであり,LS-linHMMよりも高...
吉田 諭史, 喜田 拓也
研究報告情報基礎とアクセス技術(IFAT)   2010(10) 1-8   2010年7月
本稿では,VF 符号に算術符号を組み合わせることで,検索の効率と圧縮率とを保つ方法について議論する.ここで議論する VF 符号とは,分節木と呼ばれる圧縮のための辞書木を用いて元のテキストを可変長のブロックに分割し,各ブロックに固定長の符号語を割り当てることでデータ圧縮を達成する情報源符号化方法である.VF 符号は,近年,パターン照合を高速化することのできるデータ圧縮法として見直されている.VF 符号は,符号語長が固定であるという制限から,分節木が小さいときには圧縮性能が低い.圧縮率を向上さ...
上村卓史, 喜田拓也
電子情報通信学会大会講演論文集   2010 8   2010年3月
中野 智晴, 喜田 拓也
画像ラボ   20(9) 6-11   2009年9月
吉田 諭史, 喜田 拓也
情報処理学会研究報告. データベース・システム研究会報告   148(0) 1-7   2009年7月
Yamamoto と Yokoo ら [2001] によって提案された多重分節木による AIVF 符号は,短い符号長で十分な圧縮率が得られる VF 符号 (可変ブロック固定長符号化) の一つである.しかしながら,情報源アルファベットのサイズを k とすると,k − 1個の分節木を構築するため,ただ一つの分節木を用いる一般的なVF符号化と比べて,符号・復号化時に多くの時間と領域が必要となる.本稿では,多重分節木を一つの分節木に統合し,その木の上で仮想的に多重分節木を模倣するアルゴリズムを示す...
喜田 拓也
電子情報通信学会技術研究報告. COMP, コンピュテーション   109(108) 1-8   2009年6月
本稿では,VF符号で圧縮されたテキスト上でのパターン照合アルゴリズムについて論じる.まず,圧縮照合問題の形式的枠組みであるCollage systemを用いて,VF符号上でKMP型の圧縮照合を行う汎用的なアルゴリズムを導出する.そのアルゴリズムは,O(m^2+D)時間・領域の前処理の後,O(n+R)時間で圧縮テキストを走査できる.ここで,m,n,R,Dはそれぞれ,パターン長,テキスト長,パターンの出現回数,圧縮辞書のサイズである.ただし,ここでいう圧縮辞書のサイズとは,各符号語に対応する文...
中野 智晴, 喜田 拓也
電子情報通信学会技術研究報告. PRMU, パターン認識・メディア理解   108(363) 25-30   2008年12月
現在,インターネット上に存在する多くの画像データは圧縮された形で保存されている.その圧縮形式の代表的なもののひとつとして,JPEG形式が挙げられる.通常,JPEG形式の画像に対して画像照合やパターン認識処理をするためには,一旦,元のBitmapに復元しなければならない.本稿では,JPEG画像に対して,それを復元することなく部分画像を近似パターンマッチングするアルゴリズムについて論じる.今回提案するアルゴリズムは,複数の非決定性オートマトンの動作をビットパラレル手法を用いて高速に模倣し,JP...
大谷 英行, 喜田 拓也, 宇野 毅明, 有村 博紀
情報処理学会研究報告. データベース・システム研究会報告   2008(56) 113-120   2008年6月
巨大なデータ集合の中から,有用な知識や情報を発見するデータマイニングは,現代の様々な分野で重要な技術であり,特に,時系列データを対象とした時系列データマイニングが注目を集めている.本論文では,頻出時系列エピソード発見問題を研究する.これは,与えられた系列データから,最大窓幅wの制約の元で,頻出エピソードと呼ばれる頻出する部分系列を効率的に取り出す問題である.本稿では,高速な頻出集合発見アルゴリズムLCMを元にして,エピソード発見のための深さ優先型探索アルゴリズムといくつかの高速化手法を提示...
上村卓史, 喜田拓也, 有村博紀
情報処理学会全国大会講演論文集   70th(5) 5.207-5.208   2008年3月
Compressed Pattern Matching Accelerates Keyword Search
27-32   2008年
上村卓史, 喜田拓也, 有村博紀
情報処理学会シンポジウムシリーズ(CD−ROM)   2007(3) 7B-1   2007年11月
上村 卓史, 喜田 拓也, 有村 博紀
情報科学技術フォーラム一般講演論文集   6(2) 45-46   2007年8月
斉藤 智哉, 喜田 拓也, 有村 博紀
情報科学技術フォーラム一般講演論文集   6(2) 43-44   2007年8月
上村 卓史, 喜田 拓也, 有村 博紀
電子情報通信学会技術研究報告. COMP, コンピュテーション   107(24) 71-78   2007年4月
高度なテキスト検索処理においては,テキストの特性(プロパティ)を考慮し,ある条件を満たす区間のみを対象として検索を行うという要求が存在する.本論文では,このプロパティを考慮した索引構造を構築する問題に取り組む.2006年にAmirらは,プロパティに属する区間に含まれる部分文字列のみを格納するプロパティ付き接尾辞木PSTを提案した.彼らの構築アルゴリズムは,接尾辞木から不要なノードを削除することでプロパティ付き接尾辞木を得るものである.本論文では,PSTの線形時間構築への第一歩として,必要な...
上村卓史, 喜田拓也, 有村博紀
情報科学技術フォーラム   FIT 2006 5-8-8   2006年8月
Online Construction of Truncated Suffix Tree with Word Count Limitation
Proceedings of DMSS2006   104-108   2006年
Application of Truncated Suffix Trees to Finding Sentences from the Internet
Proceedings of Core-to-Core Workshop   18   2006年
喜田拓也
情報科学技術フォーラム   FIT 2005 25-28-28   2005年8月
喜田 拓也, 南 俊朗
情報処理学会研究報告データベースシステム(DBS)   2005(68) 461-467   2005年7月
多くの図書館において所蔵文献の検索にはOPAC(Online Public Access Catalog)が用いられている.しかしながら,歴史の長い図書館では古い資料の書誌データが電子化されないままであり,そのような資料はOPACで検索することができない.すなわち,利用者は図書目録カードが入った引出しの前まで出向き,カードを一枚一枚めくりながら目的の資料を探さなければならない.このような状況を打開する手段として,図書目録カードのすべてを画像データ化し,Web上でカードを検索できるシステムを...
有村博紀, 喜田拓也
情報処理   46(1) 4-11   2005年1月
大量の電子化データの流れであるデータストリームから,有用な情報を少ない資源で効率よく取り出すためのストリームマイニング技術を概観する.まず,データストリームの特徴と,データマイニングの目的について整理し,限定された計算資源を用いて無限につづくデータストリームからマイニングを行うためのシステムに要求される性質について議論する.次に,さまざまな要約データ構造とオンライン化技術についてまとめ,最近の研究のうち特色のあるものを紹介する.
データストリームのためのマイニング技術
特集「データマイニング技術」, 情報処理   46(1) 4-11   2005年
南俊朗, 池田大輔, 喜田拓也
情報処理学会研究報告   2004(119(FI−77)) 7-22-22   2004年11月
ネットワークを基盤とした高度情報化社会にふさわしい利用者サービスを実現するためには,図書館は新技術を導入し,成長する有機体であることが求められている.そのための技術として大きな注目を集めているのがRFID(Radio Frequency Identification)技術である.これは図書に貼付されたタグがリーダ/ライタと呼ばれる外部機器よりエネルギーを供給され,それを用いて無線によりタグとリーダ/ライタ間でデータをやり取りするものである.このような技術を用いることにより,従来の図書館業務...
喜田 拓也, 坂本 比呂志, 下薗 真一
電子情報通信学会技術研究報告. COMP, コンピュテーション   104(317) 1-7   2004年9月
テキストを圧縮する最適化問題に対して,準最適解を保証する省スペースな線形時間アルゴリズムを構築する.アルゴリズムは,高々アルファベットサイズの頂点を持つ平衡二分木上の最近共通祖先を計算し,その情報を用いて,長さnの任意のテキストを最適な圧縮のサイズg_*に対して,高々O(log g_* 1og n)倍以内で近似する.アルゴリズムが使用する主記憶領域は,高々O(g_* log g_*)であり,この有効性を実験によって示す.
喜田 拓也, 有村 博紀
人工知能基本問題研究会   56 73-78   2004年7月
喜田 拓也
電子情報通信学会技術研究報告. COMP, コンピュテーション   103(622) 61-68   2004年1月
VLDCパタンとは,任意の文字列と一致するメタ記号'*'を含む文字列パタンである.いま,VLDCパタンPに対して,Pと一致する文字列の集合をPとする.このとき,VLDCパタンに対する文字列照合問題とは,与えられた文字列T中に,あるq∈Pが存在するかどうかを答えることである.今回,P中の'*'以外の部分においてk個以下の不一致を許した近似照合問題に取り組んだ.本論文では,この問題を解く三つのアルゴリズムを提案する.一つは,動的計画法に基づく近似文字列照合アルゴリズムの変形であり,mをPの長さ...
喜田拓也
情報科学技術フォーラム   FIT 2003 137-138-138   2003年8月
喜田 拓也, 宮本 哲, 竹田 正幸
情報科学技術フォーラム一般講演論文集   2002(2) 55-56   2002年9月
南 俊朗, 喜田 拓也
九州大学情報基盤センター広報 : 学内共同利用版   2(1) 25-29   2002年3月
喜田 拓也, 柴田 裕介, 竹田 正幸, 篠原 歩, 有川 節夫
全国大会講演論文集 第59回(ソフトウェア科学・工学)   177-178   1999年9月
柴田裕介, 喜田拓也, 竹田正幸, 篠原歩, 有川節夫
情報処理学会全国大会講演論文集   59th(1) 1.175-1.176   1999年9月
喜田拓也, 竹田正幸, 篠原歩
情報処理学会全国大会講演論文集   57th(1) 1.143-1.144-144   1998年10月
喜田拓也, 竹田正幸, 宮崎正路, 篠原歩
電気関係学会九州支部連合大会講演論文集   50th 275   1997年10月

書籍等出版物

 
中村 篤祥, 湊 真一, 喜田 拓也 (担当:共著)
ムイスリ出版   2013年4月   ISBN:489641215X

担当経験のある科目

 
 

競争的資金等の研究課題

 
文部科学省: 科学研究費補助金(基盤研究(A))
研究期間: 2016年4月 - 2020年3月    代表者: 有村 博紀
文部科学省: 科学研究費補助金(基盤研究(C))
研究期間: 2015年4月 - 2018年3月    代表者: 喜田 拓也
文部科学省: 科学研究費補助金(基盤研究(A))
研究期間: 2013年4月 - 2018年3月    代表者: 竹田 正幸
文部科学省: 科学研究費補助金(基盤研究(B))
研究期間: 2013年4月 - 2016年3月    代表者: 中村 篤祥
文部科学省: 科学研究費補助金(基盤研究(A))
研究期間: 2012年4月 - 2016年3月    代表者: 有村 博紀
文部科学省: 科学研究費補助金(挑戦的萌芽研究)
研究期間: 2012年4月 - 2015年3月    代表者: 湊 真一
文部科学省: 科学研究費補助金(若手研究(B))
研究期間: 2011年 - 2013年    代表者: 喜田 拓也
文部科学省: 科学研究費補助金(基盤研究(A))
研究期間: 2008年 - 2011年    代表者: 有村 博紀
本研究においては,ネットワーク上大規模半構造データに内在する知識をパターンや規則としてとりだことが可能な超調整な半天構造マイニングエンジン技術を開発し,これを現実の多様な半構造データに適用するための周辺技術を開発する.さらに,開発した基盤技術と周辺技術の実装を行い,インターネット上の大規模半構造データからの知識発見実験を行うことを目的とする.
文部科学省: 科学研究費補助金(基盤研究(B))
研究期間: 2008年 - 2011年    代表者: 湊 真一
データベース分野では,当初はハードディスク内にデータを格納することが一般的だったが、2000年以降、中規模クラスの実用的なデータベースが計算機のメモリに納まるようになってきた。そこで本研究課題では、超大規模な単一実メモリ空間を持つ計算機に、二分決定グラフ(BDD)と呼ばれる巨大な圧縮データ構造を構築して、全てを高速アクセス可能なメモリ上に格納し、高速にデータベース解析処理を行う手法を提案し、その研究実用化を進める。
文部科学省: 科学研究費補助金(特定領域研究)
研究期間: 2009年 - 2010年    代表者: トーマス ツォイクマン
本研究課題では,大規模知識処理のための超高速アルゴリズムの研究に取り組んでいる.本研究では,ウェブからの知識獲得を人間による大量のウェブ情報アクセスを支援する効率的な半自動的ツールとしてとらえ,従来の情報検索システムを超えた新しい情報アクセスシステムの開発を目指している.そのために,現在までに開発してきたウェブ情報処理技術を元に,中核技術として,機械学習と知識索引技術に基づく,適応的な知的情報獲得システムの基盤技術を開発することを目標としている.特に本年度は,下記の課題に取り組み,各課題に...
文部科学省: 科学研究費補助金(若手研究(B))
研究期間: 2008年 - 2010年    代表者: 喜田 拓也
連続データストリームに対する高速・高度なパターン照合技術およびそのためのデータ圧縮技術について研究を行った.前者については,ビットパラレル手法に基づいた,多次元データストリームに対する複雑なクエリを許すパターン照合アルゴリズムBPS(Bit-Parallel on Streams)を提案した.これにより,文字情報のみならず,数値データや分類データなどが複雑に組み合わさったクエリをデータストリームに対して行うことができるようになった.後者については,VF符号(Variable-to-fixe...
文部科学省: 科学研究費補助金(特定領域研究)
研究期間: 2007年 - 2008年    代表者: トーマス ツォイクマン
本研究のH19年度の進捗を元にして, H20年度は, これまでに提案・開発してきた基盤的なアルゴリズムをさらに発展させ, 現実の大規模知識データを高速に処理できる技術として確立させる作業を進めた.(1) パターン発見の履歴から, その利用者との対話や, 環境, データの記録から最適なパターン発見パラメータを学習する適応的パターン発見アルゴリズムを設計・開発し、その有効性を評価した.(2) 研究代表者が研究開発に成功した多項式時間確率的パターン発見技術(ALT2003, DS2006他)を用...
文部科学省: 科学研究費補助金(若手研究(B))
研究期間: 2005年 - 2007年    代表者: 喜田 拓也
本研究では、オントロジー情報などの背景知識を考慮することで、より知的な文字列照合を行うアルゴリズムの開発を目指している。具体的には、電子的に利用可能な分類階層データベースやシソーラス情報、文章構造といったオントロジー情報を利用して動作する照合アルゴリズムを開発し、それらの統合を行う。また、それ以外のオントロジー情報についても調査を行い、知的検索のための利用を模索する。申請者はこれまでに分類階層情報を考慮した文字列照合アルゴリズムに加え、Arc情報が付加された文字列照合アルゴリズムについて取...
文部科学省: 科学研究費補助金(特別推進研究)
研究期間: 2005年 - 2007年    代表者: 有村 博紀
本研究では,WWW(ウェブ)などの大規模半構造データからの知識基盤形成のための超高速半構造パターン発見技術とその周辺技術の研究開発を行う.本研究では,次の項目に関して研究開発を行った.(1)超高速半構造マイニングエンジンの研究として,変数付き系列モチーフや属性木等の有用かつ自明でない半構造データ族に対して,性能保障をもつ効率よいパターン発見アルゴリズムを開発した.これらの計算量を理論的に明らかにし,さらにこの枠組みを一般化することで,平面幾何グラフ,2次元画像パターン,伸張を許す極大系列パ...
文部科学省: 科学研究費補助金(基盤研究(A))
研究期間: 2005年 - 2007年    代表者: 岡本 青史
インターネットとWebサービス技術の急速な発展を背景として,WebページやXMLデータに代表される半構造データが,大量に流通・蓄積されるようになってきた.我々は,このような大規模半構造データに対する学習と発見の理論的基盤,及び効率的なパターン照合,データ圧縮,索引構造などの実用的処理基盤を構築し,これらの成果を高速知識発見システムに応用することを目的として研究を遂行した.半構造データに対するパターン発見の理論研究では,木構造データのためのカーネル関数の設計と解析を行い,一般的な木構造の学習...
文部科学省: 科学研究費補助金(基盤研究(B))
研究期間: 2005年 - 2007年    代表者: 湊 真一
二分決定グラフ(BDD)は,大規模論理関数を主記憶上に効率よく表現するデータ構造であり,1990年頃より,主にVLSI設計自動化の分野で盛んに研究開発されてきた.近年,このBDDが,データマイニング・知識発見の分野においても活用できることがわかってきた.特に,ゼロサプレス型BDD(ZBDD)と呼ばれるタイプのBDDは,疎な組合せ集合を効率よく扱うことができるため,現実に扱われる多くのデータベースの解析処理に適している.本研究では,ZBDDを用いた大規模データベース解析処理アルゴリズムの研究...
文部科学省: 科学研究費補助金(特定領域研究)
研究期間: 2006年 - 2006年    代表者: トーマス ツォイクマン
本年度は,下記の課題に取り組んだ.(1)超高速知識獲得アルゴリズムの研究:数学的な距離尺度と計算量理論に基づいた新しいクラスタリング技法を提案した.我々は,このクラスタリング技法の数学的な意味を明らかにするとともに,本手法を英語および日本語のテキスト語彙のクラスタリングに適用し,実際に人間の感覚に近い語彙集合に分類されることを示した.さらに,ノイズがあるデータに対しても頑健に動作するアルゴリズムを開発し,その効果を実験的に示した.(2)環境履歴と利用者対話を用いた自律・適応的な知識発見手法...
文部科学省: 科学研究費補助金(特定領域研究)
研究期間: 2004年 - 2005年    代表者: 有村 博紀, トーマス ツォイクマン
本研究は,大量のウェブページやXML等の大規模半構造データからのデータマイニング(ウェブマイニング)に基づき,大量のデータ解析を対話的に支援する効率的なツールとして,従来の情報検索システムを超えた新しい情報アクセスシステムの実現方式を明らかにすることを目標としている.その鍵になる技術として,最適パターン発見を木やグラフ構造に拡張し,計算量理論と計算学習理論の最新の成果を援用しながら,半構造データに対する頑健かつ高速な最適化パターン発見アルゴリズムの開発に取り組んだ.平成17年度は,初年度か...
文部科学省: 科学研究費補助金(基盤研究(B))
研究期間: 2004年 - 2005年    代表者: 有川 節夫
RFIDタグシステムの最新動向の調査は本研究の重要な目的であり、韓国やシンガポールなど海外の図書館やタグシステム関連企業、国内の先進的な取り組みを行っている図書館を視察した。また、自動認識総合展などに参加し最新動向調査を行なった。まず、九州大学附属図書館筑紫分館に既に導入していたRFIDタグシステムの実験を拡充し、タグ添付冊数を約5千冊から2万8千冊に増やし、実運用レベルで実証実験を行った。これにより、自動貸出機と不正帯出防止は、運用方法を工夫することで十分実用的であることが分かった。一方...
文部科学省: 科学研究費補助金(基盤研究(B))
研究期間: 2003年 - 2005年    代表者: 有村 博紀, 池田 大輔
ネットワーク上を時間的に変化しながら流れる大量半構造データストリームから有用な情報を効率よく獲得する超高速オンライン型データマイニング・システムの研究開発を行った.最終年度である平成17年度は,前年度までに研究開発した基礎理論の深化と,ネットワークデータへの応用の両面から,ストリーム指向パターン照合と半構造データマイニング,さらに,応用としてネットワーク不正侵入検出などの問題について,以下のように研究開発を行った.また,3年間の研究成果の発表・出版を行った.(1)半構造データストリームマイ...
文部科学省: 科学研究費補助金(若手研究(B))
研究期間: 2002年 - 2004年    代表者: 喜田 拓也
WWW上で広く用いられているHTMLファイルは,タグを単位とした木構造を内部表現に持つ半構造化データである.ポストHTMLとして登場し,今日ではアプリケーション間のデータ交換のための共通形式として注目を浴びているXMLファイルも同様の半構造化データである.これまで半構造化データに対する文字列処理といえば,一度テキストから木構造を抽出し,それを土台にしてタグの要素であるテキストに対して形態素解析を行ったり,部分文字列やN-gramを切り出したりした後に索引構造を構築し,それを用いて文字列照合...
文部科学省: 科学研究費補助金(基盤研究(B))
研究期間: 2002年 - 2003年    代表者: 有川 節夫
RFIDタグ(IDタグ)は,来るべきユビキタス・コンピューティング時代の核となる中心的なIT技術の一つである.非接触通信・メモリ機能・電池レスという優れた特性により,物品の管理のみならず,これまで磁気カードなどで提供されてきたあらゆるサービスに利用される可能性がある.今後もっとも重要な社会基盤技術として,より一層の普及とそれに伴う標準化,性能向上,価格低下が期待されている.その一方で,現状では実用されている例は未だ少なく,図書館における利用はその成功例の一つとして業界の注目を集めている.本...
文部科学省: 科学研究費補助金(基盤研究(B))
研究期間: 2001年 - 2003年    代表者: 篠原 歩
文字列に対する索引構造として,接尾辞木(suffix tree)や有向無閉路文字列グラフ(DAWG)がよく知られているが,我々はその両方の性質を持つ,よりコンパクトなデータ構造であるコンパクト有向無閉路文字列(CDAWG)に着目し,そのためのオンライン構築アルゴリズムを示した.また,文字列のすべての接頭辞に対するDAWGを合わせた構造に対する構築アルゴリズムを示し,与えられた文字列のすべての部分列を受理するオートマトン(部分列オートマトン)の状態数の下限の証明も行った.これらの結果はいずれ...
文部科学省: 科学研究費補助金(基盤研究(C))
研究期間: 2001年 - 2002年    代表者: 南 俊朗
本研究は「図書館自動化&電子化(Library Automation & Digitization LA&D)」の観点から図書館蔵書の電子的検索機能を実現することが大きな狙いである特に従来の電子図書館化の流れの中で忘れられがちであった図書目録カードを画像化し,Webによる検索を可能とすることにより,遡及入力の完了を待たずに全ての蔵書の検索を実現することに重点をおいている.本研究によって開発された目録カード検索システムにおいては,図書館内にある目録カードと同等のインターフェースを採用した.す...

特許

 
大濱 郁, 阿部 敏久, 有村 博紀, 喜田 拓也
大濱 郁, 阿部 敏久, 有村 博紀, 喜田 拓也