Hatena::ブログ(Diary)

(iwi)の日記

2014-06-21

DEIM フォーラム 2014 最優秀論文賞:2-Hop ラベルの直接的な計算によるグラフ最短経路クエリ処理の効率化

21:35 |  DEIM フォーラム 2014 最優秀論文賞:2-Hop ラベルの直接的な計算によるグラフ最短経路クエリ処理の効率化を含むブックマーク  DEIM フォーラム 2014 最優秀論文賞:2-Hop ラベルの直接的な計算によるグラフ最短経路クエリ処理の効率化のブックマークコメント

DEIM フォーラム 2014 での発表論文が最優秀論文に選ばれ,本日開催されたソーシャルコンピューティングシンポジウム (SoC 2014) にて行われた授賞式に参加しました.後輩の大坂君との共著論文も優秀論文賞を受賞しました.

f:id:iwiwi:20140621202847j:image:w450

このような極めて高い評価を頂けたことは身に余る光栄です.私だけでなく,著者グループ全体で見ても DEIM や関連イベントへの参加・投稿経験を持つ者は居ず,我々のような「新参者」であっても公平に高い評価をしてくださるコミュニティに感謝と敬意を表したいと思います.

元々,私の研究の興味は「アルゴリズムとデータ構造」であり,卒論の頃から,アルゴリズムの研究室(東大今井研)を選びずっと所属しています.しかし,アルゴリズムコミュニティにて重視されるような漸近的な理論解析よりも,私は大規模データ・実性能・社会へのインパクトなどに興味があり,配属当初は(正確には研究室選びの頃から)価値観の違いに悩んでいました.

そんな時,ふとしたきっかけで見つけ感激したのが,SIGMOD’10 の大規模グラフ上の最短経路クエリに関する論文でした.研究の世界をよく知らなかった当時,データベースといえば本当にデータベース自体についてのみ研究をしているのではないかと思い込んでいましたし,かなり不思議にも思いましたが,この論文は自分の興味・価値観に,ばっちり,これ以上ないほど,合致していました.「こういう研究がしたい!」と思い,卒論ではこの論文に基づいた研究を行いました.

そうしてその後も,このブログでも度々報告している通り,データベース関連の国際学会に少しずつ挑戦し,いくつかの論文がお陰様で採択されてきました.ただ,所属する研究室や近隣研究室ではデータベースコミュニティへの論文投稿の経験を持つ人は殆ど居なかったため,活動はかなりが手探りでした.実際,僕の今までの共著者は,殆どが理論系のアルゴリズム研究者です.そして,実は心の中では,「自分のような研究内容で,胸を張って参加できる研究コミュニティは存在するのだろうか」というような疑問をずっと持ち続けてきました.なにせ,研究内容はグラフアルゴリズムですが,理論解析での貢献は薄いので,アルゴリズムコミュニティでは高い評価を受けません.一方,データベースの学会に論文を採択して貰ってはいても,グラフアルゴリズムのようなトピックはとても隅っこの方の存在なのではないか,というようになんとなく感じていました.

従って今回の受賞は,受賞だけでも大変嬉しいのですが,このような背景から「僕のようなトピックでもデータベースコミュニティの一員として認めていただけるんだ」と感じられて,とても喜んでいます.これからも,きっと近いスコープで研究を続けていくと思いますので,まだ未熟者ではありますが,どうかよろしくお願いします.

2014-06-04

VLDB'14 論文採択:グラフの構造を活用した Personalized PageRank の高速計算

12:35 |  VLDB'14 論文採択:グラフの構造を活用した Personalized PageRank の高速計算を含むブックマーク  VLDB'14 論文採択:グラフの構造を活用した Personalized PageRank の高速計算のブックマークコメント

論文が国際学会 VLDB'14 に採択されました.VLDB (International Conference on Ver Large Data Bases) は SIGMOD と並ぶデータベースの最も有名な学会です.学会は 9 月に中国杭州です.

今回の論文は "Computing Personalized PageRank Quickly by Exploiting Graph Structures" というタイトルで,NII の前原さん,同じ研究室の岩田, NII の河原林先生との共著です(私は第二著者です).


内容

