PEGASUS: A Peta-Scale Graph Mining System - Implementation and Observations
U Kang, Charalampos E. Tsourakakis, Christos Faloutsos
SCS, Carnegie Mellon University
ICDM'09
======================================================
這篇最要是在探討 PEGASUS這個 peta graph mining library 對 peta-scale 資料的處理
其中提到了很多graph mining operations, ex: PageRank, diameter 等
都可以用GIM-V(Generalized Iterated Matrix-Vector)來解決
GIM-V 就是一個matrix 乘上一個vector (答案淺而易見也是一個vector)
這中間的步驟分為三個部分
1. combine2: 兩個element 相乘 (就是做一次乘法)
2. combineAll: 把n個乘法的結果全部加起來 (n-1個加法)
3. assign: 把算好的值填回去
利用這樣的架構之下，要平行來處理就變得很容易
因為在distributed system是用 <key, value> 這樣的pair來運作
combine2() 可以平行來算
算好之後全部由combineAll()來加總，每個row都要作一次combineAll()
但row之間是互相獨立來運算，所以也很容易平行
assign的值每個都是獨立的，也很容易平行
paper後面就介紹怎樣用SQL語法來做到GIM-V (看來SQL對database真的很重要)
然後再透過GIM-V來實作
1. PageRank
2. Random Walk with Restart
3. Diameter Estimation
4. Connected Components
其實很明顯上面四件事幾乎都是search engine要做的事
也因此才會用到這樣peta-scale的data mining
後面就做了一些實驗來跟baseline (naive method) 比較
從time 跟 space 上面來分析 他們所提出的fast GIM-V 至少快了5倍
======================================================
優點：
1. 利用GIM-V來作比較
像這樣large-scale data mining 要如何來比較真的很困難
作者能夠想到利用這樣的方式，然後再証明一些運算(ex: PageRank)
都能透過這樣的方法來解，提供一種比較的基準，是最大的賣點
2. 提出 fast GIM-V 比naive 方法快了5倍，這部分比較像演算法，寫得很詳細
3. 真的實作且實驗在large-scale data上 (1.5Pb & 120Gb)
之前應該沒有人實驗這麼large-scale 的data
2011年5月11日 星期三
Building a High-Level Dataflow System on top of Map-Reduce: The Pig Experience
Building a High-Level Dataflow System on top of Map-Reduce: The Pig Experience
Alan F. Gates, Olga Natkovich, Shubham Chopra, Pradeep Kamath,
Shravan M. Narayanamurthy, Christopher Olston, Benjamin Reed,
Santhosh Srinivasan, Utkarsh Srivastava
Yahoo!, Inc.
VLDB ‘09
=========================================================
面對現在愈來愈大量的及運端資料的處理，Map-Reduce是運端資料處理的方式
但其對於很多地方都有限制(ex: user define function, data type)
這篇提出的方法是用dataflow programming model 就像SQL語法一樣
提供類似的服務給大量的database處理，並研究它們的performance
"Pig" 是一種high-level dataflow system 作為SQL跟Map-Reduce的媒介
所以它也提供像是SQL那樣的語法(ex: filter, join, count...)以供search
Paper裡提到Map-Reduce的架構上有些缺點：
1. 不能直接提供較為複雜的N-step dataflows
2. 無法直接處理multiple data sets
3. 一些處理data的function ex: filtering, aggregation 都要自己implement
然後Pig會compile 這些dataflow programs成為Pig Latin然後丟進Hadoop Map-Reduce
這篇paper主要focus在一些跟原本SQL架構上不同的部分
Map-Reduce Data type的部分，原本只支援int, long, double 及 char array
這裡提到可以全部轉用Pig的byte array 來handle
Map-Reduce在Map階段，會透過指派的key來控制
然後在Reduce階段再利用這些key來作sort 及 aggregation
Pig 是把logical plan 轉為physical plan 然後再轉為Map-Reduce plan
另外在Flow control 的部分在Pig可以用push model 和 pull model來達到nested program
另外在文中也提到因為Map-Reduce是用java寫的，所以memory management是很大的問題
因為java不允許developer直接對memory allocation來作控制
最直接的想法就是把直接調整 java virtual machine 能用的記憶体空間
但這樣會降低performance 很多
這裡用的方法是透過Pig，先把data集成 bags再去處理
另外在user define function (UDF)這裡也可以透過streaming的概念
把executable files 放在Pig 的處理階一併執行，這樣就可以解決原本的限制
========================================================
這篇感覺是在Map-Reduce 的架構上說出它們現有的缺點，然後用Pig再以改進
Alan F. Gates, Olga Natkovich, Shubham Chopra, Pradeep Kamath,
Shravan M. Narayanamurthy, Christopher Olston, Benjamin Reed,
Santhosh Srinivasan, Utkarsh Srivastava
Yahoo!, Inc.
VLDB ‘09
=========================================================
面對現在愈來愈大量的及運端資料的處理，Map-Reduce是運端資料處理的方式
但其對於很多地方都有限制(ex: user define function, data type)
這篇提出的方法是用dataflow programming model 就像SQL語法一樣
提供類似的服務給大量的database處理，並研究它們的performance
"Pig" 是一種high-level dataflow system 作為SQL跟Map-Reduce的媒介
所以它也提供像是SQL那樣的語法(ex: filter, join, count...)以供search
Paper裡提到Map-Reduce的架構上有些缺點：
1. 不能直接提供較為複雜的N-step dataflows
2. 無法直接處理multiple data sets
3. 一些處理data的function ex: filtering, aggregation 都要自己implement
然後Pig會compile 這些dataflow programs成為Pig Latin然後丟進Hadoop Map-Reduce
這篇paper主要focus在一些跟原本SQL架構上不同的部分
Map-Reduce Data type的部分，原本只支援int, long, double 及 char array
這裡提到可以全部轉用Pig的byte array 來handle
Map-Reduce在Map階段，會透過指派的key來控制
然後在Reduce階段再利用這些key來作sort 及 aggregation
Pig 是把logical plan 轉為physical plan 然後再轉為Map-Reduce plan
另外在Flow control 的部分在Pig可以用push model 和 pull model來達到nested program
另外在文中也提到因為Map-Reduce是用java寫的，所以memory management是很大的問題
因為java不允許developer直接對memory allocation來作控制
最直接的想法就是把直接調整 java virtual machine 能用的記憶体空間
但這樣會降低performance 很多
這裡用的方法是透過Pig，先把data集成 bags再去處理
另外在user define function (UDF)這裡也可以透過streaming的概念
把executable files 放在Pig 的處理階一併執行，這樣就可以解決原本的限制
========================================================
這篇感覺是在Map-Reduce 的架構上說出它們現有的缺點，然後用Pig再以改進
2011年5月4日 星期三
Describable Visual Attributes for Face Verification and Image Search
Describable Visual Attributes for Face Verification and Image Search
Neeraj Kumar, Alexander C. Berg, Peter N. Belhumeur, and Shree K. Nayar
PAMI 2011
========================================================
這篇paper主要是想找出face attributes進而來做face verification 跟 image research
先利用low-level features 去learn intermediate representations
再根據given的attribute label 然後自動去train classifier
藉由classifier 去找出該用哪些representations 比較適合 each attribute
所以最後找出來的這些attribute都是有具体實際意義而不是latent
這些叫作visual attribute ，可以把它們當作visual word來用
這樣的好處是，這些representations 可以重複使用
也就是要加一種attribute 就可以用representation的組合來表示，彈性比較大
這裡主要是應用在face verification 跟 image research
a. face verification: 拿出兩張圖，問是不是同一位(可以不用非常frontal)
b. image research: "smiling asian men with glasses" 找出符合這些條件的圖
方法就是在取完各種low-level feature後
用的概念就是假設要找"gender" 來當作attribute
利用SVM來train, 準備的training data 大概是500~2000張 (可能是從網路上抓的)
然後看哪些low-level feature 最能表現出在 male > 0; female < 0
接著這個attribute就用這些feature來表示
當然這些feature的combine 要經過一些weight的調整
這樣做出來的classifier的結果 比起其他的方法都要好得多
另外還有作simile classifier
有點類似說這張臉有沒有類似某人的鼻子這樣的classifier
========================================================
實驗的結果 用這樣的方法
face verification 可以達到91.86%
如果是用人的判斷來當groundtruth 更可達到99.2% (因為有些case連人都認不出)
image search的部分則是用結果來呈現最後的結果比yahoo! image search 要好
========================================================
優點：
1. 把缺點跟不足的部分都講得很清楚，也提供別人可以研究的方向
2. 取出來的attribute都是有physical meaning ，這樣在visualization等會有幫助
3. 跟其他相關paper的結果作比較
缺點
1. 要找的 attribute都是 given，可能存在更有鑑別度的attribute
2. 每種attribute 的training data 都要去標
Neeraj Kumar, Alexander C. Berg, Peter N. Belhumeur, and Shree K. Nayar
PAMI 2011
========================================================
這篇paper主要是想找出face attributes進而來做face verification 跟 image research
先利用low-level features 去learn intermediate representations
再根據given的attribute label 然後自動去train classifier
藉由classifier 去找出該用哪些representations 比較適合 each attribute
所以最後找出來的這些attribute都是有具体實際意義而不是latent
這些叫作visual attribute ，可以把它們當作visual word來用
這樣的好處是，這些representations 可以重複使用
也就是要加一種attribute 就可以用representation的組合來表示，彈性比較大
這裡主要是應用在face verification 跟 image research
a. face verification: 拿出兩張圖，問是不是同一位(可以不用非常frontal)
b. image research: "smiling asian men with glasses" 找出符合這些條件的圖
方法就是在取完各種low-level feature後
用的概念就是假設要找"gender" 來當作attribute
利用SVM來train, 準備的training data 大概是500~2000張 (可能是從網路上抓的)
然後看哪些low-level feature 最能表現出在 male > 0; female < 0
接著這個attribute就用這些feature來表示
當然這些feature的combine 要經過一些weight的調整
這樣做出來的classifier的結果 比起其他的方法都要好得多
另外還有作simile classifier
有點類似說這張臉有沒有類似某人的鼻子這樣的classifier
========================================================
實驗的結果 用這樣的方法
face verification 可以達到91.86%
如果是用人的判斷來當groundtruth 更可達到99.2% (因為有些case連人都認不出)
image search的部分則是用結果來呈現最後的結果比yahoo! image search 要好
========================================================
優點：
1. 把缺點跟不足的部分都講得很清楚，也提供別人可以研究的方向
2. 取出來的attribute都是有physical meaning ，這樣在visualization等會有幫助
3. 跟其他相關paper的結果作比較
缺點
1. 要找的 attribute都是 given，可能存在更有鑑別度的attribute
2. 每種attribute 的training data 都要去標
Where’s Waldo: Matching People in Images of Crowds
Where’s Waldo: Matching People in Images of Crowds
Rahul Garg, Deva Ramanan, Steven M. Seitz, Noah Snavely
CVPR 2011
=================================================
這篇paper的目的很簡單，就是像在玩 "where's Waldo" 這個遊戲一樣
在一張人很多的相片裡，找出所要找的那個指定的人
這個問題困難的地方在於要找的對象通常很小，而且是在一大群人裡面找出來
傳統的一些方法，像是取feature 作matching 或是用人臉來判斷 效果都很有限
因為人很小所以feature一定很少，且人常常不是正面，所以也沒有人臉feature
不過這篇paper的假設很強，他是說在接近的時間點，同一個地點會有不同的拍攝者
也就是說這些照片是時間間隔很短，拍的場景幾乎一樣，但角度不同
那一大群人也幾乎是同一群，要找的人就在裡面
第一步是先把 user input 的那個人learn appearance model
這裡有提到如果build 相當精確的model，那就會因為動作不同或遮蔽物而影響結果
因此這裡採用的是part-based，也就是分別算出每個部分的分數，最後再合併
值得注意的是這裡的training data就只有user 的那張input
color model用的是 pixel-level RGB
因為要找的人很小，SIFT等的feature 不多
另外這裡也有說如果color特別明顯，它的weight就會上升
對於遮蔽的問題，這裡用的part-based的方法，然後根據不同part給不同的weight
最後找出的目標會用2D的投射來猜出這樣的動作改變是否合理
除了對目標一些feature的處理，還用到了3D環境一些簡單的model來輔助
例如說把input跟candidate投影到1D上面，看看高度等限制是否合理
然後用了一些假設：
a. 人通常會在同一群人裡
b. 鄰近的人通常就會是那群人
接著用MRF optimization 作出最後的結果，判斷是不是有找到
=================================================
實驗的部分
這裡有強調groundtruth是他們自己標的
但標這個的工作就算是由人來做也是相當困難
有些時候甚至是system找出來才發現之前沒有標到
最後利用PR-curve來呈現出結果
=================================================
優點：
1. 整個問題很有創意，而且算是自己定義的新問題
2. 這個問題本身就算是要人來做也不容易，問題的難度很高
缺點：
1. 假設很強，也就是換個場景就找不到，例子也都是在同一個時間點下的結果
2. 實驗的groundtruth那裡其實不是很嚴謹，不過這就算要人來標也很困難十
3. 每個input 的找出的結果個數應該都不多，不知道怎麼畫出這麼詳細的PR-curve
Rahul Garg, Deva Ramanan, Steven M. Seitz, Noah Snavely
CVPR 2011
=================================================
這篇paper的目的很簡單，就是像在玩 "where's Waldo" 這個遊戲一樣
在一張人很多的相片裡，找出所要找的那個指定的人
這個問題困難的地方在於要找的對象通常很小，而且是在一大群人裡面找出來
傳統的一些方法，像是取feature 作matching 或是用人臉來判斷 效果都很有限
因為人很小所以feature一定很少，且人常常不是正面，所以也沒有人臉feature
不過這篇paper的假設很強，他是說在接近的時間點，同一個地點會有不同的拍攝者
也就是說這些照片是時間間隔很短，拍的場景幾乎一樣，但角度不同
那一大群人也幾乎是同一群，要找的人就在裡面
第一步是先把 user input 的那個人learn appearance model
這裡有提到如果build 相當精確的model，那就會因為動作不同或遮蔽物而影響結果
因此這裡採用的是part-based，也就是分別算出每個部分的分數，最後再合併
值得注意的是這裡的training data就只有user 的那張input
color model用的是 pixel-level RGB
因為要找的人很小，SIFT等的feature 不多
另外這裡也有說如果color特別明顯，它的weight就會上升
對於遮蔽的問題，這裡用的part-based的方法，然後根據不同part給不同的weight
最後找出的目標會用2D的投射來猜出這樣的動作改變是否合理
除了對目標一些feature的處理，還用到了3D環境一些簡單的model來輔助
例如說把input跟candidate投影到1D上面，看看高度等限制是否合理
然後用了一些假設：
a. 人通常會在同一群人裡
b. 鄰近的人通常就會是那群人
接著用MRF optimization 作出最後的結果，判斷是不是有找到
=================================================
實驗的部分
這裡有強調groundtruth是他們自己標的
但標這個的工作就算是由人來做也是相當困難
有些時候甚至是system找出來才發現之前沒有標到
最後利用PR-curve來呈現出結果
=================================================
優點：
1. 整個問題很有創意，而且算是自己定義的新問題
2. 這個問題本身就算是要人來做也不容易，問題的難度很高
缺點：
1. 假設很強，也就是換個場景就找不到，例子也都是在同一個時間點下的結果
2. 實驗的groundtruth那裡其實不是很嚴謹，不過這就算要人來標也很困難十
3. 每個input 的找出的結果個數應該都不多，不知道怎麼畫出這麼詳細的PR-curve
訂閱：
文章 (Atom)