大規模 対象 た 析処理
高速化 関 取 組
鬼塚 真
主幹研究員(特別研究員)
NTTソ ン ン
自己紹
所属
NTT ソ ン ン 主幹研究員 特別研究員
群馬県出身，ワ ン ン大(911 時)
過去 研究開発
DBMS 研究開発
XML 処理/DBMS 高速化
CBoC type2 散 開発
現在 研究
MapReduce 高速化
機械学習 高速化 ( ン ， ン 等)
画像検索 ン検索
番組通知
配信
検索
管理情報区分：B 関係者限り
分散処理による大規模デ タ分析の背景 狙い
大規模 高速 処理 析 短期間 開
発 技術 確立
情報爆発 言わ 時代 迎え、情報処理
大規模 処理 対 高 い
NTT 各社 い 、各種 情報 大量
活用 う 動 進 い
背景
狙い
管理情報区分：B 関係者限り
分散処理による大規模デ タ分析の概要
技術目標:
単一 ン向 析 (機械学習 統計処理) 最
適 散処理 出
技術課題
1. 抽象言語 散 出 最適化 NII 胡教授
2. 散処理 高速処理
統計処理 集約処理，結合処理 高速化
機械学習( ン 推薦) 高速化
3. 最新 利用 た高速化 省電力 東 大横田教授
select m.source, m.dest, m.count, c.rank
from (select n.dest, sum(n.rank/n.count) as rank
from Graph as n
group by n.dest) as c,Graph as m 最適化
高速 散処理
実行計画
目
大規模 析 い
析処理 高速化 取 組
MapReduce 高速化 (HW2011)
Map Multi-Reduce: reduce 事前実行
PJoin: 事前 ン 割 準結合 利用
機械学習 高速化
K-dash: Random Walk with Restart 高速
top-k 検索 (PVLDB2012)
ン 高速化
大規模 析 い
大規模 析 MapReduce高速化 機械学習高速化
大規模 析 適用例
n-gram/ ン 析
: web ン ン /SNS
目的: 頻出 ン 学習
用途: 音声認識，日英翻訳
歴 用いた ソ
: web 歴 視聴 歴
目的: RWR, 学習
用途: ソ 検索
ワ 解析
40Gbps
serve as the incoming 92
serve as the incubator 99
serve as the independent 794
…
4-gram
大規模 析 MapReduce高速化 機械学習高速化
MapReduce 高速化
大規模 析 MapReduce高速化 機械学習高速化
MapReduce ?
散処理 ン ＆
高 性: 1万 ( ン)，
ン API: map関数/reduce関数
散処理特有 複雑さ(負荷 散 用性) 隠 い
Google 開発
web 検索 ン ン ン 用途 た 開発
PageRank 計算，転置 構築
2008年時点 20PB/day MapReduce 処理
[Dean et al., OSDI 2004, CACM Jan 2008, CACM Jan 2010]
大規模 析 MapReduce高速化 機械学習高速化
MapReduce キ
MapReduce: 散処理
散 DFS 構築
DFS: GFS (Google FS), HDFS (Hadoop DFS)
2 + Shuffle
Map : 入力 毎 map関数 実行
ン : ン毎 独立 た処理
Shuffle: 同一key (key, value) 群 束
Reduce : 束 た結 reduce 関数 実行
ン : 複数 ン た 必要 処理
大規模 析 MapReduce高速化 機械学習高速化
MapReduce キ (続 )
User
Program
Input Data
Split 1
Split 0
Split 2
Split 3
fork fork
fork
assign
map
assign
reduce
Output
File 0
Output
File 1
node
process
file
worker
Master
worker
worker
worker
worker
worker
Map
Map Map task Reduce Reduce task
shuffle
大規模 析 MapReduce高速化 機械学習高速化
例: wordCount
入力文書毎 map関数 適用
単語毎 (word, 1) 出力
単語毎 頻度 積算
大規模 析 MapReduce高速化 機械学習高速化
MapReduce 設計思想
以 要素
関数型言語 ン
• map (f) [r1,...,rn] = [f(r1),...., f(rn)]
• reduce (⊕) [r1,...,rn] = r1 ⊕ .... ⊕ rn
散環境 適用
• map: ン内 処理，reduce: ン間 処理
• 論理 ン = 物理 ン
• (key, value) + partition 関数 処理
• 処理 散特有 処理 隠 い
• 間通信 (高速 )
MapReduce 入 高速化 研究動向 高速化 取 組 研究 方向性
MapReduce: ン ン 実施例
MapReduce ン ン
Local Aggregation
Pairs and Stripes
Computing Relative Frequencies
Secondary Sorting
Relational Joins
MapReduce 利用例
転置 ン
(幅優先探索 )
EM
大規模 析 MapReduce高速化 機械学習高速化
MapReduce 高速化 取 組
1. Map Multi-Reduce:
MapReduce extended with reduce pushdown
大規模 析 MapReduce高速化 機械学習高速化
Motivation
Performance problems in MapReduce [DeWitt, 2009]
no schema, no index, ignoring data skew,
communication cost, materialization cost
In particular materialization/communication costs
Overview of Map Multi-Reduce
Idea:
Pushing down reduce function and iteratively
applying it so as to reduce intermediate data.
Efficiency:
2.4 times more efficient than original MR in real
dataset
Limitations and opportunities
• reduce function needs to be associative and commutative
: summation, count sum(2,3,1) = sum(sum(2,3),1)
: average avg(2,3,1) != avg(avg(2,3),1)
BTW, what is the pushdown?
A well-know technique in DBMS
pushdown reduces intermediate data size,
while ensuring the correctness of query result
Usually effective for single query optimization
SELECT person.name, dept.name
FROM dept, person
WHERE person.age > 20
AND person,deptid = dept.id
Query
person
join
selection
projection
dept person
join
selection
projection
Technique 1: incremental reduce
hashmap<key, value> is used for record structure
reduce function is applied before buffering at map task
Split N Map
function MapOutputBuffer sort&spill Spill files mergeParts Output file
Original MapReduce
User
Program
worker
worker
Input Data
fork fork
fork
Master
worker
assign
map
assign
reduce
Output
File 0
Output
Split 1
Split 0
Split 2
Split 3
worker
worker
worker
assign
local reduce
Technique 2: Local reduce
node
process
file
local reduce task applies the reduce function
to the map outputs of the same node
Master also controls local reduce tasks
Local Reduce
Local Reduce Local reduce task
Experiments
Hardware/software settings
Linux (CentOS5.4, 2.8GHz, main memory 8GB)×90 nodes
Java1.6, Hadoop 0.19.2
Workload
Datasets:
Trec terabyte dataset
0.5TB, # of unique terms 86,500k, 678 terms/input record
synthetic datasets (with uniform term distribution)
0.5-7TB, # of unique terms 100-400k, 62 terms/input record
Analysis pattern: wordCount
Purpose
Comparison: Map Multi-reduce variations vs MapReduce
IO reduction effect by record/local reduce
Response times (Trec terabyte)
response time is improved by 58%, 2.4 times faster.
effect of local reduce
with record & local reduces, performance of map phase is
improved, however 6% gets worse as a whole caused by
local reduce overhead.
52% 58% With record reduce
Without local reduce
with record reduce &
local reduce
Effect by record reduce (Trec terabyte)
Size of data put into buffer is reduced to 1/30
Size of spill files reduces to 1/3 (63% reduction)
Performance improved mostly by IO cost reduction
1/30
1/12
Map function
Reduce function
Record reduce
Split N MapOutputBuffer sort&spill Spill files mergeParts Output file
Reduce function is applied incrementally
67% 63%
Related work
Local aggregation
combiner: does not reduce the data put into the buffer
in-mapper combining design pattern [Lin et al., 2010]
complicates the mapper and may run out of memory.
Split N Map
function MapOutputBuffer
sort&
combine&
spill
Spill files
mergeParts
(combine)
Output fileSummary of Map Multi-Reduce
Idea:
Pushing down reduce function and iteratively
applying it so as to reduce intermediate data.
Efficiency:
2.4 times more efficient wordCount than original
MR in Trec terabyte
1.9 times than original MR in web N-gram
On going work:
Extend Map Multi-reduce to support semantic
compression on keys (stripes design pattern)
MapReduce 高速化 取 組
2. PJoin:
Efficient join processing with MapReduce
for OLAP applications
大規模 析 MapReduce高速化 機械学習高速化
技術 概要
PJoin (pre-partition-based join)
[到達点] 多 元 析(OLAP)処理 い ，
量 1/3 削減 処理時間 ，従
来技術 42.8% 高速化
[ 戦略] 複数 析処理 い 共通
処理 前 実行(事前処理) ， 析処
理時 削減
背景: 多 元 析(OLAP) ？
統計的 析処理 典型的 手法
歴 ン ン 格納 fact (大)
fact 多角的 元 集約演算 実施 た
，複数 dimension
PARTKEY
NAME
MFGR
BRAND
TYPE
SIZE
CONTAINER
COMMENT RETAILPRICE
PARTKEY
SUPPKEY
AVAILQTY SUPPLYCOST
COMMENT
SUPPKEY
NAME ADDRESS
NATIONKEY PHONE
ACCTBAL COMMENT
ORDERKEY
PARTKEY
SUPPKEY
LINENUMBER
RETURNFLAG
LINESTATUS
SHIPDATE
COMMITDATE
RECEIPTDATE
SHIPINSTRUCT SHIPMODE
COMMENT
CUSTKEY
ORDERSTATUS
TOTALPRICE ORDERDATE ORDER- PRIORITY
SHIP- PRIORITY CLERK
COMMENT CUSTKEY
NAME ADDRESS
PHONE
ACCTBAL MKTSEGMENT
COMMENT PART (P_)
SF*200,000
PARTSUPP (PS_) SF*800,000
LINEITEM (L_) SF*6,000,000
ORDERS (O_) SF*1,500,000
CUSTOMER (C_) SF*150,000
SUPPLIER (S_) SF*10,000
ORDERKEY
NATIONKEY
EXTENDEDPRICE
DISCOUNT
TAX QUANTITY
NATIONKEY NATION (N_)
25
REGION (R_) 5
集約演算
多 結合処理
化
結合 方法:
• 量 起因 通信 IO 大
通信 IO 削減 最重要課題
背景: 従来 MapReduce 結合処理 課題
orders 1
hash(x)
mapper
…
lineitem n
…
lineitem 1
Join
reducer
…
hash(x)
Join
…
量 大
hash(y)
製品単
売
伝票
[方針] 結合処理時 量 削減
[前提] OLAP 析 ，更新 参照処理 性能 重要
1対多 関係 結合処理
[戦略]
複数 析処理 い 共通的 処理
事前処理 ， 析処理時 削減
• 結合条件(主キ ) 事前
• 準結合 活用 + 中間 事前生成
複数MapReduce 間 量 削減 結合計画
[効 ]
析処理時 量 削減
PJoin 概要
BTW, what is the semi-join?
A well-know technique in distributed DBMS
Natural join ( ڇ)
BTW, what is the semi-join?
A well-know technique in distributed DBMS
Natural join ( ڇ)
BTW, what is the semi-join?
A well-know technique in distributed DBMS
Natural join ( ڇ)
BTW, what is the semi-join?
A well-know technique in distributed DBMS
Semijoin ( ڈ)(ډ)
Natural join ( ڇ)
BTW, what is the semi-join?
A well-know technique in distributed DBMS
Semijoin ( ڈ)(ډ)
Natural join ( ڇ)
BTW, what is the semi-join?
A well-know technique in distributed DBMS
Semijoin ( ڈ)(ډ)
Natural join ( ڇ)
BTW, what is the semi-join?
A well-know technique in distributed DBMS
Semijoin ( ڈ)(ډ)
Natural join ( ڇ)
BTW, what is the semi-join?
A well-know technique in distributed DBMS
Semijoin ( ڈ)(ډ)
Natural join ( ڇ)
BTW, what is the semi-join? (cont.)
A well-know technique in distributed DBMS
semi-join is used before the original join, so as to
reduce communication cost between DB severs
Employee ڇ Dep
BTW, what is the semi-join? (cont.)
A well-know technique in distributed DBMS
semi-join is used before the original join, so as to
reduce communication cost between DB severs
(Employee ڈ Dept ) ڇ Dept
Employee ڇ Dep
BTW, what is the semi-join? (cont.)
A well-know technique in distributed DBMS
semi-join is used before the original join, so as to
reduce communication cost between DB severs
(Employee ڈ Dept ) ڇ Dept
Employee ڇ Dep
[方針] 結合処理時 量 削減
[前提] OLAP 析 ，更新 参照処理 性能 重要
1対多 関係 結合処理
[戦略]
複数 析処理 い 共通的 処理
事前処理 ， 析処理時 削減
• 結合条件(主キ ) 事前
• 準結合 活用 + 中間 事前生成
複数MapReduce 間 量 削減 結合計画
[効 ]
析処理時 量 削減
PJoin 概要
PJoin 特徴 : 量削減
事前 実行
lineitem
orders
hash(x)
hash(y)
…
lineitem b
lineitem a
lineitem z
orders 1
DFS read
shuffle
製品単
売
PJoin 特徴 : 量削減
事前 実行，準結合中間 事前生成
lineitem
orders
hash(x)
hash(y)
…
lineitem b
lineitem a
lineitem z
orders 1
…
lineitem_
orders 1
hash(y)
lineitem primary key &
foreign key (orders primary key)
DFS read
shuffle
製品単
売
PJoin 特徴 : 量削減
lineitem a
orders processing
+
準結合
mapper
…
lineitem_
orders n
…
lineitem_
orders 1
orders 1
orders processing
+
準結合
Joining with
liteitem
reducer
…
Joining with
liteitem
事前 実行，準結合中間 事前生成
mapper 準結合処理後 ，reducer 残処理 実行
lineitem
orders
hash(x)
hash(y)
…
lineitem b
lineitem a
lineitem z
orders 1
…
lineitem_
orders 1
hash(y)
lineitem primary key &
foreign key (orders primary key)
DFS read
shuffle
製品単
売
従来手法 PJoin 比較
lineitem a
orders processing
+
準結合
mapper
…
lineitem_
orders n
…
lineitem_
orders 1
orders 1
orders processing
+
準結合
Joining with
liteitem
reducer
…
Joining with
liteitem
量 削減
量 削減
DFS read
shuffle
orders 1
hash(x)
mapper
…
lineitem z
…
lineitem a
Join
reducer
…
hash(x)
Join
Join
…
量 大
hash(y)
DFS read 増加
PJoin 特徴 : N 結合
PJoin
型 キ 場合
複数 mapper 実行
全 mapper 結 S 主キ
reducer 処理 能
mapper (T 主キ 結合処理) reducer (S 主キ 結合処理)
T
one manyS
T 1
one manyS
T N
onemany
T 主キ 結合処理
製品単
伝票 売
製品単
伝票 売
売店
PJoin 特徴 : 型 結合計画
多 元 析 型 キ
dimension 処理 開始 ，fact 最
後 実行 ，中間 削減
lineitem
orders
partsupp part
supplier
*
*
* *
*
lineitem,
orders,
$J2
partsupp,
part,
$J1
supplier,
nation
J1
J2
J3
J1
J2
J3 fact 結合 最後 実行
評価実験
評価環境
Linux (CentOS5.4, 2.8GHz, 主記憶 8GB)×50
Java1.6, Hadoop 0.19.2
ン : TPC-H ン
[ ] 104GB, 207GB, 311GB
準結合中間 : 83GB, 167GB, 250GB
[ 析 ] TPC-H 結合演算 利用 17
評価観点: PJoin 従来 Join 手法 比較
• 全体: PJoin ，従来 2 Join 手法 応答性能比較
• PJoin vs reduce-side join ( 型結合計画, Hive 計画)
• 詳細
• PJoin 量，HDFS read/write 量 影響
応答時間 (104GB, 50 )
従来手法 33.4% (star plan比), 42.8% (Hive plan比)
改善 効 : MapReduce job 数削減 ，HDFS+ 量削減
性能 = (HDFS r/w) + 0.5×(local r) + (local w) + 1.5×(shuffle)
1
2
3
4
5
6
respo nse tim e (m in)
PJoin
reduce-side join (star plan)
reduce-side join (Hive plan)
量 (104GB, 50 )
従来手法 62.6% (star plan), 62.2% (Hive plan)改善
Q18 悪化: WHERE条件 選択効 原因
5
10
15
20
25
30
35
40
45
Shuff le (G B)
PJoin
reduce-side join (star plan)
reduce-side join (Hive plan)
HDFS read量 (104GB, 50 )
従来手法 51.4% (star plan), 52.2 % (Hive plan)増加
PJoin 準結合中間 参照 た
10
20
30
40
50
60
H DFS Rea d (G B)
PJoin
reduce-side join (star plan)
reduce-side join (Hive plan)
PJoin
特徴:
処理 事前実行(pre-partitioning)，準結
合中間 事前生成
準 結 合 mapper 実 行 ， 残 結 合 処 理
reducer 実行
効 :
TPC-H い 30-40%応答性能 改善
量 1/3 削減
後 取 組 :
ソ 更新 対 差 更新
機械学習 高速化
大規模 析 MapReduce高速化 機械学習高速化
機械学習 高速化
1. K-dash: Random Walk with Restart
高速 top-k 検索
大規模 析 MapReduce高速化 機械学習高速化
D3-1
• Random Walk with Restart (RWR)
– 類似度 計算方法
– 起点 ン 繰 返 た定常状態
確率 類似度
• 本研究 目的
0.15
0.16
0.54
0.07
0.03
0.03
0.01
0.01
処理手順
以 処理 定常状態 得 繰 返
対象 起点
隣接 ン
一定確率 ．そう ば 戻
D3-1
応用例
• ン ン
– 人 た ， 購買 歴 た 作成
– 推薦対象者 RWR 類似度 計算
– 類似度 高い 推薦
– 協調 既存技術 高精度 拡張性 高い
推薦 購入済
D3-1
類似度 計算
• 類似度 行列 繰返 計算 定義さ
A
p
q
c
p ( 1 c )
A
p c
q
：類似度 対応 列
： 隣接行列
：起点 戻 確率
：対象 対応 成 ，そ 他 列
p
p
p
• 個 求 高い計算
1. 類似度 収束 繰返 計算 必要
K
D3-1
提案手法 概要
1. 行列 解 単 計算 繰 返 計算不要
– 隣接行列 疎 角行列 角行列 解 ，
類似度 計算
• 疎行列 用い高速 類似度 計算
• 特定 類似度 正確 計算
2. 類似度 限値 計算 探索範囲 足
– 類似度 計算 い 類似度 限値 推定
• 限値 類似度 計算 い
1
L U 1
q
L
cU
p 1 1
個 求 類似度
計算 必要 あ ？
K
D3-1
行列 解：類似度 計算
• LU 解 用い 類似度 計算
– 逆行列 計算 特定 類似度 正確 計算
– 行列 わち行列 疎 あ 逆行
列 ， 必 疎 い
• 行列 密 場合，類似度 高速 計算 い
c
U 1
q
p
L 1
I
：単 行列， LU W I ( 1 c ) A
A
1
1 U
L
W
D3-1
行列 解：基本的 考え方
• ， 成 ， / 成 積 計算
• ， 成 対応 成 計算
• わち / 成 あ ば逆行列 疎
1
1 U
L L U
U
L W
A
j i
k ik kj
ij ij ij
j
i
L
L
L
j
i
L
j
i
L
1
1 1
)
(
/
1
)
(
/
1
)
(
0
1
L
ij
L
ij
( )
/
1
)
(
1
)
(
0
1
1
L U i j
W
U
j
i
j
i
L
j
k ik kj
ij jj ij
L
ij
W
ijD3-1
行列 解：疎行列 計算方法
• 疎行列 隣接行列 / 要
素 0 ば い
• 疎行列 得 た 手法 考案
1. 複数 割 並 替え
2. た 最後 移動
3. 各 内 数 さい順 並 替え
1
1 L
U A
D3-1
類似度 推定
• 類似度 限値 推定 検索 打ち
• 類似度 限値 推定 以 通
( 1) ( )
max max
max
( ) ( ) 1
u u s
l V
v v V l v V
v v
v
u
c p A v p A v p A
p
類似度 伝搬 量 最大値
同 類似度 伝
搬量 最大値
類似度 伝 搬量 最大値
： 類似度 推定値
：類似度 計算済 集合
： 幅優先木 番号
： 番号 類似度 計算済 集合
： 重 最大値
： 重 最大値
p
uV
s)
( l
uV
l
u)
max
( v
A
A
maxu
u
l
uv
D3-1
評価実験：実験条件
• 実験 ン
– 4 3.3 GHz Intel Xeon 32GB
• 実験 – 辞書
• ン ン辞書 FOLDOC
• あ 単語 説明 そ 他 単語 用い い ，そ 単語間
あ
– ン
• Oregon Route Views Project ン
– 共著
• Condensed Matter E-Print Archive 投稿さ た論文 共著関係 得 た
• 比較手法
– Tong 提案さ た近似手法*
D3-1
評価実験：検索時間 精度
• 検索時間 検索精度 い 実験
– 提案手法 従来手法 数万倍 高速化 達成
– 提案手法 従来手法 異 検索結 正確
0.00001 0.0001 0.001 0.01 0.1 1
処理時間[s]
提案手法 K=5 提案手法 K= 5
提案手法 K=5 従来手法 特異値 個
従来手法 特異値 個
0.2 0.4 0.6 0.8 1 1.2
検索精度
提案手法
従来手法 特異値 個
従来手法 特異値 個
D3-1
評価実験：
• 辞書 用いた類似語 検索結
– 提案手法 検索結 良好
– 従来手法 近似精度 く， 個 K 検索 適さ い
1 2 3 4 5
提案手法 Microsoft Windows W2K Windows/386 Windows 3.0 Windows 3.11 従来手法 Microsoft Windows Microsoft Networking Microsoft Network W2K Thumb
提案手法 Mac OS Macintosh user interface
Macintosh file
system multitasking Macintosh Operating System
従来手法 Mac OS Rhapsody SORCERER Macintosh Operating
System
PowerOpen Association 提案手法 Linux Linux Documentation
Project Unix lint
Linux Network
Administrators' Guide 従来手法 Linux Linux Documentation
Project SL5 debianize SLANG
ンキン
Microsoft Windows
Mac OS
Linux
検索語 手法
D3-1
• 問題設定
– 大規模 対 ，RWR 基 対象 類似
個 高速 正確 検索
• 提案手法
– 行列 解
• 特定 類似度 高速 正確 計算
– 類似度 推定
• 類似度 計算 い 類似度 限値 推定
• 実験結
– 正確 検索結 保証 ，従来手法 数万倍 高速
化 達成
K
機械学習 高速化
2. ン 高速化
大規模 析 MapReduce高速化 機械学習高速化
発表 流
1. 研究 背景
2. 既存手法：Louvain法
3. 提案手法
4. 評価実験
5. め 今後 課題
背景： フ ー
フ ー 大規模化
– Ex) Facebook 2011 年 ーザ数 5億人，総
会員数 8億人を突破
フ ー ン 技術
– ー 中 ー を一定 尺度 自動分類
– 内 ッ 密 あ ， 間 ッ 疎 あ
ン 結果ほ 良い
良い ン 結果
1 2
悪い ン 結果
1 2 3
ン 結果 評価尺度
ン 指標：Modularity Q [Girvan ら, Phys.Rev.2004]
– 内 密， 間 疎 あ 程良い値を示
1 2 1 2
Modularity ン 手法
処理可能
フ 規模
1 万 ー
数百万 ー
数千万～
1 億 ー
Girvan-Newman 法 [ Girvan ら, Phys.Rev.2004 ]
Newman 法 [ Newman, Phys.Rev.2004 ]
CNM 法 [ Clauset ら, Phys.Rev.2004 ] ， WT 法 [Wakita , WWW2008]
ッ ン 存在 う ッ を削除 手法
貪欲法 ボ ム ッ Modularity を向上させ 手法
ー 導入や ー Newman 法 高速化
ロー ( フ全体) Modularity最適化アプロー
Louvain 法 [ Blondel ら, IOP and SISSA Journal 2008 ]
隣接 ー 同士 Modularity 最適化を行う手法
ローカ (部分 フ) Modularity最適化アプロー
現在，最速 つ高いModularityを示 手法 知
＜Louvain法を用いた近年 研究傾向＞
本研究 目的 貢献
本研究 目的
– Louvain 方 け 問題点
1. 第1 ( 決定処理) け 処理時間 増加
2. ー 選択順 依存 処理時間 増加
⇒ 次数 少 いノー 逐次集約 こ 解決
本研究 貢献
– 高速性
• 従来最速 さ Louvain 法 高速 処理可能
• 本研究 133 倍 高速化 確認
– 正確性
• 最 良いModularity 値示 さ 法 同等 Modularityを示
大規模 フ ー を対象
Modularity を用いた ン を高速化
発表 流
1. 研究 背景
2. 既存手法：Louvain法
3. 提案手法
4. 評価実験
5. め 今後 課題
既存手法：Louvain法
V D. B ., “F
w ,” J S M , O 2008.
=
第1 ー ： ー ローカ ン
• ン 順序 ノー を選択 ，選択 ー をModularity 最 高く
隣接 ー 同一
第2 ー ： 含 ー 一括集約
• 同一 内 ノー エッ を一括集約 重 付 フ 変換
1 1 1
12 2 6
集約 重 付 対 Modularity 向上 限 を繰 返
Louvain 法 問題点
問題点1：第1 け 処理時間 増加
– 第1 ー 第1 占
処理時間 99% 以上
– フ 規模 直接影響 ため
フ 規模 応 さ 増加
問題点2：ノー 選択順 依存 た処理時間 増加
– Louvain 法 処理を50回
試行 際 時間頻度分布
– ノー 選択順序 依存
処理時間 大幅 変化
0 1 2 3 4 5 6 7 8 9 10
頻度(回)
1 2 3 4 合計
Time
(sec)
857 0.29 0.03 0.03 857
各 毎 処理時間経過
発表 流
1. 研究 背景
2. 既存手法：Louvain法
3. 提案手法
4. 評価実験
5. め 今後 課題
基本的 アイ ア
Louvain 法 考察
– ン 集約 ー 別 い こ 計算不要 ー
ッ 多く含 い
提案手法 け アプロー
1. 決定 時点 ノー を逐次的 集約
同一 張
複数 ッ 参照
結果 自明 ー 参照
ー ッ 内部 参照
ー ン ム選択
ッ 参照数 増加
(1) 計算対象ノー 逐次集約
決定 たノー を逐次 集約
– 同一 を1 ー ， ッ を重 付 ッ 変換
こ ，計算対象 ー ッ を削減
同一 判明
逐次集約
集約処理前
特性：高速 高いModularity ン 可能
2
2
集約さ ー ッ
集約処理後
内： ッ 数 2倍
間： ッ 数 1倍
(2) ノー 枝刈 (1/2)
自明 2 ーンを逐次的 枝刈
– 自明 ーンを枝刈 こ 不要 参照を削除
– Modularity 定義 自明 ーン 以下 通
ーン1 枝刈
自明 ーン
隣接 ー ーン2 全 同
あ ー
ーン1 次数 1 ー
(2) ノー 枝刈 (2/2)
ーン2 枝刈 効率化
– ロー 1 逐次集約 ーン2 他 ー 次数
1 ー 表現さ
– 逐次集約 ーン1 枝刈 を交互 実行 こ
枝刈 可能
隣接 ー 全 同一 あ ッ 本数 1 ー
4
逐次集約処理
(3) 次数順ノー 選択
次数 少 い順 計算対象ノー を選択
– ー 中 他 ー 次数 少 い ー を優先選択 こ
ッ 比較回数を抑制
A
C D
B
ノー A B 同一 場合
ノー A 選択
ノー B 選択
ッ 参照数3
ッ 参照数2
次数 少 いノー Bを
選択 たほう 効率 良い
A
2
逐次集約
発表 流
1. 研究 背景
2. 提案手法
3. 既存手法：Louvain法
4. 評価実験
5. め 今後 課題
評価実験
概要
1. 提案手法 Louvain法 処理速度，処理精度を比較
2. 枝刈 有無，次数順選択 有無 処理速度比較
ー セッ
– Stanford 大学SNAP Project 公開 ー
• HepTh( 論理物理学系論文 共著者関係)： ー 数9,877 ッ 数
51,971
• CondMat( 論文 共著者関係)： ー 数23,133 ッ 数186,936
• HepPh( ー工学系論文 共著者関係)： ー 数12,008 ッ
数237,010
• Email ： ー 数36,692 ッ 数367,662
評価実験1：高速性 精度 評価
ン 処理速度 精度をLouvain法 比較
– 提案手法 Louvain法 対 最大133倍 高速化
• 特 エッ 数 多い フ ー ほ 高速 処理 い
– Modularity 値 同程度を示 い こ を確認
time(msec)
提案手法 Louvain法
10 2 10 3 10 4 10 5 10 6
HepTh CondMat HepPh email
提案手法 0.744 0.703 0.615 0.562
Louvain 0.685 0.644 0.621 0.57
Modularity 比較
評価実験2：枝刈 有無 評価
処理速度を比較
– 枝刈 有 方 高速 処理可能
• 特 CondMat，email 高速化効率 良く， 1.34 倍， 1.30 倍
を示 い
2000 3000 4000 5000 6000 7000
time(msec)
有
無
評価実験3：次数順選択有無 評価
処理速度を比較
– 次数順選択 方 高速 処理可能
• 特 CondMat，email 高速化効率 良く， 1.67 倍， 1.80 倍
を示 い
4000 6000 8000 10000 12000
time(msec)