この論文は大規模なソーシャルネットワークウェブグラフにおいて Personalized PageRank を高速に計算する手法を提案する論文です.Personalized PageRank は有名な PageRank の一般化です.PageRank が担っていた重要度の計算の他,関連度としても使われ,幅広い応用を持ちます.

今回の提案手法は,KDD’14 論文でも扱った Core-Tree-Decomposition を用い,グラフの性質を活用して計算を効率化します.


Core-Tree-Decomposition による Core と Whisker の分離

KDD’14 論文で扱った通り,グラフ理論における有名な概念である tree-decomposition (木分解) を拡張した core-tree-decomposition という道具を用いることにより,グラフを Core 部分と Whisker 部分に分離することができます.Whisker 部分は木に類似した構造を持ち,グラフ理論の言葉を用いて言えば treewidth (木幅) が小さいです.一方,Core 部分は密に絡みあっており,グラフ理論の言葉を用いて言えば expander graph に近いです.


Core-Tree-Decomposition の高速な計算

core-tree-decomposition を利用していくための問題点の 1 つとして,計算コストがありました.そこで本論文では,まず,データ構造の工夫により core-tree-decomposition をより高速かつ省メモリに計算するための新たなアルゴリズムを提案しています.

f:id:iwiwi:20140604123339p:image:w450


Whisker 部分の処理: LU 分解による Preconditioning

Personalized PageRank の計算は連立方程式の球解に他なりません.ただし,そのままでは LU 分解のような直接法はスケールせず,一般的には反復法が用いられます.

ただし,上記の通り,Whisker 部分は木幅が小さく,これは,この部分に関しては LU 分解が効率的に動作するということを意味します.従って,Whisker 部分に関しては LU 分解により直接的に解を求め,その解を用いて連立方程式を Core 部分のみの問題に帰着します.

f:id:iwiwi:20140604123858p:image:w300


Core 部分の処理: GMRES 法

一方,Core 部分は expander graph に近いため,LU 分解のような直接法の性能は絶望的です.しかし,逆に Core 部分は Core 部分で,expander graph に近いという性質を活用し計算を効率化することができます.

通常の Personalized PageRank の計算では基本的な反復法であるヤコビ法や Gauss–Seidel 法が用いられます.しかし,今回提案しているのは,Core 部分には GMRES 法 (generalized minimal residual method) を用いることです.expander graph から来る性質の良い連立方程式において GMRES が効率的に収束することは,理論的にも実験的にも言うことができます.

ここで面白いのは,Core と Whisker の分離を行わないでそのままの連立方程式適用した時は,GMRES 法はヤコビ法等よりも低速であるという点です.これは,そのままの問題ではあまり性質が良くなく,GMRES の高い収束性能を発揮できず,反復回数で差をつけることができないため,オーバーヘッドの部分で負けてしまうからです.一方,今回は Core 部分を抽出したことにより,オーバーヘッドを加味してもなお GMRES 法が優位に立ちます.

f:id:iwiwi:20140604123340p:image


論文採択について

今まで VLDB はとにかく負け続きだったので,第二著者とはいえ,VLDB への初の論文採択は本当に待ち望んでいたものであり嬉しいです.アルゴリズムが面白いという点が査読者にも気に入ってもらえたのが良かったのだと思います.

2014-05-29

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

20:13 |  乱択データ構造の最新事情 −MinHash と HyperLogLog の最近の進歩−を含むブックマーク  乱択データ構造の最新事情 −MinHash と HyperLogLog の最近の進歩−のブックマークコメント

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

Ustream の録画もあります.

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

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

どちらも重要かつ基礎的な操作で,b-bit MinHashHyperLogLog など,既に実用的な手法が提案されており,実際にも使われています.しかし,2014 年になって,Odd SketchHIP 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.

2014-05-13

KDD'14 に論文採択

18:34 | KDD'14 に論文採択を含むブックマーク KDD'14 に論文採択のブックマークコメント

論文が国際学会 KDD’14 に採択されました.KDD (ACM SIGKDD Conference on Knowledge Discovery and Data Mining) は ACM によって開催されるデータマイニングの最も有名な学会の 1 つです*1学会は 8/24-27 にニューヨークです.

