SIGMOD Programming Contest 2016 優勝

秋葉 拓哉
リサーチャー

2016-07-06 20:05:09

はじめまして。7/1 に入社しました新入社員の秋葉です。参加していた SIGMOD Programming Contest 2016 の結果が先週末にアナウンスされ、アドバイザーとして参加していたチームが優勝となりました。コンテストと我々のアプローチを簡単にご紹介したいと思います。

スクリーンショット 2016-07-02 0.43.16.jpg_small2

 

 

SIGMOD Programming Contest とは?

SIGMOD Programming Contest は学会 SIGMOD の併設プログラミングコンテストです。SIGMOD は VLDB と並ぶデータベース分野の最も有名な ACM 系の国際学会です。コンテストの題材も学会のテーマに沿っており、大規模データの処理の高速化を競うものが殆どです。特に、近年に論文が複数出ているようなホットなトピックが選ばれるようです。

ちなみに、参加者は学生に限定されています。チームの人数に制限はありません。チームは教員を一人アドバイザーにすることができます。前職では国立情報学研究所の特任助教でしたので、学生時代の出身研究室の後輩同輩である生田くん、林くん、矢野くん、岩田さんのチームにアドバイザーとして参加しました。特に、実装は生田くんと林くんが全て頑張ってくれました。

100 チーム以上が参加し、5 チームがファイナリストとして選出され、サンフランシスコで開催されていた SIGMOD 2016 にて結果がアナウンスされました。

スクリーンショット 2016-07-02 0.42.09.jpg_small2

 

 

今年のコンテストの問題は?

今年のコンテストの問題は、動的グラフ上のいわゆる最短経路クエリ(より正確には距離クエリ)です。入力として、まず最初に大規模なグラフが与えられます。少し前処理の時間ももらえます。次に、以下の 2 種類のクエリが与えられます。

* 距離の質問:2 頂点が指定されるので、その間の距離を答える
* グラフの変更:辺の追加や削除が指定される

細かいルールは省きましたが概ねこれだけです。とてもシンプルな問題です。グラフは小さいものから大きい物まであり、大きいものは数百万頂点・数千万辺の規模でした。

スクリーンショット 2016-07-02 0.41.29.jpg_small2

 

 

問題の難しさ

一部の方はご存知の通り、実は最短経路クエリに対する索引付け手法は僕のこれまでの専門のど真ん中でした。「ズルい!」という声すら聞こえてきそうです。それでは、果たして本当に簡単に優勝できたのでしょうか?

残念ながら、枝刈りラベリング法などの僕らが作ってきたこれまでの手法は、実は今回はほぼ全く使う事ができませんでした。その理由は、過酷な問題設定にあります。今回の問題設定では、グラフが動的であり、しかも更新の頻度が高すぎるため、ガッツリとした索引データ構造を作ってしまうと、構築・更新のコストのせいで逆に損をしてしまう状況でした。しかも、実はグラフがソーシャルグラフだったり交通グラフだったりと性質もバラバラでした。

 

他チームのアプローチ

先に他のチームのアプローチから紹介します。予想通り、過酷すぎる問題設定故に、索引データ構造を保持するようなアルゴリズム的に興味深い手法を採用しているチームは無かったようです。枝刈りやキャッシュヒット率向上のためのちょっとした処理をグラフに加えるぐらいで、基本的には両側幅優先探索をひたすら高速化していたようです。

 

我々のチームのアプローチ

我々も両側幅優先探索の効率化に尽力しました。しかし、我々のチームは他のチームと異なり、今回の問題設定に適した軽量の索引データ構造を組み込み利用しました。ここが一番面白いかと思うので、この点について重点的に紹介します。

利用した手法は k-All-Path Cover (k-APC) です。k-APC は VLDB’14 で発表されベストペーパー賞を受賞しています。これを使うと、オーバーレイグラフと呼ばれる、元のグラフを「荒くした」グラフのようなものを作ることができます。遠い頂点対の処理をする際、始点終点の近くは元のグラフを探索し、それ以外の大部分はオーバーレイグラフの上だけを探索する、というようにすることができ、処理する頂点数・枝数を減らすことができます。

