Key Value Store勉強会に参加してきた
とても楽しかった。ミドルウェア系の勉強会が一番自分の関心に近いみたい。印象に残ったことを何点か。
- Masterがあるタイプの分散ソフトウェアで、障害時のMaster選択に苦労した話を聞いて、Chubbyが便利な理由が改めてよくわかった。
- Key Value Store だとランダム・リードが主なユースケースなので分散ハッシュのアプローチが有効みたいで、分散システム系はだいたいそうだった。全文検索みたいなユースケースだとシーケンシャル・リードが大事なので、BigTableのようなB-Treeのアプローチの方が有効だが、そのあたりはあまり開拓されていないみたい。
- TokyoCabinetを最下層のストレージに使っているケースが多かった。
Mixi年賀状はセキュアな郵便システムとなるか？
Mixiがマイミクにたいして住所が分からなくても年賀状を郵送できるミクシィ年賀状を開始した。
このサービスは前のエントリ「Googleストリートビューと郵便システムの問題点」で妄想した郵便システムとほぼ同じであり、「住所」を「ネット上のID」に置き換え可能なサービスである。普通は「妄想」レベルで終わる発想を、実サービスとして、しかも、日本郵便を巻き込んで実現させるミクシィはすごいと思った。
前のエントリでも書いたが、Googleストリートビューは「住所」を重要な個人情報に変えてしまうサービスである。
今後、Googleストリートビュー的なサービスは増えていくだろうから、「住所」を第三者に公開するのが嫌われる流れは変わらないだろう。したがって、「住所」を公開しないでも郵便を受け取れるミクシィ年賀状が一般の郵便システムとして拡大していく可能性は十分に高いと思う。
Googleストリートビューと郵便システムの問題点
Googleストリートビューによって明らかになったことの１つに、「住所」を他人に気軽に公開してはならないということがある。「住所」とGoogleストリートビューを組み合わせれば、「家族構成」や「年収」・「車の車種」などの重要な個人情報が推定できる。つまり、「家族構成」「年収」と同程度の慎重さをもって、「住所」という個人情報は扱わなければならない。
ところが、多くの人は「住所」を様々な相手に公開している。それはなぜだろうか？１つの理由は、「住所」から「家族構成」などを推定するには、現地に出向く必要があり多大なコストがかかるので、あまり問題となる例が少なかった点である。だが、Googleストリートビューにより、このコストは非常に小さくなった。もう１つの理由は、「住所」を公開しないと生活を送る上で非常に不便なためである。
人が「住所」を公開する目的の多くは料金表や年賀状などの郵送物を受け取るためである。しかしながら、郵送物を受け取るだけならば、「住所」を公開する必要はない。私書箱や局止めなどを使えば、「住所」を相手に伝えなくても、郵送物を受け取ることが出来る。ただ、これらの手段は個人用ではあまり普及していないように思える。
技術用語で語ると次のようになるだろうか。郵便システムには「私書箱」と「住所」という2つのプロトコルがある。「私書箱」の方がセキュアなプロトコルだが、殆どの人が「住所」を使っている。「住所」は脆弱性を潜在的にかかえていたが、その脆弱性を利用するには非常なコストがかかるため大きな問題となることはなかった。ところが、Googleストリートビューを使えば、低コストで「住所」の脆弱性を利用することができるため、「住所」を郵便システムで利用する際の危険性が高くなった。
この問題の原因はGoogleストリートビューではなく、現在の郵便システムそのものにある。Googleストリートビューはきっかけにすぎない。しかしながら、非常に大規模かつ重要なシステムである郵便システムを改修するのは簡単ではない。そのため、Googleストリートビューを使って郵便システムの脆弱性を利用する例が増えた場合、非難されるのは郵便システムではなく、Googleストリートビューとなるだろう。
ここからは妄想になるが、いっそのこと、Googleがセキュアな郵便サービスを提供してくれたら面白いのにと思う。封筒の宛名に郵便アドレス(foo@post.gmail.com)を書いてコンビニでだせば、宛名も住所も書かなくても相手に届くようなサービスである。住所と違って、郵便用の単なる識別子なので、引越ししてもアドレスは変わらないし、信用できない相手には一定期間後に破棄される捨てアドレスを渡すことも出来るなど、現在の「住所」より格段に便利で安全なプロトコルである。このような郵便サービスが普及していれば、Googleストリートビューが非難されることは少なかったと思う。
まとめると、Googleストリートビューは郵便システムが抱えている問題点のリスクを飛躍的に高める。これは、Googleストリートビューそのものの問題ではなく、郵便システムが抱える問題である。しかしながら、郵便システムを修正することは難しいため、リスクが高まることに対する非難はGoogleストリートビューに集まる可能性が高いと思う。
TagGridのデータ配置アルゴリズムの簡単な解説
基本的なアイデア
まず、入力となるのはN個のタグ付きデータとします。また、K種類のタグがあるとします。 TagGridでは、このN個のデータとK種類のタグがそれぞれ平面上に配置されるとします。 データだけでなく、タグも2次元平面上に配置するのが大事な点です。
基本的な考え方としては、あるデータのタグが例えばseaとsunの場合、このデータの位置がseaタグと sunタグの近くになるようにデータとタグを配置します。データは複数のタグを持つので、一番良い配置方法というのは簡単には決定できません。そこで、なるだけ良さそうな配置を求めてみます。
フォーマルな問題定義
基本的なアイデアを、もう少しフォーマルに定義します。 n番目のデータの平面上の位置を 、 k番目のタグの平面上の位置を
とします。 この時、n番目のデータとq番目のタグ間の距離を
とすると、この距離は次のようになります。
例えば、あるデータのタグが3個あった場合、このデータと3個のタグとの間の距離の合計が小さくなればよいわけです。ただし、データによってはタグが10個もあったりするので、各データの重みを等しくするため、タグの個数でこの距離の合計を割ることにします。
つまり、n番目のデータのタグを とした場合(T(n)はタグの個数)、次の値がなるだけ小さくなるようにします。
最終的に小さくしたい値はnについて総和をとった次の値になります。
後は、このL(このような値を目的関数値と呼びます。)が最小になるように、データとタグを配置します。
この時、TagGridではデータを格子上に配置したいので、データの位置は整数値のみをとるようにします。
最適化アルゴリズム
上で定義した問題は離散最適化問題と呼ばれ、このような問題を解くアルゴリズムは色々とあるのですが、現在のところ一番シンプルな貪欲法を用いています。詳しく知りたい方は組合せ最適化 - Wikipediaなどを参照すると良いと思います。
貪欲法による解法を簡単に説明します。
- まず、ランダムにタグとデータを配置します。
- その後、タグとデータの位置を順番に更新していきます。タグの位置を更新するときには、データの位置を固定して、タグの位置が一番良くなるように、タグを配置します。最適なタグの位置は、そのタグを持っているデータのちょうど重心になります。
- タグの再配置の後、データの位置を更新します。この時は、あるデータと別のデータの位置を交換した場合の目的関数値を計算して、目的関数値が交換する前よりも良くなるならば、データの位置を交換します。この交換するか否かの判定処理を全てのデータの組み合わせにたいして行います。
以下、このタグの再配置とデータの再配置を適当な回数繰り返します。つまり、次のような処理の流れになります。
ランダムな初期配置 → タグの再配置 → データの再配置 → タグの再配置 → データの再配 → ・・・ → 計算終了
データの再配置にの計算量が必要となるので、データ数が16000ですと数時間程度の計算が必要でした。ただ、アルゴリズムも実装も効率化の余地はかなりあるので、頑張れば数分程度までは短縮できそうです。
「なぞり出し」ユーザ・インターフェイスを「気持ちいい」と感じる理由
はじめに
先日公開したTagGridは比較的好評だったようでAsiajinにもとりあげて頂きました。
Flickr mashup on Google App Engine from Japan – Asiajin
TagGridでは、画面全体を埋めつくすように75x75のサムネイル画像を表示しています。1024x768と比較的小さいウィンドウサイズの場合でも、表示される写真の数は70枚くらいになります。
TagGridでは、これらのサムネイル画像を一度に全部表示するのではなく、マウスを移動させるごとに、マウスでなぞった箇所の写真を表示するようにしています。このUIは個人的にもかなり気に入っているのですが、はてなブックマークでのコメントでも「気持ちいい」との評価を頂けているようです。そこで、このUIをなぜ「気持ちいい」と感じるのか理由を考えてみました。
はてなブックマーク - 16000枚のFlickrの写真を気楽に眺めるためのサービスを作ってみた - llameradaの日記
「なぞり出し」の誕生
名前ないと不便なので、このマウスオーバーで画像を表示するUIを「なぞり出し」と呼ぶことにします。「あぶり出し」からの連想です。UIの専門家ではないので、既に有名なUIなのかもしれませんが、気にしないことにします。
「なぞり出し」は偶然から生まれました。全ての画像を一度に表示するのは、Flickrのレスポンスが悪いので、使い勝手が悪いものでした。そこで、この問題をごまかす目的で「なぞり出し」を導入しました。Flickrのレスポンスが高速だったら、「なぞり出し」は使わなかったでしょう。
そんな理由で導入した「なぞり出し」ですが、非常に気に入ってしまい、「なぞり出し」の快適さを損なわないために周辺のUIの高速化をかなり頑張りました。例えば、jQueryを使っているにもかかわらず、ほとんどのcss操作にjQueryは使わず、直接DOMをいじっています。その方が高速だからです。
「なぞり出し」を「気持ちいい」と感じる理由
前置きが長くなりましたが、偶然から導入したUIのため、なぜ心地よく感じるのか理由は自分でもよくわかっていませんでした。そこで、改めてその原因を考えてみました。
一度に表示される情報量が少ない
人間が一度に処理できる情報量はあまり多くありません。そのため、大量の情報を一度に提示するよりも、徐々に小分けした方が処理しやすいです。例えば、スライドの箇条書きを、一度に全部表示するのではなく、項目ごとに徐々に表示した方がわかりやすいです。「なぞり出し」では、なぞった箇所から情報が徐々に表示されるので、人間が扱いやすいUIである可能性があります。
みかけの待ち時間が少ない
なぞった箇所から表示するので、画面上には常に変化が生じています。そのため、待ち時間が少ない快適なUIと感じるような気がします。自分がなにか操作したにもかかわらず、画面上に変化が乏しいと、不安に思ったりイライラすることが多いようです。
自分で表示する情報量をコントロールできる
自分でなぞる箇所は選択できるので、自分の情報処理能力に応じて、表示される情報量をコントロールできます。そのため、情報量が多すぎたり少なすぎたりして、ストレスを感じることがありません。
隠された情報を見つけ出すのが楽しい
隠されたものを浮かび上がらせるのは楽しい作業です。ただ、この作業が楽しいのは、提示される情報の質が高い場合に限るような気がします。
16000枚のFlickrの写真を気楽に眺めるためのサービスを作ってみた
はじめに
Flickrには綺麗な写真がたくさんありますが、写真を探すには検索キーワードの入力や、それりのクリック操作が必要で、ものぐさな私には少々面倒でした。また、Flickrは日本から遠いので、画面切替に時間がかかります。そこで、画面切替とクリック操作のあまりいらない、気楽に写真を探すためのインターフェイスを作ってみました。
http://taggrid.appspot.com/flickr/popular.html
スクリーンショットの一部です。
アイデア
基本的なアイデアは次の3点です。
- 16000枚の写真を格子上に配置
- Google Maps風のAjaxインターフェイス
- 似ている写真を近くに配置
1. の16000枚の写真はPopular Tags on Flickr | Flickrを起点にしてFlickr APIを使って取得しました。
2. のAjaxインターフェイスは自分でゴリゴリ書きました。なかなか反応速度を高速にすることが出来なくて、満足いく出来になるまで3回ぐらい書き直しています。
3. を実現するためにタグを使っています。具体的には、タグが同じ写真は格子上でも近くになるように配置しています。例えば、「sea」タグが付いた写真をまとめて配置して、「sea」タグのそばには、「beach」「ocean」「island」といったタグの写真が配置するようにします。詳細なアルゴリズムはそのうち公開したいと思っています。
ホスティング
Google App Engineを試してみたかったので、サービスのホスティングにはGAEを使っています。PythonはともかくBigTable(Datastore)は癖が多い感じです。ただ、コマンド一発でアップロード完了はかなり便利です。
今後の展開
Popular Tags以外にもFlickrの最新写真に対しても同じインターフェイスを作ってみました。
こちらは週1程度で更新する予定です。
http://taggrid.appspot.com/flickr/recent.html
タグ付きデータを格子上に配置するアプリケーションは他にも色々とありそうです。個人的には、レシピの材料をタグにしていレシピの写真を表示させてみたかったのですが、API経由で利用できるレシピDBが見付かりませんでした。CookpadあたりがAPI公開してくれると嬉しいのですが。
後はtwitterユーザのfollow関係をタグとみなして表示するのも面白そうですが、レコード数とタグ数のどちらも多いので、まともにやるとアルゴリズムがうまく動作しなさそうでちょっとためらっています。
