研究開発グループの takahi-i です。 先日名前だけご紹介したAnuenue というツールをご紹介させていただきます。Anuenue は Apache Solr のラッパーであり、検索クラスタの構築と運用を容易にする目的で制作されました。 本稿では始めに Apache Solr を選択した理由について述べ、その後、このツールを開発した背景とその目的をご紹介させていただきます。後半では実際に Anuenue を用いて検索クラスタを立ち上げます。 なぜ Apache Solr を採用したのか 昨年の秋、弊社の検索エンジンを置き換えるという計画が社内で策定され、ベースとなる検索エンジンの選定のために多くの OSS 検索エンジンを比較検討しました。このとき重視したのは一台の検索パフォーマンスと同時に、保守の容易さと、開発コミュニティの規模です。 検索エンジンの保守性に関して特に重要と考えたの

GW 中の長距離移動のために体調が優れない takahi-i です. 今回は巨大なデータをマイニングする一つの技術として LSH (Localtiy Sensitive Hashing) を紹介させていただきます. LSH とは LSH は大量なデータから類似度が高いインスタンスのペアを高速に抽出してくれるアルゴリズムです. ここでインスタンスはデータ集合の一つの要素を表します. たとえば扱うデータが E-コマースサイトの購買ログであれば, インスタンスは各ユーザですし, 画像データ集合であれば, インスタンスは個々の画像データです. LSH の詳しい解説については以下のサイトがあります. Wikipedia のエントリ LSH に関する論文がまとめられているページ 本稿ではE-コマースサイトの購買履歴データを基に LSH の機能について述べてゆきます. 以下のような E-コマースサイトの

はじめに ３月８日(月)に「言語処理学会第１６回年次大会」が開催されます！言語処理学会年次大会って何？という方もいらっしゃると思うので簡単に解説いたしますと，１年に１回主に自然言語処理学に関するたくさんの発表や講義が行われるカンファレンスです． 自然言語処理学というとなんとくむずかしそう．．．ってイメージがあるかもしれません．しかし，かならずしも専門的な知識がなくても楽しめる内容がたくさんあるのです！例えば，文書検索やレコメンデーション，テキストマイニングなど最近話題の技術は自然言語処理学の研究成果が多く使われているのです．また，最近では多くのウェブアプリケーションなどでも自然言語処理学の研究成果が使われています．今大会でもこれら加え，とても興味深い研究成果が多く発表されます！ 以下に今回の開催内容を書きましたが，これだけのボリュームがあっても，なんと今大会は参加料が無料なのです！ぜひこれ

都会よりも田舎が好きなfujisawaです。Bayesian Setsというアルゴリズムを使って、関連する文書を高速・高精度に検索できるシステムを作成しましたので、そのご紹介をさせていただきます。 Bayesian Setsとは Bayesian Setsはいくつかアイテムを入力すると、それを補完するようなアイテムを返してくれるアルゴリズムです。原著論文の先頭に"Inspired by Google Sets"と書かれているように、Google Setsを参考にして作成されています。実際にどのような出力が得られるか、Google Setsに以下の表のクエリを検索して試してみますと、 クエリ 出力 apple, banana chocolate, strawberry, vanilla, cherry, ... apple, macintosh software, windows, mac,

飲み屋に行くとかなりの確率で荷物を忘れて帰るmikioです。さて、今回はここ2ヶ月ほどで急ピッチで開発した軽量データベースライブラリ「Kyoto Cabinet」について紹介します。 開発の動機 以前から軽量データベースライブラリとしてご好評いただいているTokyo Cabinetですが、DBMとして必要十分な機能と性能を備えていてなかなか良いものだと自負しております。ただ、開発を進める中でいくつか不満な点があったのも事実です。端的に言えば、全てC言語で記述して、標準ライブラリ（とzlib/bzip2）以外の機能は全て自作しているので、最適化がしやすい反面、メンテナンスの難易度が高くなってしまっているというのが不満です。 そこで、多少性能が悪くなってもいいから、私自身としてお気楽に開発およびメンテナンスができて、移植性も高いような実装を作ってみようと思い立ったのが昨年10月頃。様々な検討を

