http://doi.acm.org/10.1145/1376616.1376651 http://doi.acm.org/10.1145/1277741.1277766 http://doi.acm.org/10.1145/1277741.1277871

現在電車中。64bitのハッシュ関数を使うと、どれも似たような結果になった。106億個URLがあると、大体全体の0.4%が衝突する。ちなみに、64bitの乱数を100億回生成しても大体6個しか衝突しない。シミュレート値と理論値が一致したので間違いないと思う。ハッ…

http://blog.clawpaws.net/post/2007/04/22/Good-Hash-Functions http://en.wikipedia.org/wiki/Hash_table と言っても、一回3時間以上かかる処理なのであと3回くらいしかできないお。速さ重視でSuperFastHashとMurmurHash2を組み合わせた64bitのハッシュ関…

100億個もできるのでどうしようかという話。めも:100億B=9.31GB。ハッシュ値は64bitなので、バイナリで保管しても74.48GBとなる。メモリ上でやるとかっこよす！なのだが、今は分散環境がないので難しい。なので、ハッシュ値を全部はき出してsort&uniqueする…

64bitのもの: そのまま使う 32bitのもの: 単体で分布を調査。その後全部の組み合わせで64bitのハッシュ値を生成しテスト 128bit以上のもの: 32bit単位で分布チェック。その後全部の組み合わせで〃 100億のURLをそれらしく生成する方法のめどはついたので、後…

http://www.cryptopp.com/ http://tanjent.livejournal.com/756623.html http://www.azillionmonkeys.com/qed/hash.html

意味があるのかどうかわからないけど、32bit単位でのハッシュ値の衝突をチェック中。そんで、分布をどうやって出力しようかと。32bitくらいだと、3億個のURLでもかなり衝突が発生してしまう。そして、そこそこ数が多いので、出てくるデータ量が半端ない。な…

32bitのハッシュ値の分布調査と、128bit以上のハッシュ値を32bit単位で切り出したときの分布調査。後は64bitのハッシュ関数調査。64bitのハッシュ関数って少ないよなぁ。。なんでだろ。

URLは使われている文字がものすごく限られてしまっているので、ハッシュ値が均等に分布するのかどうかが良くわからない。なので、その辺の調査もやってみる必要がありそう。逆に文字列に特化したハッシュ関数みたいなものも使ってみると良いかもしれない(こ…

Webクローラを作る際に重複URLを除去しつつ幅優先っぽい探索をしていく問題があるわけですが、今はそのときのURLの重複判定をどうやって効率よくやろうかという話を勉強中。その前処理として、URLに対するハッシュ関数を考え中。とりあえずURLの数が数なので…

諸事情で、本気でクローラ制作モードに移行することになりそうです。つか、あと2ヶ月の様子次第ではかなり人生計画を変更した方が良さそうな気がしなくもない。とりあえず今月はURLのsetみたいなものを効率よく作る感じの話に意識を集中させる事になりそうな…

らしい。URLの重複判定を1台で高速にやっちゃうお、というお話。なんか今まで使っていたクローラが色んな意味で好ましくないので、自分たちでクローラを作れると良いなーみたいな事になってて、その一環として調査ちう。なんかベストペーパー取っちゃったら…

ので頑張って調べてみようと思います。幸い Tomo’s HotLine のところで色々素晴らしい情報を公開してくださっており、 P2P研究者にお勧めするRFCとドラフト: Tomo’s HotLine ヘタレはまずこれを読むと良いぽいですね＞＜って訳で読んでます。あとはSkip grap…

自分の好きなことをするのですか？金になることをするのですか？将来ではなく、現在の、数秒後の世の中の役に立つことをするのですか？それとも、偉い人が興味を持つことを対象にするのですか？俺には良く分からなくなってきました。俺は研究者には向いてな…

http://homepage3.nifty.com/toremoro/index.html別にファイルシステムを作ろうとしているわけではないので京都腐府警の暇人は目を付けないでくださいね＞＜

http://www.ibm.com/developerworks/jp/java/library/j-jtp0205/index.html 面白いので空き時間に読む。

GXP : Grid and Cluster Shell

http://d.hatena.ne.jp/naoya/20080511/1210506301

id:pekeqさんがかなり色々書かれているので、ジワジワ読ませて頂こうかと…。そう言えば、DFSって今の俺の頭だとDepth First Searchが出てきちゃんだけど、Distributed File Systemでもあるんだよな。AFS http://www.pmw.org/afsbpw05/talks/kazar-afstalk.pp…

なんかダメだ。昔の悪い癖が直ってなかったというか、自分が没頭したいことを妨害する物に対して凄まじいストレスを感じる。折角頭が乗ってきてうはｗｗｗっていう状態のときに、どうでも良い授業が始まるとすげーむかつく。授業聞いてるより自分で本読んだ…

調査する学会(かな?)メモ

まだ研究室とか。本日も10時帰宅コース。

Cluster Computing and MapReduce Lecture 1 - YouTube 後で鑑賞。Part 5くらいまである模様。

学外の更に素晴らしい環境を求めて出るか、3年間 or moreを頑張るつもりで、受験勉強に使うつもりだった時間+αを全て研究に注いで頑張るか、かなり悩み始めた。とりあえず後1ヵ月は全力以上の勢いで勉強を続けてペースを計ってみる。でも学外に出ると人材の…

とりあえず12時に行ったのにデュアルディスプレイ対策で3時過ぎまで色々やってた。その後九時まで自習室研究室で勉強。 論文1つ理解 洋書80ページ 和書150ページ 英単語1Lesson 今日は簡単目の内容が多かったので、9時間くらいやってもこのくらいが限界っぽ…

残念なことに俗に言う早稲田大学理工学部、正式名称大久保工科大学から、グラフ理論の授業が消滅してしまったようです。幸い、俺は友達から教えて貰って去年受講することができました。CSからは俺とその人の二人しか受けてなかったけど、かなり良い授業内容…

これから先、グラフ(グラフ理論のグラフ)を描画できると便利な事が多くなりそう。そして更にその描画したノードに対して操作することができれば色々な事に応用ができそう。今度色々調べて作ってみようと思う。3次元に描画することが金になるようなら是非とも…

春休みに極めた方がよろしいというお告げが。

にゃあさんのついったー上で動いてたらkzkさんのを発見。そこになんか http://www.databasecolumn.com/2008/01/mapreduce-continued.html こんなのがあったのでメモ。

新年？おめでとうございます？なんのことですか？ A*関連。数学には距離と言う概念を扱う分野もあったはずなので勉強してみると良さそうな気がした。楽しすぎて発狂しそう。