実際には VLDB’14 で発表された k-APC をそのまま今回の問題設定に使うことはできませんでした。しかし、我々は実はちょうど k-APC の後続研究をしており、その技術をそのまま利用することができました。(ちなみにこの研究は論文投稿中です。)

ただし、k-APC は交通グラフのような平均距離の長いグラフでは効果があるものの、ソーシャルグラフのようなグラフでは効果がありませんでした。そこで、最初にグラフの性質を判定し、k-APC を利用するか否かの判断をするようにしました。

 

感想など

実は、SIGMOD Programming Contest では、2 年前にもグラフ解析の高速化がテーマとなっています。その時にも今回に近いメンバーで参戦したのですが、残念ながら勝つことができませんでした。今回はアルゴリズム的にも面白いアプローチで奇策が功を奏し勝つことができて本当に良かったです。頑張ってくれたメンバー達に心からお礼を言いたいです。

記事の写真は全て筑波大学の塩川先生よりご提供頂きました。ありがとうございます。

言語処理学会年次大会で文法圧縮チュートリアル講義をしてきました

maruyama
リサーチャー

2014-03-24 15:59:41

まるまるです。春がきてますね。東京はだいぶ暖かくなってきました。

先週(3/17〜3/20)行われた言語処理学会第20回年次大会(NLP2014)において「文法圧縮入門:超高速テキスト処理のためのデータ圧縮」というタイトルでチュートリアル講義をさせて頂きました。

講義資料はSlideShareで公開しています。

文法圧縮入門:超高速テキスト処理のためのデータ圧縮(NLP2014チュートリアル) from marugorithm

続きを読む »

異常検知の世界へようこそ

hido
Chief Research Officer

2013-01-17 16:22:38

比戸です。

先週Jubatusの最新0.4.0がリリースされましたが、外れ値検知機能の追加が目玉の一つとなっています(jubaanomaly)。昨年PFIへ入社して初めて手がけた仕事が公開されたということで感慨ひとしおですが、便乗してあまり語られることのない異常検知の世界について書きたいと思います。以下の資料は昨年のFIT2012で使ったものです。

続きを読む »

ウェーブレット木の世界

岡野原 大輔
リサーチャー

2013-01-09 20:43:44

岡野原です。ウェーブレット木の解説を統数研チャンネルにて行いました。

統数研チャンネル(プレミアム会員ならしばらくタイムシフト視聴可能)。

ウェーブレット木は万能のデータ構造であり、系列データ、全文検索、グラフ、二次元情報、フィンガープリントなど様々なデータに対して多くの操作をサポートします。

本解説では大規模データの背景、ウェーブレット木の作り方、使い方、様々なデータへの適用、最前線(ウェーブレット行列)などを紹介しています。本解説は拙著「高速文字列解析の世界」とあわせてみていただけたらと思います。

機械学習と自然言語処理とビッグデータ

岡野原 大輔
リサーチャー

2012-12-25 11:06:59

岡野原です。

情報処理学会主催の連続セミナー「ビッグデータとスマートな社会」での機械学習の回、自然言語処理の回での講演資料を公開しました。

今年はビッグデータという言葉が広まったということで、このテーマで話す機会が多かったです。今はビッグデータというとそれを支えるインフラ、クラウド、DBなどがまず注目されていますが、我々としては実際それを使って何をするのか、何が実現できるのかというところを注目しています。

PFIは元々こうしたデータを分析して価値を提供する(検索エンジンとかもその範疇に入ると思います)ことをずっと続けてきたわけですが、ビッグデータという言葉が広まってくれたおかげでこの考えがより受け入れられ様々な業界の方と随分と話がしやすくなったと思います。

以下の講演資料では、今ビッグデータの中でも機械学習と自然言語処理の分野において我々がどこに注目しているのかを話をしました。

bigdata2012ml okanohara from Preferred Infrastructure Inc,
  • リアルタイム分析が重要な事例の紹介、
  • それを支えるオンライン機械学習の多値分類の技術例
    (昨年のIBIS2011のチュートリアルからの抜粋、雰囲気がわかれば)
  • 大規模リアルタイム解析Jubatusについて

