« June 2005 | Main | August 2005 »

2005.07.31

hybridlist

skiplistより少ないメモリでバランス木を実現できないかなぁと探していたらhybridlistというのがあるそうだ。

skiplistと同様に基本は普通のリストで、それに加えてスキップ用リンクが使われる。skiplistは、新しくノードを挿入するときにランダムにスキップする量と数を決定するのに対し、hybridlistはスキップする間隔が一定以上あいたときにスキップ用のノードを途中に一ついれる。(skiplistと同様にこれが階層で管理されている)。
hybridの意味は下の普通のlistとskipの部分がばらばらということかな。スキップ用リンクの双方向リストの実装が面倒ならそこはSTLのを使えばいいですね。

| | Comments (2) | TrackBack (0)

2005.07.30

マクスウェルの悪魔

がうちの部屋にいると思う。夏は外より暑いし冬は外より寒い。

| | Comments (1) | TrackBack (0)

2005.07.29

Large Margin

Ben TaskarさんのACLでのチュートリアル資料がアップされている。Thesisでやったマッチングの学習に関するやつがICML 2005でとおったやつもアップされている。
http://www.cs.berkeley.edu/~taskar/
勉強になりますなぁ・・。近いうちにツールキットが公開されるらしい。いろいろ遊んでみよう

| | Comments (1) | TrackBack (0)

google reserch paper

googleは保有技術に関してなかなかアカデミックな場で発表しないという話があったのだがぼつぼつ新しいのが出ている(上のほう)。
http://labs.google.com/papers/index.html

ここのを読んでみると、高いソフトウェア開発環境があることが分かる。数百台から数千台のマシンを動かすのに数十行ぐらいのコードで動くのはすごい。この論文によるとサーチエンジンに使う転置ファイル構築用のソースが700行らしい。

2年前ぐらいにファイルシステムとクラスタの論文でて、ここんところで開発環境に関する論文がでたから、そろそろアプリケーションの中身がでてくるのかなぁ

| | Comments (3) | TrackBack (0)

2005.07.28

マンU対鹿島@国立

友人とサッカー見てきました。国立で、ラグビーの試合は何回かみたことあるけどサッカーは初。結構前の方の席でした。好調の鹿島との対戦ということもあって結構中身の濃い試合だった。試合は鹿島が勝ったけどマンUのファンになってしまいそう。

ルーニーは思っていたよりおっさん、かつごつい(ちなみに年下)。C・ロナウドとギグスは速くうまかった。期待のパクチソンは途中で怪我をしたらしく退場してしまったので残念。

| | Comments (0) | TrackBack (0)

2005.07.25

東へ

自転車置き場から消えた俺の自転車が集積場にあるということでとりに行く。いろいろ壊れていたが乗れる。久しぶりに自転車に乗ったのでうれしくて(遠くに行きたくて?)なんとなく渋谷まで行く。ハンズでいろいろ買う。

後はずっとプログラミング。compressed suffix arraysとかクラスタリングとか。incrementalな構築を加えて10GBぐらい処理できそう。今はまだ無理だけど使えるリソース増えてきたしTB indexingとかしたいなぁ。googleはペタいっちゃってるけど、デスクトップ1台でできたら、それはそれでいいんじゃないかと。

桃くいたいななと思っていたので帰りに桃を買って食べる。さすがに4個食べたら苦しくなった。いま弱っている。

| | Comments (0) | TrackBack (0)

2005.07.24

アルゴリズム談義

バイトの人たちとアルゴリズムの話となる。

グラフマイニング。特にGastonについて。 gspanより10倍ぐらい速いらしい。このTech Reportが詳しい 
基本的な方針はグラフマイニングで候補部分グラフを少しずつ大きくしていくのだが、そこでもし候補部分グラフがパスや木ならば閉路を含むような複雑なグラフの相同性チェックとかはいらないので簡単なチェックですませてしまおうというQuick Startの方針

skiplistとその拡張について。skiplistはAVLや赤黒木などの平衡木の難しい実装を使わなくても、ランダマイズドアルゴリズムを使うと簡単な実装で平衡木と同じようなことができますよという素敵な話。この方針は木だけでなくほかのいろいろなアルゴリズムに使える。実際にグラフとかへの拡張がすでにやられている。

Cache-Oblivious Algorithmはこの場で初めて聞いた。Reading list Cacheを意識したアルゴリズム設計をする場合は普通、キャッシュの特性(ラインサイズやライン数)を意識してそれをパラメーターにいれるが(例えばラインサイズにぴったりあうようにバッファリングするとか)、このアルゴリズムを使うとそのパラメーター項がなぜか最後の計算量項から消えて、どのようなキャッシュ構成であっても(キャッシュミス回数とかの観点で)最適なアルゴリズムとなる。理論だけじゃなくて実際のアルゴリズム(例えばFunnnel sort/heap)も存在する。

| | Comments (8) | TrackBack (0)

2005.07.20

北へ

宇都宮、茂木、水戸へいってきた。

途中にあった大谷石資料館がすごかった。ものすごい空間
宇都宮で餃子の店はしごしていろいろ食った。うまかった。
その後ツインリンクもてぎへ行きちょうど開催していたバイクの7時間耐久の終わる頃をみてきた。
その後水戸へ行き水戸ラーメンを食べようと思ったが、店見つからず。そもそも行こうと思っていた偕楽園は午後4時にしまるため間に合わず。東京でラーメンくいました

| | Comments (0) | TrackBack (0)

2005.07.17

なぞなぞ

バイトに行ってクラスタリングをもりもり書いていた。

夕食に近くのインドカレー屋に。そこでなぜかいろいろななぞなぞが出されあう。