先月ハワイに行ってきてオルオルな （ハワイ語で '楽しい' という意味） 気分の takahi-i です。最近ログデータの有効活用が話題になっていますが、検索エンジンが出力する検索クエリログを使用してどんなことができるのかについて紹介させていただきます。 検索クエリログ 検索クエリログ (以下検索ログ) は検索エンジンを使用するユーザから発行された検索の履歴を保存したファイルです。検索ログのフォーマットは使用する検索エンジンや Web サーバによって異なります。さらにまた検索ログが含む情報にも差異があることが考えられますが、本稿では検索ログは解析を行う上で重要な三つの要素を含むと仮定します。三つの要素とはユーザ ID （もしくは IP アドレス）、クエリ文、そしてクエリが検索エンジンに処理された時間です。以下検索ログの一例を載せます。 ユーザID クエリ文 クエリ発行時 438904 Su

開発部・システム運用グループの長野です。9月10日・11日に東工大大岡山キャンパスで開催されたPerlのカンファレンス、YAPC::Asia 2009に参加してきました。 昨年は2つのセッションをやらせて頂きましたが、今年は1つだけ発表をしましたので、資料を公開します 大規模画像配信とPerl SlideShareで公開しています。 大規模画像配信とPerl View more documents from kazeburo. 一部アニメーションを利用していますので、PowerPointもあわせて参照してください。 mixiの画像配信については、このブログや技術評論社様の雑誌等を通して何度か紹介していますが、今回は携帯向けの画像配信、特に画像の動的変換について取り上げました。 画像を扱うライブラリはいくつも種類があり、変換速度や変換後の画像に違いがあります、今回の発表ではその比較もしていま

相対性理論のボーカルが頭から離れないmikioです。熱いわっふるの声に応えて今回はTokyo Cabinetのテーブルデータベースにおける検索機能の実装について語ってみたいと思います。とても長いのですが、最後まで読んだあかつきには、自分でも全文検索エンジンを作れると思っていただければ嬉しいです。 デモ モチベーションをあげていただくために、100行のソースコードで検索UIのデモを作ってみました。Java 6の日本語文書を対象としているので、「stringbuffer」とか「コンパイル」とか「倍精度浮動小数」とかそれっぽい用語で検索してみてください。 インデックスがちゃんとできていれば、たった100行で某検索エンジン風味の検索機能をあなたのデータを対象にして動かすことができます。ソースコードはこちら（テンプレートはこちら）です。 でも、今回はUIの話ではないのです。ものすごく地味に、全文検索

梅雨。部屋干しした洗濯物による異臭騒ぎに苦しむmikioです。今回は、Tokyo Cabinetのテーブルデータベースで超お手軽に全文検索をする方法について説明します。 使い方 テーブルデータベースについてまずおさらいしておきましょう。PerlやRubyのハッシュのようにコラム名とその値を関連づけた構造を、主キーを識別子として保存するデータベースです。例えばRubyからデータを保存するに以下のように行います。データベースであることをほとんど意識させないというのが素敵ポイントです。APIはCでもPerlでもRubyでもほとんど同じなので、言語にかかわらず同じようにレコードを操作できます。 require 'tokyocabinet' include TokyoCabinet # データベースを開く tdb = TDB::new tdb.open("casket", TDB::OWRITER

逆転検事を先日クリアして、久しぶりに逆転裁判1〜3をやり直そうか迷い中のfujisawaです。シンプルなデータクラスタリングツールを作成しましたので、そのご紹介をさせていただきます。 クラスタリングとは クラスタリングとは、対象のデータ集合中で似ているもの同士をまとめて、いくつかのグループにデータ集合を分割することです。データマイニングや統計分析などでよく利用され、データ集合の傾向を調べたいときなどに役に立ちます。 例えば下図の例ですと、当初はデータがゴチャゴチャと混ざっていてよく分からなかったのですが、クラスタリングすることで、実際は3つのグループのデータのみから構成されていることが分かります。 様々なクラスタリング手法がこれまでに提案されていますが、有名なところではK-means法などが挙げられます。ここでは詳細については触れませんが、クラスタリングについてより詳しく知りたい方は以下の

