@johtaniの日記 3rd

お久しぶりです。インフルエンザで一家全滅という最悪の状況に陥っていた我が家でした。 流行してるみたいなのでみなさんも気をつけてください。 さて、そんな中、OSSAJのミニセミナーでSolrについて簡単に話しをしてきました。 人生初Ustだったのですが、ぶっ倒れている中作成した資料だったためなんとも情けない発表だった気がします。（言い訳カッコ悪いですね。。。） 関係者の皆様、申し訳ございませんでした。

@yusukeyさんにサインをもらう目的で勉強会に参加してきました。前回もらいそびれたのでｗ 残念ながら、まだTwitter APIを触ってないし、利用したサービスも思いついてないんですが。。。 けど、勉強になりました。 といことで、いつものごとく、自分メモです。

いつものようにSolr勉強会に参加してきました。 皆勤賞を継続中です。（暇人というはなしも。。。） 今回は話しを聞きたいですねぇといったら、いやいや、話もしてくださいと言われてしまったので、 発表もしてきました。 発表資料はブログの最後に掲載してあります。

Hadoopソースコードリーディング第7回に参加しました。 いつものごとく、自分用のメモをとっていたので。 第6回（2010/12）には参加してたのですが、あれからそういえば、話が無いなぁと思っていたところに 再開するという話がTwitterに流れてきたので、即申し込みしました。 思い返せば、Hadoopに興味をもって少し触っているところで参加したのだったなぁと感慨深い思いを思い出しました。

今回は、触ろうと思って触れていないMongoDBの勉強会に行って来ました。 2週連続の渋谷で、さすがに今回は出口をすんなりでれました。 今回は初のGMOさんのビルへの潜入です。 ということで、いつものごとく自分のメモを残しておきます。

