理論と応用の乖離

Fast Exact Shortest-Path
Distance Queries on Large
Networks by Pruned
Landmark Labeling
𠮷田悠一
国立情報学研究所 & プリファードインフラストラクチャー
博士時代の研究テーマ
狭義には「グラフと制約充足問題に対する準線形
時間アルゴリズム」
– よく有る問題に対する超速いアルゴリズム
広義には「理論計算機科学」
• P ≠ NPを証明
• 乱数、証明、学習…を計算の観点から理解
• 応用を謳ったものも多いが…
2
理論と応用の乖離
自然科学の研究の流れ
応用
具体例の
考察
モデル化
実験
による確認
理論
から予想
理論
3
理論と応用の乖離
自然科学の研究の流れ
応用
具体例の
考察
モデル化
実験
による確認
理論
から予想
理論
計算機科学でもこのサイクルを回せないか？
例: 複雑ネットワークにおける最短路クエリ
4
複雑ネットワーク
例:
• ソーシャルネットワーク
• ウェブグラフ
• 通信ネットワーク
• 生物学的ネットワーク
特徴的な構造:
スケールフリー性、スモールワールド…
5
最短路クエリ
入力グラフに対し、
1. インデックスを生成し、
2. 距離dG(s, t)答える。
s
t
目的: 良いトレードオフ
スケーラビリティ
インデックス構築時間
インデックスサイズ
クエリ性能
クエリ応答時間
6
手法
• 幅優先探索を全頂点から行う
• シンプルなアイデアで探索を枝刈り
6
4
7
1
6
5
7
8
1
2
9
4
10
3
11
4
7
8
1
2
9
12
6
5
5
8
2
9
10
12
3
11
10
12
3
11
• 詳細はポスターで
7
スケーラビリティ
実験に使われた最大グラフサイズ
(インデックス構築時間 < 1日)
×106 Edges
1000
100
数百倍大きいグラフ
10
1
0.1
TEDI
HCL
[SIGMOD’10] [SIGMOD’12]
TD
[EDBT’12]
HHL
[ESA’12]
PLL
(this work)
インデックスサイズ＆クエリ応答時間(数μs)は同等
8
効率性の理由
複雑ネットワーク = コアフリンジ構造
• コア: 多くの最短路が通る
• フリンジ: 木っぽい
両者ともに枝刈りによく貢献すると証明可能
9
まとめ
CSでも理論と応用のサイクルを回せるか？
応用
理論
データベース
理論
計算機科学
データ
マイニング
ネットワーク
科学
10
機械学習
経済物理

Download Report