ACM Paris Kanellakis Award (Theory and Practice Award)
Paris Kanellakis Theory and Practice Award はコンピュータの世界に重要な実用的インパクトを引き起こした理論的研究成果に対して贈られる賞だそうです．賞金は $10,000．
Paris Kanellakis 氏はデータベース分野の研究者でしたが，1995 年に飛行機事故に巻き込まれ亡くなったそうです．賞金にはご両親からの寄付に加え ACM の分科会などからの支援が含まれているそうです．
- Paris Kanellakis Theory and Practice Award - ACM Award
- Paris Kanellakis Award - Wikipedia, the free encyclopedia
以下は受賞者と受賞の対象となった成果の表です．上記の Wikipedia 英語版の記事に記載されている表の日本語版……のつもりでしたが，Wikipedia にはよくわからない説明が多くても試しに公式ウェブページの説明を開くとよく知っているキーワードが出てきたりということも多く，そこそこの部分は結局公式ウェブページの説明に基づいています．
| 年 | 受賞者 | 受賞の対象となった研究成果 |
|---|---|---|
| 1996 | Leonard Adleman, Whitfield Diffie, Martin Hellman, Ralph Merkle, Ronald Rivest, and Adi Shamir | 公開鍵暗号 |
| 1997 | Abraham Lempel and Jacob Ziv | データ圧縮（LZ アルゴリズム） |
| 1998 | Randal Bryant, Edmund M. Clarke, E. Allen Emerson, and Kenneth L. McMillan | 記号モデル検査と BDD |
| 1999 | Daniel Sleator and Robert Tarjan | スプレー木 |
| 2000 | Narendra Karmarkar | 内点法 |
| 2001 | Eugene Myers | シーケンスアラインメントアルゴリズム（BLAST） |
| 2002 | Peter Franaszek | Constrained Channel Coding |
| 2003 | Gary Miller, Michael Rabin, Robert Solovay, and Volker Strassen | 素数判定アルゴリズム（Miller-Rabin，Solovay-Strassen） |
| 2004 | Yoav Freund and Robert Schapire | ブースティング（機械学習） |
| 2005 | Gerard Holzmann, Robert Kurshan, Moshe Vardi, and Pierre Wolper | 形式的検証システム（COSPAN，SPIN） |
| 2006 | Robert Brayton | 回路設計のための論理合成 |
| 2007 | Bruno Buchberger | グレブナー基底 |
| 2008 | Corinna Cortes and Vladimir Vapnik | SVM (Support Vector Machine) |
| 2009 | Mihir Bellare and Phillip Rogaway | Practice-Oriented, Provable-Security (POPS) |
| 2010 | Kurt Mehlhorn | Library of Efficient Data types and Algorithms (LEDA) |
| 2011 | Hanan Samet | 4 分木等の多次元データに対するデータ構造 |
| 2012 | Andrei Broder, Moses S Charikar and Piotr Indyk | LSH (Locality-Sensitive Hashing) |
| 2013 | Robert D. Blumofe, and Charles E. Leiserson | 並列プログラミング（Cilk 等） |
回路・ハードウェア寄りの分野は不得手なので不正確かもしれません．より適切な日本語訳などもし有れば教えて頂ければと思います．
Core Decomposition of Uncertain Graphs (KDD'14)
定義
- uncertain graph
- 各辺に対し存在する確率が与えられる
- リンク予測の出力，影響，protein-interaction （ノイズ）
- (k, η)-core
- 極大部分グラフ H, [deg_H(v) ≧ k] ≧ η
計算
- 小さい方から剥ぎ取る
- 確率の計算がちょっと入るが簡単な DP
応用実験
- 影響最大化：密グラフとして抽出する前処理
- Task-Driven Team Formulation：それっぽいチームを探す
ダメな統計学
http://id.fnshr.info/2014/12/17/stats-done-wrong-toc/
知っている部分もあったが面白かった
- (1) はじめに
- 統計的処理がきちんと行われず誤った結論が導きだされている論文は半数以上かもしれないらしい（医学の話）
- (2) データ分析入門
- (3) 検定力と検定力の足りない検定
- (4) 擬似反復：データを賢く選べ
- 100 人で 10 回計測 → 1000 のデータ点？ではない
- 「擬似反復」と呼ばれる
- 対策法
- 独立していないデータ点の平均をとる
- 独立していないデータ点を別個に分析 → 多重比較
- 階層モデル
- (5) p値と基準率の誤り
- 「基準率」 ＝ 調査対象のもののうち，真に有効であるものの割合
- p = 0.05 で判定を行うと，5% は擬陽性になる
- 真に陽性である確率（＝基準率）と併せて考えないと結果が殆ど擬陽性になる
- p < 0.05 ≠ 「これの結果が偶然の確率は 5% だ」 （よくある勘違い）
- 偽発見率を制御する方法：ベンジャミーニ＝ホッホベルク法
- (6)有意であるかないかの違いが有意差でない場合
- (7) 停止規則と平均への回帰
- 停止規則 ＝ 有意差が出たら実験を止める
- しばしば結果が実際より誇張される
- サイズの違う集合での平均点の「上位」「下位」は両方小さい集合になる（ばらつくから）
- 停止規則 ＝ 有意差が出たら実験を止める
- (8) 研究者の自由：好ましい雰囲気？
- 統計処理の際，無視して良い要素，除外する outlier 等で結果が大きく好ましい方向にねじ曲げられる
- (9) 誰もが間違える
- データを公開してほしい
- (10) データを隠すこと
- データを要求して送ってくる著者グループは 3/4
- データを得られた研究の半分がデータの処理に誤りがあった
- 15% では誤りによって有意な結果が出てしまっていた
- データを共有したがらないグループの方が誤りが多い
- マイナーな論文誌のほうがデータ処理法を隠す
ここから後は技術的な話ではなく教育等についての議論
次に誰かが「この結果は p<0.05で有意だから、これが偶然である確率は20分の1しかない！」と言うのを聞くことがあったら、私のためにその連中の頭を統計の教科書でぶったたいでください
高画質動画配信の方法
最近，やはり動画配信の時代だなと思う．どうせなら高画質で配信をしたい．その方法を調べる．
前提：Web カメラは NG
Logicool C920(t) は Web カメラとしては評判が良い．これは俺も持っているし，ICPC 放送の時とかはチョクダイもこれを持ってくる．定番のようだ．
まーしかし，やっぱりサイズもサイズだし画質はお遊びレベル感が否めない．特に，今年の ICPC 配信はカーテンを閉めた暗めの部屋だったからか，結構辛かった様子．
もっとデカいカメラは直接 PC につながるのか？
繋がらないようだ．
ここで，もっとデカいカメラはデジタル一眼レフとかデジタルビデオカメラを想定．USB に繋いでそのまま配信〜という用途で使えるものは今の所ない様子．
「HDMI スルー出力」
動画配信用途でそういったカメラを使う際のキーワードは「HDMI スルー出力」というものらしい．この機能を用いて，カメラから映像をそのまま HDMI で出力し，それを PC に取り込む．
HDMI スルーはできる機種は結構限られているらしい．メーカーのウェブページを見てもよくわからないので，口コミを探すしかない．
俺の E-M5 はできない．パナソニックの GH シリーズができるらしく，GH-2 時代から高画質配信界隈で好評らしい．α7 もできるらしい．
ちなみに
高画質配信を目指す界隈は「シネ UST」なんて呼ばれているらしい．
https://www.facebook.com/cineust
latex 執筆時に omake -P で快適自動ビルド
博論執筆の現実逃避で自分の latex 執筆環境の改善を少し試みる．
eps → pdf
eps の図を入れまくると tex のコンパイルが遅くなり omake -P の快適さが薄れてしまう．tex からは pdf を入れるようにして，omake で事前に eps を pdf に変換するようにした．
OMakefile
問題は，自分の画像のディレクトリ構造が上の OMakefile で想定されているものよりももっと深いこと．これに対応するのが簡単かと思いきや omake 初体験にはかなり骨が折れた．
omake はドヤ顔で「omake のルールには有効範囲のスコープがあるので管理しやすい！ワイルドカードを用いるルールが適用されるのはカレントディレクトリだけだ！」って言っているのだけれど，それがめっちゃ困るっていう．export というものを使うと変数等をグローバル化したりできるっぽいのだが，ワイルドカードのルールは頑張っても外に出てくれず，自分のググり力で３０分ググった感じでは出すのに成功してる人は見つけられなかった．
というわけで愚直に foreach する以下のような物を書いたら動いた．
EPS_IMAGE_FILES = $(glob $(IMAGE_DIR)/*.eps $(IMAGE_DIR)/*/*.eps $(IMAGE_DIR)/*/*/*.eps) foreach(EPS_FILE, $(EPS_IMAGE_FILES)) PDF_FILE = $(addsuffix .pdf, $(removesuffix $(EPS_FILE))) XBB_FILE = $(addsuffix .xbb, $(removesuffix $(EPS_FILE))) $(PDF_FILE): $(EPS_FILE) $(EPSTOPDF) $< $(XBB_FILE): $(PDF_FILE) $(EBB) $<
no BoundingBox
上記のように Bounding Box を用意してやっても no BoundingBox と言われることがある．調べると，ファイルパスにドットが２つ以上入っていると起こる有名なバグみたいだ．これはひどい．
結果
EPS 使用時
omake thesis.pdf 10.17s user 0.61s system 100% cpu 10.740 total
PDF 使用時
omake thesis.pdf 0.89s user 0.09s system 99% cpu 0.977 total
満足．
発表中に画面にニコ動風にコメントを流したい
２つソフトが見つかった．どっちもすぐにマトモに動作した．
Querying K-Truss Community in Large and Dynamic Graph (SIGMOD'14)
- 問題
- グラフ G，クエリ：頂点 v, 整数 k
- v を含む k-truss community をすべて列挙
- k-truss vs. clique percolation
- clique percolation: コミュニティと呼べない，パラメータが３つも，NP-Hard
- k-truss: コミュニティの直径が |C|/k，高枝連結度，パラメタ１つ，多項式時間
- index
- dynamic update
- 下界だか上界だかを使って処理を枝刈りするらしい
Reverse Top-k Search using Random Walk with Restart (VLDB'14)
- RWR
- Bookmark Coloring Algorithm (BCA)
- 受け取って少し確定して残りを配るタイプのやつ
- ハブを活用
- ハブの頂点は受け取っても配らないことにして，後でまとめて影響を計算
- Bookmark Coloring Algorithm (BCA)
- Reverse Top-K RWR Query
- 頂点 q と k → 頂点 u からのの RWR で q が top-k に入る u を全て答える
- 応用：「こいつに強い影響を与えている物の集合」が得られる
- spam detection
- popularity of authors in co-authorship network
- promotion in co-purchase graph
- Offline indexing
- 各頂点から BCA を t ステップ走らせる → RWR の下界
- 改良：ハブ，サイズ圧縮，・・s
- Online Query Algorithm
- proximity の上界と下界を狭めていくよくあるタイプ
- 実験結果
- web-Google で前処理時間 10^6 秒とは・・・
- 応用実験 (5.4)
- spam detection, co-author network を試している
国内学会の全国大会の大まかな日程
後輩が国内イベント（全国大会）に行ってみたいと言っていたので調べてリストアップしてみる．日程は目安として前回のもの．
- DEIM（データ工学と情報マネジメントに関するフォーラム（日本データベース学会年次大会））
- http://db-event.jpn.org/deim2015/
- 申込 12/19，論文 1/9，発表 3/2-4（郡山）
- JSAI（人工知能学会全国大会）
- http://www.ai-gakkai.or.jp/jsai2015/
- 申込 1/16，論文 3/24，発表 5/30-6/2（函館）
- 日本オペレーションズ・リサーチ学会 春季研究発表会（秋季もある）
- http://www.orsj.or.jp/2015spring/
- 申込・論文 1/7, 発表 3/26-27（東京）
- 全国処理学会全国大会
- http://www.ipsj.or.jp/event/taikai/77/
- 申込 11/21，論文 1/9，発表 3/17-19（京都）
- （山下記念賞を頂いているので参加する）
他に関連が有りそうなものがあれば教えて下さい．
Path Skyline の計算サーベイ
厳密列挙アルゴリズム
- (1984) On a multicriteria shortest path problem
- Martin's Algorithm (元祖 Label Setting Approach)
- (JACM'91) Multiobjective A*
- 最初に single source でなく point-to-point にして global domination を導入したっぽい
- (EJOR'92) A multicriteria pareto-optimal path algorithm
- multidijkstra (MD)．各コスト単体での距離（→下界）を前計算．
- (SEA'09) Pareto Paths with SHARC
- 前処理してる．次元が増えるとつらそう（変な制約を追加して厳密性を緩和してる）
- (ICDE'10) Route skyline queries: A multi-preference path planning approach
- ARSC
- reference node embedding という前処理により下界を前計算
- (2012) Multiobjective heuristic search in road maps
- クエリごとの前処理系
- (Arxiv'14) ParetoPrep: Fast computation of Path Skylines Queries
- グローバルな前処理はなし，クエリ事の前処理系
- MD とかより良い下界が計算できるから良い，みたいな感じっぽい
- みてない
- (2012) Faster Multiobjective Heuristic Search in Road Maps
- (2011) Multiobjective route planning with precalculated heuristics
- (2012) An Analysis of Some Algorithms and Heuristics for Multiobjective Graph Search
- (2013) A case of pathology in multiobjective heuristic search
その他
OR 系では multi-objective shortest path problem と呼ばれているらしい
- サーベイ
- (2000) A classification of bicriterion shortest path (bsp) algorithms
- (2009) A comparison of solution strategies for biobjective shortest path problems
- (2007) Selected multicriteria shortest path problems: An analysis of complexity, models and adaptation of standard algorithms
- (2000) A survey and annotated bibliography of multiobjective combinatorial optimization
- 指数個の Skyline があるので NP-Hard
- (1980) Multiple criteria decision making theory and application
- 相関が強ければ Skyline は少ない
- (2001) Pareto shortest paths is often feasible in practice
- FPTAS
- (1980) Multiple criteria decision making theory and application
- (1987) Approximation of pareto optima in multiple-objective, shortest-path problems
- (2006) Multiobjective optimization: Improved fptas for shortest paths and non-linear objectives with applications.
- 遺伝的アルゴリズム
- (2007) Evolutionary algorithms for the multi-objective shortest path problem
クラウドストレージを用いた個人データのバックアップ法の比較
クラウドストレージを使って，個人データの簡単かつ安心なバックアップを実現したい．現在の選択肢を調べてみた．
前提
自分がバックアップしたいデータは，写真が中心．現在 1TB 弱．
（ただ，将来的には数 TB 行きそう．）
Amazon S3/Glacier
有名なヤツ．1GB/1円．
- メリット
- データは 99.999999999% 保証．
- 完全従量制なので，容量の上限等を来にしなくて良い．
- デメリット
- ダウンロードが不便．
- 複数ヶ所でのデータの同期には使えない
- （関連して）料金体系が複雑．ミスるとダウンロードで莫大な請求が来る可能性がある．
- Amazon Glacier からデータを取り出すときには気をつけようね - takatoshiono's blog
- システムも個人向けに作られていないため面倒臭そう．
- ダウンロードが不便．
Google Drive
今年の 3 月に Google Drive が凄い安くなったらしい．1TB で $9.99/月．
Online Topic-aware Influence Maximization Queries (EDBT'14)
- topic-aware IC model (ICDM'12)
- 情報と辺にベクトルがあって，内積で伝搬確立が決まる
- http://francescobonchi.com/icdm12.pdf
- 提案手法
- 1000 点ぐらい代表的なベクトルを作って，先に計算しておく
- クエリが来たら適当に混ぜて答えを作る
- 怪しい謎の努力がいっぱいある
- 実験結果
- 普通に計算してもはやそうな小さなグラフ
問題は面白そう
Collaborative learning in networks (PNAS'12)
模倣と集合知
複雑ネットワークと模倣との関係
Journal of Experimental Psychology: General, 2008
PNAS'12
- 今度は 100X100 のグリッドでやっぱり最適化
- 距離の短い＆クラスターの少ないネットワークのほうがパフォーマンスが高い
- ジレンマ
- 模倣を行う参加者ほど利得が高い
- しかし模倣する参加者が増えるとピークは発見されにくい
SIGMOD 2014
グラフ
- Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency
- Tripartite Graph Clustering for Dynamic Sentiment Analysis on Social Media
- Querying K-Truss Community in Large and Dynamic Graphs
- Reachability Queries on Dynamic Graphs: A Hierarchical Labeling Approach
- Local Search of Communities in Large Graphs
- Scalable Similarity Search for SimRank
- Efficient Cohesive Subgraphs Detection in Parallel
- Parallel Subgraph Listing in a Large-Scale Graph
- OPT: A New Framework for Overlapped and Parallel Triangulation in Large-scale Graphs
- Fast and Unified Local Search for Random Walk Based K-Nearest-Neighbor Query in Large Graphs
グラフだけどあんまり関係なさそう
- Scalable Big Graph Processing in MapReduce
- In Search of Influential Event Organizers in Online Event-based Social Networks
- Efficient Location-Aware Influence Maximization
- Efficient Algorithms for Optimal Location Queries in Road Networks
- Navigating the Maze of Graph Analytics Frameworks using Massive Graph Datasets
- Localizing Anomalous Changes in Time-evolving Graphs
- Mining Statistically Significant Connected Subgraphs in Vertex Labeled Graphs
- Querying Big Graphs within Bounded Resources
- Answering Top-k Representative Queries on Graph Databases
それ以外で気になる
- A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison and Radix-Sort
日本人
- AutoPlait: Automatic Mining of Co-evolving Time Sequences
- Resource-Oriented Approximation for Frequent Itemset Mining from Bursty Data Streams
