乱択データ構造の最新事情 −MinHash と HyperLogLog の最近の進歩−

本日，PFI セミナーにて「乱択データ構造の最新事情 −MinHash と HyperLogLog の最近の進歩−」というタイトルで話をさせてもらいました．スライドは以下になります．

Ustream の録画もあります．

内容としては，以下の操作を効率的に行うための集合に関するデータ構造 (Sketch) の最近の進歩を紹介しました．

  • 集合の類似度の推定 (Jaccard 係数)
  • 集合異なり数の推定 (distinct counting)

どちらも重要かつ基礎的な操作で，b-bit MinHash や HyperLogLog など，既に実用的な手法が提案されており，実際にも使われています．しかし，2014 年になって，Odd Sketch や HIP Estimator という，これらをさらに改善する手法が立て続けに発表されました．

今日の発表ではこれを踏まえ，まず MinHash の基礎を復習し，次に今まで最も有力な手法であった b-bit MinHash，HyperLogLog の説明をし，最後にこれらの新しい手法を紹介しました．新しい手法は両方とも，新しいアイディアに基づく本質的な改善ながら，手法自体はかなりシンプルなので，実装も困難ではないと思います．是非使ってみて下さい．

今日の発表は主に以下の 2 つの論文に基づいています．より詳しい情報は論文をご参照下さい．

  • Michael Mitzenmacher, Rasmus Pagh, and Ninh Pham. Efficient estimation for high similarities using odd sketches. In WWW 2014.
  • Edith Cohen. All-Distances Sketches, Revisited: HIP Estimators for Massive Graphs Analysis. In PODS 2014.

Cache-Oblivious データ構造入門 @DSIRNLP#5

「データ構造と情報検索と言語処理勉強会」にお邪魔して，「Cache-Oblivious データ構造入門」という発表をさせてもらいました．

実はこういうインターネットから集う感じのいわゆる勉強会に参加するのは初めてでした．発表も初めてなので結構緊張していて大変だったのですが，参加者の皆さんがとても優しくて助かりました．懇親会 (新年会) もとても楽しかったです．主催の overlast さん，会場を提供してくださっていたスマートニュースさん，どうもありがとうございました．


発表の内容は以下のような感じです．

  1. DB の索引としての B 木の利点の復習
  2. Cache-Oblivious の考え方
  3. vEB レイアウト (Cache-Oblivious の例)
  4. 実際の事例紹介 (TokuDB)

ちなみに，実況ツイートをしてくださっていた方々の説明が大変良い要約になっています（僕の舌足らずの説明よりよっぽどわかりやすい，ありがとうございます！）．ハッシュタグつきのツイートを適当に引用させてもらいます．一方で，データ構造の説明部分は図を見てもらえば結構一発に近いと思うのでそちらを見てもらえればと思います．

WWW'14 に論文採択

論文が国際学会 WWW'14 (23rd International World Wide Web Conference) に採択されました！ WWW はその名の通りウェブに関するトップ学会で，比較的新しいものの最近ではかなりの人気を誇る学会だと思います．

WWW の最近の人気は，例えば Microsoft Academic Search の学会ランキングで伺うことができます．最近 5 年に限定すると，なんとコンピュータ科学の全分野合わせても 2 位*1，最近 10 年にしても 3 位ということで，かなり順位が高いです．その分もちろん競争も激しく，採択率は 84/650 = 12.9% だそうです． 所属する河原林グラフ ERATO からもかなりの本数が提出されたようですが，知る限り残ったのは僕の論文だけのようです．

論文タイトルは "Dynamic and Historical Shortest-Path Distance Queries on Large Evolving Networks by Pruned Landmark Labeling" というもので，またもや研究室同期の岩田と NII の吉田さんとの共著になっています．

内容について

論文タイトルからわかるとおり，これまた SIGMOD'13，CIKM'13，ALENEX'14 と出してきた最短路クエリの論文の続きの新編です．今回も対象は大規模なソーシャルネットワークやウェブグラフです．そして，論文タイトルの冒頭になっているとおり，今回は Dynamic と Historical というのが新しい点です．この論文の貢献は主に 2 つあります．

貢献 1: Dynamic Update

今までの最短路クエリではグラフは静的であることを仮定し，グラフの変更を反映するには前計算をしなおす必要がありました．しかし，今回提案する動的更新アルゴリズムを組み込むと，なんとグラフの変更を即座に反映することができるようになります． ちなみに 1 本の枝に対する処理は数ミリ秒で終わります．