息子が3ヶ月になり、日に日に出来る事が増えていくのを見て、親馬鹿度合いがますます増えているかぜぶろです。 さて、もう手に取って読んで頂いた方も多くいらっしゃると思いますが、技術評論社様からでているWEB+DB PRESSのVol.50から「大規模Webサービスの裏側――inside mixi's backend」と題して、mixiのシステム運用についての連載をスタートしました！ mixiは2008年12月末で、ユーザー数1,630万人、月間ページビューはPCとモバイルを合わせ143億PVとなり、日本でも有数の規模を誇るサイトに成長しています。 このブロクでも何度か紹介してきていますが、mixiの成長とともに大規模・複雑化しているmixiのサービスを支えるシステムの大半は、サービス開始当初から現在までオープンソースのソフトウェアで構築され、運用が行なわれてきています。WEB+DB PRESS

サボっていた早朝ジョギング＠駒沢公園を再開して2週間たち、やっと抜かれる数より抜く数の方が増えてきたmikioです。今回は、PerlやRubyのハッシュの代用としてTokyo Cabinetを使うことでメモリ使用量を激減させられることを説明します。 抽象データベースAPI Tokyo Cabinetには抽象データベースという機構があり、先日、そのPerlとRubyのバインディングをリリースしました。それを使うと、各種言語のハッシュとほぼ同じような共通したインターフェイスで、以下のデータ構造を利用することができます。 オンメモリハッシュ：各種言語に標準のハッシュと同じく、メモリ上でkey/valueの関係を表現する。 オンメモリツリー：メモリ上の二分探索木としてkey/valueの関係を表現する。 ファイルハッシュ：いわゆるDBMとして、ファイル上でkey/valueの関係を表現する。 ファ

先日、隅田川の屋形船で花見と洒落込んだのですが、その日はまだ一分咲きも行ってなくて悲しい思いをしたmikioです。今回はTokyo Tyrant（TT）に格納したデータを対象としてMapReduceのモデルに基づく計算をする方法について述べます。 MapReduceとは Googleが使っているという分散処理の計算モデルおよびその実装のことだそうですが、詳しいことはググってください。Googleによる出自の論文やApacheプロジェクトによるHadoopなどのオープンソース実装にあたるのもよいでしょう（私は両者とも詳しく見ていませんが）。 今回の趣旨は、CouchDBがMapReduceと称してJavaScriptで実現しているデータ集計方法をTTとTCとLuaでやってみようじゃないかということです。簡単に言えば、以下の処理を実装します。 ユーザから計算開始が指示されると、TTは、DB内の

はじめまして！08年度新卒エンジニアの「きょろ」こと井上恭輔と申します。ミクシィではコミュニケーション開発チームというところで、mixi上の色々なコミュニケーションサービスの開発を担当しています。 就職で東京に出てきて早10ヶ月、最初は周囲の歩く速度に付いて行けなくて悩んでいましたが、今では新宿駅を迷わず歩けるまでに成長しました。本日は慣れたついでに、そろろそエンジニアブログにも仲間入りしたいなと思いましたので、記事の初投稿に挑戦してみようと思います。 曰く「ハードボイルドな技術ネタ」の多い当ブログですが、今回は頭を使わずに読める、文字通り「コーヒーブレイク」的な記事をお届けできればと思います。駄文ではありますが、お付き合い頂ければ幸いです。 エンジニアのガソリン「コーヒー」 みなさんコーヒーはお好きですか？私はコーヒーが大好きで、1日にかなりの量のカフェインを摂取します。朝はブラックコー

