« Top-k文書列挙問題 | Main | NLP2010 言語処理学会チュートリアル »

2010.02.22

fujimap: 簡潔な連想配列

博論終わったので仕事の合間にfujimapというライブラリを作ってみました。

fujimap project

fujimapは作業領域が非常に小さい連想配列で、文字列からなるKeyを利用して、整数値もしくは文字列からなるValueを登録・参照することができるライブラリです。

今巷では大規模なKey Value Stroe (KVS)が流行っていますがFujimapは一台のマシンのメモリ上で動作することを想定して作成されています.Fujimapの特徴は必要な作業領域量が非常に小さいことです.キー自体を明示的に保存しないため、作業領域は値を格納するのに必要なサイズと、許容するfalse positive(後述)にのみ依存します。

例えば、google N-gramのunigramの約1300万キーワードとそれらの頻度の対数を記録する場合、false positiveを気にしないなら、一キーワードあたり約4bit(全部で7MB、もともと136MB)で格納できます。C++ std::mapの約1/100です。メモリが10GBある場合、同じようなデータなら200億 Key/Valuesぐらいを高速に操作できます。

fujimapではKeyを明示的に格納しません。それでも登録したKeyに対しては正しい値を常に返します.それに対して、登録されていないKeyに対してはユーザーが設定した確率で誤り、NOTFOUNDが返らずにランダムな値が返ってきてしまいます(false positive rate, 偽陽率).Bloom Filterのようにfalse positive側のみにエラーをゆるし情報理論的限界を破っています.

fujimapが必要とするサイズと偽陽率はトレードオフの関係にありfpLenと呼ばれるパラメータで設定できます.1KeyあたりfpLen bitのオーバーヘッドで偽陽率は2^{-fpLen}となります.例えば、1keyあたり10bitのオーバーヘッドで2^{10}分の1、つまり約0.1%の確率で登録されていないKeyに対しても、NOTFOUNDではなく、何らかの値が返ってしまいます.

これはKeyがどのような文字列からなる場合でも同様になりたちます.例えば,Keyの長さが1KBのように長い場合でも、その格納に必要なBit数はfpLenと値のみで決まります.

いくつかの実験結果は先ほどのページに乗せてあります.
先ほどのGoogle N-gramの例では

1keyあたりに必要なbit数
std::map 573 bit
tx 35.4 bit (keyの保存に29.4 bit , 値の保存に6bit)
fujimap 4.4 bit

であり、構築時間、参照時間はstd::mapとほぼ同じです

これらの実験結果やAPIなど詳細についてはプロジェクトページをみてください。

説明や使用例、アプリケーションなどは随時追加していきます。

注意点として、fujimapでは一応、動的な追加、変更が一応C++ APIではサポートされているのですが、それらの命令を使った途端に先ほどの偽陽率や登録したキーには必ず正しい結果が返ってくるという保障がなくなります。このあたりについてはきれいに説明できないので使う必要がないなら極力使わないようにしてください。どうしたらきれいに外から使えるかまだ考え中です。

--
Fujimapの内部はいくつかの研究を元にしたものに実装的な工夫を追加しています.
Fujimapの基本的なアイディアは最小完全ハッシュ関数と同様のもので、N個のKeyに対し衝突しない[0,N-1]の値を割り当てる手法を値を格納する方法に拡張しています.

まず、FujimapでKey kを格納する場合R個(R=2,3など)のハッシュ関数での値h1(k), h2(k),... hr(k)を求めます.次に、ビット配列Bから、これらの排他的論理輪の値を求めます v = B[h1(k)...] ^ B[h2(k)...] ^ B[hr(k)...]; このvがkに対応する値です.

値は擬陽性をチェックする部分(fpLen bit)と、それ以降の実際の値を格納する部分からなります.キーkに対し、先ほどのハッシュ関数とは異なるハッシュ関数でkに対するsignatureを求めておき、先ほどのvの先頭fpLen bitがsignaretueと一致する場合は、それが実際の値、そうでない場合は登録されていないKeyということでNOTFOUNDを返すようにします。

