湊 真一

J-GLOBALへ         更新日: 17/01/06 20:31
 
アバター
研究者氏名
湊 真一
 
ミナト シンイチ
URL
http://www-alg.ist.hokudai.ac.jp/~minato/
所属
北海道大学大学院
部署
大学院情報科学研究科 情報理工学専攻
職名
教授
学位
博士(工学)
その他の所属
国立情報学研究所

プロフィール

北海道大学 大学院 情報科学研究科 情報理工学専攻 大規模知識処理研究室 教授. 大規模離散構造データの表現と演算処理アルゴリズムの研究・教育に従事. 1988年 京都大学 工学部 情報工学科 卒業. 1990年同大学院修士課程, 1995年同博士課程(社会人)修了. 博士(工学). 1990年度より2003年度までNTT研究所に勤務. 1997年1月~12月 スタンフォード大学 計算機科学科 客員研究員. 1999年 NTT未来ねっと研究所 主任研究員. 1999~2000年度 慶応義塾大学 湘南藤沢キャンパス(SFC) 兼任非常勤講師. 2004年度より北海道大学 大学院 情報科学研究科 アルゴリズム研究室 助教授(2007年准教授に名称変更). 2010年10月より同研究室 教授. 2015年度より同研究科 知識メディア研究室(2016年より大規模知識処理研究室に名称変更) 教授(現職). 2015年4月~2020年3月 科研費基盤(S) 離散構造処理系プロジェクト 研究代表者. 2011年度より 早稲田大学 先進グリッド技術研究所 招聘研究員(兼務). 2014年度より 国立情報学研究所 客員教授(兼務). 2015年度より北海道大学 電子科学研究所 附属社会創造数学研究センター 教授(兼務). 2015年度より産業技術総合研究所 人工知能研究センター 客員研究員(兼務). 2000年 情報処理学会山下記念研究賞, 2005年度および2008年度 人工知能学会研究会優秀賞, 2010年 電子情報通信学会 情報・システムソサイエティ論文賞(先見論文). Knuthの名著"The Art of Computer Programming"(Vol.4, Fascicle 1, 2009年)において, 湊が考案したデータ構造「ZDD」が項目として詳しく掲載された(日本人初). 著書 "Binary Decision Diagrams and Applications for VLSI CAD" (Kluwer, 1995年). 2012年8月~2013年4月 日本科学未来館メディアラボ第11期展示「フカシギの数え方」出展. (2013年7月~2014年4月 北海道大学総合博物館にて再展示. ) 2000年~2003年 情報処理学会論文誌 編集委員. 国際ワークショップALSIP2008, 2011, 2012, 2014 Workshop ChairおよびCo-organizer. 2007年~2011年 北大情報科学研究科グローバルCOEプログラム推進担当者. 2009年10月~2016年3月 科学技術振興機構(JST) ERATO 湊離散構造処理系プロジェクト 研究総括(兼務). 2012年~2016年 科研費新学術領域「計算限界解明」総括班連携研究者. 2014年よりJSTさきがけ「社会と調和した情報基盤技術の構築」領域アドバイザ. 2007年より電子情報通信学会 情報ネットワーク(IN)研究会 専門委員. 2014年より電子情報通信学会 コンピュテーション(COMP)研究会 専門委員. 2010年~2014年 人工知能学会評議員. 電子情報通信学会シニア会員, 情報処理学会シニア会員, IEEE, 人工知能学会 各会員.

研究分野

 
 

経歴

 
2015年5月
 - 
現在
産業技術総合研究所 人工知能研究センター 客員研究員
 
2014年4月
 - 
現在
国立情報学研究所 客員教授
 
2010年10月
 - 
現在
北海道大学 大学院 情報科学研究科 教授
 
2010年
 - 
現在
早稲田大学 先進グリッド技術研究所 客員研究員/招聘研究員
 
2009年10月
 - 
2015年3月
科学技術振興機構 (JST) ERATO湊離散構造処理系プロジェクト 研究総括
 
2012年11月
 - 
2013年3月
東京工業大学 非常勤講師
 
2004年3月
 - 
2010年9月
北海道大学 大学院 情報科学研究科 助教授/准教授
 
1998年
 - 
2004年
NTT 未来ねっと研究所 研究主任, 主任研究員
 
1999年
 - 
2001年
慶応義塾大学 湘南藤沢キャンパス 非常勤講師
 
1990年
 - 
1998年
NTT LSI研究所 研究員, 研究主任
 
1997年1月
 - 
1997年12月
スタンフォード大学 客員研究員
 

学歴

 
1994年4月
 - 
1995年3月
京都大学 工学研究科 情報工学専攻 博士後期課程(社会人)
 
1998年4月
 - 
1990年3月
京都大学 工学研究科 情報工学専攻 修士課程
 
1984年4月
 - 
1988年3月
京都大学 工学部 情報工学科
 

委員歴

 
2014年6月
 - 
現在
電子情報通信学会  コンピュテーション研究専門員
 
2014年4月
 - 
現在
科学技術振興機構  さきがけ「社会と調和した情報基盤技術の構築」 アドバイザ
 
2012年
 - 
2014年
電子情報通信学会  論文特集号編集委員
 
2010年
 - 
2014年
人工知能学会  評議員
 
2007年
 - 
2014年
電子情報通信学会  情報ネットワーク研究専門委員会
 
2011年6月
 - 
2012年5月
稲盛財団  京都賞先端技術部門専門委員
 
2010年
 - 
2012年
電子情報通信学会  論文特集号編集委員
 
2010年
 - 
2012年
情報処理学会  論文特集号編集委員
 
2009年
 - 
2011年
電子情報通信学会  論文特集号編集委員
 
2008年
 - 
2010年
電子情報通信学会  論文特集号編集委員
 
2007年
 - 
2009年
電子情報通信学会  論文特集号編集委員
 
2006年
 - 
2008年
電子情報通信学会  論文特集号編集委員
 
2005年
 - 
2007年
電子情報通信学会  論文特集号編集委員
 
2005年
 - 
2007年
情報処理学会  論文特集号編集委員
 
2004年
 - 
2006年
電子情報通信学会  論文特集号編集委員
 
2004年
 - 
2006年
情報処理学会  論文特集号編集委員
 

受賞

 
2013年9月
電子情報通信学会 基礎・境界ソサイエティ Fundamentals Review ベストオーサー賞
 
2012年3月
電子情報通信学会 情報ネットワーク研究会 研究賞
受賞者: 井上 武, 湊 真一
 
2010年
電子情報通信学会 情報・システムソサイエティ論文賞(先見論文)
 
2009年
人工知能学会研究会優秀賞
 
2006年
人工知能学会研究会優秀賞
 
2000年
システムLSI設計技術研究会 研究賞
 
2000年
山下記念研究賞
 
1992年
全国大会奨励賞
 
1992年
回路とシステム軽井沢ワークショップ奨励賞
 
1992年
75周年記念論文優秀賞
 

