KDD'16 論文採択：省メモリなグラフスケッチのデータ構造 - iwiwiの日記
国際学会 KDD 2016 に論文が採択されました．KDD はデータマイニング分野の最も有名な会議です．発表は 8 月にサンフランシスコです．オーラル発表有りの採択です． 今回の論文は "Compact and Scalable Graph Neighborhood Sketching" というタイトルで，私が主著であり，研究室で特任技術専門員としてお手伝いしてもらっていた矢野さんとの共著です．内容はグラフ向けデータ構造 All-Distances Sketches の実用上の問題点である空間使用量を大幅に削減するための新しいデータ構造の提案です．以前に「大規模グラフのコンパクトでスケーラブルな全距離スケッチ」というタイトルで人工知能学会の人工知能基本問題研究会にて議論させて頂いていたものです． 背景：All-Distances Sketches とは？ All-Distances Ske
PHP の壊れた mt_rand の品質を統計的に検証した - iwiwiの日記
メルセンヌ・ツイスターと似て非なるアルゴリズムが実装されていたことが発覚して話題の PHP の mt_rand 関数の品質を統計的に検証しました．果たして，PHP の「壊れた」mt_rand は安心して使うことができるのでしょうか……？ ちなみに，結論から言うと，PHP の壊れた mt_rand は，（少なくともこのテストの範囲では）本家メルセンヌ・ツイスターと遜色ない品質を持っているようです．ただし，最後に PHP の乱数の別の懸念点についても紹介します． 壊れた mt_rand とは PHP の mt_rand は，ドキュメントによると，有名な乱数生成アルゴリズム「メルセンヌ・ツイスター」を利用して高品質の乱数を生成する関数です．ところが，どうやら一部では知られていたこととして，PHP の mt_rand の実装にはバグがあり，本家メルセンヌ・ツイスターと挙動が一致していませんでした．
ALENEX'15 論文採択：指数時間 Branch-and-Reduce アルゴリズムの実性能 - iwiwiの日記
国際学会 ALENEX 2015 に論文が採択されました．ALENEX (Meeting on Algorithm Engineering & Experiments) は実験系アルゴリズム (experimental algorithmics) を扱う最も有名な会議の 1 つで，理論系アルゴリズムのトップ学会 SODA (Symposium on Discrete Algorithms) に併設して開催されます．発表は来年の 1 月にアメリカの San Diego です． 今回の論文は "Branch-and-Reduce Exponential/FPT Algorithms in Practice: A Case Study of Vertex Cover" というタイトルで，研究室同期の岩田との共著です． 背景１：アルゴリズム研究における理論と実性能の乖離 アルゴリズムが好きな人はよ
Microsoft Research Silicon Valley 最後の日を見て - iwiwiの日記
8 月中旬より，インターンとしてマウンテンビューに位置する Microsoft Research Silicon Valley (MSR SVC) に滞在して研究をしていました．期間は 3 ヶ月の予定で，11 月中旬まで居る予定でした．しかし，Microsoft の経営判断により MSR SVC の閉鎖が突然決定され，所属チームの方々を含む殆どの研究者は解雇となり，僕の滞在も突如終了になりました． このショッキングな事件は，英語のみならず日本語のニュースサイトにも取り上げられています． Microsoft to close Microsoft Research lab in Silicon Valley | ZDNet Microsoft Research closing Silicon Valley lab in latest job cuts - GeekWire http://www
ALENEX'14 に論文採択 - iwiwiの日記
国際学会 ALENEX 2014 に論文が採択されました．ALENEX (Meeting on Algorithm Engineering & Experiments) は SIAM によって開催される実験系アルゴリズム (experimental algorithmics) を扱う最も有名な会議の 1 つで，理論系アルゴリズムのトップ学会 SODA (Symposium on Discrete Algorithms) に併設して開催されます．発表は来年の 1 月にアメリカのオレゴンです． 今回の論文は "Fast Shortest-path Distance Queries on Road Networks by Pruned Highway Labeling" というタイトルで，研究室の後輩の河田君，同期の岩田，NII の河原林先生との共著です．タイトルからご察しの通り，SIGMOD'
平面グラフと交通ネットワークのアルゴリズム - iwiwiの日記
本日，PFI セミナーにて「平面グラフと交通ネットワークのアルゴリズム」というタイトルで話をさせてもらいました．スライドは以下になります． 「平面グラフでは色々な問題が効率的に解けると聞くけど一体何故？」 「道路ネットワークを処理するにはそういうアルゴリズムが使われているの？」 というような自分が昔持っていた疑問に答える，そんなつもりで準備をしました．そんな疑問を持っている方は，是非ご覧ください． 内容は以下のような感じです． 平面グラフのアルゴリズム（理論コミュニティ） 平面グラフとは何か 平面グラフのアルゴリズムテクニックとその応用例 双対グラフ 小さいセパレータの存在 (r-division) グラフ分割 (Deletion Decomposition) 交通ネットワークのアルゴリズム（応用コミュニティ） どのような課題が取り組まれているか 道路ネットワークは平面グラフなのか？ 経路
SIGMOD'13 に論文採択 - iwiwiの日記
論文が国際学会 SIGMOD'13 (ACM SIGMOD International Conference on Management of Data) に採択されました．SIGMOD はデータベース分野のトップ会議です．日本からの論文は知る限り 5 年ぶりだと思います．修士の間の研究で，この厳しい戦いを勝ち抜き論文採択に至ることができ，本当に嬉しいです． 論文は "Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling" というタイトルで，研究室同期の岩田と NII の吉田さんとの共同研究です． 内容について 扱っている問題は前回の EDBT 論文と同じく，大規模ネットワーク上の最短路クエリです．グラフに対し，ある程度の前計算データを蓄えておく事により，2 点間の最短
プログラミングコンテストチャレンジブック 第二版 発売中 - iwiwiの日記
プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える? 作者: 秋葉拓哉,岩田陽一,北川宜稔出版社/メーカー: マイナビ発売日: 2012/01/28メディア: 単行本（ソフトカバー）購入: 25人 クリック: 473回この商品を含むブログ (36件) を見る 第二版，発売しております！よろしくお願いします． 第二版の紹介は以下の記事を見てもらえればと思います． 第二版が出ます！プログラミングコンテストチャレンジブック - (iwi)の日記 ちなみに，新宿の紀伊国屋さんでは先行発売がされていました． 【新宿南店】どこよりも早く先行発売！『プログラミングコンテストチャレンジブック 第２版』 | 本の「今」がわかる 紀伊國屋書店 追記 Twitter でつぶやくと第二版が貰えるプレゼント企画がやってます．2/6 までです．欲しい方
大規模グラフアルゴリズムの最先端 - iwiwiの日記
昨日，PFI セミナーにて「大規模グラフアルゴリズムの最先端」というタイトルで発表をさせてもらいました．スライドは以下になります． 大規模グラフアルゴリズムの最先端 View more presentations from iwiwi 当日は Ustream もされており，録画された発表もご覧になれます． http://www.ustream.tv/recorded/19713623 内容の流れとしては，以下のようになっています． 導入 アルゴリズム界隈での話題 最新の研究動向 道路ネットワークでの最短路クエリ処理 基礎的な手法：双方向 Dijkstra，A*, ALT 最新の手法：Highway Dimension + Hub-Labeling Algorithm DB 界隈での話題 最新の研究動向 複雑ネットワークでの最短路クエリ処理 基礎的な手法：ランドマークを用いた最短距離推定 最
EDBT'12 に論文採択 - iwiwiの日記
卒論とその続きで昨年夏学期にやっていた研究に関する論文が EDBT'12 (15th International Conference on Extending Database Technology) に採択されました．会議は 3 月末にドイツです． 論文は "Shortest-Path Queries for Complex Networks: Exploiting Low Tree-width Outside the Core" というタイトルで， MIT の Christian Sommer さんと NII の河原林先生との共著になっています． Christian Sommer さんは，MIT でグラフの最短路に関連するトピックをひたすらやられているアルゴリズム系の人です． セオリーからプラクティスまで，幅広い知識と経験を持っていて，今回も様々なアイディアやアドバイスを頂きました．
プログラミングコンテストの本を書きました - iwiwiの日記
id:wata_orz や kita_masa と少しずつ書いていたプログラミングコンテストの本がようやく完成し，発売間近となりました． http://book.mycom.co.jp/book/978-4-8399-3199-5/978-4-8399-3199-5.shtml Google Code Jam，TopCoder，ICPC, 情報オリンピックなどのような，問題を解くプログラミングコンテストの，特にアルゴリズムに関する話題に焦点を絞った本です．全探索や動的計画法などの基礎的な部分から始まりますが，ネットワークフローや数論などのレベルの高い話題まで扱っており，幅広いレベルの人に楽しんでもらえると思います． また，アルゴリズムの解説だけでなく，章の中で POJ (PKU Judge Online) の問題を扱い，章末で Google Code Jam の問題を扱っています．特に，P
Google Code Jam 世界大会 - iwiwiの日記
アイルランドのダブリンで行われた Google Code Jam の世界大会に行ってきました． 結果は 9 位でした． コンテストについて B → A (small のみ) → C → D の順に解きました．順番は異なれど，同様の問題たちを解いている人が多いです． ただ， D について，非常に後悔しています． すぐに large の解法が分かっていたにもかかわらず，賢くない実装をしてしまって，Wrong Answer を出し，その後，結局 2 時間もデバッグに使ってしまいました． その 2 時間があれば，もっといろいろ出来ていたんじゃないでしょうか．悔しい・・・！ 結果について 9 位でした．とりあえず一桁順位は取りたいな，と思っていたので，目標は達成できました．嬉しいです． しかし，一桁の中では一番下だし，TCO09 も 9 位だったし，もっと上の順位をとってみたいです．特に，今回の問題
C++ で気軽に時間測定がしたい - iwiwiの日記
プログラムの一部分の所要時間をちょっと調べたいと思っても，前で時間を調べて，後ろで時間を調べて，引き算したものを出力して，と色々書かねばならず，意外と面倒です． Ruby の benchmark はいいなあと思っていたら，id:tanakh さんの PFI セミナーを思い出したので，それっぽいものを C++ で実現してみました． （2/21 19:30 頃に「もう少し便利に」のバージョンの問題点と解決について追記しました） 例 int main() { benchmark { sleep(1); } benchmark { sleep(2); } } こんな感じで書くと 1.000013 sec 2.000009 sec こんな感じで標準エラー出力に表示． ソースコード これを上に書いておけば OK です． #include <sys/time.h> struct __bench__ {
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
UTPC 2011 を実施しました - iwiwiの日記