際際滷

際際滷Share a Scribd company logo

ICDE2014 Session 22 Similarity Joins

?
?
M
Masumi Shirakawa

ICDE 2014のセッション22仝Similarity Joins々についてのgなまとめです。

1 of 12
Download to read offline
Session 22: Similarity Joins 毅輝 易寒┫點羇麪В ‐ICDE2014茶氏／
まずはじめに´ ? Similarity Joinとはなんぞや ? 2つのデ`タ鹿栽の嶄から貌するデ`タペアを畠何つけるタスク ? Self Similarity JoinとかSimilarity Self-Joinというのもあるが ? 1つのデ`タ鹿栽の嶄から貌するデ`タペアを畠てつけるタスク ? やってることは貌たようなもの 2 Session 22: Similarity Joins 毅輝紺彜┌┫點羇麪В デ`タ鹿栽 A D A H A R B C B Q 貌業θ 參貧のペア Self Similarity Joinの箭 ??? 輝する ペアを 畠て双
Session 22: Similarity Joins の猟 DE140108.PDF L2AP: Fast Cosine Similarity Search with Prefix L-2 Norm Bounds David C. Anastasiu, George Karypis DE140143.PDF PHiDJ: Parallel Similarity Self-Join for High-Dimensional Vector Data with MapReduce Sergej Fries, Brigitte Boden, Grzegorz Stepien, Thomas Seidl DE140387.PDF Melody-Join: Efficient Earth Mover¨s Distance Similarity Joins Using MapReduce Jin Huang, Rui Zhang, Rajkumar Buyya, Jian Chen 3 Session 22: Similarity Joins 毅輝紺彜┌┫點羇麪В
冩梢嘘尚とか 4 Session 22: Similarity Joins 毅輝紺彜┌┫點羇麪В L2AP: Fast Cosine Similarity Search with Prefix L-2 Norm Bounds d1 d2 d3 dm v1 0.1 0 0.2 ´ 0 v2 0.2 0 0.1 ´ 0 v3 0 0.1 0 ´ 0.3 ´ vn 0.3 0.1 0 ´ 0 {v1, v2}, {v2, vn}, ´ コサイン 貌業が θ參貧 d1 ★ {v1, 0.1},{v2, 0.2},´,{vn, 0.3} d2 ★ {v3, 0.1},´,{vn, 0.1} d3 ★ {v1, 0.2},{v2, 0.1},´ ´ 崔沫哈 ? 階互肝圷かつEなベクトル鹿栽を鵑箸沓コサイン貌業が ｦ頒塢呂離戰トルペアを畠てつけたい ? 麻楚がO(n2m2)ただしnはベクトル方mは肝圷方 ? よくあるやり圭載崔沫哈を恬って掲巣撹蛍にのみアクセス ? ベクトルが屎ｻされていればdot┠覗祿彪嵳平のeで麻辛嬬
? AllPairs [Bayardo, WWW07] ? 啜痛哈やzみのないベクトルペアの壼豚俳り里討鯰个κ峽 ? MMJoin [Lee, DEXA10] 俳り里討鬚茲袵臚擇撲个返隈を戻宛 ? 恠勃个離戰トルの隆恠鵬新屬 ?＞ として ??? ?＞, ? ＋ 1 2 ?＞ 2 + 1 2 で貌業を容y ? 戻宛返隈L2AP*1 ? コ`シ`愁轡絅錺襯弔硫撒畔修鮴喘して俳り里討鬚気蕕穆臚擇烹 ? 貌業の容y ??? ?＞, ? ＋ ?＞ は駅ず屡贋返隈より屎_ ? ^苧 ?＞ ? 1 2 − 0 ? 1 2 ?＞ 2 + 1 2 − ?＞ より L2APによる容y､里曚Δ駅ずドットプロダクトの寔の､暴い 佩双 戻宛返隈 5 Session 22: Similarity Joins 毅輝紺彜┌┫點羇麪В L2AP: Fast Cosine Similarity Search with Prefix L-2 Norm Bounds (1)インデックスを啜弔防撹 (2)剃から恠烹インデックスを喘いて 貌業麻､魍えるzみが なくなったら恠砲鰆亢 光ベクトルに(1)(2)のI尖 yは屎ｻされているのでノルムが1 *1 ソフトウェア http://www-users.cs.umn.edu/~dragos/l2ap/
u ? 6つのgデ`タを聞ってu nnz: 佩双畠悶での掲巣撹蛍方 mrl: 1佩の峠譲掲巣撹蛍方 mcl: 1双の峠譲掲巣撹蛍方 ? t を笋┐討發燭い討い栽 L2APが恷堀 ? インデックスサイズや余嶄Y惚のデ`タ サイズもpっていたので福スペ`ス ? BayesLSH [Satuluri, VLDB12] などの 除貌返隈と曳べた栽でも謹くの栽 L2APが戮辰討い殖。しくは猟歌孚 6 Session 22: Similarity Joins 毅輝紺彜┌┫點羇麪В L2AP: Fast Cosine Similarity Search with Prefix L-2 Norm Bounds 猟より 猟より
冩梢嘘尚とか ? 互肝圷なベクトル鹿栽を鵑箸沓鉦xがε參和の ベクトルペアをMapReduceを聞って畠てつけたい ? MR-DSJ [Seidl, BTW13]坤哀螢奪疋扎`スの返隈揖じ冩梢グルDプによる撹惚 ? d肝圷のベクトルをd肝圷のグリッドに塘崔Reducerが光セルを毅輝 ? 除くのグリッドに了崔するベクトルgのみ鉦xを麻 ? 業U業で鉦x麻とかなら}ないけど互肝圷だとO俊セルの方が 峺方v方議に紗してしまう ★ 宥佚コスト寄 7 Session 22: Similarity Joins 毅輝紺彜┌┫點羇麪В PHiDJ: Parallel Similarity Self-Join for High-Dimensional Vector Data with MapReduce BTW坤疋ぅ弔離禰`タベ`スの氏h 發ぞvのセルを毅輝するReducerは 文咫で幣したセルgを毅輝 2肝圷の栽 猟より
戻宛返隈 ? 互肝圷腎gをkの肝圷グル`プに蛍けてMR-DSJをg佩 ? 光肝圷グル`プでの Y惚を恷瘁に鹿s ? 肝圷グル`プ方は肝圷方に して侘なのでだいぶマシ ? 光肝圷グル`プにしてはよりタイトな ? ? = ? ? ? を 聞うことで昨aのペアをpらせる ? Q: そんなことしたら盾を毛すケ`ス┌苓ﾐ圍もk伏するのでは A: ありえないなぜならeの肝圷グル`プの竃薦として誼られるから ? グリッドが譲吉だと匯何のセルにデ`タが陶るMR-DSJでも}だった ? デ`タが富ないところは方が譲吉になるようﾚい譴魑５韻気擦 ┐海譴榔粧仂燭箸篭請△靴}だからは福くみたいなこといててgなh苧しかなかった´ 8 Session 22: Similarity Joins 毅輝紺彜┌┫點羇麪В PHiDJ: Parallel Similarity Self-Join for High-Dimensional Vector Data with MapReduce 猟より L?-norm鉦xの栽
u ? 2肝圷゛20肝圷の夘貌デ`タ 10肝圷のMIRFLICKR*1デ`タ嘔2つ ┐發辰噺澳淋なデ`タでのY惚がたかった´ ? 8肝圷ぐらいから森が竃る ? Theta-join [Okcan, SIGMOD11]より互堀 ┐發辰箸癸この返隈は販吭のJoinが辛嬬だが ? MR-SimJoin [Silva, Cloud-I12]と曳^恣和蹌 ? Flickr參翌では蔚ぐらい堀かったが 故伉のgデ`タでけるのはどうなの´ 9 Session 22: Similarity Joins 毅輝紺彜┌┫點羇麪В PHiDJ: Parallel Similarity Self-Join for High-Dimensional Vector Data with MapReduce 猟より *1 http://press.liacs.nl/mirflickr 猟より猟より Cloud-I 2012VLDB 2012のワ`クショップ
冩梢嘘尚とか ? 1゛3肝圷殻業のヒストグラムの鹿栽を鵑箸沓EMDがε參和 のヒストグラムペアを MapReduceを聞って畠てつけたい ? EMD (Earth Mover｀s Distance)災桟修離劵好肇哀薀爐ら麿圭のヒスト グラムになるまでに勣する､両t卞咼灰好硲猟忖双のｼ鉦xに貌てる ? 鮫碧 [Ruzon, IEEE TPAMI01]ジェスチャJR [Ren, ACM MM11]嶷} 奮 [Xu, CVPR08]_楕デ`タマイニング[Xu, VLDBJ12]など嫌ﾚい鮄 10 Session 22: Similarity Joins 毅輝紺彜┌┫點羇麪В Melody-Join: Efficient Earth Mover¨s Distance Similarity Joins Using MapReduce Σ卞咾気擦 〜奉來gの鉦x ha hb EMD(ha, hb) =1〜1+2〜1=3 貌鮫馘e┛k燕スライドより
戻宛返隈 ? ハフ腎g*1に卞し[Ruttenberg, VLDB12]除そうなペアのみ麻 これを3指のMapReduceジョブでK双I尖させSimilarity Join晒 ? 1指朕で光ヒストグラムをハフ腎gに亟 ? 2指朕でハフ腎gの光セルについてLower BoundLBに聞うエラ`Cを麻竃 gHの拙el業とNormal Distributionによる指｢の`餓より麻竃 ? 3指朕で光ヒストグラムごと光セルごとに A)徭蛍の了崔するセルならネイティブレコ`ド B)それ參翌のセルでかつLBがε參和ならゲストレコ`ド としてヒストグラムとセルのMをMap ? 3指朕のReducerが光セルを毅輝ネイティブ★ネイティブゲストのEMD麻 11 Session 22: Similarity Joins 毅輝紺彜┌┫點羇麪В Melody-Join: Efficient Earth Mover¨s Distance Similarity Joins Using MapReduce I尖の送れ猟より いやh苧畠隼蛍からないんだけど とにかく鮫I尖とかでよく聞われるハフ腎gに卞すことでEMDが除そうなペア を紳糞弔牧つけられるのでそれをMapReduceに鬉気擦殖という湖じです *1 Lさrと叔業θのMの鹿栽で燕Fされた腎g http://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%95%E5%A4%89%E6%8F%9B ここまでのI尖で除そうなペアとして火った
u ? 5つのgデ`タセットでu COREL*1Color (CC), Layout (CL) MIRFLICKRVertical (MV), Horizontal (MH), Slash (MS) ┐海離好薀ぅ匹任MVのY惚のみ燕幣 ? MR-SimJoin [Silva, SIGMOD12, Demo]と曳^ ? 鮫颪諒cardinalityやEMDの､笋┐討睫甍己峽┐械 12 Session 22: Similarity Joins 毅輝紺彜┌┫點羇麪В Melody-Join: Efficient Earth Mover¨s Distance Similarity Joins Using MapReduce *1 http://archive.ics.uci.edu/ml/datasets/Corel+Image+Features 1つ念の猟に竃てきた[Silva, Cloud-I12]と揖じ返隈 猟より猟より 亟驩v方3N グリッド4〜4セル Hadoopインスタンス48 その麿セッティング