論文

 
Shuhei Denzumi, Ryo Yoshinaka, Hiroki Arimura and Shin-ichi Minato
Journal of Discrete Applied Mathematics      2015年   [査読有り]
Takeru Inoue,Norihito Yasuda,Shunsuke Kawano,Yuji Takenobu,Shin-ichi Minato,Yasuhiro Hayashi
IEEE Trans. Smart Grid   6(2) 843-852   2015年   [査読有り]
Masaaki Nishino,Norihito Yasuda,Shin-ichi Minato,Masaaki Nagata
Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25-30, 2015, Austin, Texas, USA.   1219-1225   2015年   [査読有り]
Yuma Inoue,Shin-ichi Minato
Reversible Computation - 7th International Conference, RC 2015, Grenoble, France, July 16-17, 2015, Proceedings   186-199   2015年   [査読有り]
Hiroyuki Hanada,Shuhei Denzumi,Yuma Inoue,Hiroshi Aoki,Norihito Yasuda,Shogo Takeuchi,Shin-ichi Minato
WALCOM: Algorithms and Computation - 9th International Workshop, WALCOM 2015, Dhaka, Bangladesh, February 26-28, 2015. Proceedings   161-174   2015年   [査読有り]
Takahisa Toda,Shogo Takeuchi,Koji Tsuda,Shin-ichi Minato
WALCOM: Algorithms and Computation - 9th International Workshop, WALCOM 2015, Dhaka, Bangladesh, February 26-28, 2015. Proceedings   317-322   2015年   [査読有り]
Takeru Inoue, Hiroaki Iwashita, Jun Kawahara, and Shin-ichi Minato
Journal on Software Tools for Technology Transfer (STTT)      2014年   [査読有り]
Yuma Inoue,Takahisa Toda,Shin-ichi Minato
IEICE Transactions   97-A(6) 1171-1179   2014年   [査読有り]
Takeru Inoue,Keiji Takano,Takayuki Watanabe,Jun Kawahara,Ryo Yoshinaka,Akihiro Kishimoto,Koji Tsuda,Shin-ichi Minato,Yasuhiro Hayashi
IEEE Trans. Smart Grid   5(1) 102-111   2014年   [査読有り]
Takeru Inoue,Toru Mano,Kimihiro Mizutani,Shin-ichi Minato,Osamu Akashi
22nd IEEE International Conference on Network Protocols, ICNP 2014, Raleigh, NC, USA, October 21-24, 2014   296-307   2014年   [査読有り]
Yuma Inoue,Shin-ichi Minato
Algorithms and Computation - 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings   103-114   2014年   [査読有り]
Hiroshi Aoki,Takahisa Toda,Shin-ichi Minato
Trends and Applications in Knowledge Discovery and Data Mining - PAKDD 2014 International Workshops: DANTH, BDM, MobiSocial, BigEC, CloudSD, MSMV-MBI, SDA, DMDA-Health, ALSIP, SocNet, DMBIH, BigPMA,Tainan, Taiwan, May 13-16, 2014. Revised Selected Papers   457-469   2014年   [査読有り]
Shogo Takeuchi,Takahisa Toda,Shin-ichi Minato
Trends and Applications in Knowledge Discovery and Data Mining - PAKDD 2014 International Workshops: DANTH, BDM, MobiSocial, BigEC, CloudSD, MSMV-MBI, SDA, DMDA-Health, ALSIP, SocNet, DMBIH, BigPMA,Tainan, Taiwan, May 13-16, 2014. Revised Selected Papers   494-503   2014年   [査読有り]
Norihito Yasuda,Masaaki Nishino,Shin-ichi Minato
Trends and Applications in Knowledge Discovery and Data Mining - PAKDD 2014 International Workshops: DANTH, BDM, MobiSocial, BigEC, CloudSD, MSMV-MBI, SDA, DMDA-Health, ALSIP, SocNet, DMBIH, BigPMA,Tainan, Taiwan, May 13-16, 2014. Revised Selected Papers   504-510   2014年   [査読有り]
Shin-ichi Minato,Takeaki Uno,Koji Tsuda,Aika Terada,Jun Sese
Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2014, Nancy, France, September 15-19, 2014. Proceedings, Part II   422-436   2014年   [査読有り]
Masaaki Nishino,Norihito Yasuda,Shin-ichi Minato,Masaaki Nagata
Proceedings of the 2014 SIAM International Conference on Data Mining, Philadelphia, Pennsylvania, USA, April 24-26, 2014   1073-1081   2014年   [査読有り]
Ryutaro Kurai,Norihito Yasuda,Hiroki Arimura,Shinobu Nagayama,Shin-ichi Minato
Proceedings of the Prague Stringology Conference 2014, Prague, Czech Republic, September 1-3, 2014   3-16   2014年   [査読有り]
Shuhei Denzumi,Jun Kawahara,Koji Tsuda,Hiroki Arimura,Shin-ichi Minato,Kunihiko Sadakane
Experimental Algorithms - 13th International Symposium, SEA 2014, Copenhagen, Denmark, June 29 - July 1, 2014. Proceedings   187-198   2014年   [査読有り]
「おねえさんの問題」の最先端 ― YouTube動画と世界記録 ―
湊 真一
情報処理   54(11) 1152-1159   2013年10月   [査読有り][招待有り]
Compact Complete Inverted Files for Texts and Directed Acyclic Graphs Based on Sequence Binary Decision Diagrams
Shuhei Denzumi, Koji Tsuda, Hiroki Arimura and Shin-ichi Minato
In Proc. of Prague Stringology Conference 2013 (PSC2013)   157-167   2013年9月   [査読有り]
Z-Skip-Links for Fast Traversal of ZDDs Representing Large-Scale Sparse Datasets
Shin-ichi Minato
In Proc. of European Symposium on Algorithms 2013 (ESA 2013)   LNCS 8125 731-742   2013年9月   [査読有り]
BDD/ZDDを基盤とする離散構造処理系の最近の展開
湊 真一
電子情報通信学会 2013ソサイエティ大会 講演論文集   AK-1 SS-1-SS-4   2013年9月   [招待有り]
Enumeration of Region Partitioning for Evalcuation Planning based on ZDD
Atsushi Takizawa, Yasufumi Takechi, Akio Ohta, Naoki Katoh, Takeru Inoue, Takashi Horiyama, Jun Kawahara, and Shin-ichi Minato
In Proc. of International symposium on Operation Research & its Applications (ISORA2013)   64-71   2013年8月   [査読有り]
Recent Research Activities on BDD/ZDD-based Discrete Structure Manipulation
Shin-ichi Minato
In Poc. of 2013 International Workshop on Machine Learning and Applications to Biology (MLAB Sapporo 2013)   13-13   2013年8月   [招待有り]
Techniques of BDD/ZDD: Brief History and Recent Activity
Shin-ichi Minato
IEICE Trans. Inf. & Syst.   E96-D(7) 1419-1429   2013年7月   [査読有り][招待有り]
Efficiently generating classical and vincular pattern avoiding permutations based on permutation decision diagrams
Yuma Inoue, Takahisa Toda, and Shin-ichi Minato
In Proc. of Permutation Patterns 2013   43-44   2013年7月   [査読有り]
Debugging of Reversible Circuits Using PiDDs
Laura Tague, Mathias Soeken, Shin-ichi Minato and Rolf Drechsler
In Proc. of IEEE 43rd International Symposium on Multiple-Valued Logic (ISMVL2013)   316-321   2013年5月   [査読有り]
Recent Topics on BDD/ZDD-Based Discrete Structure Manipulation
Shin-ichi Minato
In Proc. of Reed-Muller Workshop 2013 (RM2013)   1-7   2013年5月   [招待有り]
青木洋士, 湊真一, 湊真一, 山下茂
電子情報通信学会技術研究報告   113(50(COMP2013 9-18)) 149-156   2013年5月
Succinct Indices Based on Zero-Suppressed Binary Decision Diagrams
Shuhei Denzumi, Jun Kawahara, Koji Tsuda, Hiroki Arimura, Kunihiko Sadakane, Shin-ichi Minato
電子情報通信学会コンピュテーション研究会, 信学技報   112(498) 23-30   2013年3月
湊真一, 湊真一
電子情報通信学会技術研究報告   112(498(COMP2012 52-62)) 15-22   2013年3月
Using PiDDs in the Design of Reversible Circuits (Work-In-Progress)
Mathias Soeken, Robert Wille, Shin-ichi Minato, and Rolf Drechsler
In Robert Gluck and Tetsuo Yokoyama, editors, "Reversible Computation, 4th International Workshop RC 2012 Revised Papers,"   LNCS 7581 197-203   2013年2月   [査読有り]
Shared-Memory Parallel Frontier-Based Search
湊 真一
Shogo Takeuchi, Jun Kawahara, Akihiro Kishimoto and Shin-ichi Minato   LNCS 7748 170-181   2013年2月   [査読有り]
井上 祐馬, 戸田 貴久, 湊 真一
情報処理学会研究報告. AL, アルゴリズム研究会報告   2013(5) 1-8   2013年2月
パターン回避順列とは,任意の部分列が特定の順序関係を持たないような順列をいう.パターン回避順列は,VLSIの設計などの応用に現れるフロアプランとの対応が明らかになるなど,応用分野でも近年注目を集めている.本稿では,順列集合を効率的に扱うことができるπDDというデータ構造に基づき,パターン回避順列,およびその拡張である隣接条件付きパターン回避順列を列挙索引化するアルゴリズムを示す.
岩下 洋哲, 中澤 吉男, 川原 純, 宇野 毅明, 湊 真一
情報処理学会研究報告. AL, アルゴリズム研究会報告   2013(8) 1-6   2013年2月
正方形を縦横それぞれn分割してできる(n+1)×(n+1)グリッドグラフにおいて、対角の2頂点を結ぶパスの数はnに対して急激に増大する。例えばn=10に対しては1024もの数となり、もはや一つずつ列挙するようなことはできない大きさである。これまでにKnuthのアルゴリズムに基づく方法でn=21までのパス数が計算されているが、我々はグリッドグラフの性質を利用して計算速度と使用メモリを大幅に改善し、n=23までの計算に成功した。
湊 真一
オペレーションズ・リサーチ : 経営の科学   57(11)    2012年11月   [査読有り][招待有り]
湊 真一
オペレーションズ・リサーチ : 経営の科学   57(11) 597-603   2012年11月   [査読有り][招待有り]
本稿では,与えられたグラフ構造のなかから,ある制約条件を満たすような部分グラフ構造をすべて列挙し,それらをBDD/ZDDを用いて圧縮表現して索引化する技法について述べる.まず,BDD/ZDDとその演算処理系について簡単に説明し,次に,ZDDを用いた高速なパス列挙索引化アルゴリズムSimpathの概要を解説する.このアルゴリズムはKnuthが近年提案したものであるが,制約条件によって多くのバリエーションが存在することから,われわれはそれらを総称して「フロンティア法」と呼んでいる.本稿ではフロ...
川原 純, 湊 真一
オペレーションズ・リサーチ : 経営の科学   57(11) 604-609   2012年11月   [査読有り][招待有り]
本記事では,フロンティア法によるs-tパス列挙の技法を,s-tパスだけではなく,全域木やマッチング,集合被覆などにも適用できることを示す.最初に,フロンティア法を用いて,与えられたグラフのすべての全域木の集合や,すべての根付き全域森の集合を表現するZDDを構築する手法について述べる.次に,s-tパスや全域木の場合を一般化する形で,フロンティア法が適用可能な種々の問題を分類,整理して,統一的な視点から述べる.
井上 武, 高野 圭司, 渡辺 喬之, 川原 純, 吉仲 亮, 岸本 章宏, 津田 宏治, 湊 真一, 林 泰弘
オペレーションズ・リサーチ : 経営の科学   57(11) 610-615   2012年11月   [査読有り][招待有り]
本稿では,フロンティア法を用いた電力網の最適化手法を述べる.電力網の最適化は非凸な組合せ最適化問題であり,バックトラックを伴う伝統的な手法では大域的な最適解を得られる保証がなかった.われわれは,フロンティア法といくつかのアルゴリズムを組み合せて「解のみからなる探索空間(ZDD)」を構築し,最適解の探索を最短経路問題に帰着する.このようにして,最適性の保証された解を容易に発見する.また,この探索空間には,障害復旧構成や損失分布推定など,最適化以外にもさまざまな利用価値があることを示す.
吉仲 亮, 岩下 洋哲, 川原 純, 斎藤 寿樹, 鶴間 浩二, 湊 真一
オペレーションズ・リサーチ : 経営の科学   57(11) 616-622   2012年11月   [査読有り][招待有り]
本稿では,フロンティア法による,与えられたグラフ上の特定の制約を満たす部分グラフ抽出の具体的応用例として,ナンバーリンクとスリザーリンクと呼ばれるパズルそれぞれのための解答器と問題生成器のアルゴリズムを提案し,実験結果を報告する.また,この技術を用いたスリザーリンクの問題作成支援についても議論する.
湊 真一
電子情報通信学会技術研究報告 : 信学技報   112(309) 35-40   2012年11月   [招待有り]
岩下 洋哲, 川原 純, 湊 真一
電子情報通信学会技術研究報告 : 信学技報   112(320) 25-29   2012年11月
Ryo Yoshinaka, Jun Kawahara, Shuhei Denzumi, Hiroki Arimura, and Shin-ichi Minato
Information Processing Letters   112(16) 636-640   2012年8月   [査読有り]
In this article, we disprove the long-standing conjecture, proposed by R.E. Bryant in 1986, that his binary decision diagram (BDD) algorithm computes any binary operation on two Boolean functions in linear time in the input-output sizes. We presen...
Takeru Inoue and Shin-ichi Minato
IEICE Trans. Communications, special section on "Future Internet Technologies Against Present Crises"   E95.B(7) 2210-2221   2012年7月   [査読有り]
Yusaku Kaneta, Shingo Yoshizawa, Shin-ichi Minato, Hiroki Arimura, and Yoshikazu Miyanaga
IEICE Transactions on Information and Systems   E95.D(7) 1847-1857   2012年7月   [査読有り]
In this paper, we propose a novel architecture for large-scale regular expression matching, called dynamically reconfigurable bit-parallel NFA architecture (Dynamic BP-NFA), which allows dynamic loading of regular expressions on-the-fly as well as...
川原 純, 斎藤 寿樹, 湊 真一
電子情報通信学会誌   95(6) 505-511   2012年6月
近年,グラフ上の2点間のパスを列挙する高速なアルゴリズムがKnuthによって提案された.一般的な列挙アルゴリズムは解空間を探索し,解を一つ一つ出力するのに対し,KnuthのアルゴリズムはZero-suppressed Binary Decision Diagram(ZDD)と呼ばれるデータ構造を用いて,全解をコンパクトに表現して出力する.我々はKnuthのアルゴリズムをフロンティア法と名付けて一般化し,様々なグラフ構造の列挙に適用した.本稿ではフロンティア法について解説し,リンクパズルの求...
湊 真一
人工知能学会誌   27(3) 232-238   2012年5月   [査読有り][招待有り]
Yasuyuki Shirai, Koji Tsuruma, Yuko Sakurai, Satoshi Oyama, and Shin-ichi Minato
Proc. of 16th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD 2012), (LNAI 7301, Springer)   7301 183-194   2012年5月   [査読有り]
Finding All Solutions and Instances of Numberlink and Slitherlink by ZDDs
Ryo Yoshinaka, Toshiki Saitoh, Jun Kawahara, Koji Tsuruma, Hiroaki Iwashita, and Shin-ichi Minato
Algorithms   5(2) 176-213   2012年4月   [査読有り]
Synthesis of Semi-Classical Quantum Circuits
Shigeru Yamashita, Shin-ichi Minato, and D. Michael Miller
Journal of Multi-Valued Logic & Soft Computing   18(1) 99-113   2012年1月   [査読有り]
Compiling Bayesian Networks for Parameter Learning Based on Shared BDDs
Masakazu Ishihata, Taisuke Sato and Shin-ichi Minato
Proc. of The 24th Australasian Joint Conference on Artificial Intelligence (AI2011), (LNAI 7106, Springer)   203-212   2011年12月   [査読有り]
SAKURAI Yuko, UEDA Suguru, IWASAKI Atsushi, MINATO Shin‐Ichi, YOKOO Makoto
Proc. of 14th International Conference on Principles and Practice of Multi-Agent Systems (PRIMA-2011), (LNAI 7047, Springer)   7047 4-18   2011年11月   [査読有り]
An Efficient Algorithm for Constructing a Sequence Binary Decision Diagram Representing a Set of Reversed Sequences
Hiroshi Aoki, Shigeru Yamashita and Shin-ichi Minato
Proc. of 2011 IEEE International Confenrece on Granular Computing   54-59   2011年11月   [査読有り]
High-speed String and Regular Expression Matching on FPGA
Yusaku Kaneta, Shingo Yoshizawa, Shin-ichi Minato, and Hiroki Arimura
Proc. of Asia Pacific Signal and Information Processing Association Annual Summit and Conference 2011 (APSIPA ASC 2011      2011年10月   [査読有り]
Implementation of Sequence BDDs in Erlang
Shuhei Denzumi, Hiroki Arimura, Shin-ichi Minato
Proc. of Tenth ACM SIGPLAN Erlang Workshop   90-91   2011年9月   [査読有り]
Notes on Sequence Binary Decision Diagrams: Relationship to Acyclic Automata and Complexities of Binary Set Operations
Shuhei Denzumi, Ryo Yoshinaka, Hiroki Arimura and Shin-ichi Minato
Proc. of Prague Stringology Conference 2011 (PSC2011)   147-161   2011年8月   [査読有り]
MINATO Shin‐ichi
Proc. of 14th International Conference on Theory and Applications of Satisfiability Testing (SAT-2011) (LNCS 6695, Springer)   90-104   2011年6月   [査読有り]
MINATO Shin‐ichi
New Gener Comput   29(2) 223-238   2011年4月   [査読有り][招待有り]
BDD/ZDDを基盤とする離散構造と演算処理系の最近の展開
湊 真一
電子情報通信学会 基礎・境界ソサイエティ Fundamentals Review   4(3) 224-230   2011年1月   [査読有り][招待有り]
Dynamic Reconfigurable Bit-Parallel Architecture for Large-Scale Regular Expression Matching
Yusaku Kaneta, Shingo Yoshizawa, Shin-ichi Minato, Hiroki Arimura and Yoshikazu Miyanaga
Proc. of the 2010 International Conference on Field-Programmable Technology (FPT'10)   21-28   2010年12月   [査読有り]
佐藤 泰介, 湊 真一
人工知能学会誌   25(6) 796-802   2010年11月   [査読有り][招待有り]
KANETA Yusaku, MINATO Shin‐ichi, ARIMURA Hiroki
Lect Notes Comput Sci   6393 372-384   2010年   [査読有り]
YAMASHITA Shigeru, MINATO Shin-ichi, MILLER D. Michael
IEICE transactions on fundamentals of electronics, communications and computer sciences   91(12) 3793-3802   2008年12月   [査読有り]
Recently much attention has been paid to quantum circuit design to prepare for the future “quantum computation era.” Like the conventional logic synthesis, it should be important to verify and analyze the functionalities of generated quantum circu...
岩崎 玄弥, 湊 真一, ツォイクマン トーマス
電子情報通信学会論文誌. D, 情報・システム   91(3) 608-618   2008年3月   [査読有り]
近年,ゼロサプレス型二分決定グラフ(ZBDD: Zero-suppressed Binary Decision Diagrams)を用いたデータベースの効果的な解析手法が提案されている.二分決定グラフ(BDD)は大規模論理関数データの表現方法として広く用いられている.今回はトランザクションデータベースに関して,大規模なアイテムの組合せ集合を処理するのに適したZBDDを用いる.ZBDDのデータ構造は変数の順序に大きく影響を受ける.我々は,ZBDDを生成する前処理としてアイテム変数の順序付けを...
MINATO Shin‐ichi, UNO Takeaki, ARIMURA Hiroki
Lect Notes Comput Sci   5012 234-246   2008年   [査読有り]
MINATO Shin-ichi, ARIMURA Hiroki
人工知能学会論文誌 = Transactions of the Japanese Society for Artificial Intelligence : AI   22(2) 165-172   2007年11月   [査読有り]
Frequent item set mining is one of the fundamental techniques for knowledge discovery and data mining. In the last decade, a number of efficient algorithms for frequent item set mining have been presented, but most of them focused on just enumerat...
MINATO Shin-ichi, ITO Kimihito
人工知能学会論文誌 = Transactions of the Japanese Society for Artificial Intelligence : AI   22(2) 156-164   2007年11月   [査読有り]
In this paper, we present a method of finding symmetric items in a combinatorial item set database. The techniques for finding symmetric variables in Boolean functions have been studied for long time in the area of VLSI logic design, and the BDD (...
湊 真一, 有村 博紀
電子情報通信学会論文誌. D, 情報・システム   89(2) 172-182   2006年2月   [査読有り]
大規模なトランザクションデータを,計算機上でコンパクトに表現して効率的に処理することは,データマイニングにおける重要な基盤技術の一つである.本論文では,VLSI CADの分野で大規模論理関数データの表現法として広く用いられている二分決定グラフ(BDD: Binary Decision Diagrams)をデータマイニングの分野に応用する方法を提案する.BDDの中でも「ゼロサプレス型BDD」(ZBDD: Zero-suppressed BDD)と呼ばれるデータ構造は,大規模な組合せ集合データ...
MINATO Shin‐ichi
Lect Notes Comput Sci   4012 169-181   2006年   [査読有り]
MINATO Shin‐ichi
Lect Notes Comput Sci   4265 321-326   2006年   [査読有り]
井上 武, 谷 誠一郎, 高橋 宏和, 湊 真一, 宮崎 敏明, 豊島 鑑
電子情報通信学会論文誌. D-I, 情報・システム, I-情報処理   88(2) 272-291   2005年2月   [査読有り]
IP multicastは, これまで10年以上にわたって研究開発が進められてきたが, インターネット全域に広く展開されるには至っていない.この原因の一つとして, IP multicastを使ったマルチキャストシステムは, 初期投資が大きいという点が考えられる.FlexcastはIP multicastと同様にルータで分岐を行う方式であるが, マルチキャスト機能をネットワーク層からより上位の層へと移したため, 部分的な導入でサービスを開始できるという特徴をもつ.我々はこのようなFlexca...
Minato Shin-ichi
IEEE Transactions on Computers   51(5) 474-485   2002年5月   [査読有り]
Binary decision diagrams (BDDs) are commonly used for handling Boolean functions because of their excellent efficiency in terms of time and space. However, the conventional BDD manipulation algorithm is strongly based on the hash table technique, ...
湊 真一
応用数理   9(3) 194-206   1999年9月   [査読有り][招待有り]
Manipulation of Boolean functions is one of the fundamental research subject in Computer Science. Many real-life problems in digital system design and testing can be expressed as a sequence of operations on Boolean functions. Recently, BDDs (Binar...
H. Okuno, S. Minato, and H. Isozaki
Information Processing Letters   66(4) 195-199   1998年   [査読有り]
ROTTER Dror, HAMAGUCHI Kiyoharu, MINATO Shin-ichi, YAJIMA Shuzo
IEICE transactions on fundamentals of electronics, communications and computer sciences   80(10) 1774-1781   1997年10月   [査読有り]
Minato has proposed a canonical representation for polynomial functions using zero-suppressed binary decision diagrams (ZBDDs). In this paper, we extend binary moment diagrams (BMDs) proposed by Bryant and Chen to handle variables with degrees hig...
Shin-ichi Minato
Formal Methods in System Design   10(2) 221-242   1997年4月   [査読有り]
Recently, there has been a lot of works on LSI design systems using Binary Decision Diagrams (BDDs), which are efficient representations of Boolean functions. We previously developed a Boolean expression manipulator, that can quickly calculate Boo...
奥乃 博, 湊 真一
情報処理学会論文誌   36(8) 1789-1799   1995年8月   [査読有り]
BDD(二分決定グラフ) はブール関数のコンパクトな表現方法である.我々は,BDDを使用して組合せ問題の複数の解を同時に表現したり,ATMSといった多重文脈型真偽維持システムの機能拡張をする方法を検討してきた.与えられた問題記述あるいは制約条件からBDDを構築する過程は制約充足問題の解法とみなすことができる.本稿では,2種類のBDD,算術論理式が使用できる通常のBDDと組合せ集合が使用できるZBDD (Zero-Suppressed BDD) を取り上げ,それらを用いた制約充足問題の解放を...
Minato Shin-ichi
IEICE transactions on fundamentals of electronics, communications and computer sciences   76(10) 1721-1729   1993年10月   [査読有り]
Recently, there has been a lot of research on solving combinatorial problems using Binary Decision Diagrams (BDDs), which are very efficient representations of Boolean functions. We have already developed a Boolean Expression Manipulator, which ca...
Minato Shin-ichi
IEICE transactions on fundamentals of electronics, communications and computer sciences   76(6) 967-973   1993年6月   [査読有り]
Manipulation of Boolean functions is one of the most important techniques for implementing of VLSI logic design systems. This paper presents a fast method for generating prime-irredundant covers from Binary Decision Diagrams (BDDs), which are effi...
湊 真一
情報処理   34(5) 593-599   1993年5月   [査読有り][招待有り]
湊 真一
電子情報通信学会誌   75(11) 1146-1149   1992年11月   [査読有り]
湊 真一, 石浦 菜岐佐, 矢島 脩三
情報処理学会論文誌   32(1) 77-85   1991年1月   [査読有り]
論理関数を効率よく表現し,論理演算を高速に行うことは,論理設計支援システムを実現する上で重要な問題である.AkersやBryantが提案した二分決定グラフによる表現法は,入力変数の順序を固定することにより論理関数を一意に表すことができ,また,多くの実用的な関数を比較的コンパクトに表現できる.さらに,複数の関数を同時に効率良く表現できるように改良したものを共有二分決定グラフと呼ぶ.本論文では,共有二分決定グラフを用いた論理関数の処理手法について述べ,その効率化手法として,否定エッジ,入力反転...
High-speed String and Regular Expression Matching on FPGA
Yusaku Kaneta, Shingo Yoshizawa, Shin-ichi Minato, and Hiroki Arimura
Proc. of Asia Pacific Signal and Information Processing Association Annual Summit and Conference 2011 (APSIPA ASC 2011)      [査読有り]

Misc

 
菅谷輝治, 戸田貴久, 湊真一
電子情報通信学会技術研究報告   114(509(COMP2014 42-51)) 19-27   2015年3月
鈴木浩史, 湊真一
電子情報通信学会大会講演論文集(CD-ROM)   2015 ROMBUNNO.DS-1-7   2015年2月
井上祐馬, 湊真一, 湊真一
電子情報通信学会大会講演論文集(CD-ROM)   2015 ROMBUNNO.DS-1-12   2015年2月
Shin-ichi Minato
Encyclopedia of Algorithms      2015年   [査読有り]
西野正彬, 安田宜仁, 平尾努, 湊真一, 湊真一, 永田昌明
言語処理学会年次大会発表論文集(Web)   21st E7-2 (WEB ONLY)   2015年
井上祐馬, 湊真一
電子情報通信学会技術研究報告   114(238(COMP2014 25-31)) 25-29   2014年10月
竹延祐二, 河野俊介, 林泰弘, 安田宜仁, 湊真一
電気学会電力技術研究会資料   PE-14(115-117.119-127.187-202) 127-132   2014年9月
竹延祐二, 河野俊介, 林泰弘, 安田宜仁, 湊真一
電気学会電力・エネルギー部門大会論文集(CD-ROM)   2014 ROMBUNNO.P22   2014年9月
井上武, 間野暢, 水谷后宏, 湊真一, 明石修
電子情報通信学会技術研究報告   114(207(IN2014 50-73)) 1-6   2014年9月
瀧澤重志, 武知祥史, 大田章雄, 中野浩太郎, 加藤直樹, 井上武, 堀山貴史, 川原純, 湊真一, 湊真一
日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集   2013 66-67   2013年9月
戸田貴久, 戸田貴久, 湊真一, 湊真一
人工知能学会全国大会論文集(CD-ROM)   27th ROMBUNNO.2E5-OS-09B-4   2013年6月
西野正彬, 安田宜仁, 湊真一, 永田昌明
人工知能学会全国大会論文集(CD-ROM)   27th ROMBUNNO.2E5-OS-09B-3   2013年6月
「今どきの若者」にとっての学会とは
湊 真一
コンピュータ ソフトウェア   30(1) 1-1   2013年5月   [依頼有り]
伝住 周平, 川原 純, 津田 宏治, 有村 博紀, 湊 真一, 定兼 邦彦
電子情報通信学会技術研究報告. COMP, コンピュテーション   112(498) 23-30   2013年3月
多くの実問題の中において,集合族を扱う必要に迫られることはままあることである.大規模な集合族を操作することはウェブからの情報抽出や,情報統合,データマイニングに対する重要な基盤技術である.こういった目的に対し,ゼロサプレス型二分決定グラフ(ZDD)と呼ばれる特別な二分決定グラフ(BDD)が使用されることがある.しかしながらZDDを格納するためには巨大なメモリ領域が必要であり,また所属性判定演算も低速であるという問題がある.本論文では静的なZDDを圧縮した索引である密集ゼロサプレス型二分決定...
岩下 洋哲, 川原 純, 湊 真一
電子情報通信学会技術研究報告. DC, ディペンダブルコンピューティング   112(321) 25-29   2012年11月
近年、グラフ上の2点間の全てのパスを表現したZero-suppressed Binary Decision Diagram(ZDD)を高速に構築するアルゴリズムがKnuthによって発表され、ZDDを用いた新たな列挙手法が注目を集めている。この手法に基づいたこれまでのアプリケーションの多くでは、構築されたZDDに対して様々な条件によるフィルタリングを行って最終的に必要な結果を取り出している。この計算中に発生しやすいメモリ爆発を避けるため、我々は、中間的なZDD構造を構築することなく最終的なZ...
岩下 洋哲, 川原 純, 湊 真一
電子情報通信学会技術研究報告. VLD, VLSI設計技術   112(320) 25-29   2012年11月
近年、グラフ上の2点間の全てのパスを表現したZero-suppressed Binary Decision Diagram(ZDD)を高速に構築するアルゴリズムがKnuthによって発表され、ZDDを用いた新たな列挙手法が注目を集めている。この手法に基づいたこれまでのアプリケーションの多くでは、構築されたZDDに対して様々な条件によるフィルタリングを行って最終的に必要な結果を取り出している。この計算中に発生しやすいメモリ爆発を避けるため、我々は、中間的なZDD構造を構築することなく最終的なZ...
湊 真一
電子情報通信学会技術研究報告. CS, 通信方式   112(309) 35-40   2012年11月
計算機が扱う問題の多くは,離散構造の処理を基盤としている.近年,論理や集合のような基本データ構造を効率よく処理する「BDD」「ZDD」と呼ばれるデータ構造とアルゴリズムが様々な分野で活用されている.このような技法をベースとして,種々の離散構造を統合的に演算処理する技法を体系化し,分野横断的かつ大規模な実問題を高速に処理する技術基盤を構築することを目標として,「JST ERATO湊離散構造処理系プロジェクト」が2009年に採択された.その後,本格的な研究活動を開始してから約2年半が経過し,こ...
湊 真一
日経コンピュータ   0(818) 90-92   2012年9月   [依頼有り]
10の140乗―。配電網の経路組み合わせの数は天文学的数字にのぼる。湊真一氏のチームは、その中から電力損失が最小となる経路をわずか1時間で探索、配電網全体でロスを3%削減できることを証明した。スマートグリッドの実現を後押ししたのは、湊氏が考案した圧縮アルゴリズム「ZDD」だ。―配電網の経路は、どのくらい複雑なのですか。
井上 武, 高野 圭司, 渡辺 喬之, 川原 純, 吉仲 亮, 岸本 章宏, 津田 宏治, 湊 真一, 林 泰弘
電子情報通信学会技術研究報告. IN, 情報ネットワーク   112(134) 37-42   2012年7月
フロンティア法は,与えられたグラフから制約を満たす全サブグラフを探索し,ZDDとして出力するアルゴリズムである.ZDDを出力とすることで,アルゴリズムの結果を最適化や検証などの有用な応用につなげられるという利点がある.本稿は,フロンティア法を用いた電力網の解析手法について述べる.電力網の複雑な制約にもかかわらず,我々はフロンティア法によって最適な網構成を発見することができた.また,通信網への応用についても簡単に紹介する.
湊 真一
電子情報通信学会技術研究報告. IN, 情報ネットワーク   112(134) 31-36   2012年7月
「論理」や「集合」を始めとする様々な離散構造を統合的に演算処理する技法を体系化し,分野横断的かつ大規模な実問題を高速に処理する技術基盤を構築することを目標として「JST ERATO湊離散構造処理系プロジェクト」が発足し,約2年9ヶ月が経過した.この間,多くの興味深い研究成果が得られ始めているが,その中でも,種々の制約条件を満たすグラフ構造をBDD/ZDDを用いて全列挙して索引化する技法(通称フロンティア法)は,Knuthが近年示したパス列挙アルゴリズムSimpathをさらに一般化したもので...
井上 武, 高野 圭司, 渡辺 喬之, 川原 純, 吉仲 亮, 岸本 章宏, 津田 宏治, 湊 真一, 林 泰弘
電子情報通信学会技術研究報告. IN, 情報ネットワーク   112(134) 37-42   2012年7月
伝住 周平, 有村 博紀, 湊 真一
電子情報通信学会技術研究報告. COMP, コンピュテーション   112(93) 9-16   2012年6月
大規模な文字列データを操作することは文字列処理の分野において重要な課題である.本稿では2009年にLoekitoらによって提案された系列二分決定グラフ(Sequence Binary Decision Diagram)と呼ばれるデータ構造を取り扱う.このデータ構造は多数の文字列を要素として含む文字列集合をコンパクトかつ一意に表現し,演算処理を効率良く行える.しかし,今まで提案された処理系では最小限の基本的な集合演算しか用意されていなかった.本稿では系列二分決定グラフの基本的な構造を示した上...
川原 純, 湊 真一
電子情報通信学会技術研究報告. COMP, コンピュテーション   112(93) 1-7   2012年6月
多くの組合せ問題の解全体は集合族として表現可能である.集合族を表すデータ構造として,Zero-suppressed Binary Decision Diagram(ZDD)が用いられる.解全体を表すZDDが構築できれば,組合せ問題の解全体を列挙して出力することは容易であり,さらに,解の効率的な保持,条件を指定しての検索,一様サンプリング等,解の活用が可能となる.我々が提案するフロンティア法は,組合せ問題の解全体を表現するZDDを直接的に構築する手法であり,複数の研究者によって個々の問題に対...
伝住 周平, 有村 博紀, 湊 真一
電子情報通信学会技術研究報告 : 信学技報   112(93) 9-16   2012年6月
配電網の最適経路を探索し、配電ロスを最小化へ 「超高速アルゴリズム」にできること
湊 真一
科学技術振興機構 広報誌 JST NEWS   (5) 8-11   2012年5月   [依頼有り]
青木 洋士, 山下 茂, 湊 真一
電子情報通信学会技術研究報告. COMP, コンピュテーション   112(21) 23-28   2012年4月
二分決定グラフ(Binary Decision Diagram, BDD)は,論理関数を効率良く処理することができるグラフである.BDD処理系のメモリ効率は,節点数に依存する.BDDの節点数を削減する手法として,BDDに属性枝を付与する手法が提案されている.BDDに属性枝を付与すると,同じ部分グラフの数が増加し,同一の節点が効率良く共有される.一方,系列二分決定グラフ(Sequence Binary Decision Diagram, SeqBDD)は,文字列集合を表現するデータ構造である...
井上 武, 高野 圭司, 渡辺 喬之, 川原 純, 吉仲 亮, 岸本 章宏, 津田 宏治, 湊 真一, 林 泰弘
電子情報通信学会総合大会講演論文集   2012(2) "SS-9"-"SS-12"   2012年3月
吉仲 亮, 岩下 洋哲, 川原 純, 斎藤 寿樹, 鶴間 浩二, 湊 真一
電子情報通信学会総合大会講演論文集   2012(2) "SS-5"-"SS-8"   2012年3月
山田 倫大, 湊 真一
電子情報通信学会総合大会講演論文集   2012(1) "S-25"-"S-26"   2012年3月
井上 祐馬, 湊 真一
電子情報通信学会総合大会講演論文集   2012(1) "S-27"-"S-28"   2012年3月
山田 倫大, 湊 真一
電子情報通信学会ソサイエティ大会講演論文集   2011(1) "S-2"   2011年8月
山田 倫大, 湊 真一
電子情報通信学会ソサイエティ大会講演論文集   2011(1) "S-2"   2011年8月
湊 真一
電子情報通信学会技術研究報告. IN, 情報ネットワーク   111(146) 51-56   2011年7月   [依頼有り]
計算機が扱う問題の多くは,離散構造の処理を基盤としている.近年,論理や集合のような基本データ構造を効率よく処理する「BDD」「ZDD」と呼ばれるデータ構造とアルゴリズムが様々な分野で活用されている.このような技法をベースとして,種々の離散構造を統合的に演算処理する技法を体系化し,分野横断的かつ大規模な実問題を高速に処理する技術基盤を構築することを目標として,「ERATO湊離散構造処理系プロジェクト」が2009年10月にJSTにより採択された.2010年4月より5年間の計画で,本格的な研究活...
斎藤 寿樹, 川原 純, 吉仲 亮, 井上 武, 湊 真一
電子情報通信学会技術研究報告. IN, 情報ネットワーク   111(146) 57-62   2011年7月
近年,ZDD(Zero-suppressed Binary Decision Diagram)を用いたグラフ上のパス列挙アルゴリズムが提案された.ZDDとは,組合せ集合を圧縮して表現できるデータ構造である.グラフ上のパスを辺の組合せと同一視すると,ZDDを用いてパスの集合を表現できる.また,ZDDには多様な演算が定義されており,これらを利用すると効率的にパス集合を操作できる.我々は通信ネットワークでの利用を想定し,ZDDを利用したパス管理ソフトウェアを開発した.このソフトウェアは与えられた...
井上 武, 湊 真一
電子情報通信学会技術研究報告. IN, 情報ネットワーク   111(146) 63-68   2011年7月
震災直後は多くの人々がWebで情報収集を行ったため,有用なサイトほどアクセスが増加し,サーバがダウンする傾向がみられた.その際に情報収集・拡散ツールとして利用されたTwitterでは,140文字という制限のため,URL短縮サービスを用いて長いURLを短縮することが多い.短縮URLをクリックすると,ユーザは短縮サービスによって元のURLへと転送される.この振る舞いは,URL短縮サービスが「indirection layer(トラフィックの変向点)」として機能しうることを示唆する.我々はこの特...
川原 純, 斎藤 寿樹, 鈴木 拡, 湊 真一, 吉仲 亮
数理解析研究所講究録   1744(0) 35-41   2011年6月
湊 真一
電子情報通信学会技術研究報告. RECONF, リコンフィギャラブルシステム   111(31) 61-66   2011年5月   [依頼有り]
計算機が扱う問題の多くは、離散構造の処理を基盤としている.近年,論理や集合のような基本データ構造を効率よく処理する「BDD」「ZDD」と呼ばれるデータ構造とアルゴリズムが様々な分野で活用されている.このような技法をベースとして,種々の離散構造を統合的に演算処理する技法を体系化し,分野横断的かつ大規模な実問題を高速に処理する技術基盤を構築することを目標として,FERATO湊離散構造処理系プロジェクト」が2009年10月にJSTにより採択された.2010年4月より5年間の計画で,本格的な研究活...
湊 真一
電子情報通信学会技術研究報告. COMP, コンピュテーション   111(20) 25-32   2011年4月
「順列」は「組合せ」と並んで離散数学や計算機科学の基礎をなす重要な概念であり,ソーティング,順序付け,マッチング,符号化等,多くの局面に現れる.本稿では,「πDD」(順列二分決定グラフ)と呼ぶ新しい二分決定グラフを提案する.πDDは,多数の順列を要素として含む順列集合をコンパクトかつ一意に表現し,演算処理を効率よく行える.中でも,全ての順列の合成を求める直積演算は強力で実用的である.本稿ではπDDの基本的なデータ構造と演算アルゴリズムを示し,さらに簡単な応用例として,あみだくじの解析および...
青木 洋士, 山下 茂, 湊 真一
電子情報通信学会技術研究報告. COMP, コンピュテーション   111(20) 17-23   2011年4月
トライなどの接頭辞の共通部分を同じグラフで表現する系列集合を表すデータ構造において,系列集合に含まれる全ての系列を逆順にした系列集合を効率良く構築できると,接尾辞を指定した系列の検索を効率良く行うことができる.これは,逆順の系列集合に対しての接頭辞を指定した系列の検索が,元の系列集合に対しての接尾辞による検索に対応するからである.本稿では,接頭辞と接尾辞の共通部分を同じグラフで表現するデータ構造の系列二分決定グラフ(Sequence Binary Decision Diagram, Seq...
河原 吉伸, 津田 宏治, 鷲尾 隆, 武田 朗子, 湊 真一
電子情報通信学会技術研究報告. IBISML, 情報論的学習理論と機械学習   110(476) 63-68   2011年3月
特徴選択は,所与の特徴(パラメータや属性,関数などの集合)の中から問題解決に有効なその一部を取り出すタスクであり,機械学習や統計科学,データマイニングなどにおける最も重要な課題の一つである.この問題は近年,解釈性や計算効率の有用性から,疎な解を誘導しやすいノルムを用いた正則化損失関数最小化の枠組みで議論される場合が多い.損失関数の多くは集合関数として見た場合,劣モジュラ性を有するため,本稿では,特徴選択を劣モジュラ関数最適化として定式化する.これは,最も疎な解を誘導しやすいl_0ノルムを用...
斎藤 寿樹, 川原 純, 吉仲 亮, 鈴木 拡, 湊 真一
情報処理学会研究報告. AL, アルゴリズム研究会報告   2011(17) 1-6   2011年2月
与えられたグラフ中のパスを列挙する問題は古典的な問題である.これまで,解を列挙するアルゴリズムや解の数を数えるアルゴリズムがいくつか提案されているが,一般に解の数は極めて多く,解の数を求める問題は #P-完全であるため,満足のいく高速な列挙アルゴリズムの実現は難しい.近年 Knuth は,ZDD (Zero-suppressed Binary Decision Diagram) を用いた任意のグラフの任意の 2 点間を端点とするパスを列挙するアルゴリズムを提案した.ZDD とは集合族を圧縮...
MINATO Shin‐ichi, ONSJOE Mikael, WATANABE Osamu
Res Rep Math Comput Sci Ser C Comput Sci (Web)   (274) WEB ONLY C-274   2011年1月
「おめでとうソサイエティ論文賞」ゼロサプレス型二分決定グラフを用いたトランザクションデータベースの効率的解析手法
湊真一, 有村博紀
電子情報通信学会 情報・システムソサイエティ誌   15(3) 15   2010年11月   [依頼有り]
岡崎 佑太, 湊 真一
情報科学技術フォーラム講演論文集   9(2) 111-113   2010年8月
石畠 正和, 亀谷 由隆, 佐藤 泰介, 湊 真一
電子情報通信学会技術研究報告. IBISML, 情報論的学習理論と機械学習   110(76) 153-163   2010年6月
本論文では命題論理に基づく確率モデルに対するEMアルゴリズムを二分決定グラフと順序符号化を用いて効率的に実行する方法を提案する.提案手法の時間/空間計算量は観測を表現するBDDのサイズに比例し,noisy-ORモデルと隠れマルコフモデルに対する確率学習計算量は従来法と一致する.更に,提案手法は論理に基づくアブダクションより得られた任意の論理式で表される仮説を統計的に評価可能である.本論文ではアブダクションにより得られたバイオデータに関する仮説を提案手法により評価し,化学的にに妥当な仮説が上...
金田 悠作, 湊 真一, 有村 博紀
電子情報通信学会技術研究報告. COMP, コンピュテーション   110(37) 23-29   2010年5月
正規表現は,アルファべットΣの文字と,結合"・"と選択"|"だけから構成されるとき,非巡回正規表現(acyclic regular expression)と呼ばれる.本稿では,非巡回正規表現のクラスに対して,長さmと深さdをもつ非巡回正規表現と長さnをもつ入力テキストを入力として受け取り,O(md)の前処理時間とO(md/w)領域を用いて,O(nmd/w)時間で正規表現照合問題を解く効率よいアルゴリズムを与える.このために,正規表現と等価な非決定性有限オートマトン(NFA)の状態遷移計算を...
金田 悠作, 湊 真一, 有村 博紀
電子情報通信学会総合大会講演論文集   2010(1)    2010年3月
金田 悠作, 吉澤 真吾, 湊 真一, 有村 博紀, 宮永 喜一
電子情報通信学会技術研究報告. CPSY, コンピュータシステム   109(394) 131-136   2010年1月
本稿では,重要なデータストリーム処理問題の一つである正規表現パターン照合に対して,ビット並列型パターン照合手法に基づいた高速なハードウェア指向アルゴリズムを提案する.並列ビット分配と呼ぶ新しいビット並列手法を用いて,文字と,連接,和,Kleeneプラスから構成される非消去的正規表現のクラスに対して,O(md log b+m|Σ|)前処理時間とO(md log b/ω+m|Σ|/ω)領域を用いて,O(mdn log b/ω)実行時間の効率的な正規表現照合アルゴリズムを与える.これはd,b,|...
金 在成, 吉澤 真吾, 金田 悠作, 湊 真一, 有村 博紀, 宮永 喜一
電子情報通信学会技術研究報告. CPSY, コンピュータシステム   109(394) 31-34   2010年1月
FPGA (Field Programmable Gate Array)は製造後も論理回路を再構成することが可能であり,近年ではLSI設計分野以外の研究者や開発者がFPGAを利用して専用計算機の構築する研究例が多く見られる.しかしながら,FPGA研究に参入するには専門のハードウェア知識の習得や設計環境の整備等の障壁を乗り越える必要がある.本報告では,異分野共同研究を円滑に実施するためのeラーニングと連携した遠隔FPGAシステムの開発を行った.本システムは利用者がコンピュータを用意するのみで...
金田 悠作, 吉澤 真吾, 湊 真一, 有村 博紀, 宮永 喜一
電子情報通信学会技術研究報告. RECONF, リコンフィギャラブルシステム   109(395) 131-136   2010年1月
本稿では,重要なデータストリーム処理問題の一つである正規表現パターン照合に対して,ビット並列型パターン照合手法に基づいた高速なハードウェア指向アルゴリズムを提案する.並列ビット分配と呼ぶ新しいビット並列手法を用いて,文字と,連接,和,Kleeneプラスから構成される非消去的正規表現のクラスに対して,O(md log b+m|Σ|)前処理時間とO(md log b/w+m|Σ|/w)領域を用いて,O(mdn log b/w)実行時間の効率的な正規表現照合アルゴリズムを与える.これはd,b,|...
金 在成, 吉澤 真吾, 金田 悠作, 湊 真一, 有村 博紀, 宮永 喜一
電子情報通信学会技術研究報告. RECONF, リコンフィギャラブルシステム   109(395) 31-34   2010年1月
FPGA(Field Programmable Gate Array)は製造後も論理回路を再構成することが可能であり,近年ではLSI設計分野以外の研究者や開発者がFPGAを利用して専用計算機の構築する研究例が多く見られる.しかしながら,FPGA研究に参入するには専門のハードウェア知識の習得や設計環境の整備等の障壁を乗り越える必要がある.本報告では,異分野共同研究を円滑に実施するためのeラーニングと連携した遠隔FPGAシステムの開発を行った.本システムは利用者がコンピュータを用意するのみで遠...
金 在成, 吉澤 真吾, 金田 悠作, 湊 真一, 有村 博紀, 宮永 喜一
電子情報通信学会技術研究報告. VLD, VLSI設計技術   109(393) 31-34   2010年1月
FPGA (Field Programmable Gate Array)は製造後も論理回路を再構成することが可能であり,近年ではLSI設計分野以外の研究者や開発者がFPGAを利用して専用計算機の構築する研究例が多く見られる.しかしながら,FPGA研究に参入するには専門のハードウェア知識の習得や設計環境の整備等の障壁を乗り越える必要がある.本報告では,異分野共同研究を円滑に実施するためのeラーニングと連携した遠隔FPGAシステムの開発を行った.本システムは利用者がコンピュータを用意するのみで...
金田 悠作, 吉澤 真吾, 湊 真一, 有村 博紀, 宮永 喜一
電子情報通信学会技術研究報告. VLD, VLSI設計技術   109(393) 131-136   2010年1月
本稿では,重要なデータストリーム処理問題の一つである正規表現パターン照合に対して,ビット並列型パターン照合手法に基づいた高速なハードウェア指向アルゴリズムを提案する.並列ビット分配と呼ぶ新しいビット並列手法を用いて,文字と,連接,和,Kleeneプラスから構成させる非消去的正規表現のクラスに対して,O(mdlogb+m|Σ|)前処理時間とO(mdlogb/w+m|Σ|/w)領域を用いて,O(mdlogb/w)領域の高速なアルゴリズムを与える.ここで,nは入力長を表わし,mとd,bは,それぞ...
JST戦略的創造研究推進事業EARTOプロジェクトの採択について
湊 真一
北海道大学大学院情報科学研究科広報誌 IST NEWS   (20) 1-2   2010年1月   [依頼有り]
石畠 正和, 亀谷 由隆, 佐藤 泰介, 湊 真一
人工知能学会論文誌   25(3) 475-484   2010年
We propose an Expectation-Maximization (EM) algorithm which works on binary decision diagrams (BDDs). The proposed algorithm, BDD-EM algorithm, opens a way to apply BDDs to statistical learning. The BDD-EM algorithm makes it possible to ...
岡崎 佑太, 湊 真一
情報科学技術フォーラム講演論文集   8(2) 199-201   2009年8月
金崎 健之, 湊 真一
情報科学技術フォーラム講演論文集   8(2) 553-555   2009年8月
D. E. Knuthの名著「The Art of Computer Programming」に、研究成果「ZDD」が掲載されたことについて
湊 真一
北海道大学大学院情報科学研究科広報誌 IST NEWS   (18) 1-2   2009年7月   [依頼有り]
鈴木 拡, 湊 真一
電子情報通信学会技術研究報告. COMP, コンピュテーション   109(54) 1-7   2009年5月
二分決定グラフ(BDD)は,論理関数のグラフ表現であり,大規模な論理関数データでも比較的コンパクトなデータ構造として表現できる.さらに,BDDの特殊な型であるゼロサプレス型BDD(ZDD)は組合せ集合データの表現・処理に適しており,情報科学における様々な問題に応用できる.その一つの例が制約充足問題である.制約充足問題を解くために多くのアルゴリズムが考案されているが,その一方で,解集合の解析や新たな制約を加えて別の制約充足問題を解くということは,また別の問題として残っている.そこで,BDDま...
金田 悠作, 吉澤 真吾, 湊 真一, 有村 博紀, 宮永 喜一
電子情報通信学会総合大会講演論文集   2009(1)    2009年3月
倉井 龍太郎, 湊 真一, ツォイクマン トーマス
電子情報通信学会技術研究報告. PRMU, パターン認識・メディア理解   108(94) 53-57   2008年6月
本研究ではNormalized Compression Distance(NCD)とセロサプレス型BDD(ZBDD)を用いた,テキストの分類手法について提案する.NCDはコルモゴロフ複雑性を利用して定義される文字列同士の距離であるNormalized Information Distanceを近似したものである.NCDは一般的にgzip,bzip2といった既存の圧縮ソフトウェアを利用して計算される.対して本研究ではZBDDの持つアイテム組合せ集合を圧縮して保管する能力を利用してこのNCDを...
倉井 龍太郎, 湊 真一, ツォイクマン トーマス
電子情報通信学会技術研究報告. DE, データ工学   108(93) 53-57   2008年6月
倉井 龍太郎, 湊 真一, ツォイクマン トーマス
電子情報通信学会技術研究報告. PRMU, パターン認識・メディア理解   108(94) 53-57   2008年6月
湊 真一, 石原 晋也
情報処理学会研究報告. SLDM, [システムLSI設計技術]   30 133-140   2001年9月
従来のBDD処理系では, 限界を超える大規模なBDDを扱う記憶あふれを起こし動作不能になるという問題があった.本稿では, BDDの規模によらず一定の実記憶の範囲内で動作し仮想記憶にあふれ出すことのないBDD処理アルゴリズムを提案する.本手法は, ストリーム形式のBDDデータを入出力とし, 主記憶は一時的なワークエリアとしてのみ使用する.実験結果によれば, 従来のBDD処理系が苦手としていた問題ほど本手法は有効であり, 従来の100分の1以下の主記憶容量でも効率良く動作する場合である.さらに...
奥乃 博, 湊 真一
Bit   29(4) 67-77   1997年4月

書籍等出版物

 
ERATO 湊離散構造処理系プロジェクト (担当:編者)
森北出版   2015年4月   ISBN:4627852614
Reversible Computation," 6th International Conference, RC 2014, Kyoto, Japan, July 10-11, 2014. Proceedings
Shigeru Yamashita and Shin-ichi Minato (担当:共編者)
Springer   2014年7月   
2014年度 科学技術振興機構 ERATO湊離散構造処理系プロジェクト講究録
湊 真一 (担当:監修)
2005年6月   
2013年度 科学技術振興機構 ERATO湊離散構造処理系プロジェクト講究録
湊 真一 (担当:監修)
ERATO湊離散構造処理系プロジェクト   2014年7月   
2012年度 科学技術振興機構 ERATO湊離散構造処理系プロジェクト講究録
湊 真一 (担当:監修)
ERATO湊離散構造処理系プロジェクト   2013年7月   
中村 篤祥, 喜田 拓也, 湊 真一 (担当:共著)
ムイスリ出版   2013年4月   ISBN:9784896412154
2011年度 科学技術振興機構 ERATO湊離散構造処理系プロジェクト講究録
湊 真一 (担当:監修)
ERATO湊離散構造処理系プロジェクト   2012年7月   
2010年度 科学技術振興機構 ERATO湊離散構造処理系プロジェクト講究録
湊 真一 (担当:監修)
ERATO湊離散構造処理系プロジェクト   2011年6月   
電子情報通信学会「知識ベース」
湊 真一 (担当:分担執筆, 範囲:論理代数と論理関数)
電子情報通信学会   2011年3月   
Interdisciplinary advances in adaptive and Intelligent assistant Systems: concepts, techniques, applications, and Use
Shin-ichi Minato and Nicolas Spyratos (担当:分担執筆, 範囲:BDD-Based Combinatorial Keyword Query Processing)
IGI Global   2011年1月   
Progress in Representation of Discrete Functions (Synthesis Lectures on Digital Circuits and Systems)
Shin-ichi Minato (担当:分担執筆, 範囲:Data Mining Using Binary Decision Diagrams)
Morgan & Claypool Publishers   2010年5月   
英語で学ぶ計算理論
Thomas Zeugmann, 湊 真一, 大久保 好章 (担当:共著)
コロナ社   2009年3月   
New Frontiers in Applied Data Mining," PAKDD 2008 International Workshops, Osaka, Japan, May 20-23, 2008, Revised Selected Papers
S. Chawla, T. Washio, S. Minato, S. Tsumoto, T. Onoda, S. Yamada, A. Inokuchi (担当:共編者)
Springer   2009年2月   ISBN:978-3-642-00398-1
The VLSI Handbook
Shin-ichi Minato and Saburo Muroga (担当:分担執筆, 範囲:Binary Decision Diagrams)
CRC/IEEE Press   1999年12月   
Binary Decision Diagrams and Applications for VLSI CAD
Shin-ichi Minato
Kluwer Academic Publishers   1996年11月   
Representation of Discrete Functions
Shin-ichi Minato (担当:分担執筆, 範囲:Graph-Based Representations of Discrete Functions)
Kluwer Academic Publishers   1996年5月   

講演・口頭発表等

 
「フカシギの数え方」― 組合せ爆発に立ち向かう最先端アルゴリズム 技術 [招待有り]
湊 真一
国立情報学研究所オープンハウス2013基調講演   2013年6月14日   国立情報学研究所
フカシギの不思議 [招待有り]
湊 真一
日本科学未来館 第11期メディアラボ トークイベ ント   2013年1月19日   日本科学未来館

担当経験のある科目

 
 

Works

 
北海道大学総合博物館 企画展示 「フカシギの数え方」
湊 真一   教材   2013年7月 - 2014年4月
日本科学未来館 研究成果展示 「フカシギの数え方」
湊 真一   教材   2012年8月 - 2013年4月
Knuth; The Art of Computer Programming への研究成果の掲載、および同書の校訂作業への協力
2008年
VSOP: 「重み付き積和集合」計算プログラム
2005年

競争的資金等の研究課題

 
文部科学省: 科学研究費補助金(基盤研究(S))
研究期間: 2015年 - 2019年    代表者: 湊 真一
湊離散構造処理系プロジェクト
科学技術振興機構: ERATO
研究期間: 2009年10月 - 2015年3月    代表者: 湊 真一
文部科学省: 科学研究費補助金(挑戦的萌芽研究)
研究期間: 2012年 - 2012年    代表者: 湊 真一
文部科学省: 科学研究費補助金(基盤研究(A))
研究期間: 2008年 - 2011年    代表者: 有村 博紀
本研究においては,ネットワーク上大規模半構造データに内在する知識をパターンや規則としてとりだことが可能な超調整な半天構造マイニングエンジン技術を開発し,これを現実の多様な半構造データに適用するための周辺技術を開発する.さらに,開発した基盤技術と周辺技術の実装を行い,インターネット上の大規模半構造データからの知識発見実験を行うことを目的とする.
文部科学省: 科学研究費補助金(基盤研究(B))
研究期間: 2008年 - 2011年    代表者: 湊 真一
データベース分野では,当初はハードディスク内にデータを格納することが一般的だったが、2000年以降、中規模クラスの実用的なデータベースが計算機のメモリに納まるようになってきた。そこで本研究課題では、超大規模な単一実メモリ空間を持つ計算機に、二分決定グラフ(BDD)と呼ばれる巨大な圧縮データ構造を構築して、全てを高速アクセス可能なメモリ上に格納し、高速にデータベース解析処理を行う手法を提案し、その研究実用化を進める。