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 の実装にはバグがあり，本家メルセンヌ・ツイスターと挙動が一致していませんでした．
AAAI'15 論文採択：Top-k 最短経路クエリとネットワーク構造予測への応用 - iwiwiの日記
国際学会 AAAI 2015 に論文が採択されました．AAAI は人工知能分野の最も有名な会議の 1 つです．発表は来年の 1 月にアメリカのオースティンです．AAAI への論文採択は 2 年連続となります． 今回の論文は "Efficient Top-k Shortest-path Distance Queries on Large Networks by Pruned Landmark Labeling" というタイトルで，研究室後輩の林くん，京大の則さん，研究室同期の岩田，NII の吉田さんとの共著です．内容は，グラフにおける Top-k 最短経路を高速に計算するためのスケーラブルなインデクシング技法の提案，及びそのネットワーク構造予測への応用です．特に，応用面のインパクトを示す試みを論文内に入れることができたのが大変気に入っています． 背景：ネットワーク上の 2 点間の関連度推定に
1/30 発売！「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」 - iwiwiの日記
書籍「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」が近日中に発売される予定です．会津大の渡部先生が著者で，Short Coding 本の Ozy さんと私が協力としての参加です．どうかよろしくお願いします． プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 作者: 渡部有隆,Ozy(協力),秋葉拓哉(協力)出版社/メーカー: マイナビ発売日: 2015/01/30メディア: 単行本（ソフトカバー）この商品を含むブログ (4件) を見る 本書はアルゴリズムとデータ構造の入門書です．整列，探索，木構造などをはじめとする基礎的なアルゴリズムとデータ構造を初学者向けに説明します．前提とするのは基礎的なプログラミング能力のみです．コード例では C++ を用いています． これだけだと，よくある本のように思われるかもしれません．しかし，本書は非常にユニークな特徴として，オン
DEIM フォーラム 2014 最優秀論文賞：2-Hop ラベルの直接的な計算によるグラフ最短経路クエリ処理の効率化 - iwiwiの日記
DEIM フォーラム 2014 での発表論文が最優秀論文に選ばれ，本日開催されたソーシャルコンピューティングシンポジウム (SoC 2014) にて行われた授賞式に参加しました．後輩の大坂君との共著論文も優秀論文賞を受賞しました． このような極めて高い評価を頂けたことは身に余る光栄です．私だけでなく，著者グループ全体で見ても DEIM や関連イベントへの参加・投稿経験を持つ者は居ず，我々のような「新参者」であっても公平に高い評価をしてくださるコミュニティに感謝と敬意を表したいと思います． 元々，私の研究の興味は「アルゴリズムとデータ構造」であり，卒論の頃から，アルゴリズムの研究室（東大今井研）を選びずっと所属しています．しかし，アルゴリズムのコミュニティにて重視されるような漸近的な理論解析よりも，私は大規模データ・実性能・社会へのインパクトなどに興味があり，配属当初は（正確には研究室選びの
乱択データ構造の最新事情 −MinHash と HyperLogLog の最近の進歩− - iwiwiの日記
本日，PFI セミナーにて「乱択データ構造の最新事情 −MinHash と HyperLogLog の最近の進歩−」というタイトルで話をさせてもらいました．スライドは以下になります． Ustream の録画もあります． http://www.ustream.tv/recorded/48151077 内容としては，以下の操作を効率的に行うための集合に関するデータ構造 (Sketch) の最近の進歩を紹介しました． 集合の類似度の推定 (Jaccard 係数) 集合異なり数の推定 (distinct counting) どちらも重要かつ基礎的な操作で，b-bit MinHash や HyperLogLog など，既に実用的な手法が提案されており，実際にも使われています．しかし，2014 年になって，Odd Sketch や HIP Estimator という，これらをさらに改善する手法が立て続
WWW'14 に論文採択 - iwiwiの日記
論文が国際学会 WWW'14 (23rd International World Wide Web Conference) に採択されました！ WWW はその名の通りウェブに関するトップ学会で，比較的新しいものの最近ではかなりの人気を誇る学会だと思います． WWW の最近の人気は，例えば Microsoft Academic Search の学会ランキングで伺うことができます．最近 5 年に限定すると，なんとコンピュータ科学の全分野合わせても 2 位*1，最近 10 年にしても 3 位ということで，かなり順位が高いです．その分もちろん競争も激しく，採択率は 84/650 = 12.9% だそうです． 所属する河原林グラフ ERATO からもかなりの本数が提出されたようですが，知る限り残ったのは僕の論文だけのようです． 論文タイトルは "Dynamic and Historical Shor
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