bigdata2012nlp okanohara from Preferred Infrastructure Inc,
  • 自然言語処理を取り巻く世界の変化(多言語化・大規模リアルタイム化)
  • 情報フィルタリングの重要性の増加
  • 業界における自然言語処理
  • 次の自然言語処理を支えるツール

Centroid Path Decompositionを使ったトライでダブル配列と勝負してみた

preferred

2012-06-04 10:58:23

釣りタイトルを付けたかったのですがさっぱり思いつかないのでもう諦めました。徳永です。

今回はCentroid Path Decomposition(以下CPD)についての話を書きます。直訳すると重心パス分解となるでしょうか。Trieを実現するためのテクニック(普通のツリーにも使えるのかな?なかなか難しそうですが…)の一つです。CPDは一年前の弊社岡野原の記事に出てきますが、私のような素人にはあれだけでは理解できない部分があったので、今回はちょっと論文を読んでみました。

続きを読む »

空間木を利用した関連事例の抽出技術

preferred

2012-01-27 19:56:31

はじめまして伊藤です。1月から PFI で働いてます。

今回は関連事例の抽出技術についてお話しします。関連事例の抽出は推薦(レコメンド)サービス等で利用される技術です。ここで事例は扱う対象によって異なります。対象が文書集合であれば、事例は文書を表しますし、E-コマースサービスのログデータであれば、サービスを利用するユーザを表します。
続きを読む »

大規模データ処理勉強会でJubatusに関する発表をしました

海野 裕也
リサーチャー

2011-12-11 23:18:01

金曜日はしっかりバルスしました、海野です。先週の木曜日に、NTTデータ様で行われた大規模データ処理勉強会に出席し、Jubatusに関する発表を行いました。実は、前のポストの @tanakh さんの PFI Seminar と、発表時間が完全にかぶってしまいましたw 資料はこちらです。

当日のUSTREAMもあるようです。

11月のJubatus Workshopでの発表の内、機械学習に関する部分をまとめ直したような内容です。こちらにご参加くださった方には物足りない内容だったかもしれません。オンラインかつ分散という設定での機械学習の理論はまだまだ萌芽的で、今後の大規模データ時代に花開くのかもしれないなぁ、ということを最近思うのでした。

文書解析のための簡潔データ構造

岡野原 大輔
リサーチャー

2011-12-02 18:41:30

岡野原です。

12/1〜12/2に高松で開催されたALSIP2011で文書解析のための簡潔データ構造の最近の進展について話をしてきました。

ここの業界の進展は速く毎年様々な方法が出てきますが、要点だけを上げると

– Wavelet Treeがアルファベットサイズが大きい場合のRank/Select操作だけではなく、2D矩形探索、最頻要素列挙など様々な問題を効率的に解けることが分かってきて非常に重要なデータ構造であることが分かってきた。2D探索も、もはや数億 x数億とかでも解けてしまうので2D探索を利用するような様々な手法が全部現実的になった。

– Top-K Queryが盛り上がっている。検索などデータ構造に問い合わせをする際に、該当する結果を全部を列挙することの高速化は理論的にも難しいが、スコアが高い順(例えばterm frequencyやPageRankなど)にk個だけ列挙するだけなら非常に高速にできる。この場合も大体Wavelet TreeのGreedy Searchが使われるが、Top-Kを効率的に実現するためのデータ構造(グリット上の優先度付キュー)も研究が盛ん

– CFG (Straight Line Program)をベースにしたGrammer Compressionが実用的になって、いろいろなところで使われ始めている。元々Navarroらのグループが多く利用していたRePairだけではなく、九大の研究グループが中心となってやっている方法などはかなり実用的になってきた。現実的な時間での文法抽出だけでなく、抽出した後のデータに対する簡潔データ構造表現も盛ん。

ちなみに高松ということで、ご飯は、うどん、うどん、鍋+うどん、徳島ラーメンでした。

線形識別器でカーネルトリックを使う方法

preferred

2011-09-05 16:01:47

WEB+DB PRESS Vol.64に「作って学ぶ日本語入力」という特集記事を書かせていただきました。徳永です。全国の書店で発売中ですので、ぜひみなさんお買い求めください。(宣伝)

さて今回は、線形識別器でカーネルを使うのと同じ効果を得るための手法を紹介したいと思います。

続きを読む »

12