今回の論文は "Network Structural Analysis via Core-Tree-Decomposition" というタイトルで,NII の前原さん・河原林先生との共著です.


内容

タイトルの通り,Core-Tree-Decomposition を用いてネットワークを解析するという論文です.対象とするグラフはソーシャルネットワークウェブグラフ等の現実世界のグラフです.今まで得られなかった面白い知見が Core-Tree-Decomposition により見出せることを示しました.


グラフの Core と Whisker

ソーシャルネットワークウェブグラフのようなグラフは,Core と Whisker を持つというようなことがたびたび唱えられ多くの人により信じられてきました.Core は比較的密な部分,そして Whisker はその周辺部分であり木に近い構造をしています(Fringe とか Periphery とか呼ばれたりもするものと大体同じ).

しかし,その概念は比較的ぼんやりしたもので,あまりちゃんとした数学的な定式化は存在せず,従って関連する議論はあまり進んでいませんでした.

f:id:iwiwi:20140513182433p:image


Core-Tree-Decomposition とは

Core-Tree-Decomposition は Tree-Decomposition (木分解) を拡張した概念です.木分解とは,グラフを木のように扱うための道具です.グラフが実際に木に近い場合,より正確には「木幅が小さい」場合に,良い木分解が存在し,グラフを上手く扱えるようになります.現実のグラフは Core 部分の存在により全体としては木っぽいわけではないので,現実のグラフにあわせて木分解を拡張した概念が Core-Tree-Decomposition になります.

f:id:iwiwi:20140513182434p:image

(ちなみに,木分解の拡張を現実世界のグラフに適用するという話は実は卒論からしばらくやっていて EDBT’12 で発表した話でもありまして,その続きという感じもあります.)


Core-Tree-Decomposition による Core と Whisker の発見

現実のネットワークに Core-Tree-Decomposition を適用すると,木幅の小さな部分とそうでない部分に分離することができます.ここで,木幅が小さいとは構造が木に近いという意味だったことを思い出すと,分離された木幅の小さな部分を Whisker とみなし,残った部分を Core とみなすことができます.そしてグラフの固有値分布を見ることにより,Core 部分が expander graph と呼ばれる種類のグラフに近く,単に辺数が多いだけでなく密に絡み合った部分を取り出すことに成功していることを検証しました.

f:id:iwiwi:20140513182435p:image:w300


グラフアルゴリズムの性能予測への応用

自分の開発してきた Pruned Landmark Labeling (PLL) をはじめとして,グラフアルゴリズムの一部は現実のネットワークにおいて理論的な最悪計算量より遥かに高速に動作します.しかし,同じようなサイズ(=頂点数&枝数)のグラフであってもアルゴリズムの性能が大きく異なることがあり,その原因などはあまりよく議論されてきませんでした.

そこで本研究では,木分解によりそのような性能の違いをある程度説明できるかもしれないということを議論しています.具体例として,PLL などの最短経路索引を例に取り,最短経路索引の性能が木分解の結果を用いてある程度予測できることを示しました.定性的な議論のみならず,定量的な,そして理論的な裏付けを伴う議論になっています.

f:id:iwiwi:20140513182436p:image


論文採択について

今回の論文は自分としては初めての「新しいアルゴリズムを提案しない論文」になります.今までの論文ではアルゴリズム有用であることを売りに書いてきたので,今回は「解析結果が面白い」ことが売りという点で初めての取り組みでした.この結果がどのぐらい面白いと思ってもらえるのかというのがなかなか予想がつかず不安もありましたが,なんとか査読者達にも面白さを理解してもらうことができて良かったです.

ちなみに,後続研究としてこの分解の性質を活用した高速なアルゴリズムの設計も行なってます.そちらも大変面白いですので乞うご期待.

*1Microsoft Academic Search で調べますと All Years, Last 10 Years, Last 5 Years のいずれを選んでもデータマイニング分野で一番上に来ます.

2014-01-11

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

22:39 | Cache-Oblivious データ構造入門 @DSIRNLP#5を含むブックマーク Cache-Oblivious データ構造入門 @DSIRNLP#5のブックマークコメント

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

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


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

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

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