fpLen bit以降の値は実際の値を固定bit長のBinary符号、もしくはGamma符号で格納しています.

登録されている全てのキーに対し、上のように操作して正しく動作するようにB中ビット値を決定する問題は連立方程式の問題となります.この問題は最小完全ハッシュ関数を決定するのと同様に、キー集合とそれらの依存関係からハイパーグラフを構築し、そのハイパーグラフ中から次数が1である頂点とそれにつながっている枝を順にのぞいていき、次にこの順番と逆に各bitの値をgreedyに決定していくことによりキーに比例する時間で決定できます。

非常に大規模なキー集合を扱う場合、構築に必要な作業領域が大きくくなってしまう問題が生じます.そのため、Fujimapでは最初にKeyの集合を簡単なハッシュ関数を利用していくつかのブロックにわけておきます。そして各ブロック内部で先ほどの手法を利用してキーと値を結び付けます.各ブロックのサイズをディスクの1ブロックと同程度にすることにより、ディスクアクセスを生じる場合でもシーク回数が一回でできるようなデコードも実現可能です.

--
fujimapの開発にあたり、開発環境をいろいろ変えています

ビルドシステムにautomakeから変更しwafを使っています(隣の隣の席の田中さんによるwaf解説)
ものすごく速くて色がついて怪しいautomakeの黒魔術を使わなくて便利です。まだいまいちわかっていなくて例をちょっと変えたものしかつかっていないけど。

あと、google code projectをフル活用。あとdoxygenからgoogle project wikiに変換するやつがうまく動けば、いいんだけど、どうも動く動かない

--
ちなみにライブラリの名前は博論書きの時にお世話になった富士そばに由来しています。天玉が好きです。

|

« Top-k文書列挙問題 | Main | NLP2010 言語処理学会チュートリアル »

Comments

Awesome! Its truly awesome article, I have got much clear idea on the topic of from this article.

Posted by: kreisrunder haarausfall Ursachen | 2013.11.20 at 01:00 AM

For hottest news you have to visit world-wide-web and on internet I found this web page as a finest web site for hottest updates.

Posted by: Kay | 2014.04.19 at 06:52 PM

With havin so much written content do you ever run into any issues of plagorism or copyright infringement? My site has a lot of unique content I've either authored myself or outsourced but it appears a lot of it is popping it up all over the internet without my authorization. Do you know any methods to help prevent content from being ripped off? I'd really appreciate it.

Posted by: free films online | 2014.07.20 at 05:18 AM

However when your еx bоyfriend is deliberately stɑying away from you. Tɦe CIA responded with a coup thɑt murdered Allende and replaced him with а brutal tyrant, General Augսsto Pinochet. All were staunchly conservative, fiercely anti-communist and soсially еlite.

Posted by: Heidi Booth | 2014.11.01 at 11:50 AM

A trend of ɦiv cases among ƅlack women can Ƅe attributed to black men on the down low. The big decision you'll have to make is what level оf challenge you want to have. Coverіng only ɑ few days, tɦis chaƿter gives tҺe Rockеt Boys one of the thingѕ tҺat they had been looking for through tҺe entire story.

Posted by: Ultimate Herpes Protocol Pdf Free Download | 2014.11.01 at 01:48 PM

A trend of Һiv cases among black women can be attrіbuted tо black men on the down low. Search term in Meta-tag - Meta-tag is ultimately intended to tell the google seaгϲh of just wɦat your internet site is mostly about. Winning youг еx ƅack աith the right techniques is а powerful process that cannot be underestimated.

Posted by: Heidi Booth | 2014.11.01 at 02:47 PM

I think mƴ marriage iѕ in trouble and I want to save іt. (Anytime I get ANYTHIΝG even remotely 'οffbeat', I contact the tabloids) They list toll-frеe numbers, e-mails and weЬsites for tipѕ and hot photoѕ in eveгy taЬloid just on the chance that YOU will ɡet that 'milliоn dollar' shot. All were staunchly ϲonservative, fiercely anti-communist and socially elite.

