湊 真一

J-GLOBALへ         更新日: 18/09/11 20:42
 
アバター
研究者氏名
湊 真一
 
ミナト シンイチ
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周年記念論文優秀賞
 

論文

 
Graph Minors from Simulated Annealing for Annealing Machines with Sparse Connectivity
Yuya Sugie, Yuki Yoshida, Normann Mertig, Takashi Takemoto, Hiroshi Teramoto, Atsuyoshi Nakamura, Ichigaku Takigawa, Shin-ichi Minato, Masanao Yamaoka, and Tamiki Komatsuzaki
Proc. of 7th International Conference on the Theory and Practice of Natural Computing (TPNC 2018      2018年12月   [査読有り]
Scalable Enumeration Approach for Maximizing Hosting Capacity of Distributed Generation
uji Takenobu, Norihito Yasuda, Shin-ichi Minato, and Yasuhiro Hayashi
International Journal of Electrical Power & Energy Systems      2018年12月   [査読有り]
Separate Compilation of Bayesian Networks for Efficient Exact Inference
Shan Gao, Masakazu Ishihata, Shin-ichi Minato
人工知能学会論文誌   33(6A)    2018年11月   [査読有り]
Fast Enumeration of All Pareto-Optimal Solutions for 0-1 Multi-Objective Knapsack Problems Using ZDDs
Hirofumi Suzuki and Shin-ichi Minato
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences      2018年9月   [査読有り]
Fast compilation of graph substructures for counting and enumeration
Teruji Sugaya, Masaaki Nishino, Norihito Yasuda, and Shin‑ichi Minato
Behaviormetrika      2018年6月   [査読有り]
Efficient Bandit Combinatorial Optimization Algorithm with Zero-Suppressed Binary Decision Diagrams
Shinsaku Sakaue, Masakazu Ishihata, and Shin-ichi Minato
Proc. of the 21st International Conference on Artificial Intelligence and Statistics (AISTATS 2018)   585-594   2018年4月   [査読有り]
Evaluation of Annual Energy Loss Reduction Based on Reconfiguration Scheduling
IYuji Takenobu, Norihito Yasuda, Shunsuke Kawano, Yasuhiro Hayashi, and Shin-ichi Minato:
IEEE Trans. Smart Grid   9(3) 1986-1996   2018年3月   [査読有り]
記号モデル検査によるスマートオブジェクトの近接連携シナリオの効率的な検証
蓑田玲緒奈, 湊真一
電子情報通信学会論文誌D 学生論文特集号   J101-D(3) 470-480   2018年3月   [査読有り]
Fast Packet Classification Algorithm for Network-wide Forwarding Behaviors
Takeru Inoue, Toru Mano, Kimihiro Mizutani, Shin-ichi Minato, and Osamu Akashi
Computer Communications   116 101-117   2018年1月   [査読有り]
BDD-Constrained A* Search: A Fast Method for Solving Constrained Shortest-Path Problems
Fumito Takeuchi, Masaaki Nishino, Norihito Yasuda, Takuya Akiba, Shin-ichi Minato and Masaaki Nagata
IEICE Transactions on Information and Systems   E100-D(12) 2945-2952   2017年12月   [査読有り]
Probabilistic CCRN: Reliability Analysis of Ubiquitous Computing Scenarios Using Probabilistic Model Checking
Reona Minoda, Masakazu Ishihata, and Shin-ichi Minato
Proc. of the 11th International Conference on Mobile Ubiquitous Computing, Systems, Services and Technologies (UBICOMM 2017)   85-91   2017年11月   [査読有り]
Fast Message Passing Algorithm Using ZDD-Based Local Structure Compilation
Gao Shan, Masakazu Ishihata, and Shin-ichi Minato
Proc. of the Third Workshop on Advanced Methodologies for Bayesian Networks (AMBN2017)   117-128   2017年9月   [査読有り]
Fast Compilation of s-t Paths on a Graph for Counting and Enumeration
Teruji Sugaya, Masaaki Nishino, Norihito Yasuda, and Shin-ichi Minato
Proc. of the Third Workshop on Advanced Methodologies for Bayesian Networks (AMBN2017)   129-140   2017年9月   [査読有り]
Frontier-based Search for Enumerating All Constrained Subgraphs with Compressed Representation
Jun Kawahara, Takeru Inoue, Hiroaki Iwashita, and Shin-ichi Minato
IEICE Trans. Fundamentals   E100-A(9) 1773-1784   2017年9月   [査読有り]
Statistical Emerging Pattern Mining with Multiple Testing Correction
Junpei Komiyama, Maskazu Ishihata, Hiroki Arimura, Takashi Nishibayashi and Shin-ichi Minato
Proc. of the 23rd SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2017)   897-906   2017年8月   [査読有り]
Power of Enumeration - Recent Topics on BDD/ZDD-Based Techniques for Discrete Structure Manipulation
Shin-ichi Minato
IEICE Transactions on Information and Systems   E100-D(8) 1556-1562   2017年8月   [査読有り][招待有り]
Efficient Scenario Verification of Proximity-based Federations among Smart Objects through Symbolic Model Checking
Reona Minoda and Shin-ichi Minato
Proc. of the 7th International Joint Conference on Pervasive and Embedded Computing and Communication Systems (PEC 2017)   13-21   2017年7月   [査読有り]
Verifying Scenarios of Proximity-based Federations among Smart Objects through Model Checking and Its Advantages
Reona MINODA and Shin-ichi MINATO
IEICE Transactions on Information and Systems   E100-D(6) 1172-1181   2017年6月   [査読有り]
Generating All Patterns of Graph Partitions within a Disparity Bound
Jun Kawahara, Takashi Horiyama, Keisuke Hotta, and Shin-ichi Minato
Proc. of the 11th International Workshop of Algorithms and Computation (WALCOM2017)   LNCS 20267 119-131   2017年3月   [査読有り]
BDD-Constrained A* Search: A Fast Method for Solving Constrained DAG Shortest-Path Problems
Fumito Takeuchi, Masaaki Nishino, Norihito Yasuda, Takuya Akiba, Shin-ichi Minato and Masaaki Nagata
Proc. of Workshops at the 31st AAAI Conference on Artificial Intelligence, The AAAI-17 Workshop on Symbolic Inference and Optimization (SymInfOpt 2017)   944-950   2017年2月   [査読有り]
Compiling Graph Substructures into Sentential Decision Diagrams
Masaaki Nishino, Norihito Yasuda, Shin-ichi Minato and Masaaki Nagata
Proc. of the 31st AAAI Conference on Artificial Intelligence (AAAI2017)   1213-1221   2017年2月   [査読有り]
Dancing with Decision Diagrams: A Combined Approach to Exact Cover
Masaaki Nishino, Norihito Yasuda, Shin-ichi Minato and Masaaki Nagata
Proc. of the 31st AAAI Conference on Artificial Intelligence (AAAI2017)   868-874   2017年2月   [査読有り]
Verifying Scenarios of Proximity-based Federations among Smart Objects through Model Checking
Reona Minoda, Yuzuru Tanaka, and Shin-ichi Minato
Proc. of the Tenth International Conference on Mobile Ubiquitous Computing, Systems, Services and Technologies (UBICOMM 2016)   65-71   2016年10月   [査読有り]
Generating All Solutions of Minesweeper Problem Using Degree Constrained Subgraph Model
Hirofumi Suzuki, Sun Hao, and Shin-ichi Minato
Proc. of the 2016 International Conference on Parallel & Distributed Processing Techniques & Applications (PDPTA'16)   356-362   2016年7月   [査読有り]
Using PiDDs for Nearest Neighbor Optimization of Quantum Circuits
Robert Wille, Nils Quetschlich, Yuma Inoue, Norihito Yasuda, and Shin-ichi Minato
Proc. of the 8th International Conference on Reversible Computation (RC 2016)   181-196   2016年7月   [査読有り]
Maximizing Hosting Capacity of Distributed Generation by Network Reconfiguration in Distribution System
Yuji Takenobu, Shunsuke Kawano, Yasuhiro Hayashi, Norihito Yasuda, and Shin-ichi Minato
Proc. of 19th Power Systems Computation Conference (PSCC 2016)   1-7   2016年6月   [査読有り]
Zero-suppressed Sentential Decision Diagrams
Masaaki Nishino, Norihito Yasuda, Shin-ichi Minato, and Masaaki Nagata
Proc. of the 30th AAAI Conference on Artificial Intelligence (AAAI2016)   1058-1066   2016年2月   [査読有り]
A Dynamic Programming Algorithm for Tree Trimming-based Text Summarization
Takeru Inoue, Hiroaki Iwashita, Jun Kawahara, and Shin-ichi Minato
International Journal on Software Tools for Technology Transfer (STTT)   18(1) 57-66   2016年2月   [査読有り]
Factorization of ZDDs for Representing Bayesian Networks Based on d-Separations
Shan Gao and Shin-ichi Minato
Proc. of the Second International Workshop on Advanced Methodologies for Bayesian Networks (AMBN 2015)   168-183   2015年11月   [査読有り]
Yuma Inoue,Shin-ichi Minato
Reversible Computation - 7th International Conference, RC 2015, Grenoble, France, July 16-17, 2015, Proceedings   9138 186-199   2015年7月   [査読有り]
A Dynamic Programming Algorithm for Tree Trimming-based Text Summarization
Masaaki Nishino, Norihito Yasuda, Tsutomu Hirao, Shin-ichi Minato, Masaaki Nagata
Proc. of the 2015 Annual Conference of the North American Chapter of the ACL (NAACL-HLT 2015)   462-471   2015年5月   [査読有り]
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年   [査読有り]
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月   [査読有り]
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月   [招待有り]
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月   [査読有り]
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月   [査読有り]
湊 真一
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月   [査読有り]
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月   [査読有り]
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月   [査読有り]
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月   [査読有り]
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月   [査読有り][招待有り]
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年   [査読有り]

Misc

 
鈴木 浩史, 石畠 正和, 湊 真一
JSAI大会論文集   2018(0) 4K2OS16b03-4K2OS16b03   2018年6月
<p>ネットワーク設計は運送や通信など様々なサービスやシステムにおける重要な課題であり,グラフ構造を用いてネットワーク設計問題として定式化されている.ネットワーク設計問題は,候補グラフ集合と制約が与えられたとき制約を満たす目的グラフを見つける問題である.いくつかの代表的な制約に対しては,多くのアルゴリズムが提案されてきた.しかし,応用にあたって,より一般的な制約や数式的に記述できない制約が要求された場合,既存のアルゴリズムでは不十分である.そこで我々は,ネットワーク設計問題に対する統一的な...
湊 真一
情報処理   59(3) 243-247   2018年2月
ZDD(ゼロサプレス型二分決定グラフ)は,組合せを要素とする離散的な集合データを計算機上で効率よく扱うためのデータ構造である.ZDDは元々は1990年代にVLSI設計自動化の分野で考案され発展した技法であるが,2000年代以降は,データベース解析,制約充足,組合せ最適化,統計データ処理など,さまざまな用途に広く応用されている.最近,DAシンポジウムにおいてナンバーリンク問題を題材としたアルゴリズムデザインコンテストが開催されることになり,著者らのグループはZDDを用いたソルバを作成して,初...
林 大祐, 羽室 行信, 岡田 克彦, 湊 真一
人工知能基本問題研究会   105 33-39   2018年1月
金森 憲太朗, 石畠 正和, 湊 真一, 有村 博紀
人工知能基本問題研究会   105 50-57   2018年1月
西野 正彬, 安田 宜仁, 湊 真一, 永田 昌明
NTT技術ジャーナル   29(9) 13-16   2017年9月
戸田 貴久、, 斎藤 寿樹, 岩下 洋哲, 川原 純, 湊 真一
コンピュータ ソフトウェア   34(3) 97-120   2017年8月
列挙問題とは,与えられた条件を満たす対象(解)をすべて求める問題であり,電力網解析など社会のさまざまな問題への応用がある.さまざまな組合せ列挙問題に対して,問題の解集合を表現するデータ構造ZDDを高速に求める方法(トップダウンZDD構築法)を通して元の問題を効率的に解く汎用的な手法の研究が近年盛んに行われている.本論文ではトップダウンZDD構築に焦点を絞り,基礎となるアルゴリズムから,複雑な問題制約に対処するための発展的手法,プログラミングツールTdZddの基本的な使い方,さらに,具体的な...
鈴木 浩史, 石畠 正和, 湊 真一
人工知能基本問題研究会   104 26-31   2017年8月
間野 暢, 井上 武, 水谷 公宏, 湊 真一, 明石 修
電子情報通信学会技術研究報告 = IEICE technical report : 信学技報   117(129) 13-18   2017年7月
坂上 晋作, 石畠 正和, 湊 真一
電子情報通信学会技術研究報告 = IEICE technical report : 信学技報   117(110) 43-48   2017年6月
戸田 貴久, 斎藤 寿樹, 岩下 洋哲, 川原 純, 湊 真一
コンピュータ ソフトウェア   34(3) 3_97-3_120   2017年
列挙問題とは,与えられた条件を満たす対象(解)をすべて求める問題であり,電力網解析など社会のさまざまな問題への応用がある.さまざまな組合せ列挙問題に対して,問題の解集合を表現するデータ構造ZDDを高速に求める方法(トップダウンZDD構築法)を通して元の問題を効率的に解く汎用的な手法の研究が近年盛んに行われている.本論文ではトップダウンZDD構築に焦点を絞り,基礎となるアルゴリズムから,複雑な問題制約に対処するための発展的手法,プログラミングツールTdZddの基本的な使い方,さらに,具体的な...
湊 真一
人工知能 : 人工知能学会誌 : journal of the Japanese Society for Artificial Intelligence   31(3) 452-463   2016年5月
川原 純, 堀田 敬介, 堀山 貴史, 湊 真一
日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集   2015 12-13   2015年9月
青木 洋士, 安田 宜仁, 湊 真一
電子情報通信学会技術研究報告 = IEICE technical report : 信学技報   115(205) 35-39   2015年9月
伊藤 華, 井上 祐馬, 湊 真一
情報科学技術フォーラム講演論文集   14(1) 115-116   2015年8月
竹内 文登, 鈴木 浩史, 白石 恒介, 井上 祐馬, 湊 真一
情報科学技術フォーラム講演論文集   14(2) 329-330   2015年8月
鈴木 浩史, 湊 真一
電子情報通信学会技術研究報告 = IEICE technical report : 信学技報   115(15) 15-20   2015年4月
菅谷 輝治, 戸田 貴久, 湊 真一
電子情報通信学会技術研究報告 = IEICE technical report : 信学技報   114(509) 19-27   2015年3月
本研究では,ハイパーグラフの極大独立集合を列挙する効率的な手法を提案する.提案手法では,ハイパーグラフの頂点を効率よく削除,復元するためにDancing linksと呼ばれるデータ構造を採用し,合わせて解の索引付けのためにZero-suppressed binary decision diagrams(ZDD)と呼ばれる圧縮手法を用いる.提案手法は,ハイパーグラフの全ての極大独立集合を列挙する厳密解法である.
井上祐馬, 湊真一, 湊真一
電子情報通信学会大会講演論文集(CD-ROM)   2015 ROMBUNNO.DS-1-12   2015年2月
鈴木浩史, 湊真一
電子情報通信学会大会講演論文集(CD-ROM)   2015 ROMBUNNO.DS-1-7   2015年2月
井上 祐馬, 湊 真一
電子情報通信学会総合大会講演論文集   2015(1) "S-23"-"S-24"   2015年2月
鈴木 浩史, 湊 真一
電子情報通信学会総合大会講演論文集   2015(1) "S-13"-"S-14"   2015年2月
西野正彬, 安田宜仁, 平尾努, 湊真一, 湊真一, 永田昌明
言語処理学会年次大会発表論文集(Web)   21st E7-2 (WEB ONLY)   2015年
Shin-ichi Minato
Encyclopedia of Algorithms      2015年   [査読有り]
ホリルロハマン ムハマド, 湊 真一
人工知能学会全国大会論文集   29 1-4   2015年
竹内 文登, 安田 宜仁, 湊 真一
人工知能学会全国大会論文集   29 1-4   2015年
倉井 龍太郎, 安田 宜仁, 湊 真一
人工知能学会全国大会論文集   29 1-4   2015年
湊 真一
電子情報通信学会誌 = The journal of the Institute of Electronics, Information and Communication Engineers   97(12) 1074-1079   2014年12月
論理関数や集合などの基本的な離散構造データを効率良く演算処理することは,様々な応用分野に共通する基盤技術として非常に重要である.本稿ではBDD(Binary Decision Diagram,二分決定グラフ)及びZDD(Zero-suppressedBDD,ゼロサプレス型BDD)を用いた離散構造データの処理技法を概観する.まずBDDによるブール演算処理,ZDDによる組合せ集合の代数処理について述べ,次に文字列集合や順列集合への発展について述べる.更に最近注目されているグラフ列挙の手法や,そ...
川原 純, 湊 真一
電子情報通信学会誌 = The journal of the Institute of Electronics, Information and Communication Engineers   97(12) 1086-1090   2014年12月
基礎的な離散構造の一つである順列(置換)は,ソーティングや順序付け,マッチング,レイアウト,符号化等,多くの実用的な問題で現れる.近年提案されたπDDは,多数の順列の集合を圧縮された状態で保持するデータ構造であり,二つの順列集合の和集合や共通集合を求める演算,二つの順列集合から任意に要素を取り出して積をとって得られる集合の計算等,各種集合演算をサポートする.本稿では,ルービックキューブの最小手順の計算やあみだくじの線の引き方の数え上げを題材に,πDDの基礎的な事柄について解説し,順列集合の...
井上 祐馬, 湊 真一
電子情報通信学会技術研究報告 = IEICE technical report : 信学技報   114(238) 25-29   2014年10月
オイラー路とは,グラフ上の全ての辺をちょうど1度だけ通る路である.無向グラフにおけるオイラー路の数え上げ問題は#P完全であるが,動的計画法により比較的効率よく計算できる.本稿ではオイラー路が辺の順列であることに着目し,順列集合を扱える決定グラフを用いて,全てのオイラー路の列挙索引化を行う.決定グラフの構築アルゴリズムに動的計画法を応用することで,数え上げと同等の時間での列挙索引化を可能にする.
竹延祐二, 河野俊介, 林泰弘, 安田宜仁, 湊真一
電気学会電力技術研究会資料   PE-14(115-117.119-127.187-202) 127-132   2014年9月
井上 武, 間野 暢, 水谷 后宏, 湊 真一, 明石 修
電子情報通信学会技術研究報告 = IEICE technical report : 信学技報   114(207) 1-6   2014年9月
設定検証や故障検知などの魅力的なSDNアプリは,ネットワーク全体の情報を利用することで従来より高度な機能を提供している.これらの機能はいずれもパケット分類過程を内包するが,従来のパケット分類が「各スイッチ」で行われるアクションを決定すれば十分であったのに対し,SDNでは「ネットワーク全体」でのパケットの振る舞いを決めなければならない.しかし,ネットワーク全体での振る舞いはスイッチごとのアクションの「組合せ」として定義されるため,その探索空間は複雑に分割され,既存のパケット分類手法では扱えな...
竹延祐二, 河野俊介, 林泰弘, 安田宜仁, 湊真一
電気学会電力・エネルギー部門大会論文集(CD-ROM)   2014 ROMBUNNO.P22   2014年9月
ホリルロハマン ムハマド, 湊 真一
情報科学技術フォーラム講演論文集   13(1) 85-86   2014年8月
鮑若愚, 白井康之, 湊真一
第76回全国大会講演論文集   2014(1) 621-622   2014年3月
昨今の就職活動において大半の学生は就職情報サイトを活用している。就職情報サイトは企業情報検索やエントリーを簡単に行えるだけでなく、学生のプロフィールに応じてお薦め企業のリストをメール配信するなどの支援も行う。しかし学生は配信情報を全てチェックすることが困難であり、せっかく提供された情報を無駄にしてしまう場合が多い。本研究ではメール配信された企業情報をもとに、学生の指向性を取り入れ、より適した企業を推薦し、さらに企業の話題性を分かりやすく提示するシステムの提案を行う。
ホリルロハマン ムハマド, 湊 真一
電子情報通信学会総合大会講演論文集   2014(1) "S-19"-"S-20"   2014年3月
安井 雄一郎, 藤澤 克樹, 竹内 聖悟, 湊 真一
ハイパフォーマンスコンピューティングと計算科学シンポジウム論文集   2014 106-115   2013年12月
青木 洋士, 戸田 貴久, 湊 真一
電子情報通信学会技術研究報告. COMP, コンピュテーション   113(252) 1-8   2013年10月
ZDDはアイテムの組合せ集合を表現するデータ構造である.ZDDは様々なデータマイニングなどの問題に利用されている.巨大で疎な組合せ集合を表すZDDは,バランスの悪い形状になりやすく,これは性能の低下の原因になりやすい.本稿では,ある種のZDDとして三分索引化ZDDを提案する.さらに,三分索引化ZDDと従来のZDDとの変換アルゴリズムを示す.計算機実験により,提案データ構造のZDDと比べた優位性を示す.
瀧澤 重志, 武知 祥史, 大田 章雄, 中野 浩太郎, 加藤 直樹, 井上 武, 堀山 貴史, 川原 純, 湊 真一
日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集   2013 66-67   2013年9月
瀧澤重志, 武知祥史, 大田章雄, 中野浩太郎, 加藤直樹, 井上武, 堀山貴史, 川原純, 湊真一, 湊真一
日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集   2013 66-67   2013年9月
西野正彬, 安田宜仁, 湊真一, 永田昌明
人工知能学会全国大会論文集(CD-ROM)   27th ROMBUNNO.2E5-OS-09B-3-4   2013年6月
戸田貴久, 戸田貴久, 湊真一, 湊真一
人工知能学会全国大会論文集(CD-ROM)   27th ROMBUNNO.2E5-OS-09B-4-4   2013年6月
伝住 周平, 川原 純, 津田 宏治, 有村 博紀, 湊 真一, 定兼 邦彦
電子情報通信学会技術研究報告. COMP, コンピュテーション   112(498) 23-30   2013年3月
多くの実問題の中において,集合族を扱う必要に迫られることはままあることである.大規模な集合族を操作することはウェブからの情報抽出や,情報統合,データマイニングに対する重要な基盤技術である.こういった目的に対し,ゼロサプレス型二分決定グラフ(ZDD)と呼ばれる特別な二分決定グラフ(BDD)が使用されることがある.しかしながらZDDを格納するためには巨大なメモリ領域が必要であり,また所属性判定演算も低速であるという問題がある.本論文では静的なZDDを圧縮した索引である密集ゼロサプレス型二分決定...
湊 真一
コンピュータソフトウェア   30(1)    2013年1月
岩下 洋哲, 川原 純, 湊 真一
電子情報通信学会技術研究報告. DC, ディペンダブルコンピューティング   112(321) 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月
湊 真一
電子情報通信学会技術研究報告. IN, 情報ネットワーク   112(134) 31-36   2012年7月
「論理」や「集合」を始めとする様々な離散構造を統合的に演算処理する技法を体系化し,分野横断的かつ大規模な実問題を高速に処理する技術基盤を構築することを目標として「JST ERATO湊離散構造処理系プロジェクト」が発足し,約2年9ヶ月が経過した.この間,多くの興味深い研究成果が得られ始めているが,その中でも,種々の制約条件を満たすグラフ構造をBDD/ZDDを用いて全列挙して索引化する技法(通称フロンティア法)は,Knuthが近年示したパス列挙アルゴリズムSimpathをさらに一般化したもので...
井上 武, 高野 圭司, 渡辺 喬之, 川原 純, 吉仲 亮, 岸本 章宏, 津田 宏治, 湊 真一, 林 泰弘
電子情報通信学会技術研究報告. IN, 情報ネットワーク   112(134) 37-42   2012年7月
フロンティア法は,与えられたグラフから制約を満たす全サブグラフを探索し,ZDDとして出力するアルゴリズムである.ZDDを出力とすることで,アルゴリズムの結果を最適化や検証などの有用な応用につなげられるという利点がある.本稿は,フロンティア法を用いた電力網の解析手法について述べる.電力網の複雑な制約にもかかわらず,我々はフロンティア法によって最適な網構成を発見することができた.また,通信網への応用についても簡単に紹介する.
川原 純, 湊 真一
電子情報通信学会技術研究報告. COMP, コンピュテーション   112(93) 1-7   2012年6月
多くの組合せ問題の解全体は集合族として表現可能である.集合族を表すデータ構造として,Zero-suppressed Binary Decision Diagram(ZDD)が用いられる.解全体を表すZDDが構築できれば,組合せ問題の解全体を列挙して出力することは容易であり,さらに,解の効率的な保持,条件を指定しての検索,一様サンプリング等,解の活用が可能となる.我々が提案するフロンティア法は,組合せ問題の解全体を表現するZDDを直接的に構築する手法であり,複数の研究者によって個々の問題に対...
伝住 周平, 有村 博紀, 湊 真一
電子情報通信学会技術研究報告. COMP, コンピュテーション   112(93) 9-16   2012年6月
大規模な文字列データを操作することは文字列処理の分野において重要な課題である.本稿では2009年にLoekitoらによって提案された系列二分決定グラフ(Sequence Binary Decision Diagram)と呼ばれるデータ構造を取り扱う.このデータ構造は多数の文字列を要素として含む文字列集合をコンパクトかつ一意に表現し,演算処理を効率良く行える.しかし,今まで提案された処理系では最小限の基本的な集合演算しか用意されていなかった.本稿では系列二分決定グラフの基本的な構造を示した上...
伝住 周平, 有村 博紀, 湊 真一
電子情報通信学会技術研究報告 : 信学技報   112(93) 9-16   2012年6月
配電網の最適経路を探索し、配電ロスを最小化へ 「超高速アルゴリズム」にできること
湊 真一
科学技術振興機構 広報誌 JST NEWS   (5) 8-11   2012年5月   [依頼有り]
青木 洋士, 山下 茂, 湊 真一
電子情報通信学会技術研究報告 : 信学技報   112(21) 23-28   2012年4月
井上 祐馬, 湊 真一
電子情報通信学会総合大会講演論文集   2012(1) "S-27"-"S-28"   2012年3月
吉仲 亮, 岩下 洋哲, 川原 純, 斎藤 寿樹, 鶴間 浩二, 湊 真一
電子情報通信学会総合大会講演論文集   2012(2) "SS-5"-"SS-8"   2012年3月
山田 倫大, 湊 真一
電子情報通信学会総合大会講演論文集   2012(1) "S-25"-"S-26"   2012年3月
井上 武, 高野 圭司, 渡辺 喬之, 川原 純, 吉仲 亮, 岸本 章宏, 津田 宏治, 湊 真一, 林 泰弘
電子情報通信学会総合大会講演論文集   2012(2) "SS-9"-"SS-12"   2012年3月
山田 倫大, 湊 真一
電子情報通信学会ソサイエティ大会講演論文集   2011(1) "S-2"   2011年8月
井上 武, 湊 真一
電子情報通信学会技術研究報告. IN, 情報ネットワーク   111(146) 63-68   2011年7月
震災直後は多くの人々がWebで情報収集を行ったため,有用なサイトほどアクセスが増加し,サーバがダウンする傾向がみられた.その際に情報収集・拡散ツールとして利用されたTwitterでは,140文字という制限のため,URL短縮サービスを用いて長いURLを短縮することが多い.短縮URLをクリックすると,ユーザは短縮サービスによって元のURLへと転送される.この振る舞いは,URL短縮サービスが「indirection layer(トラフィックの変向点)」として機能しうることを示唆する.我々はこの特...
斎藤 寿樹, 川原 純, 吉仲 亮, 井上 武, 湊 真一
電子情報通信学会技術研究報告. IN, 情報ネットワーク   111(146) 57-62   2011年7月
近年,ZDD(Zero-suppressed Binary Decision Diagram)を用いたグラフ上のパス列挙アルゴリズムが提案された.ZDDとは,組合せ集合を圧縮して表現できるデータ構造である.グラフ上のパスを辺の組合せと同一視すると,ZDDを用いてパスの集合を表現できる.また,ZDDには多様な演算が定義されており,これらを利用すると効率的にパス集合を操作できる.我々は通信ネットワークでの利用を想定し,ZDDを利用したパス管理ソフトウェアを開発した.このソフトウェアは与えられた...
湊 真一
電子情報通信学会技術研究報告. IN, 情報ネットワーク   111(146) 51-56   2011年7月   [依頼有り]
計算機が扱う問題の多くは,離散構造の処理を基盤としている.近年,論理や集合のような基本データ構造を効率よく処理する「BDD」「ZDD」と呼ばれるデータ構造とアルゴリズムが様々な分野で活用されている.このような技法をベースとして,種々の離散構造を統合的に演算処理する技法を体系化し,分野横断的かつ大規模な実問題を高速に処理する技術基盤を構築することを目標として,「ERATO湊離散構造処理系プロジェクト」が2009年10月にJSTにより採択された.2010年4月より5年間の計画で,本格的な研究活...
川原 純, 斎藤 寿樹, 鈴木 拡, 湊 真一, 吉仲 亮
数理解析研究所講究録   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) 17-23   2011年4月
トライなどの接頭辞の共通部分を同じグラフで表現する系列集合を表すデータ構造において,系列集合に含まれる全ての系列を逆順にした系列集合を効率良く構築できると,接尾辞を指定した系列の検索を効率良く行うことができる.これは,逆順の系列集合に対しての接頭辞を指定した系列の検索が,元の系列集合に対しての接尾辞による検索に対応するからである.本稿では,接頭辞と接尾辞の共通部分を同じグラフで表現するデータ構造の系列二分決定グラフ(Sequence Binary Decision Diagram, Seq...
湊 真一
電子情報通信学会技術研究報告. COMP, コンピュテーション   111(20) 25-32   2011年4月
「順列」は「組合せ」と並んで離散数学や計算機科学の基礎をなす重要な概念であり,ソーティング,順序付け,マッチング,符号化等,多くの局面に現れる.本稿では,「πDD」(順列二分決定グラフ)と呼ぶ新しい二分決定グラフを提案する.πDDは,多数の順列を要素として含む順列集合をコンパクトかつ一意に表現し,演算処理を効率よく行える.中でも,全ての順列の合成を求める直積演算は強力で実用的である.本稿ではπDDの基本的なデータ構造と演算アルゴリズムを示し,さらに簡単な応用例として,あみだくじの解析および...
河原 吉伸, 津田 宏治, 鷲尾 隆, 武田 朗子, 湊 真一
電子情報通信学会技術研究報告. 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モデルと隠れマルコフモデルに対する確率学習計算量は従来法と一致する.更に,提案手法は論理に基づくアブダクションより得られた任意の論理式で表される仮説を統計的に評価可能である.本論文ではアブダクションにより得られたバイオデータに関する仮説を提案手法により評価し,化学的にに妥当な仮説が上...
金田 悠作, 湊 真一, 有村 博紀
情報処理学会研究報告   2010(1)    2010年6月
金田 悠作, 湊 真一, 有村 博紀
電子情報通信学会技術研究報告. 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月
金田 悠作, 吉澤 真吾, 湊 真一, 有村 博紀, 宮永 喜一
電子情報通信学会技術研究報告. VLD, VLSI設計技術   109(393) 131-136   2010年1月
本稿では,重要なデータストリーム処理問題の一つである正規表現パターン照合に対して,ビット並列型パターン照合手法に基づいた高速なハードウェア指向アルゴリズムを提案する.並列ビット分配と呼ぶ新しいビット並列手法を用いて,文字と,連接,和,Kleeneプラスから構成させる非消去的正規表現のクラスに対して,O(mdlogb+m|Σ|)前処理時間とO(mdlogb/w+m|Σ|/w)領域を用いて,O(mdlogb/w)領域の高速なアルゴリズムを与える.ここで,nは入力長を表わし,mとd,bは,それぞ...
金 在成, 吉澤 真吾, 金田 悠作, 湊 真一, 有村 博紀, 宮永 喜一
電子情報通信学会技術研究報告. VLD, VLSI設計技術   109(393) 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,|...
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) 553-555   2009年8月
岡崎 佑太, 湊 真一
情報科学技術フォーラム講演論文集   8(2) 199-201   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ま...

