« November 2006 | Main | January 2007 »

2006.12.28

疎なbit arrayに対する現実的なRank/Selectデータ構造

久しぶりに研究紹介。

最近書いた論文です。
"Practical Entropy-Compressed Rank/Select Dictionary.", Daisuke Okanohara and Kunihiko Sadakane.
In the Proc. of ALENEX 2007, to appear[paper]

この論文では、疎なbit array B[0...n-1]に対するrank/select操作を高速に実現するデータ構造を4つ提案しています。 rank(x)はB[0...x]中にある1の数を返し、select(x)はx番目の1の位置を返す関数です。
古典的な問題ですが、これを最小(entropyに近い限界)かつ高速(定数時間、もしくはそれに近い時間)で実現する現実的なデータ構造は存在しませんでした。これを4つの違ったデータ構造で実現したというものです。
このデータ構造はsuccinct data structureを構成する上で不可欠なもので、今まで各データ構造毎に、疎なbit arrayを効率よく保存する方法がデータ構造の特徴を利用することで提案されていたのが、これを使えば統一的に解決されます。

実際どう作って、どういう特徴があるかはペーパーを参照してください。

このデータ構造はそれ以外にも使える場面があって、例えば、単調増加列の整数列を保存する場合も、その整数がある場合にはその位置のbitは1、それ以外が0であるようなbit vectorで保存すれば、selectを使って整数をランダムアクセスできます。
具体的に転置ファイルの例では、0番から100万番まで文書番号があって、ある単語が出ている文書番号を小さい順に保存する場合を考えたとき、この単語が6万文書で出現しているとしたら、これを保存するのにはそのままでは60000*32bit = 240KByteかかるのですが、提案したデータ構造(この用途にはsdarrayがいいかな)を使うと60000 * (2 + 4)bit = 45K Byteぐらいで保存できます。さらに二つの整数列のintersectionをとることもできます(i番目の位置のbitを取得する操作はrankの操作と同様にしてできる)。

また、疎な行列(やグラフ)を保存するのにも使えて、今いろいろ試しているところです

| | Comments (208) | TrackBack (0)

忘年会と年末

火曜。
研究室発表で修論の現状報告。あとは精度をぐりぐりあげてアプリケーション作って論文書けばよいだけ。ほぼ全部。
その後、打ち合わせがあってその後学科忘年会。ものすごい雨でずぶぬれでタクシーでいこうとしたがタクシーも止まらず、店の名前と場所も分からずさまよい、心が折れそうになった後に着いた。
20台後半が近づきつつある中どうしたらいいのかを、あーだこーだを話した。
で、二次会は大体いつものメンバーであーだこーだを話した。

| | Comments (0) | TrackBack (0)

2006.12.22

そんな年末もあるよ

考え事をしながら、サンドイッチを食べていたらサンドイッチの具側が外に来るように食べていた。最後に外側2枚が余った。

考え事をしながら、うどんがくるのをまちながら水を自分をとりにいって戻ってきたら、既に机に水を二つとってあり三つめの水だった。隣の会社員が、え!?と言っていたが、仕方ないので三つのんだ

海外ホテルの予約をとるため頑張って国際電話をかけた先が、音声認識で予約をとるという革新的システムだったのだが、自分の英語の発音が悪く思い通りの予約がとれない

| | Comments (0) | TrackBack (0)

2006.12.19

鍋等

最近の主なイベント

・先々週末、コーディング合宿に行ってきました(ここ)。風呂と寝ている時間以外はコーディング。いろいろできたのでよかった。あと、寿司やらバリ料理やら食ったものが全ておいしかった。また行ってもいいなぁ。

・ラグビー部OBでの恒例の忘年会。大きかった人がさらに大きくなっていた。料理がみんなどんどん上手になっていた。俺は家事は退化してきている。しかし家で鍋やって一人1万3000円は食いすぎなようなきがする。

