List Comprehension and Mnesia

2008-03-09

プログラミング Erlang に出てくる Database Mnesia. query を list comprehension で書く. quote みたいのはないのに, どうやって list comprehension を query に map するのかと思ったら, list comprehension からは query handle というのが返されるらしい. C++ の expression template に似ている気もする. すげーな Mnesia. collective intelligence も list comprehension の威力を伝えていたし. だいぶ印象がかわった.

How Rackspace Now Uses MapReduce and Hadoop to Query Terabytes of Data

Hadoop. 実用してるとこ結構あるんだな. Yahoo もようやく使ってるというニュースがあったし. あとは last.fm も使ってるんだっけ？ http://wiki.apache.org/hadoop/PoweredBy に色々書いてるか.

処理するデータやアプリがあるってのは大前提だよな. このごろはほんとにアプリが羨しい. この話はすげー面白い. プレインテキストから素の MySQL, 変な構成 (merge table とか), でようやく v3.0 で Hadoop に到達. こうやって順にステップアップしてかんと分散システムってでいきないよなと思う.

Open Issue in Recommender Systems

Idea

P2P Recommendation

引用 attack

Unfair Ratings in Reputation Systems Dellarocas (EC 2000)
Robustness of Collaborative Filtering O’Mahony (TOIT 2004)
Self-Selection, Slipping, Salvaging, Slacking, and Stoning: The Impacts of Negative Feedback at eBay Khopkar ACM EC ’05

privacy

Privacy-preserving recommender systems: Polat et al 2003, Berkovsky et al 2005, Ramakrishnan et al 2001
Anti-Aliasing WWW 2004
- http://www.ra.ethz.ch/CDstore/www2004/docs/1p30.pdf

Predictions Perturb Perception (Cosley CHI ’03)

RRTR

subdivision surface. すげー懐しい. 学生の頃はけっこう熱心に勉強した. あのころから流行り物に弱かったんだな.

Squirrel

マニュアルすって読んでる. 言語は普通だ. 普通なのは良いことだ. class がちゃんと first class ぽいのは面白いが, table との一貫性はもうちっとがんばっても良かったんじゃないか. と, 思っている様子がマニュアルから伺えた.

頭いたい. ぼーっとする

花粉のせいと鬱のせいと半分くらいかな. RRTR 言って a 氏と話しているうちに気分は若干改善.

Squirrel

マニュアル読んだ. thread, weakref よく考えられてる. thread は別 VM になって, かつ root table が share されるのね. ここが一番心配だったけど, さすがによく考えられてる. root table を share しなければ concurrent に動かせる. すげー good. たぶん class も書き換えなければ share しても平気そうだし. でも refcount のガードが心配か...

コード読む甲斐がありそうだな, これは.

Weakref in Squirrel

よくできてんな.

weakref (SQWeakRef) 自身も refcounted なオブジェクト
SQObject (SQRefCounted) は最大ひとつの weakref を持つ
SQRefCounted は要求されると on demand に weakref をつくってかえす
SQRefCounted は削除時に weakref のもつ自身への参照を null にする
weakref は削除時に SQRefCounted のもつ自身への参照に nil を代入する.

このくらいでいいかもなー. linked_ptr の方が良いところもある(no dynamic-allocation)けど, こっちの方がシンプルだ.

refconted-object の mixin or subclass で weak-referable ってのをつくる？でも weakref できるかどうかを使われる側が決めるのは厳しいか. まーオブジェクトはちょっとデブになれってことかもね. 巡回参照避けるにはやむなし.

Revokable とは何がちがうのか？-> ちゃんと開放されて参照がなくなる.

boost は？ refcount のオブジェクトに use_count と weak_count がある. 巡回参照はおきないのか？-> おきない. 結局 boost も否応なしに weak 分の overhead はある. weak は業界標準認定で OK ぽい.

弱参照実装の候補:

Squirrel 方式
intrusive 方式
ID + テーブル方式
linked_list 方式
boost 方式

trade-offs

空間効率
性能
参照先書き換え
thread-safety

Idea:

weak-ref 用のコンテナ
intrusive_weak_ptr : ぐぐると話はあるが実装はないな.

OSS Recommenders

なんか Java のしか見当らないんだけど, 速いやつはないのかな.

速いやつを書きたいなー. とりあえず taste くらいの機能を揃えれば使ってもらえるんだろうか.

taste の文書を読んで機能と設計を学ぼう. クラスタリング + item-item くらいでだいたい OK だと思うんだけど, どうなんだろね.

links:

http://www.paulperry.net/notes/cf.asp

Taste

居ても立ってもおられず.

interfaces:

model : User(id, prefs), Item(id,recommendable), Preference(user,item,value), DataModel(database abstraction)
recommender: recommend(), estimatePref(), setPref(), removePref()
- ClusteringRecommender(getCluster()), ItemBasedRecommender(mostSimilarItems(item or itemlist), recommendedBecause), Rescorer, RecommendedItem, slopeone
correlation
- ItemCorrelation: (item, item) -> double の map interfaceb
- UserCorrelation
- この package は誰が使うの？ Recommender?
- 距離関数の実装ということだろうか？実装には Pearson とかあるね.
neighborhood/UserNeighborhood : Q: 誰が使う？
eval
- RecommenderBuilder : factory
- IRStatistics : ようからん. IR 関係の情報って...計算できんの？
extra(不要): web, ejb, transforms(たぶん. どっかのフック.)

んー. 恐しいほど patan と似てるなー... 設計の趣味は理解できるというか, 近い. ちゃんと java っぽい作りになってるし.

slopeone ?
なんとなく incremental にできなそうな API だけど, 実際は database になんかしてる？
- もっとも patan も incremental じゃないか...

なんか地味に書けば勝てそうだなあ. アーキテクチャは似たようなかんじにして, アルゴリズムの種類を増やしていけばいいのかな. 問題は taste がどれだけ現実に実用的なレベルなのかっつうことか. ちょっと探した感じだと採用事例ないなあ. でも開発自体は active なんだよね. cofe とか cofi はとまってる.

いちおう敬意を表して taste っぽい名前をつけるのがいいかもね.

標準でローカルで動く速いデータソースを用意してやるのがよさそうね.

TODO:

datamodel の実装見る
recommender の実装みる
- 特に clustering まわり: hybrid はあるか？
- 計算結果のキャッシュはあるか？永続的か？

ねよう...