書籍等出版物

 
2017年度 JSPS 科研費基盤(S)「離散構造処理系の基盤アルゴリズムの研究」 講究録
湊 真一
基盤(S)離散構造処理系プロジェクト,   2018年7月   
人工知能学大事典, 人工知能学会編
湊 真一 (担当:分担執筆, 範囲:BDD とZDD, 6章-36節, pp. 344-34)
共立出版   2017年7月   
2016年度 JSPS 科研費基盤(S)「離散構造処理系の基盤アルゴリズムの研究」 講究録
湊 真一 (担当:監修)
基盤(S)離散構造処理系プロジェクト,   2017年6月   
鈴木 譲, 植野 真臣, 黒木 学, 清水 昌平, 湊 真一, 石畠 正和, 樺島 祥介, 田中 和之, 本村 陽一, 玉田 嘉紀 (担当:分担執筆, 範囲:離散構造処理の技法と確率モデル, 第5章, pp. 125-144)
共立出版   2016年7月   ISBN:4320111397
2015年度 JST ERATO湊離散構造処理系プロジェクト / JSPS 科研費基盤(S)「離散構造処理系の基盤アルゴリズムの研究」 講究録
湊 真一 (担当:監修)
基盤(S)離散構造処理系プロジェクト,   2016年6月   
2014年度 科学技術振興機構 ERATO湊離散構造処理系プロジェクト講究録
湊 真一 (担当:監修)
ERATO湊離散構造処理系プロジェクト   2015年6月   
ERATO 湊離散構造処理系プロジェクト (担当:編者)
森北出版   2015年4月   ISBN:4627852614
Applications of Zero-Suppressed Decision Diagrams (Synthesis Lectures on Digital Circuits and Systems)
T. Sasao and J. Butler, editor (担当:分担執筆, 範囲:The Power of Enumeration - BDD/ZDD-Based Algorithms for Tackling Combinatorial Explosion, chapter 3, pp. 49-62)
Morgan & Claypool Publishers   2014年11月   
Encyclopedia of Algorithms
Ming-Yang Kao, editor (担当:分担執筆, 範囲:Counting by ZDD)
2014年9月   
Reversible Computation," 6th International Conference, RC 2014, Kyoto, Japan, July 10-11, 2014. Proceedings
Shigeru Yamashita and Shin-ichi Minato (担当:共編者)
Springer   2014年7月   
2013年度 科学技術振興機構 ERATO湊離散構造処理系プロジェクト講究録
湊 真一 (担当:監修)
ERATO湊離散構造処理系プロジェクト   2014年7月   
2012年度 科学技術振興機構 ERATO湊離散構造処理系プロジェクト講究録
湊 真一 (担当:監修)
ERATO湊離散構造処理系プロジェクト   2013年7月   
中村 篤祥, 湊 真一, 喜田 拓也 (担当:共著)
ムイスリ出版   2013年4月   ISBN:489641215X
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月   ISBN:4339024384
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

講演・口頭発表等

 
「フカシギの数え方」― 組合せ爆発に立ち向かう最先端アルゴリズム 技術 [招待有り]
湊 真一
国立情報学研究所オープンハウス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)と呼ばれる巨大な圧縮データ構造を構築して、全てを高速アクセス可能なメモリ上に格納し、高速にデータベース解析処理を行う手法を提案し、その研究実用化を進める。