・辻井研の忘年会であんこう鍋。あんこうはファミコンの美味しんぼの中でしか出会ったことがなかったが、ようやく食べることができた。うまかった。辻井先生と、日本のバブル崩壊とそれに伴う若者の精神構造の変化というお題でずっと話していた。その後のカラオケではいろいろ振り付けを勉強させてもらった。中島みゆきは言葉の壁を越えて通用した

| | Comments (0) | TrackBack (0)

2006.12.07

プール廃棄ガイドライブ

最近何したか

先週、知り合いと約束して代官山にあるプールに行ってきて泳いできました。広くてとてもよかったのですが、初めて行ったので挙動不審で、係りの人に3回ぐらい呼び止められました。思う存分泳げてきもちよかった

備品廃棄は先週と今週。去年は巨大サーバーラックを階段から降ろすということがありましたが(何人か巻き込まれても仕方ないと思った)、今年は小物が主。とはいえ、結構時間がかかり大変でした。とはいえ結構疲れた。掃除は苦手です。

OBガイドに参加して神宮で外国人をガイドしてきました。最長老でした、が、とても楽しかった。だんだん知識が薄れてきたのが残念。口承でいろいろ伝えていたのですが、最近ネットで見つかるようになってきた・・。明治神宮の森はもともと人工林で自然林になるように植物学者によって計画的に植樹されたものだとか、これが代々木の元になった木だとか、鳥居は台湾の木で二代目だよとか。

先日、高校の友人(白田)が東京に凱旋ライブをしにきたとのことでみにいってきました。関西、九州の学園祭をまわってきたそうですごいなぁ。高校以来久しぶりに会ったけどお互いすぐわかりました。ライブはよかったですなぁ。歌の世界も厳しそうですが、楽しんでやってたのが何より。

| | Comments (3) | TrackBack (0)

師走

最近日記書いてなかったですが、なかなか日記に書けることがなかったのと、書こうと思ったときにココログがメンテナンスしていたからです。まぁそうはいってもココログは使い続けます。

最近読んだ中でおもしろかった論文

"Online Passive-Aggressive Algorithms" Koby Crammer, Ofer Dekel, Joseph Keshet, Shai Shalev-Shwartz and Yoram Singer, Journal of Machine Learning Research 7, pages 551-585, 2006. [pdf]

オンライン学習でバイナリ、多クラス、構造を持った出力(これに近いmiraについては kudoさんによる解説参照)を学習できる。perceptronと似たような形で学習でき、非常に簡単な更新式でパラメータを更新していく。
実際C++でかいたら50行程度で学習プログラムができた。
このモデルの基となったmax margin法はバッチ処理でトレーニングすると非常に計算量がかかるので、それを近似とはいえ簡単な形で学習できるのはいい。理論的解析も累積損失の形だが一応ある。

今、これでサイズの大きい問題を解いているところ

"Compact Data Structures with Fast Queries (2005) ", Daniel K. Blandford [pdf (citeseer cache)]

(oxyさん論文紹介どうもです)
配列、木、グラフなどのデータ構造をいかに小さく保存して、かつその上で高速な操作を実現するかという話は最近良く出てきますが、この仕事では動的な更新方法なども言及されていて、具体的な実装方法もつめているところがいい。
興味深いのはグラフのコンパクトな保存方法。通常ランダムに生成されたグラフはどうやってもコンパクトに表現できないのですが、現実世界に登場するグラフは大抵 separable (わずかな頂点を取り除くだけでグラフがほぼ同じ大きさの二つのグラフに分解される性質)なので、それを利用して圧縮表現を可能とするという話。具体的には自分の頂点と隣接する頂点の集合を差分表現して保存する際に、もしグラフがseparableならば、頂点番号を張り替えることで、差分が小さい数ばかりとなってコンパクトに表現できる。

| | Comments (5) | TrackBack (0)

« November 2006 | Main | January 2007 »