ソート済みの数値配列に対しては、binary searchではなくinterpolation searchをするとO(loglogN)で済むというような記述があるので調べてみる。

テーブルの作り方が分かった瞬間もの凄く内容が理解できるようになったので圧縮の方法も書いておく。後でブロックサイズという物を用意するが、今は簡単のため、全てを圧縮する物として話を進める。とりあえず各テーブル毎にソート済みの64-bit値の配列を持…

論文のやり方だと、各テーブル毎にπという関数を用意。この関数はnブロック中、テーブル毎に固有なkブロックを先頭p-bitになるように移動する。T[i].insert(π(f))と言うイメージっぽい。Tの中身はソートされている。これでバイナリサーチとか書かれていた意…

同じような考え方でできるみたいなので考えてみる。

Detecting near-duplicates for web crawling3.1.2の式の意味を考えてみた。fはfingerprintのbit数、kは最大許容Hamming距離、2^dは比較するfingerprintの数。pminはテーブルでチェックしたい(処理をやり過ごしたい)最低bit数。定数τはこれ以下の時はテーブ…

最適化のレポ明日中にやらないとorz

最近金の相場が良いようで、スロ屋でコインを買うだけ買って換金する人、換金所以外で同額買い取りをしている人が増えている模様。ちなみに、スロ屋だと2500円相当の金が今日現在3000円近くで買い取られている。万枚だしたら数万得する計算。換金所涙目。こ…