「第6回Solr勉強会」に参加しました。 なんだかんだと第6回で、今のところ皆勤賞です。 ということで、主に自分用ですが、メモなどとったので。 概要 日時 :2011/09/12 19:00 to 21:00 定員 :110 人 会場 :株式会社 ECナビ 1.「Lucene/Solr 3.2-3.4」 by ロンウイット 関口 宏司さん ※Solr2.9.4、3.1でデグレードし、Solr3.4で修正されたバグがあります。 インデックス中にPCがシャットダウンされた場合にインデックスが壊れてしまうものあり。 Solr3.1-3.3は使用しないようにとのこと。 ○index ・IndexWriter.addDocuments(docs) 複数ドキュメントの更新が可能になった。 ※検索で話をする親子関係のNestedQuery向けの登録にも利用する。 この登録では途中でフラッシュされないため、セグメントが分割されない特徴あり。 複数だけでなく、 ・TieredMergePolicy ※Lucene3.2/Solr3.3からデフォルトになった。 新しいインデックスのマージポリシー。（amebaの開発者ブログに説明があった。） インデックスの登録順が守られていたが、このマージ処理では保証がされなくなったので注意が必要。 ・update.chain update.processorがdeprecatedに。 update.chainというパラメータに変更 ○index(cont'd) ・TwoPhaseCommit ・UniqFieldsUpdateProcessor 重複した値を削除するための機能。 UIMAでの提案から取り込まれた ○search ・group=on 検索グルーピング機能を使えるパラメータ ・{!term} クエリパーサを通さないでTermQueryをかける機能。 ・structured explanation debug=onの算出根拠を XMLタグで構造化されたExplanationが取得可能に ・ReloadCacheRequestHandler 関口さん担当。ExternalFileField インデックス外（外部ファイル）を元にFunctionQueryの情報を利用可能にできるのだが、 このファイルのリロードが可能になる。 ・Carrot2　3.5.0 アップグレード。 デモあり。Carrot2のworkbenchとか　○search(cont'd) ・hl.phraseLimit parameter FastVectorHighlighterの高速化用パラメータ。 ・{!cache=false} キャッシュを利用しないためのローカルパラメータ。fqのローカルパラメータに利用可能。 検索セッション内でキャッシュへの処理（参照・登録）をしなくなる ・BlockJoinQuery NestedDocumentQueryの名前が変更された。 （Luceneで登録されたところまで。） ○schema ・KStemFilter PoterStemmerとは別のstemmer ・ReversePathHierarchyTokenizer パスの構造化インデックスの逆バージョン ・ommitPositions="true" 指定が可能になった。 ・version 1.4 スキーマのバージョンが新しくなった。 ○admin/tools ・action=MERGEINDEXES&srcCore=coreName コア名指定可能。 ・action=UNLOAD&deleteIndex=true UNLOAD時にインデックス削除 ・action=CREATE&property.name ※ぎゃーーー。打ち込み失敗。 ○ぎゃーーーー失敗。 ○技術者大募集中！！ Q&A Q：クラスタリングの日本語は大丈夫？入門には制限があると記載があったが。 A：analyzerが記載が簡単になってるかは不明 前処理をして別フィールドにメタデータ的にある程度単語で区切ったようなものを作成したほうがいい。 Q：グルーピングで、グルーピング後のファセット件数が取得可能か？ A：3.4ではグループ数で表示可能。 パラメータ指定で可能。 2.「Solr＠cookpad」 by ＠PENGUINANA_ さん ○COOKPADとは？ ・レシピ投稿サイト ・105万のユーザのレシピ ・30代女性の1/2が利用 ○レシピ検索 ・PC：1307万UU、1億回強/月 ・モバイルで利用が多く、スーパの店頭などで利用？ ・Androidもあるよ。 ○人気順検索（Solrですよ） ○自己紹介 ・＠PNGUINANA_ ・情報可視化＋検索が好き！！ yats、など ○Solrはどのように利用 ・レシピ検索 ・もしかして ○Tritonnから移行 同じ検索結果になるようにして徐々に移行 ○なぜ？ パフォーマンスが良い。 フィールド追加が簡単 レプリケーション->ファイルベース プロトタイピングが楽 ○Solr4 nightly（on Oracle JVM） ・マルチコア利用 ・Ruby on Railsから ○簡単な構成＋説明 ・バッチからSolrへの更新をしている。 ※Analyzerを利用せず、バッチ側で分かち書き、正規化、同義語展開を行っている。 Rubyで全部かけるほうが社内に展開しやすい。 ・バッチ終了後、可能ならoptimize ※検索速度がmax20%高速になる。 ・マスタ->スレーブレプリケーションはschema.xmlもレプリケート 新規フィールド追加などはレプリケーションだけで実行できて楽。 ・アプリはMySQLとSolrのSlaveにアクセス。 Solrにはidのみ。本文はMySQLから取得 インデックスサイズを小さくできる＝レプリケーション時間が短くなる オンメモリにできるため検索速度も向上 ○監視（munin） ・監視項目（コア別）： クエリ：QTime/QPS キャッシュ：hit/eviction キャッシュから漏れている数をみてキャッシュサイズを定期的に変更して無駄をなくす インデックス：サイズ/docの数 運用してから重要。開始当初は気にしてるが、そのうち気にならなくなるため。 レプリケーション：所要時間 スレーブ間でのズレを検知するため。 ※コアごとに監視することで、問題点を把握しやすくしている。 ○監視（nagios） ・監視項目（コア別）： サーバの基本的なヘルスチェック Solrが動いてるサーバのはなし。 レプリ：インデックスバージョンのチェック ズレが長いとメールが飛ぶ ○便利だった機能 ・DynamicField フィールドをあとから簡単に追加可能。 例：人気順のアルゴリズムの違うフィールド。検索用フィールド ・FacetQuery 絞り込み検索をクエリで記載可能。 現時点では社内向け検索機能で利用。 ※ファセットで簡単な解析もやってる。 例：鍋の季節ごとの登録件数。 ・HTTP経由で色々可能 検索の並列化 通常検索画面：3クエリを同時実行 あるプロトタイプ画面だと8クエリで実行したりしてる。 ・分散検索（Distributed Search） 簡単にsharding可能 思いクエリは４shardで投げる オーバヘッドが大きいので思いクエリにだけ利用しているらしい。 ○開発の流れ ・まずはステージングを更新 ・問題なければマスターも更新 例外： フィールド追加するだけだったら直接マスタへ 例：ファセット追加など。 ○パフォーマンスとか大丈夫？ 本番で複数のバージョンを持っており、 バグっていても自動フォールバックするらしい。 価値があったらパフォーマンス向上＋テスト追加 例：スニペット変更 ○気になっている機能 ・not to cache(SOLR-2429) ・SurroundQuery(Solr-2703) ・JOIN(SOLR-2272) SQLのJOINなイメージ ・BloomFilter(SOLR-1375) 単語が存在するかどうかのチェック ○Solr入門おすすめ ○おすすめ ・http://blog.sematext.com 月一で新機能が出てくる ・SolrのJIRA ・@otisg ○今後やりたいこと ・わかち書きの精度向上 ・検索セッションの分析 nDCG、クエリ分類、検索意図 ・デバイス対応 ・パーソナライズ Q&A Q：同義語は誰が集めている？ A：外部辞書を利用。０件キーワードから解析して取得 単語登録も一緒。 Q：プチトマトとトマトの違いはどうやってる？ A：上位、下位の概念で同義語を利用している。 本にあるよ。 Q：もしかしてはSolrの機能？ A：Solrではない。訂正候補の単語をSolrに検索してからチェックして表示する。 Q：人気順はどういった計算をしてるんですか？計算してから登録？By 大谷 A：１フィールドに外から入れている。 Q：RubyからSolrの利用方法は？独自？ライブラリ？By 大谷 A：Rsolrを利用しており、コネクション管理にだけ利用している。 あとは、ラッパーを独自で作成。 Q：4.0を利用している理由は？なかなかチャレンジャー。By関口 A：グループクエリを利用したかったため。 実際には重くて使えていない。 今は必要ないかもと思っている。年始のバージョンを利用。いつでも入れ替え可能。 マスタスレーブ構成のsolrのバージョンアップはサービスアウトしてから入れ替える。 3. 「Solrを用いた検索システムの構築」　by データセクション株式会社 高井さん いろいろな試行錯誤について ○データセクションについて 言語処理を元にデータの解析（Twitterとかブログとか）している会社。 ・昔は自社で検索サーバを構築していた ・Luceneを利用して検索サーバを構築するように変更。 ○構成（過去？） ・Lucene＋RMI 3.0から縮小で、4.0で廃止に ○SolrにするかLuceneにするか？ ・いろいろ機能があるからSolr使ってみるかｗ ○Solr導入は1.4.1から スペック マスタ： メモリ：16G Disk：2Tｘ12 スレーブ： 256GのSSDを利用 JavaVMが32bit ○ひと月分を1shardにして登録 ○検証＋手探り？ メモリが足りない。 Solrのキャッシュを全Offに。 BOBO SolrPluginってのを利用 compressオプションも利用。 各スレーブにキューを用意して1つだけしか処理しない。（なんでだ？？） ○結果 キャッシュはフィルタキャッシュのみ利用 ユーザが同じクエリを投げるのはほぼないので。 フィルタキャッシュのエントリのメモリ量の計算式（あとで資料が出てくるかなぁ。） ○問題点 ・レプリケーションでインデックスサイズの2倍の容量が必要になる。 ・レプリケーションの日時フォーマットのバグ（SOLR-1995）を踏んでしまった。 ・レプリケーション後にインデックスが消えない場合がある ○検討（1.4.1->3.2） うれしい要素 レプリケーションバグがfix 省メモリや範囲検索の高速化など　かなしい要素 compressが使えなく（しかも回答してからriindexしてくれる） ○検討 余計なインデックス消す nearinfinityが出しているlucene-compressionを利用 https://github.com/nearinfinity/lucene-compression ○残った問題 facet.rangeが使えないなど。 ○じゃあ集約サーバつくっちゃえ（すごいな。） facet書き換えコンポーネントなど。 ○シャードのインデックスサイズが下がった 130GiB->90GiB これはlucene-compressionの効果 ○ここまでの変更はプラグインにて対応（この一覧いいかも） ○感想 コンポーネント化されてて、簡単に追加機能が実装可能 用途次第であまりスペック高くなくても使える。 Q&A Q：Twitterのデータのクロール方法は？ A：HTMLをスクレイピングしている。publicなTLのみ。 Q：いきなりSolrに入れる？Solrの前処理は？ A：SolrJを利用して前処理済みのデータを登録している。 4. 「Anuenueの紹介と最近の進捗」 by @takahi_i さん（mixi） ○自己紹介 ・NAIST出身 ・ファストサーチ ・今はmixi ○mixiとは？ ○社内の緊急タスク ・内製検索エンジンをメンテナンスしやすいOSSにしたい！ ->Solrを選択 Anuenueも実装 ○Anuenueの作成理由は？ インデックス運用が面倒（検索（distributed search）はあるがインデックスは自前） クラスタ用のコマンドが提供されていない。 ○Anuenueが提供する機能 ・検索クラスタの簡単設定 ・クラスタ用コマンド ・もしかして機能 ○機能：Anuenueのクラスタ設定 Merger：クライアントからのクエリをMasterに分散 Master：インデックス作成側 Slave：検索用スレーブ。マスタからコピー ○クラスタの管理コマンド クラスタのコマンドを用意。 起動、コミット、登録など ○SolrCloud向けのAnuenueを検討中 branch-cloudにあります。 今後の予定 インスタンス追加削除を動的に実行できるようにしたい ○Hadoop Conferenceの宣伝ｗ Oluolu：Hadoop上で動くクエリログマイニングツール Likelike：LSHをHadoopで実装（Hadoop Conference 2011 Fallで発表） 5. LT 5.1　「solrとRの連携について」　by @yutakashino さん（BakFoo） Python本、Zope本を書いてます。 ○NHKの実証実験で利用？ ○TwitterストリームをSolrにストア facet.date ○Rでキーワード頻度グラフ Node.js、Redis、R、Solrを使ってる。しかもPython ○デモ キーワード＋日付でグラフが出てくる。 Rでプロット。 GoogleのチャートAPIを利用すると面白いことができる。 5.2　「 Apache ManifoldCF」　by 阿部さん(ロンウィット) ○Apache Incubator ○Manifold Connector Framework Solr ＜－ MCF ＜－ web＋non-web repositories すぐに利用可能。 ○概要 出力はSolr。 接続先はWeb、DB、CMS、などなどいろいろRepositoryConnectorというのがあります。 ○Crawler Agent クロールに関するJobの管理 接続先、スケジュールなど ○Windowsサーバのクロールもできる 社内のナレッジ共有などに使える。権限周りも簡単に対応可能。 JCIFS.jarによりWindowsの権限情報を取得 ○クロール設定画面もある デモ ○導入が簡単なのがおすすめ。 ○ManifoldCFの資料関連 http://www.manning.com/wright 懇親会についてはあとで記載します！！ ということで追記です。 懇親会でも色々と面白い話を聞けました。 @PENGUINANA_さんにはCOOKPADのCI関連の話を聞けました。 1日に数度リリースするという話もあるようでした。

