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
Greedy Algorithms and Local Search (Chapter 2, The Design of Approximation Algorithms)
2.1 Scheduling jobs with deadlines on a single machine
- 問題：スケジューリング．max(締切を過ぎた時間) を最小化したい
- NP-hard (0 以下か否かの判定だけでも strongly NP-hard)
- 以下，d_i < 0 と仮定する
- アルゴリズム：Greedy に締切が近いやつからやっていく
- 近似値の評価
- 最適値の lower-bound を得る
- 近似値の upper-bound を得る
省略：大体おなじ
- 2.2 The k-center problem
- 2.3 Scheduling jobs on identical parallel machines
2.4 The traveling salesman problem
2.5 Maximizing flota in bank accounts
- 問題概要
- 銀行を k 個選んで float の和を最大化せよ
- 近似アルゴリズム：Greedy
- 証明：submodular
An Introduction to Approximation Algorithms (Chapter 1, The Design of Approximation Algorithms)
Set Cover 問題をひたすら扱う
- Deterministic LP rounding
- 要素の最大次数を f とする
- LP を解き，1/f 以上になっているやつを 1 にする
- f 近似
- Deterministic dual LP rounding
- 相補性定理
- Primal-dual を使うと簡単に Dual 解が求まる
- Greedy
- 「コスト/新たにカバーできる要素数」が最大のものをとっていく
- H_n 近似（タイト）
- Randomized LP rounding
- 定数 c
- 集合 j に対し，「確率 x^*_j で表が出るコイン」を c ln n 回振って，表が出たら採用
- 確率 1/n^{c-1} でカバーされる
- コストの期待値 c ln n
- 「コスト | カバーされる」の期待値 2c ln n
関数ポインタと関数オブジェクトと仮想関数の速度比較
趣旨
アルゴリズム内の処理の一部を指定させる一般的な方法には以下がある．
- 関数ポインタを使う (qsort 等)
- 関数オブジェクトを使う (std::sort 等)
- 仮想関数を使う
これらで性能がどう変化するかを測定した．
結果概要
wandbox にて実験した：http://melpon.org/wandbox/permlink/H7VjfOqgiEh4XWCP
pointer: 5.036541 sec
template: 3.373498 sec
virtual: 4.716775 sec
inline: 3.322171 sec
- pointer とは関数ポインタで指定した場合
- template とは関数オブジェクトで指定した場合
- virtual とは仮想関数を使って指定した場合
- inline とは指定なしでベタ書きした場合，一番最適化が効くはず
結果は template が inline とほぼ同等の速度で他より有意に高速であった．予想通りですね．これは，最適化の対象となるコードがベタ書きにかなり近くなり，インライン化等を含む最適化が効果的に働くから．
CPLEX 色々
探索ノード数を得る
IloCplex cplex(model);
...
cplex.solve();
cout << "Nodes: " << cplex.getNnodes() << endl;
カット数を得る
cout << "Cuts: " << cplex.getNcuts(IloCplex::CutClique) << endl;
- http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r4/index.jsp?topic=%2Filog.odms.ide.help%2Frefdotnetopl%2Fhtml%2FT_ILOG_CPLEX_Cplex_MIPCallback.htm
- http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r5/index.jsp?topic=%2Filog.odms.ide.help%2Frefjavaopl%2Fhtml%2Filog%2Fcplex%2FIloCplex.CutType.html
- getNほげcuts 系は deprecated http://www.hpc.science.unsw.edu.au/files/docs/ilog/cplex/12.1/html/Content/Optimization/Documentation/CPLEX/_pubskel/ps_releasenotescplex13.html
ruby -ne 'puts "IloCplex::" + $_.split("=")[0].strip + ","' int num_cuts = 0;
for (IloCplex::CutType c : {
IloCplex::CutCover,
IloCplex::CutGubCover,
IloCplex::CutFlowCover,
IloCplex::CutClique,
IloCplex::CutFrac,
IloCplex::CutMCF,
IloCplex::CutMir,
IloCplex::CutFlowPath,
IloCplex::CutDisj,
IloCplex::CutImplBd,
IloCplex::CutZeroHalf,
IloCplex::CutLocalCover,
IloCplex::CutTighten,
IloCplex::CutObjDisj,
IloCplex::CutLiftProj,
IloCplex::CutUser,
IloCplex::CutTable,
IloCplex::CutSolnPool}) {
num_cuts += cplex.getNcuts(c);
}
cout << "Cuts: " << num_cuts << endl;
厳密解を求めさせる
cplex.setParam(IloCplex::Param::MIP::Tolerances::MIPGap, 0.0);
並列を封じる
cplex.setParam(IloCplex::Param::Threads, 1);
国際ジャーナル
そろそろジャーナルにも論文を出してみたいのですが，本当にどこがいいのか分からない……ﾀﾞﾚｶﾀｽｹﾃｰ
DB 系
ランキング http://academic.research.microsoft.com/RankList?entitytype=4&topdomainid=2&subdomainid=18&last=10
ACM TODS
多分超有名？でも会議論文からの差分を 30% 要求される．通る気がしない．
http://tods.acm.org/Authors.html#ManuscriptPreparation
A submitted manuscript that is based on one or more previous publications by one or more of the authors should have at least 30% new material. (略)
VLDB Journal
やっぱりこっちも超有名？ こっちも 30% の差分を要求される．
http://vldb.org/vldb_journal/index.php/author-guidelines/submission-rules
A submission that substantially overlaps the authors' previous refereed or copyrighted publications, such as an extended version of a conference paper, must contain at least 30% significant new content.
IEEE TKDE
よく見かける気がする．見かける数が多いということはちょっとは緩いのではないかと推測していたが，なんとここでも差分が要求されるのであった……
http://www.computer.org/portal/web/peerreviewjournals/author
Papers previously published in conference proceedings, digests, preprints, or records are eligible for consideration provided that the papers have undergone substantial revision, and that the author informs the journal coordinator at the time of submission.
ていうか conference どころか preprint からも差分を要求するってなんかもう意味が分からないんだけれどなんでこういう慣習がまかり通ってるんだ……．でも revision だけでいいなら新しい貢献はなくてもいい？
Please be aware that editors and reviewers are required to check the submitted manuscript to determine whether a sufficient amount of new material has been added to warrant publication.
...
then you are required to cite the previous work(s) and clearly indicate how the new submission offers substantively novel or different contributions beyond those of the previously published work(s).
そんなことはなさそうだった（絶望）
その他
論文を殆ど見たことが無いけれど以下のようなジャーナルがあるようだ．
- Information Systems (IS)
- 出版社がよく見かける（緑色のサイトの） ELSEVIER である．よく知らない所よりは安心できる．
- Information Systems Research (ISR)
- 謎の出版社．名前がややこしい．
- Knowledge and Information Systems Journal (KAIS)
- Journal of Intelligent Information System (JIIS)
- Data Mining and Knowledge Discovery (DMKD/DAMI)
James Cheng 先生 (http://www.cse.cuhk.edu.hk/~jcheng/publications.html) は駆け出しの頃はこれらのジャーナルを利用していた模様．KAIS 2 件，JIIS 1 件，DMKD 1 件．
その他
World Wide Web Journal
国際会議 World Wide Web に対応するジャーナルなのではないか，超ハイジャーナルなのでは，と思わせておいて多分実はそこまでのレベルではないっぽい予感がする（よく知らないけど）．結構見かける．
http://www.springer.com/computer/database+management+%26+information+retrieval/journal/11280
Submission of a manuscript implies: that the work described has not been published before;
ん？
Internet Mathematics
よく知らないけれどたまに見かける気がする．
- http://projecteuclid.org/euclid.im
- http://www.tandfonline.com/action/authorSubmission?journalCode=uinm&page=instructions#.Uu-nL3V_vj4
Please note that Internet Mathematics uses CrossCheck™ software to screen papers for unoriginal material. By submitting your paper to Internet Mathematics you are agreeing to any necessary originality checks your paper may have to undergo during the peer review and production processes.
conference paper をベースに提出したら unoriginal 判定されてしまうのか？
結論
どのジャーナルもなんか originality とか novelty を要求していてわけがわからなくなった．もしやこちらの界隈では best papers に選ばれて special issue に招待されない限り会議論文をそのままジャーナルなんて出せない？
というかびっくりしたけれどかの有名な Jure Leskovec も実はジャーナルは 11 本しか出してない？（DBLP 調べ）一方学会論文は 70 本を超える．ジャーナルはあまり要らないのか？
しかし喜連川先生はジャーナルも 60 本を超えていた，流石．（会議は200本超え）
ジャーナルとは一体何なのか……（続く）