ただし，対応しているグラフの変更は今の所残念ながら辺の追加のみです．しかし，現実のネットワークでは辺の追加の方が削除よりも遥かに多いため，実用的にはそれでもかなり価値があるという事を主張しています．今までは再構築をするまで反映されなかった変更が，追加だけとはいえ即座に追加されるのは有用であると思います．

貢献 2: Historical Queries

さらに，データ構造にもう少し情報を入れることにより，最新の状態での距離だけでなく，「昔，時間 t の頃の距離はいくつだったか？」や「距離が変化したのはいつか？」というような質問に答えることができるということを提案しています．

これを使うと，辺に時間の入った大規模なグラフデータにおいて，距離を使った指標がどのように時間経過と共に変化していくかを観察できるようになります．下図はその例です．

(Fig.3 は平均距離と有効直径の変化，Fig.4 は近接中心性の変化，Fig.5 は temporal hop plot です．）

論文採択について

今回の論文も，実は最初に VLDB に投稿して落とされていて，その次で WWW に投稿しました．

この論文に限らず，VLDB では，正直毎回かなり納得の行かない査読コメントと共に落とされています．かなり頭に来たので，今回は DB 分野はもういいかなということで思い切って WWW に投稿するという判断をしました．これは，どうやら正解だったようです．同等の競争率のはずですが，かなり高い評価と共に論文は採択されました．

とはいえもちろん，VLDB に出した原稿をただ WWW に再提出して採択されたわけではなく，かなり念入りに修正をしています．特に，WWW の査読でウケるように，「何ができるか」に重点を起き，上で示した例などを追加しました．また，VLDB で納得してもらえなかった点の議論の防御を強めました．

特に今回は，「更新で削除が対応していない」という点がかなりきつい防御ポイントで，VLDB で落とされたのもその点の影響も大きかったと思います． 「WWW に 5 年で 6 本」で有名な松尾先生も仰っている通り，論文を通すためには失点を少なくすることが重要であり，こういう大きな突っ込まれ得るポイントがあると，例え面白くても「論文を通す」という観点からは結構厳しいです．そのような部分を今回は議論で押し切ることができたというのは少し自信につながり嬉しいです．

*1:1 位は納得の CVPR ですね． その次という順位は結構すごいように思います．このランク付けがどれだけ意味のあるものかという議論の余地は当然ありますが，少なくともこの指標ではこの順位だということに一定の意味はあると思います．

ALENEX'14 に論文採択

国際学会 ALENEX 2014 に論文が採択されました．ALENEX (Meeting on Algorithm Engineering & Experiments) は SIAM によって開催される実験系アルゴリズム (experimental algorithmics) を扱う最も有名な会議の 1 つで，理論系アルゴリズムのトップ学会 SODA (Symposium on Discrete Algorithms) に併設して開催されます．発表は来年の 1 月にアメリカのオレゴンです．

今回の論文は "Fast Shortest-path Distance Queries on Road Networks by Pruned Highway Labeling" というタイトルで，研究室の後輩の河田君，同期の岩田，NII の河原林先生との共著です．タイトルからご察しの通り，SIGMOD'13 論文から続く最短路クエリの手法 Pruned Landmark Labeling (PLL) のシリーズ 3 作目です（SIGMOD'13, CIKM'13 *1, そして今回 ALENEX'14）．

内容

今回の論文の題材は，道路ネットワークにおける最短路クエリのアルゴリズムです．前回の PFI セミナーの後半で扱っていたトピックです．

SIGMOD で発表した最初の PLL の論文では，対象とするネットワークをソーシャルネットワークやウェブグラフのようないわゆる「複雑ネットワーク」とし，それらのネットワークの特徴を活用していました．道路ネットワークは，それらのネットワークに対し性質が随分異なる（例えば，とても次数の高いハブのような頂点が存在しない）ので，そのままでは道路ネットワークで高い性能を出すことができませんでした．

そこで，この論文では，道路ネットワークに特化した手法として "Pruned Highway Labeling" を提案しています．この手法は，以下の点が新しいと思います．

  • まず，データの持ち方が進化しています．詳細は省略しますが，今までは純粋に頂点から頂点への距離を保存していたところを，頂点からパスへの距離をうまく保存するようにすることにより，ネットワークに高速道路のような中心的なパスが存在することを活用できるようにしています．
  • ラベルが頂点ベースからパスベースのものとなっていますが，枝刈り Dijkstra のアルゴリズムをパス全体から一気に走らせるアルゴリズムにより，パス 1 本分のラベルを一気に効率的に計算できます．


特徴

この手法は，以下のような点で面白いと思っています．

  • 高速道路の活用：複雑ネットワークでは「中心的な頂点（＝ハブ）」を活用していたのに対し，道路ネットワークでは「中心的なパス（＝高速道路）」を活用します．最近の道路ネットワークの手法は，高速道路をそこまで陽に活用できていませんでした．
  • Thorup の Distance Oracle との類似性：以前の PFI セミナーで紹介した通り，理論コミュニティで純粋な理論的計算量を勝負している手法と，実際に実装された際の性能を勝負している手法は，今までかけ離れていました．しかし，今回の手法は，パスにより平面を分割しパスへの距離を保存してゆくという点で，理論コミュニティでの有名な平面グラフの最短路クエリ手法と似たアプローチになっています．

また，今回の論文で，ついに「複雑ネットワーク上の最短路クエリ」「DAG 上の到達可能性クエリ」「交通ネットワーク上の最短路クエリ」という大規模グラフ上のクエリの中で最もよく研究されてきたと言える 3 種類のクエリの研究の歴史に PLL の名前を刻むことができました．今まで，かなりバラバラな手法がそれぞれに独立に開発されてきていたのに対し，ある程度統一的な手法でそれぞれで良い性能が出るというのは，今までに無かったことだと思います．

*1:ちなみにこのブログはまさに CIKM へ発表に来ているところで書いています

ICFP Programming Contest 2013 優勝！


WINNER: UNAGI--THE SYNTHESIS
　
Java, C#, PHP, Ruby and Haskell
are programming tools of choice for discriminating hackers
　
Takuya Akiba, Yoichi Iwata,
Kentaro Imajo, Toshiki Kataoka,
Naohiro Takahashi, Hiroaki Iwami
　
University of Tokyo, Google, Keio University and AtCoder
Japan

8 月に開催された ICFP Programming Contest 2013 の結果が ICFP 2013 で本日発表され，我々は念願の優勝をついに果たしました．これは嬉しい！（事前に知っていましたが，例によって発表まで秘密にするように言われていました．）

写真は現地の imos のツイートより拝借．

ICFP Programming Contest について

ICFP Programming Contest は「なんでもあり」が特徴の，他とは一線を画す特徴的なプログラミングコンテストです．ACM の関数型プログラミング言語の学会 ICFP (International Conference on Functional Programming) に伴って毎年開催されていまして (1) プログラミング言語自由 (2) 計算資源自由 (2) チーム人数制限なし (3) 72 時間勝負 (4) 問題の形式も毎年大きく変化，等の特徴があります．優勝者は「その年のプログラミング言語」を決めることとなっており「その年はその言語の文句は言えない」とか．

チームについて

今年は，以下のメンバーで出場しました．（アルファベット順）

  • chokudai
  • imos
  • iwiwi
  • sulume
  • tos
  • wata

チーム名は "Unagi: The Synthesis" です（何故か運営にいつも ":" を "--" に置換される）．一応僕はリーダー的な立場でした（＝呼びかけをしたのと雑用を多くしただけ）．

このチームは，2 年前に準優勝したチーム "Unagi: The Gathering" をベースとしています．その際，優勝者は 301 点だったのに対し準優勝の我々は 300 点でした．準優勝はとても嬉しくはありましたが，一方で 1 点差にとても悔しい思いをしました．

去年は色々あって（主に僕の都合が悪く）一旦チームが崩壊していましたが，そこから，今年出られるメンバーで再集結＆新たなメンバーを勧誘して結成したのが今年のチーム "Unagi: The Synthesis" です．今年も（今年は今まで以上に）勝ちに行くことを強く意識して結成しました．全員が他のプログラミングコンテスト (ICPC, TopCoder 等) のバックグラウンドを色濃く持つ一方で，能力のバランス（アイディア力，アルゴリズム実装力，システム実装力，関数型言語等）を考えながら構成しました．

問題と結果について

今年の問題は，Program Synthesis という研究トピックを題材にした，割と真面目な問題でした．一言で言うと，「向こうが秘密のプログラムを持っていて，入力を渡すと出力を返してくれるので，秘密のプログラムを当てる．どれだけ多くの問題を当てられるか」という問題です．詳細はこちら．

我々のソルバーは，特に特別な道具 (SAT/SMT ソルバー等) には頼らず，基本的に枝刈り探索＋ヒューリスティクスをひたすらチューニングしてきました．色々なバリエーションを作り，それを Amazon EC2 をふんだんに使って分散実行しました．

普段，ICFP Programming Contest はリバースエンジニアリングやショートコーディング等を伴うもっと奇抜な問題が多いのに対し，かなり純粋な問題だったところも，優勝につながった要因だと思います．また，（2 年前からひきずっている）チームの最大の欠点である，メンバーが使える・使いたいプログラミング言語がバラバラというのが余り問題にならなかったのも助かりました．

皆思い思いのプログラミング言語を使ったので，「今年のプログラミング言語」は「Java, C#, PHP, Ruby and Haskell」ということになりました．（多くてちょっとダサいですが，毎年大抵どの言語を指定するかは使った言語にかかわらず指定できるのに対し，今年はアンケートに書いたプログラミング言語がそのまま使われてしまいました．）今年のプログラミング言語たちをよろしくお願いします．

感想など

ICFP Programming Contest に 2 年前から本気で参加するようになったのは，3 年前に尊敬する先輩たちのチーム Pure Pure Code++ が優勝し，とてつもなくかっこ良く感じたというのがあります．この際の先輩方のチームも，ICPC や TopCoder 等で名高い方々で構成されたチームで，そういう方々がそういうコンテストだけでなく色々な要素での総合力勝負でも圧倒したところに憧れ，自分もそうなってみたいと思い真面目に参加するようになりました．憧れの優勝についに手が届き，とても嬉しいです．

もちろん，次の目標は連覇です．今回は比較的問われる能力が純粋だった（総合力勝負性が少し低かった）という点もあり，「また勝つ」ということへのモチベーションは失われていないと思います．簡単なことではないと思いますが，どちらにせよ（順位に関わらず）とても楽しいイベントでもありますので，来年も参加したいと思います．

参加中の風景など


期間中は集まってやってました．


序盤（もちろん全完してない）から「全完した」などと意味不明な情報戦を仕掛ける wata．


ボーナス問題が出現すると共に「再集結」したなどとさらなる大嘘を書く wata．



最後は時間が足りなくなってきたので 4 問同時に見守る．


ちなみに，最終的な得点は 1696 点でした．2 位に 100 点程度差をつけての優勝ということです．


全完とはこういうことだったらしいです．

平面グラフと交通ネットワークのアルゴリズム

本日，PFI セミナーにて「平面グラフと交通ネットワークのアルゴリズム」というタイトルで話をさせてもらいました．スライドは以下になります．

  • 「平面グラフでは色々な問題が効率的に解けると聞くけど一体何故？」
  • 「道路ネットワークを処理するにはそういうアルゴリズムが使われているの？」

というような自分が昔持っていた疑問に答える，そんなつもりで準備をしました．そんな疑問を持っている方は，是非ご覧ください．

内容は以下のような感じです．

  • 平面グラフのアルゴリズム（理論コミュニティ）
    • 平面グラフとは何か
    • 平面グラフのアルゴリズムテクニックとその応用例
      • 双対グラフ
      • 小さいセパレータの存在 (r-division)
      • グラフ分割 (Deletion Decomposition)
  • 交通ネットワークのアルゴリズム（応用コミュニティ）
    • どのような課題が取り組まれているか
    • 道路ネットワークは平面グラフなのか？
    • 経路計画の手法 4 つ（CH, CRP, HL, PHL）

平面グラフのアルゴリズムの話は，日本語の資料は世の中にほとんど無いと思うので，わりかし珍しい話だとは思います．しかし，時間の制約もあってあまり踏み込んではないので，基礎的なグラフアルゴリズムさえわかっていればそこそこ理解できるような簡単な話になっています．そして，結構それでも（純粋な意味で）面白いと思います．

交通ネットワークの話は，応用寄りの方にも興味を持ってもらえるよう，2 系統の手法の話を 2 つずつしました．前者 2 つは，Bing Maps や OSRM 等で実際に採用されている，拡張性等の面で使いやすい手法です．そして，後者 2 つは，純粋に性能を追い求める手法になっています．

Ustream の録画もあります．

CIKM'13 に論文採択×2

執筆した論文が 2 本同時に国際学会 CIKM'13 (ACM International Conference on Information and Knowledge Management) に採択されました．CIKM は情報検索，データマイニング，データベースの３つの分野が合わさっている大きな会議です．Full paper での採択は競争が厳しく，去年の採択率は 13% だったのですが，今年はちょっと上がって 17% (=143/848) だったようです*1．今回の 2 本の論文は，1 本が Full paper としての採択になりましたが，もう片方は Short paper での採択になりました．

発表は，10 月末にサンフランシスコです．以下，2 本の論文を簡単に紹介します．

Linear-Time Enumeration of Maximal k-Edge-Connected Subgraphs in Large Networks by Random Contraction (Full paper)

研究室同期の岩田と NII の吉田さんとの共同研究です．極大 k 枝連結部分グラフを列挙するアルゴリズムです．言い方を変えると，頂点集合をサイズ k 未満のカットで分割します．

我々のアルゴリズムは，非常にシンプルな乱択アルゴリズムです．基本は，二頂点をランダムに縮約しながら，次数 k 未満の頂点を発見したらその頂点を切除する（元のグラフで対応する辺を除去する），これを何度か繰り返す，というだけです．これは，有名な Karger の最小カットアルゴリズムを，k 未満のカットを発見させることに特化させたものになります．ただ，最小カット問題では，ランダム縮約ベースのアルゴリズムは実用上は他の物より低速で，実際に使われることはありません．ランダム縮約が実際に実装され高い性能を出している点がこの論文の 1 つ面白い点になると思います．

実際には，そのアルゴリズムに，さらに少しのアルゴリズム的工夫と，高速な実装のための工夫をしています．理論的な解析がまた面白くて，まず Karger が行った解析と同様の解析でイテレーション回数を抑えられるのですが，その上で，グラフにちょっとした仮定を入れると，我々が加えたアルゴリズム的工夫が劇的にイテレーション回数を減らすということが証明できます．実験でのみならず，性能向上を理論的にもある程度説明できているのが面白いと思います．

極大 k 枝連結部分グラフは，興味深いことに，k-core というポピュラーな密部分グラフのモデルと深い関係があります．極大 k 枝連結部分グラフへの分割は，常に k-core への分割の細分になっています．k-core は多くの応用を持つため，極大 k 枝連結部分グラフの列挙も応用があると期待できます．

Fast and Scalable Reachability Queries on Graphs by Pruned Labeling with Landmarks and Paths (Short paper)

研究室の後輩の矢野君（主著者）と研究室同期の岩田と NII の吉田さんとの共同研究です．ついこの前に発表してきた SIGMOD'13 の最短路クエリの論文の続きで，SIGMOD'13 のエントリで最後に言及した後続研究の 1 つです．

到達可能性クエリは，与えられた有向グラフを前処理しておき，「2 点の間に有向パスがあるか否か」という質問に高速に答えるという問題です．最短路クエリ問題に含まれる問題ではありますが，ターゲットとするグラフの性質が異なることから，性能を出すことまで考えると自明な応用とは言い切れないものです．この論文ではまず，SIGMOD'13 論文の最短路クエリ手法 Pruned Landmark Labeling (PLL) について，到達可能性クエリのアルゴリズムとして性能を出すための少しの変更を議論しています．

さらに，到達可能性クエリでは最短路クエリと異なり距離を答えなくて良いという点を活用した，PLL の拡張である Pruned Path Labeling (PPL) という新しい手法を提案しています．基本的なアイディアとしては，「1 本のパスを決めたとして，各点 v から『パスのできるだけ上の頂点でどれに v から到達できるか』『パスのできるだけ下の頂点でどれからなら v に到達できるか』を知っておけば，そのパスを通るパスを持つ二点対については全て到達可能性が答えられるようになる」というものです．PLL ではラベルを付ける相手が頂点だったのに対し，PPL ではそれをパスに一般化しているということです．

こちらも，理論的解析も面白いです．SIGMOD 論文同様，PLL も PPL も木幅が制限されたグラフでの効率性は証明できます．しかし，PPL に限っては，さらに H-minor-free のグラフでの効率性も証明することができます．H-minor-freeness は木幅の制限より一般的な制限と言えるので，PPL は理論的にも PLL を改善しているということが言えます．

*1:ただ，分野によって競争の激しさが結構違うかもしれません．