Session 4 : Security II

Size: px

Start display at page:

Download "Session 4 : Security II"

しのぶかたづ
4 years ago
Views:

1 SIGMOD2011 勉強会 Session 19: Ranking 担当 : 池田大塚三津石安永 ( 筑波大学 ) 1 Session 19: Ranking 担当 : 池田大塚三津石安永 ( 筑波大 )

2 セッション概要 1. On Pruning for Top-K Ranking in Uncertain Databases 確率的データベースにおけるトップ k ランキング (PRF 関数 ) の高速化 2. PathSim: Meta Path-Based Top-K Similarity Search in Heterogeneous Information Networks 異種情報ネットワークにおける類似検索手法の提案 3. Optimizing and Parallelizing Ranked Enumeration ランク付けの最適化問題解法アルゴリズム Lawler-Murty s procedure の並列化 4. Efficient Rank Join with Aggregation Constraints Rank Join(Top-k queries) での集約制約を用いた効率化 2 Session 19: Ranking 担当 : 池田大塚三津石安永 ( 筑波大 )

3 On Pruning fot Top-k Ranking in Uncertain Databases Chonghai Wang, Li Yan Yuan, Jia-Huai You, Osmar R Zaiane (University of Alberta), Jian Pei (Simon Fraser University) 3 Session 19: Ranking 担当 : 池田大塚三津石安永 ( 筑波大 )

4 研究の目的ひとことで言うと? 確率的データベースにおけるトップ k ランキング手法である PRF を Pruning して高速化生成ルール r 論文中の Figure1 から引用 PRF(Parameterized Ranking Functions(VLDB 09)) トップ k ランキングの様々な手法を, パラメータを調整することで近似的にシミュレートするランキング関数 PRF ω : Υ( t) WPW ( t) ω( t, βw( t)) Pr( W) PW(t) βw(t) ω(t, i ) : tを含む全ての可能世界のセット : 可能世界 Wにおけるtの位置 : 重み関数 4 Session 19: Ranking 担当 : 池田大塚三津石安永 ( 筑波大 )

5 キーアイディア確率的データベースTが与えられた時に, q 個のタプルのセット (Q = {t 1,..., t q }) と, それらに関連づけられた生成ルールr (R = {r 1,..., r l }) を考える. 任意の t Qに対し, それらのUpper Boundを見つけることが目的. そのため次の式を満たすような実数 c i を求める c < 0 の場合, 次のように変形可能この時,t が Upper Bound にあたる 5 q i1 c iυ( ti) 0 c i Υ( t) Υ( ti) c tiq, tit Session 19: Ranking 担当 : 池田大塚三津石安永 ( 筑波大 )

6 評価実験実験内容 2 つのランキング方法 (random2, PT-k) に対して k などを変えて計算するタプル数, 実行時間などの比較を行う結果特に PT-k 関数に対し素晴らしい高速化を実現論文中 ( の Figure6 から引用 6 Session 19: Ranking 担当 : 池田大塚三津石安永 ( 筑波大 )

7 [2]PathSim: Meta Path-Based Top-K Similarity Search in Heterogeneous Information Networks Yizhou Sun (UIUC), Jiawei Han (UIUC), Xifeng Yan (UCSB), Philip Yu (UIC), Tianyi Wu (Microsoft) 7 Session 19: Ranking 担当 : 安永 ( 筑波大 )

8 研究の目的ひとことで言うと? 異種情報ネットワークにおける類似検索手法の提案類似検索この著者と領域評判が似ている著者は? 同種ネットワークにおける類似検索オブジェクト間のパスの多さオブジェクト間の近さ異なるタイプのオブジェクトは区別できない提案する類似検索パスのセマンティクスを考慮 top-k 検索の処理の効率化異種情報ネットワークの例 :DBLPネットワーク VLDB paper1 花子 paper2 SIGMOD paper3 太郎同種ネットワークの例 : コミュニティネットワーク花子春子太郎 8 Session 19: Ranking 担当 : 安永 ( 筑波大 )

9 キーアイディア Meta Path 2 つのオブジェクト間のパスをオブジェクトと関係の種類の並びで記述共著者の関係の Meta Path オブジェクト間の新しい関係 ( top-k 検索処理の高速化に使用 ) 提案する類似検索手法で Meta Path を使う PathSim 以下の特徴をもつオブジェクト間の類似性を高く評価指定した Meta Path に属するパスの数が多い見た目のバランスが似ている春子 p1 花子 writing written-by 著者論文著者 9 Session 19: Ranking 担当 : 安永 ( 筑波大 )

Path の長さの影響 MP > (MP) 2 > (MP) 3 C) Meta Path がセマンティクスを表せているか下図 MP:

10 評価実験対象データ : DBLP ネットワーク,Flicker ネットワーク A) 提案手法と既存手法それぞれの検索結果の比較入力 : オブジェクト,Meta Path 出力 : 類似度の高い順見比べると提案手法が良 MP: 画像 - タグ画像 [2] B) Meta Path の長さの影響 MP > (MP) 2 > (MP) 3 C) Meta Path がセマンティクスを表せているか下図 MP: 画 - タグー画 - グループー画 - タグー画 [2] Session 19: Ranking 担当 : 安永 ( 筑波大 ) 10

11 Optimizing and Parallelizing Ranked Enumeration Konstantin Golenberg (The Hebrew University), Benny Kimelfeld (IBM Research - Almaden), Yehoshua Sagiv (Hebrew University, Jerusalem) 11 Session 19: Ranking 担当 : 大塚 ( 筑波大 )

12 Optimizing and Parallelizing Ranked Enumeration 研究の目的ひとことで言うと? ランク付けの最適化問題解法アルゴリズム Lawler-Murty s procedure の並列化 Lawler-Murty s procedure 問題に対する Answer 列挙 12 Keyword サーチなど Answer の結果をソート上位 k 個並べるコスト大上位 1 個のみ最適化問題データを制約により区分けし最適化問題を解く Session 19: Ranking 担当 : 大塚 ( 筑波大 ) st Ans nd Ans

13 Optimizing and Parallelizing Ranked Enumeration キーアイディア Freezing 16 領域 A ( 確定 ) 区分けした各領域での最大値計算は領域ごとに処理時間が異なるすべての領域で計算が終了するまで待機計算中の領域の現時点での最大値が他の領域の最大値より小さい場合計算を中断 (Freezing) する並列化 27 領域 B ( 計算中 ) 各領域の計算をスレッドに割り当てただけでは処理速度はほとんど向上しない idle 状態の発生 31 領域 C ( 確定 ) 領域 B の計算中断 31 が最大値 16 領域 A ( 確定 ) 27 領域 B ( 計算中 ) 29 領域 D ( 計算中 ) 23 領域 E ( 計算中 ) 領域 C を分割 Computed Answer タスクと Frozen タスクにわけ Frozen タスクでは複数のスレッドで最大値計算を行なっておく Computed Answer タスクで空きができた時点で Frozen タスクにある中で最もスコアの大きい物と Computed Answer タスクにあるスコアを比較 13 Session 19: Ranking 担当 : 大塚 ( 筑波大 )

14 % of Serial Freezing % of Lawler-Murty Optimizing and Parallelizing Ranked Enumeration 評価実験 (VLDB2011 発表スライド Sesson9-3 より ) Simple Lawler-Murty vs. Freezing グラフ探索結果の処理時間の比較 Freezing により処理時間を約 56% に削減 SingleCore Freezing vs. MultiCore 1000 通常の並列化では 4core 使用して 1core の Freezing と同程度のパフォーマンス Freezing を組み合わせた並列化では 8 スレッドで Freezing の約 5% の処理時間 ms k = 10, 100 Simple Lawler-Murty Freezing Mondial Short Medium Long Short Medium Long % 40% 30% Number of Threads 20% 10% 0% Number of Threads 14 Session 19: Ranking 担当 : 大塚 ( 筑波大 )

15 Efficient Rank Join with Aggregation Constraints Min Xie (University of British Columbia), Laks Lakshmanan (University of British Columbia), Peter Wood (Birkbeck, University of London) 15 Session 19: Ranking 担当 : 三津石 ( 筑波大 )

16 研究の目的ひとことで言うと? Rank Join (Top-k queries) における集約制約 (Aggregation Constraints) を用いた効率的アルゴリズムの提案 Rank Join のアプリケーション例 package recommendation 集約制約の例 Museum.Cost+Restaurant.Cost 20 集約制約を用いた Rank Join の例から引用集約とは結合結果リレーションにおける各タプル内の値の集約 16 Session 19: Ranking 担当 : 三津石 ( 筑波大 )

17 キーアイディア Rank Join を実行する際には多くの状況で集約制約は自然に (naturally) でてくるもの集約制約を用い Rank Join の実行時間を効率化できるとよい集約制約を用いた効率的アルゴリズムを提案提案アルゴリズム決定的アルゴリズム (2つの枝刈り戦略) 1. SubS-Pruning 2. Adaptive SubS-Pruning 確率的アルゴリズム 17 Session 19: Ranking 担当 : 三津石 ( 筑波大 )

18 評価実験実験内容 4 つのアルゴリズムを実装し実行速度と枝刈りを比較 (a) Post Filtering( ナイーブ ) (b) SubS-Pruning (c) Adaptive SubS-Pruning (d) Probabilistic 確率的アルゴリズムの結果の質を評価結果提案アルゴリズムはいずれも既存手法を上回る性能確率的アルゴリズムは高い 18 質の結果を返す

スライド 1

スライド 1 ICDE2016 & WWW2016 勉強会 WWW2016 Session 22 京都大学加藤誠 WWW2016 Session 22 Modeling User Exposure in Recommendation Dawen Liang (Columbia University) Laurent Charlin (McGill University) James McInerney (Columbia