SIGMOD2011中継つぶやきまとめ（2日目）
-
- いいね！0
chiemi
@chiemi
メモ；ACM Digital LibraryでのSIGMOD2011 Proceedingsの入手先 http://goo.gl/rGwTs 若干わかりづらかったので。
2011-06-15 22:21:50
Yoshiharu Ishikawa
@yoshi_ishikawa
I'm attending the tutorial "Privacy-aware Data Management for Information Networks".
2011-06-15 14:36:14
Yoshiharu Ishikawa
@yoshi_ishikawa
active attackという方式では，攻撃者は匿名化の前にネットワーク上にリンクを張る（例：ブログ上でリンクを張るなど）．後で識別の助けになるようなグラフ構造（パターングラフ）もこっそり作っておき，匿名化されたデータの中でその構造を探す．
2011-06-15 14:57:12
Yoshiharu Ishikawa
@yoshi_ishikawa
匿名化の指標：k-degree anonymous -- グラフ中のどのノードについても，そのノードと同じ次数の少なくともk-1個のノードがグラフ中にある．動的計画法で，時数の変化を最小にするような変換を見つける．うまくグラフが作れないこともあり．
2011-06-15 15:04:18
Yoshiharu Ishikawa
@yoshi_ishikawa
グラフの変換法は大まかには三つ：directed alternation（辺の追加・削除），generalization（複数のノードをまとめる），random alternation（確率的に辺を追加削除，rewiring）
2011-06-15 15:07:12
Yoshiharu Ishikawa
@yoshi_ishikawa
有用性（utility）をどう評価するか？一般には，さまざまな指標を用いてオリジナルのグラフと比較．次数，パス長，クラスタリング係数など．[Hay PVLDB 08]
2011-06-15 15:11:22
Yoshiharu Ishikawa
@yoshi_ishikawa
次はdifferential privacyの利用について．変換したグラフをリリースするのではなく，グラフに関する問合せに対し「安全な」結果を返す．output perturbation（ノイズ追加）が基本．
2011-06-15 15:13:50
Yoshiharu Ishikawa
@yoshi_ishikawa
differential privacyに関する多くの研究はtabular dataに対するもので，network dataに関する研究は少ない． ここで [Dwork, TCC 06] のアイデアの説明続く．難しい．サーベイは [Dwork, CACM 10]にあり．
2011-06-15 15:19:50
Yoshiharu Ishikawa
@yoshi_ishikawa
differential privacyに関する多くの研究はtabular dataに対するもので，network dataに関する研究は少ない． ここで [Dwork, TCC 06] のアイデアの説明続く．難しい．サーベイは [Dwork, CACM 10]にあり．
2011-06-15 15:19:50
Yoshiharu Ishikawa
@yoshi_ishikawa
differential privacyのネットワークへの適用の問題：単一の辺の情報だけを守ればよいのではない．"differential object"に対する概念は何か? [Kifer SIGMOD 11] でアイデアあり．
2011-06-15 15:21:44
Yoshiharu Ishikawa
@yoshi_ishikawa
[Hay, ICDM 09] [Hay PVLDB 10] のアイデアを説明中．ちと難しい．
2011-06-15 15:25:48
Yoshiharu Ishikawa
@yoshi_ishikawa
subgraph counting query（特定の構造：例 - 三角形 を求める問合せ）への対応について．sensitivityが高いので，対応が難しい場合あり．[Behoora, PVLDB 11]を参照．
2011-06-15 15:31:26
Yoshiharu Ishikawa
@yoshi_ishikawa
[Machanavajjhala, VLDB 11]では，友人のプライベートなデータを用いてレコメンドする手法が提案されている．differential privacyを利用．
2011-06-15 15:32:28
Yoshiharu Ishikawa
@yoshi_ishikawa
今度は，講演者がKun Liu (Yahoo!) に交代．ちなみにこれまでは，Gerome Miklau (U. Massachusetts, 概要)，Michael Hay (U. Mass, differential privacy) が担当．後の2名の講演者は不参加．
2011-06-15 15:40:33
Yoshiharu Ishikawa
@yoshi_ishikawa
プライバシーのリスクを Privacy Score ではかる方法がある [Liu, ICDM]．Sensitivity, visibilityという2つの要素の掛け合わせを足しこんで定義される．item response theory (IRT)によりスコア評価．
2011-06-15 15:46:03
Yoshiharu Ishikawa
@yoshi_ishikawa
プライバシー情報は，明示的に共有していなくても，voting, community detection, classificationなどの手法で推定できる．単純な例では，女性ばかりからなるコミュニティで，一つ性別が分からないノードがあったとき，おそらく女性と推定できる．
2011-06-15 15:50:52
Yoshiharu Ishikawa
@yoshi_ishikawa
collaborative privacy managementという概念あり．[Squicciarini WWW09]．各ユーザはプライバシーレベルごとにどの程度のbenefitがあるかを示す．システムは，全体のsocial benefitが最大になるように調整．
2011-06-15 16:00:16
Yoshiharu Ishikawa
@yoshi_ishikawa
今度は，Stream and Complex Event Processingというセッションに参加．通信状況が悪いのでまとめて報告．
2011-06-15 18:49:23
Yoshiharu Ishikawa
@yoshi_ishikawa
最初はChanging Flights in Mid-air: A Model for Safely Modeifying Continuous Queriesという論文（ETH Zurichほか）．
2011-06-15 18:51:57
Yoshiharu Ishikawa
@yoshi_ishikawa
連続的問合せを途中でとめたり，修正を加えたりしたときに，それが結果にどう影響すべきかのモデルを提案．変更により問合せがどのようなライフサイクルをたどるかをオートマトンで表現．
2011-06-15 18:52:19
Yoshiharu Ishikawa
@yoshi_ishikawa
次はHow Soccer Players Would Do Stream Joins (ETH Zurich)という論文．発表者のJens Teubnerは以前見たことがある．分かりやすいプレゼンをする人．
2011-06-15 18:52:52
Yoshiharu Ishikawa
@yoshi_ishikawa
メニーコアシステムにおける並列性を生かすには通信がかなりキーポイントで，メニーコアのハードウェアのためのアルゴリズムを提案．
2011-06-15 18:53:03
Yoshiharu Ishikawa
@yoshi_ishikawa
ストリームの結合の並列化には CellJoinがあるが，通信などの非効率性があった．本手法試合前にサッカー選手が握手する様子をヒントにする．二つのストリームは反対の方向に流れ，タプルはそれらが出会ったときに比較される．実際には，タプルはあるコアから次のコアというように流れていく．
2011-06-15 18:54:48
Hideyuki Kawashima
@h_kaw
@yoshi_ishikawa Handshake Joinにつきまして merger の最適化処理に関する説明がございましたでしょうか．我々の再実装ではそこがボトルネックになり困っておりまして...お暇な時にもしもご教示頂けましたら幸いです．
2011-06-16 01:16:18
Yoshiharu Ishikawa
@yoshi_ishikawa
@h_kaw @h_kaw うーん，そうですね．論文を見ると書いてあるのかもしれませんが，発表では細かい話は一切なしでした．直観的な説明が中心で，詳しく説明していないのに分かった気にさせるうまい発表でした．
2011-06-16 06:06:13