Posted by: ultimate herpes protocol pdf torrent | 2014.11.01 at 03:49 PM

After үou have found out the truth about the existence of thе secret email then that is the onlу time that you should tɦink about the next steps that you are going to take. (Anytime I gеt ANYTHING еven remotely 'offbeat', I contact the tabloids) They list toll-free numbers, е-mails and ѡebsites for tips and hot photos in every tablօid just on the chance that YOU will ǥet that 'million dollar' shot. The good news is you can get it naturallү and not only see your sexual performance improve but alѕo your overall health.

Posted by: ultimate herpes protocol pdf download | 2014.11.02 at 04:44 AM

Do I want to find a girlfriend tҺat I can settle down wіth, and fall in loѵe (gasp). Therefore, be ready for both genders to exerciѕe their riɡht in this regard. Dulcе military baѕe in New Mexico is a black ops government lɑb which iѕ 7 stories deep undeг the Archuleta Mesa.

Posted by: Heidi Booth | 2014.11.17 at 03:49 PM

Strategies and these multiple concepts form a theoretical base that facilitates the WIDA expectations structure. WIDA's standards reflect how-to instruct instructional dialect inside the situation of content area instruction and outline the development of English language improvement.

Posted by: cach hoc tieng anh hieu qua cho nguoi moi bat dau | 2014.11.23 at 08:14 PM

However wҺen your ex boyfriend is deliƄerately ѕtaying away from you. Therefore, be ready for both genders to exeгcise their right in this regarԀ. Winning your eх back with the right techniques iѕ а ρowerful рrocess that cannot be underestimated.

Posted by: http://collegedatingcoaches.com/ | 2014.12.09 at 11:33 AM

If you are currently experiencing English grammar you must take a support of good online grammar checker. It truly is important to acquire checker that can benefit your instance a grammar checker that's contextual is very important. Activities.

Posted by: phuong phap hoc tieng anh | 2015.01.05 at 08:16 PM

I think this is among the most significant info for me. And i am glad reading your article. But want to remark on few general things, The web site style is wonderful, the articles is really nice : D. Good job, cheers

Posted by: delhi escorts | 2015.01.18 at 11:23 AM

Pretty section of content. I just stumbled upon your site and in accession capital to assert that I get in fact enjoyed account your blog posts. Any way I'll be subscribing to your feeds and even I achievement you access consistently quickly.

Posted by: กล้องcctv | 2015.03.02 at 06:59 AM

It's wonderful that you are getting thoughts from this piece of writing as well as from our dialogue made at this place.

Posted by: promo code match.com | 2015.04.06 at 09:17 PM

It defines spaces, effects how we fill and creates atmosphere. Although coffee is generally not free, you can sip your way to unlimited frre Wi-Fi access. However, Apple remains in the lead when it comes to the number of apps available for download and developer earnings.

Posted by: App Nana Hack | 2015.04.30 at 12:27 AM

If you do have Android Put on-compatible fitness trackers and wearables, then Google Fit gets even much better.

Posted by: simcity buildit cheat | 2015.08.03 at 01:31 AM

Oh my goodness! Incredible article dude! Thanks, However I am going through difficulties with your RSS. I don't know the reason why I can't join it. Is there anybody getting identical RSS problems? Anybody who knows the answer can you kindly respond? Thanks!!

Posted by: delhi escort | 2015.10.08 at 05:32 PM

Simply wish to say your article is as astounding. The clearness in your put up is just spectacular and i could assume you're an expert in this subject. Fine along with your permission let me to clutch your feed to keep updated with drawing close post. Thank you one million and please carry on the enjoyable work.

Posted by: delhi escort | 2015.10.20 at 03:49 PM

Post a comment



(Not displayed with comment.)




TrackBack

TrackBack URL for this entry:
http://app.cocolog-nifty.com/t/trackback/3041/47637359

Listed below are links to weblogs that reference fujimap: 簡潔な連想配列:

« Top-k文書列挙問題 | Main | NLP2010 言語処理学会チュートリアル »