日本語 | English

秋葉 拓哉 (Takuya Akiba)

国立情報学研究所でアルゴリズムを研究している研究者（特任助教）です．

データベース，情報検索，人工知能などに応用を持つ，大規模なデータを効率的に処理するための実用的なアルゴリズムとデータ構造の開発に関心があります． 現在はソーシャルネットワークやウェブグラフのような現実世界の大規模ネットワークに向けた効率的なアルゴリズムの開発に取り組んでいます．

以前は ACM-ICPC, TopCoder, Google Code Jam のようなプログラミングコンテストに積極的に参加していました．私の TopCoder レーティングは最高で 3292 であり，これは当時世界 4 位でした．関連した書籍も執筆しています．

主な研究内容

詳しくは業績リストをご覧下さい．

最短経路やその関連問題に対するクエリ応答

2 点間の最短経路の計算は大規模グラフデータにおける最も重要な処理の 1 つであり， グラフデータベースのクエリ処理やネットワークを考慮した情報検索などの幅広い応用を持ちます． 我々の開発した Pruned Labeling アルゴリズムは， 数億辺規模のネットワークの索引を数時間で構築し， 索引構築後は任意の 2 点間の距離を数マイクロ秒で回答することができます．

Akiba+, SIGMOD'13 Yano+, CIKM'13 Akiba+, ALENEX'14 Akiba+, WWW'14 Akiba+, AAAI'14
Akiba, LSNA'14 Akiba+, ALSIP'12 矢野+, COMP'13 河田+, COMP'13 秋葉+, DEIM'14

木分解によるコア・フリンジ構造のアルゴリズム的活用

現実のネットワークは密に結合している中心のコア部分とその周辺の木に近いフリンジ部分を持つと考えられています． 木分解という道具を用いて，フリンジやコアの性質を解析したり，その性質をアルゴリズム的に活用したりする方法を探っています．

Akiba+, EDBT'12 Maehara+, VLDB'14 秋葉, 学士論文 Akiba, WAAC'11

極大k枝連結部分グラフの列挙

極大k枝連結部分グラフは，多くの応用を持つ密部分グラフのモデル k-core の細分であり，k-core よりも強い連結性を保証します．我々のランダム縮約に基づいたアルゴリズムは，非常にシンプルながら，精度に理論的保証を伴い，数億辺規模のネットワークであっても一時間程度で処理ができます．

Akiba+, CIKM'13 秋葉, 修士論文

主なプログラミングコンテスト戦歴

ACM-ICPC, TopCoder, Google Code Jam のようなプログラミングコンテストは，提示される問題に対し効率的なアルゴリズムを考えそれを正しく実装するという，アルゴリズム設計とプログラム実装の複合競技です．

国内の大会では，高校時代の情報オリンピックをはじめとして多数の優勝経験を持ちます．世界的な大会では，これまで 10 回以上オンラインの予選等を勝ち抜き海外の決勝戦へ招待されています．特に，何度かはトップ 10 入賞の成績を収めています．例えば，Google Code Jam 2010 では世界 9 位，TopCoder Open 2012 では世界 4 位を獲得しました． 東京大学プログラミングコンテストや ACM-ICPC OB/OG の会において問題作成なども担当しています．

詳しくは業績リストやこちらのインタビュー記事をご覧下さい．

国内大会での主な戦歴

  • 優勝: 日本情報オリンピック 2006 (個人戦)
  • 優勝: ACM-ICPC アジア地区予選 2011 福岡大会 (チーム戦)

国際大会での主な戦歴

  • 9 位: Google Code Jam 2010 World Finals (個人戦)
  • 4 位: TopCoder Open 2012 Algorithm Track (個人戦)
  • 銅メダル: ACM ICPC 2012 World Finals (チーム戦)
  • 優勝: ACM ICFP Programming Contest 2013 (チーム戦)

書籍

プログラミングコンテストを通じて得た知見・ノウハウをまとめた本「プログラミングコンテストチャレンジブック」を執筆しました．知識だけでなく設計法や活用法にも焦点を当てた新しいアルゴリズムの本として，日本では計一万部を超える売上を見せ，韓国・台湾・中国にて翻訳版が発売されています．

詳しくは業績リストをご覧下さい．

                       

アルゴリズム解説スライド

最新のアルゴリズムの進展やプログラミングコンテストにおけるテクニック等を紹介した解説スライドを公開しています． 詳しくは業績リストや SlideShare をご覧下さい．

     

ソフトウェア

優れたアルゴリズムを広く使ってもらうため， アルゴリズムを使ってもらいやすい形に実装したものを， オープンソースのソフトウェアライブラリとして公開しています． 詳しくは GitHub などをご覧下さい．

連絡先