ついに発売されたスト4のコンシューマ機版をやりたくてしょうがないけど筐体を買ってもらえないので、駅前のゲーム屋のディスプレー前で垂涎するばかりのmikioです。今回は連載の最終回で、各種スクリプト言語を使ってお手軽にテーブルデータベースを操作する方法について説明します。 TokyoCabinet::TDB まずは、TCのPerlバインディングとRubyバインディングの最新版を入手してください。それぞれテーブルデータベースを扱うための TokyoCabinet::TDB というクラスが加わっています。以下のようなIDLによるガイドラインに準拠したインターフェイスが提供されますので、使い方は言語にかかわらず同じようになるはずです。 module TokyoCabinet { interface TDB { boolean open(in string path, in long omode);

コアライブラリを一生懸命書くとユーティリティやバインディングなどの周辺機能がおろそかになり、逆も然りで、工数割り当てのジレンマが歯がゆいmikioです。今回は余談として、Tokyo Cabinetのテーブルデータベース（TCTDB）を作る途中で思いついた更新機能と性能検証について述べます。 アトミックな更新 再び TCTDBで好評だったっぽいアトミックな更新機能をその他のデータベースでも実装してみました。例えばハッシュデータベース（TCHDB）では以下の関数が提供されます。 typedef void *(*TCPDPROC)(const void *vbuf, int vsiz, int *sp, void *op); bool tchdbputproc(TCHDB *hdb, const void *kbuf, int ksiz, const char *vbuf, int vsiz,

最近、忙しさを理由に英会話レッスンをサボりがちになってよろしくないなと猛省するmikioです。今回は、Tokyo CabinetのテーブルデータベースをTokyo Tyrantを使ってデータベースサーバとして利用する方法について述べます。 とりあえず使ってみる Tokyo CabinetとTokyo Tyrantの最新版（1.4.4と1.1.12）がリリースされていますので、インストールしておいてください。またも社員名簿を作ってみましょう。まずは、TTのサーバを実行します。データベースファイルの接尾辞には「.tct」を指定して、テーブルデータベースファイルと接続します。 ttserver casket.tct 別の端末でクライアントを操作して、"put" コマンドで社員を登録しましょう。「-sep」は、コラムのキーと値を区切る文字を指定するオプションです。"|" 以外でも任意の区切り文字を

インフルエンザで休んだ影響で仕事が鬼のように溜まって消化不良のmikioです（こんな記事を書いている場合じゃない）。さて今回は、Tokyo Cabinetでリレーショナル風データベースを実現したテーブルデータベース（TCTDB）の実装について説明します。 SQLiteとの違いは？ SQLiteはアプリケーション組み込み型のSQL対応リレーショナルデータベースのライブラリです。TCのテーブルデータベースよりもはるかに高機能で、それでいて性能も大変優れています。いわゆるデスクトップアプリケーションに組み込むデータベースをお探しであれば、TCなんかではなく、断然SQLiteがおすすめです。 一方で、TCなどのDBMは、より単純なデータ操作をより高速に実行できるように設計および実装されています。典型的なユースケースとして、大規模Webサイトのアカウント管理や、データマイニングに伴う集計操作が挙げら

正月早々インフルエンザにかかって寝込んだmikioです。電車に乗る時や繁華街などに出る時はマスク着用が必須ですね。さて今回は、Tokyo Cabinetで実装したテーブル方式のデータベースについて紹介します。意外にどうして強力な機能なので、このネタは連載することを予告します。 テーブルデータベースとは 簡単に言えば、リレーショナルデータベースのテーブルのように、複数の列からなるレコードを格納できるデータベースです。SQLや表結合などの複雑な機能はサポートしませんが、そのぶん高速に動作します。つまり、DBMの速度で動くリレーショナル風データベースです（厳密にはリレーショナルデータベースではありません）。 TCの基本となるハッシュデータベースは、単純なkey/value型のデータベースであり、つまりキーにも値にもスカラ（数値や文字列などの特に構造を持たない単一の値）しか格納することはできません