・動物が逆立ちして歩いている国は?
・ピノキオがヤカンでお湯を沸かそうとしても沸かせないのはなぜ?
・雨が降っているときに助かる駅は?

みんなで悩んでいる険しい顔になっている時は、まるで険悪な雰囲気になっているかのよう。

カレーは辛かったけどおいしかった。

| | Comments (0) | TrackBack (0)

2005.07.16

部屋大掃除

penという雑誌でかっこいいオフィスがいろいろ紹介されていた。うちを省みると人がそもそも住む場所ではないような気がする。というわけで大掃除&改造中。
掃除しているうちに大量の片方の靴下が出てきた。もう片方の靴下達はどこへ。

少し住みやすくなってきた。

| | Comments (22) | TrackBack (0)

2005.07.13

スターウォーズ

日曜に見てきました。よかった。
エピソード4,5,6が見たくなった。後で解説本読んだらさらに楽しめますね

| | Comments (0) | TrackBack (0)

2005.07.09

CODE COMPLETE

ソフトウェア開発者は読んでおいたほうがいい本。
まださらっとしか読んでないけど、読みやすく、ためになる本ですね。高いけど。

CODE COMPLETE (上)(下)」 Steve McConnel著 クイープ訳

| | Comments (2) | TrackBack (0)

2005.07.08

たくさん Semi supervised clustering

しましまさんから読んでおくといいよ論文リストをいただいて、うはうは読んでます。
制約付き(この二つの要素は必ず同じクラスタ内である制約のmust link、そうでないcannot link)と確率モデルのつながりがまぁ面白い。ユーザーインターフェースとのつながりもあってまだ先がありそう。
Sugato Basuさんの博論あたりが詳しいみたい。

| | Comments (2) | TrackBack (0)

2005.07.07

semisupervised clustering

みたいのを書いてました。動かしてみる。名前からも、もうよくわからない
夜は明日発表のPCI、PCI-Xバスについて調べて書いていた。たぶん明日やられる

IT・ネット業界地図という本が面白そうだったので読んでみたら、おもしろかった。日本はyahoo!が検索利用者数でgoogleに勝っている世界的に見たら珍しいところ。yahooはポータルサイトとして便利だし、ニュースとかのチョイスがいいから俺も毎日必ず見るけども。稼ぐって大変だよなぁ。

| | Comments (0) | TrackBack (0)

2005.07.06

charniak+johnson parser

今年のaclで発表された parserを入れていろいろやってみました。
論文 parser
英語の知識が乏しいものとしては、ざっと結果みてみるとこれでいいんじゃないと思ってしまうのですが、このparse結果をSemantic Role Labelingとかに利用するともっと精度が欲しいそうだ。文正解率とかに直すとまだまだなのだろうか。訓練データとテストデータのドメイン変えるとまだ、だめみたいだしね。

#とりびあ charniakの先生はminsky

| | Comments (0) | TrackBack (0)

2005.07.03

binBWT

whiteさんのところでリンクされていたやつ
A space-efficient construction of the Burrows Wheeler Transform for genomic daya J. of Computational Biology to appear
Ross A. Lippert. Space-Efficient Whole Genome Comparisons with Burrows-Wheeler Transforms. J. of Computational Biology. Volume 12, Number 4 (2005), pp407--415

文字をunary符号化して(A- 0 C->10 T->110 G->1110)、binary列に対してincremental BWT。アルファベットが2種類だけだからbit array列を赤黒木で管理しておくだけでよい。(アルファベットが3以上の場合はwavelet treeを使えばよくて、それはwhiteさんがすでにやっている)

これと似た話で、最初にHuffman符号化して、そのbit列に対しFM-indexを作るというものもある。
Szymon Grabowski, Veli Mäkinen, Gonzalo Navarro, and Alejandro Salinger.
A Simple Alphabet-Independent FM-Index.
To appear in Proc. PSC'05.

最初に符号化して処理する方法がはやってますね。

Canonical Huffman使って文字列に対してbinary符号化して(この時符号化前と符号化後で順序関係は保たれる)方法でもincremental BWTできそうだな。unary符号化とは違って文字の始まる位置を別に保存しておく必要がある上に、一つ前の文字って復元できるのかなぁ・・うーむわからん

1GのMemoryで3GBaseのゲノム配列のSuffix Arraysが構築できる時代になったのか。8時間ぐらいだが、他の手法で24時間かかったという論文もあったからIncrementalな構築の中では速いほうなんだろう。

実装しているうちにもっといい手法がでてくる。でも待ってても仕方ないし、作りたいと思ったときが作り時。

| | Comments (0) | TrackBack (0)

2005.07.01

CSA vs FM-index

今年もCopressed Suffix Arrays (CSA) とFM-indexに関する論文がたくさんでている。話は理論的なものからより実用面での話しに変わってきている。
CSA、FM-indexどちらもBWTをベースにしていて、nバイトをインデクシングするのに4nバイトかかるSAをそのまま保存するかわりにCSAはψ、Fm-indexはBWT後のテキストを圧縮した形(rank操作付き)で保存する。FM-indexはψ^{-1}の情報(のようなもの)を保持しているので対称なindexともいえる。
今後は圧縮率ではなく検索速度の方が重要になってくると思われる。今はまだ圧縮なしSAよりはるかに遅い(実装やパラメーターにもよるけど、まだ十倍程度の差がある)。パターン長を変えたときの比較がよくあるが、圧縮Hgt配列をCSAに組み合わせての検索ってまだないのだろうか。そうするとパターン長に依存せずにO(logN)でできるだろうに。みつけてないだけか、Hgt配列の順序が特殊だからできないのか。

| | Comments (141) | TrackBack (0)

« June 2005 | Main | August 2005 »