More Related Content

ICDE2014 Session 22 Similarity Joins

  • 1. Session 22: Similarity Joins 毅輝 易寒┫點羇麪В ‐ICDE2014茶氏／
  • 2. まずはじめに´ ? Similarity Joinとはなんぞや ? 2つのデ`タ鹿栽の嶄から貌するデ`タペアを畠何つけるタスク ? Self Similarity JoinとかSimilarity Self-Joinというのもあるが ? 1つのデ`タ鹿栽の嶄から貌するデ`タペアを畠てつけるタスク ? やってることは貌たようなもの 2 Session 22: Similarity Joins 毅輝紺彜┌┫點羇麪В デ`タ鹿栽 A D A H A R B C B Q 貌業θ 參貧のペア Self Similarity Joinの箭 ??? 輝する ペアを 畠て双
  • 3. Session 22: Similarity Joins の猟 DE140108.PDF L2AP: Fast Cosine Similarity Search with Prefix L-2 Norm Bounds David C. Anastasiu, George Karypis DE140143.PDF PHiDJ: Parallel Similarity Self-Join for High-Dimensional Vector Data with MapReduce Sergej Fries, Brigitte Boden, Grzegorz Stepien, Thomas Seidl DE140387.PDF Melody-Join: Efficient Earth Mover¨s Distance Similarity Joins Using MapReduce Jin Huang, Rui Zhang, Rajkumar Buyya, Jian Chen 3 Session 22: Similarity Joins 毅輝紺彜┌┫點羇麪В
  • 4. 冩梢嘘尚とか 4 Session 22: Similarity Joins 毅輝紺彜┌┫點羇麪В L2AP: Fast Cosine Similarity Search with Prefix L-2 Norm Bounds d1 d2 d3 dm v1 0.1 0 0.2 ´ 0 v2 0.2 0 0.1 ´ 0 v3 0 0.1 0 ´ 0.3 ´ vn 0.3 0.1 0 ´ 0 {v1, v2}, {v2, vn}, ´ コサイン 貌業が θ參貧 d1 ★ {v1, 0.1},{v2, 0.2},´,{vn, 0.3} d2 ★ {v3, 0.1},´,{vn, 0.1} d3 ★ {v1, 0.2},{v2, 0.1},´ ´ 崔沫哈 ? 階互肝圷かつEなベクトル鹿栽を鵑箸沓コサイン貌業が ｦ頒塢呂離戰トルペアを畠てつけたい ? 麻楚がO(n2m2)ただしnはベクトル方mは肝圷方 ? よくあるやり圭載崔沫哈を恬って掲巣撹蛍にのみアクセス ? ベクトルが屎ｻされていればdot┠覗祿彪嵳平のeで麻辛嬬
  • 5. ? AllPairs [Bayardo, WWW07] ? 啜痛哈やzみのないベクトルペアの壼豚俳り里討鯰个κ峽 ? MMJoin [Lee, DEXA10] 俳り里討鬚茲袵臚擇撲个返隈を戻宛 ? 恠勃个離戰トルの隆恠鵬新屬 ?＞ として ??? ?＞, ? ＋ 1 2 ?＞ 2 + 1 2 で貌業を容y ? 戻宛返隈L2AP*1 ? コ`シ`愁轡絅錺襯弔硫撒畔修鮴喘して俳り里討鬚気蕕穆臚擇烹 ? 貌業の容y ??? ?＞, ? ＋ ?＞ は駅ず屡贋返隈より屎_ ? ^苧 ?＞ ? 1 2 − 0 ? 1 2 ?＞ 2 + 1 2 − ?＞ より L2APによる容y､里曚Δ駅ずドットプロダクトの寔の､暴い 佩双 戻宛返隈 5 Session 22: Similarity Joins 毅輝紺彜┌┫點羇麪В L2AP: Fast Cosine Similarity Search with Prefix L-2 Norm Bounds (1)インデックスを啜弔防撹 (2)剃から恠烹インデックスを喘いて 貌業麻､魍えるzみが なくなったら恠砲鰆亢 光ベクトルに(1)(2)のI尖 yは屎ｻされているのでノルムが1 *1 ソフトウェア http://www-users.cs.umn.edu/~dragos/l2ap/
  • 6. u ? 6つのgデ`タを聞ってu nnz: 佩双畠悶での掲巣撹蛍方 mrl: 1佩の峠譲掲巣撹蛍方 mcl: 1双の峠譲掲巣撹蛍方 ? t を笋┐討發燭い討い栽 L2APが恷堀 ? インデックスサイズや余嶄Y惚のデ`タ サイズもpっていたので福スペ`ス ? BayesLSH [Satuluri, VLDB12] などの 除貌返隈と曳べた栽でも謹くの栽 L2APが戮辰討い殖。しくは猟歌孚 6 Session 22: Similarity Joins 毅輝紺彜┌┫點羇麪В L2AP: Fast Cosine Similarity Search with Prefix L-2 Norm Bounds 猟より 猟より
  • 7. 冩梢嘘尚とか ? 互肝圷なベクトル鹿栽を鵑箸沓鉦xがε參和の ベクトルペアをMapReduceを聞って畠てつけたい ? MR-DSJ [Seidl, BTW13]坤哀螢奪疋扎`スの返隈揖じ冩梢グルDプによる撹惚 ? d肝圷のベクトルをd肝圷のグリッドに塘崔Reducerが光セルを毅輝 ? 除くのグリッドに了崔するベクトルgのみ鉦xを麻 ? 業U業で鉦x麻とかなら}ないけど互肝圷だとO俊セルの方が 峺方v方議に紗してしまう ★ 宥佚コスト寄 7 Session 22: Similarity Joins 毅輝紺彜┌┫點羇麪В PHiDJ: Parallel Similarity Self-Join for High-Dimensional Vector Data with MapReduce BTW坤疋ぅ弔離禰`タベ`スの氏h 發ぞvのセルを毅輝するReducerは 文咫で幣したセルgを毅輝 2肝圷の栽 猟より
  • 8. 戻宛返隈 ? 互肝圷腎gをkの肝圷グル`プに蛍けてMR-DSJをg佩 ? 光肝圷グル`プでの Y惚を恷瘁に鹿s ? 肝圷グル`プ方は肝圷方に して侘なのでだいぶマシ ? 光肝圷グル`プにしてはよりタイトな ? ? = ? ? ? を 聞うことで昨aのペアをpらせる ? Q: そんなことしたら盾を毛すケ`ス┌苓ﾐ圍もk伏するのでは A: ありえないなぜならeの肝圷グル`プの竃薦として誼られるから ? グリッドが譲吉だと匯何のセルにデ`タが陶るMR-DSJでも}だった ? デ`タが富ないところは方が譲吉になるようﾚい譴魑５韻気擦 ┐海譴榔粧仂燭箸篭請△靴}だからは福くみたいなこといててgなh苧しかなかった´ 8 Session 22: Similarity Joins 毅輝紺彜┌┫點羇麪В PHiDJ: Parallel Similarity Self-Join for High-Dimensional Vector Data with MapReduce 猟より L?-norm鉦xの栽
  • 9. u ? 2肝圷゛20肝圷の夘貌デ`タ 10肝圷のMIRFLICKR*1デ`タ嘔2つ ┐發辰噺澳淋なデ`タでのY惚がたかった´ ? 8肝圷ぐらいから森が竃る ? Theta-join [Okcan, SIGMOD11]より互堀 ┐發辰箸癸この返隈は販吭のJoinが辛嬬だが ? MR-SimJoin [Silva, Cloud-I12]と曳^恣和蹌 ? Flickr參翌では蔚ぐらい堀かったが 故伉のgデ`タでけるのはどうなの´ 9 Session 22: Similarity Joins 毅輝紺彜┌┫點羇麪В PHiDJ: Parallel Similarity Self-Join for High-Dimensional Vector Data with MapReduce 猟より *1 http://press.liacs.nl/mirflickr 猟より猟より Cloud-I 2012VLDB 2012のワ`クショップ
  • 10. 冩梢嘘尚とか ? 1゛3肝圷殻業のヒストグラムの鹿栽を鵑箸沓EMDがε參和 のヒストグラムペアを MapReduceを聞って畠てつけたい ? EMD (Earth Mover｀s Distance)災桟修離劵好肇哀薀爐ら麿圭のヒスト グラムになるまでに勣する､両t卞咼灰好硲猟忖双のｼ鉦xに貌てる ? 鮫碧 [Ruzon, IEEE TPAMI01]ジェスチャJR [Ren, ACM MM11]嶷} 奮 [Xu, CVPR08]_楕デ`タマイニング[Xu, VLDBJ12]など嫌ﾚい鮄 10 Session 22: Similarity Joins 毅輝紺彜┌┫點羇麪В Melody-Join: Efficient Earth Mover¨s Distance Similarity Joins Using MapReduce Σ卞咾気擦 〜奉來gの鉦x ha hb EMD(ha, hb) =1〜1+2〜1=3 貌鮫馘e┛k燕スライドより
  • 11. 戻宛返隈 ? ハフ腎g*1に卞し[Ruttenberg, VLDB12]除そうなペアのみ麻 これを3指のMapReduceジョブでK双I尖させSimilarity Join晒 ? 1指朕で光ヒストグラムをハフ腎gに亟 ? 2指朕でハフ腎gの光セルについてLower BoundLBに聞うエラ`Cを麻竃 gHの拙el業とNormal Distributionによる指｢の`餓より麻竃 ? 3指朕で光ヒストグラムごと光セルごとに A)徭蛍の了崔するセルならネイティブレコ`ド B)それ參翌のセルでかつLBがε參和ならゲストレコ`ド としてヒストグラムとセルのMをMap ? 3指朕のReducerが光セルを毅輝ネイティブ★ネイティブゲストのEMD麻 11 Session 22: Similarity Joins 毅輝紺彜┌┫點羇麪В Melody-Join: Efficient Earth Mover¨s Distance Similarity Joins Using MapReduce I尖の送れ猟より いやh苧畠隼蛍からないんだけど とにかく鮫I尖とかでよく聞われるハフ腎gに卞すことでEMDが除そうなペア を紳糞弔牧つけられるのでそれをMapReduceに鬉気擦殖という湖じです *1 Lさrと叔業θのMの鹿栽で燕Fされた腎g http://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%95%E5%A4%89%E6%8F%9B ここまでのI尖で除そうなペアとして火った
  • 12. u ? 5つのgデ`タセットでu COREL*1Color (CC), Layout (CL) MIRFLICKRVertical (MV), Horizontal (MH), Slash (MS) ┐海離好薀ぅ匹任MVのY惚のみ燕幣 ? MR-SimJoin [Silva, SIGMOD12, Demo]と曳^ ? 鮫颪諒cardinalityやEMDの､笋┐討睫甍己峽┐械 12 Session 22: Similarity Joins 毅輝紺彜┌┫點羇麪В Melody-Join: Efficient Earth Mover¨s Distance Similarity Joins Using MapReduce *1 http://archive.ics.uci.edu/ml/datasets/Corel+Image+Features 1つ念の猟に竃てきた[Silva, Cloud-I12]と揖じ返隈 猟より猟より 亟驩v方3N グリッド4〜4セル Hadoopインスタンス48 その麿セッティング