かなり遅くなりましたが、第1回 データ構造と情報検索と言語処理勉強会 #DSIRNLPに参加しました。 帰ってから２日半ほど寝込んでしまい、更新が遅れました。。。 初の土曜日開催の勉強会でしたが、家族を説得してなんとか参加しました。 おかげで色々と面白そうなキーワードが拾えてよかったです。（拾っただけで理解するのはかなり時間がかかりそうですが。。。） ということで、前回同様、個人的にメモを取ったので。誤記などあるかもしれませんが、その時はコメントいただければと。 0.DSIRNLPについて ※ボランティアで受付してたので聞けず。 1.TRIEにトライ！～今日からはじめるTRIE入門～ @echizen_tm さん 資料：http://www.scribd.com/doc/58688141/Try-for-Trie 1.TRIEの説明 実装についてはあとでスライドをみればいいか。（※ボランティアで受付してたので前半聞けず） ・パトリシア木 ・Double Array ・LOUDS ・XBW 2.作ってみた その1　ベーシック Q.ノードのラベルどーする？ ・固定長（ラベル＝1文字） 定数時間でアクセス可能 ・可変長（ラベル＝任意文字列） Patricia木に拡張可能 A.拡張性を考えて可変長に！ 3.LOUDSとは？ 概要 Jacobsonが提案　Level-Order Unary Degree Sequenceの略（いつからLOUDSになったのか不明） 構築済みTRIEからLOUDSを構築 作業領域がO(NlogN)からO(N)に ・ノードに幅優先で順番（Level-Order）をつける ・子ノードの数を付ける。Unary符号で実装 作ってみた ・UnaryよりVerticalCodeのほうがよさそう http://d.hatena.ne.jp/echizen_tm/20100531/1275323074 ・dag_vectorを使ってもいいかもよ？ 4.QA Q.可変長を配列にすればいいんじゃね？ A.単純にやると効率悪そう？ ※LOUDSをlucene-gosenに適用するとなんか嬉しいことあるかな？ 現状はDouble-Arrayだけど。 2. ランキング学習ことはじめ（Solr系に利用できそうな予感。。。ごごご。。。むずかしい。。。） @sleepy_yoshi さん NTTのSuharaさん「話がうまい」 数原　良彦 自己紹介 情報検索、ランキング学習をやってる。 三浦半島在住 ねらい ランキング学習の認知度を高める、ざっくり伝える。　ごめんなさい　「実装」についてをわすれてた。 ・ランキング学習とは？ Learning to rank preference learningとは違う 教師あり機械学習で検索ランキングに適用 ・歴史 従来は単一ランキング クエリ・文書関連度（TF-IDF、BM25） 文書の重要度（PageRank、HITS、SALSAなど） 近代的なランキングの実装方法 上記データを利用して関数を適用する。 ・何を正解とするのか？ 適合性評価の作成方法 評価点数を多段階で点数化 ランキング評価方法 ランキングを正解データと比較 NDCG（Normalized Discounted Cumulative Gain）　※分類問題におけるモデルの生成 Training Data＋学習アルゴリズム＝＞モデル ランキング学習の訓練データ 素性や評価はクエリごとに変わってくるTraining data（ここが違う） ここまでのまとめ 正解データは適合度至上主義！ ランキング学習手法 ３つのアプローチ 教師あり機械学習（識別学習）≒ どのような目的関数/損失関数を どのように最適化するのか アプローチ 1.Pointwise手法 単一のデータに対して損失関数を設定 2.Pairwise手法 同一クエリのペアに対して損失関数を設定 3.Listwise手法 同一クエリのリストに対して損失関数を設定 Pointwise：あまりつかえない。 例：二値分類（適合＋１不適合－１）で学習 補足：Perceptron 例：PRank しきい値と重み両方修正する。 Pairwise：Pointwiseよりいいらしい 文書ペアで損失を設定 MQ2007、MQ2008データセットの結果 Pairwise手法とListwise手法を比較しても そんなに悪くないらしい IR-SVMってので偏りなどを排除できて、精度向上になるよ NLP2011でPARankっての発表したよ（手前味噌） QA Q.じゃんけんみたいに循環しない？（nokuno） A.半順序のデータだと起きるが、検索の場合は全順序なので大丈夫だよ Listwise：Pairwiseよりいいらしい ListNetってのあり。 AdaRank 検索評価指標を直接最適化するブースティング手法 性能はいまいち？実装は簡単 その他の話題 Click-through logs Query-dependent ranking Feature selection Transfer learning/Domain adaptation Diversity/Novelty 公開Dataset LETOR3.0/4.0 Dataset MSLR-WEB Datasetなど 実装 RankingSVM Stoch…. Learning to Rank教科書 英語の資料が今年複数出たみたい まとめ 近代的な検索エンジンは多数のランキング素性を利用 評価データを用いてランキング素性の最適な重み付けを求める方法 。。。 機械学習手法は論文≒実装 なので、ソースコード見るほうが重要（論文にないノウハウがあるよ） 3.snappy調べてみた @machy　町永圭吾（赤いポータルサイト） TopCoderなどで活躍中？ ・snappyは圧縮/伸張ライブラリ zlibよりサイズが大きいけど一桁はやいですぞ。 ・インストールなど google－gflagsってのがないと動作しないよ。 ・比較してみた（zlib） 一桁は言い過ぎだけど、はやかった。 ・比較してみた（lzo） Hadoopで利用されているlzo はやかった。 ・仕組みは？ zlib　辞書式符号化＋ハフマン符号化＝出力 snappy　辞書式符号化＋リテラル＝出力 ・辞書式符号化は？ 前に出てきたデータで同じ文字列の部分について端折る ・ハフマン符号化 よく出てくる記号を短い符号で置き換えることで圧縮する。 ・snappyの符号化 基本バイト単位での処理にすることで、高速化してるみたい。 ・snappyの辞書参照元の探し方 ハッシュテーブル利用してマッチする位置を検索 4byte窓でハッシュ値を計算してハッシュテーブルを更新 ・圧縮しにくいデータ（同じ単語が出てこないパターン）について 圧縮をあきらめ始める（32回同じのが見つからないと窓の移動幅が1つずつ大きくなる） 16KB（フラグメント内）での比較回数が1008回に抑えられる。 ・特徴 ハッシュがしょうと移したらあるはずのマッチが見つからないこともある。 メモリ消費量を抑えるためのハッシュのサイズ？ 最悪ケースのサイズを予め確保してから処理するため、メモリの再確保が起きないのではやいぞ。 4.類似文字列検索してますか？ @overlast さん　Yな会社 1.曖昧な情報を処理する能力 曖昧な情報を解決しようとする能力が高い。 例：お笑い芸人の芸がサンプルｗ 画像検索は曖昧クエリに答える例。。。 スターバックス、スタバ、SUTABA スータバでも画像が出てきた。->女子高生とかが「スータバ」で画像をアップしてたりするから。 文字列を使った検索は現代のインフラになってるよね。 例：iタウンページ タイトルとかに「スターバックスコーヒー」って書いてないとだめ。？ 「スタバ」800件くらい　->　正規化で「ー」消してるんじゃないの？ 「スータバックスコーヒー」0件　ちがうな。シノニム辞書登録してるな。 曖昧なクエリ（キーワード）から検索できないかなぁ？ 曖昧情報の処理は文字列処理にこそ必要 なんでヒットしたかがわかるのが正解　なんでヒットしたかわからないけど、ちゃんと出てきたから正解！ 2.ゼロ件ヒット問題（ゼロマッチ） ピクシブ百科事典 「ピングドラム」だと17件 「ピンクドラム」だと0件　しかも真っ白！！ 使いにくいよね。けど、一般的な検索システムの問題だよね。 Googleだと出てくる「ピンクドラム」の結果の最初にはピングドラムが出てくる。 ->リンクがはられているから出てきた？みんなの間違いで助けられてる 食べログ 「俺のハンバーグ」 「俺はハンバーグ」で検索したら。。。「俺はハンバーグで連れは。。。」がヒット->しらねーよｗ まとめ ゼロ件ヒットは機会損失！！ 3.曖昧な文字列で正しい文字列を探す方法 正しい文字列って？ 1.表記誤りがない 2.心の底で求めている ※異表記同義、同表記異義、異言語表記（日本語の情報を英語で検索）などもある 正しさはユーザによって変わる。 正しい文字列をさがす手法 クエリ表記の正誤という軸 誤の場合表記をヒントに似た文字列を検索してみる。 探したい対象が正確か曖昧か 表記意外がヒントで同じ対象に到達できる？ どんな情報を手がかりにする？ 編集距離（レーベンシュタイン） 検索ログ 4.Apporoの紹介 チョコ？いや、ロケット？いや、Approximate … http://code.google.com/p/apporo/ 中小規模だと使えそう SimString 今後 よみかな、ローマ字表記に基づく類似文字列検索＋高速化の予定 技術概要 Suffix Array N-gram Searchベースの近似文字列照合 Bit Parallel Matchingによる編集距離計算 5.検索と言語と文化（仮） @mizuno_takaaki さん 放送禁止のためメモなし。 7.自然言語処理におけるargmax操作 @hitoshi_ni さん ※順番変更 ・近似解法 その１　全探索 いや、無理でしょ、計算が。 その２　貪欲法 最適解が出るかは不明。 その３　ビームサーチ 上位kこの仮説を保持しながら幅優先探索 ・動的計画法 すでに最大値がわかっていて、ゴールから眺めてみる。 逆からたどるとルートがわかるんじゃないか。 マルコフ性につけ込むことで、わかるんじゃないか。 計算量：品詞数の2乗 （品詞数の2乗）＊形態素数 DPの実装 Viterbiかなぁ？ ・整数計画法（線形->整数） 自然言語処理としては整数計画法でだいたいOK。 アルゴリズム ・手元の解空間中から許容解を得る ・分枝してそこから最大値を求める 最大値＞許容解ならそちらを探索。 プログラム実装する？ すごく大変じゃないけど簡単でもないね。 問題の弱点がわかってるなら実装してもいいよね。 整数計画法の場合lp_solveなどのフリーのソフトで解くのがいいよ。エクセルでも解けるよ ILP（整数計画法？） 問題の切り分けに使える。 まとめ ILPで解けたら、いろいろ自分で考えると面白いよ。 その他のバズワード 参考資料 組み合わせ最適化＝1万円超 アリ本 6.ソーシャルグラフ分析(導入編) @kimuras さん　mixiの木村さん ・グラフ探索部分はまた今度。 ・テキストマイニングや検索エンジンまわりやってる。 ・ノードが数1千万、エッジが数億のオーダー ・分散技術の発展によるアルゴリズムの多様化 これまで RDBからDumpしたデータをKVSに入れて頑張ってた。 Dump部分でデータ構造を毎回構築 問題点 変更による再実装、メンテナンスコスト、 これから graphDBに取組中。マイニングに最適な感じ graphDBの実装 OrientDB、Neo4jとか Neo4jって ACIDトランザクション可能 EmbeddedGraphDatabaseだとAGPLｖ３だから気をつけてね。 luceneで全文検索インデックスつくってるみたい。 Gremlinってのがquery言語を汎化してるらし。 とあるSNSのデータを使ってみたよ。 メモリ64G、CPUは1コアしか使えなかったよ。 ノード：15million、枝：600million