Bing検索の裏側―BitFunnelのアルゴリズム - Hatena Developer Blog

はてなアプリケーションエンジニアの id:takuya-a です。 この記事では、Microsoft の検索エンジン Bing で採用された BitFunnel アルゴリズムを紹介します。 昨年のエンジニアアドベントカレンダーでは、文字列検索のアルゴリズム全般について紹介しました（文字列アルゴリズムの学びかた - Hatena Developer Blog）。今年はそのなかでも、インデックス（索引）を使った全文検索アルゴリズムについてのお話になります。 この記事の前半は全文検索の入門にもなっていますので、検索技術になじみがない方にも楽しんでいただけるのではないでしょうか。 逆に、「そんなのもう知ってるよ！」という方は、本題である「BitFunnel アルゴリズムの詳細」から目を通していただければと思います。 この記事は、はてなエンジニア Advent Calendar 2017の21日目の

[takuya-a]

検索も楽しいよ！って伝えたくて書きました。これをきっかけに情報検索に興味をもってくれる方が増えたらうれしいです。

[roshi]

ブルームフィルタやHyperLogLogなど、確率を伴うアルゴリズムって不思議な魅力ある。

[toya]

「この記事の前半は全文検索の入門にもなっていますので、検索技術になじみがない方にも楽しんでいただけるのではないでしょうか」

[daiksy]

今日中に読み切れる気がしない超大作

[y_uuki]

全文検索の話。超大作で読みきれない

[nobuoka]

わかりやすい〜。 概念的には転置インデックスっぽいけど、ハッシュ関数により情報量が減らされてるのと分散処理しやすくなってるのが特徴なのかなー、と思った。 (全然違うかもしれない)

[natroun]

これすごく面白かったな。読んでる間は「意外と単純なんだなー」とか思えちゃうところもすごい。

[chezou]

途中までは、類似文書の表現とかのアレだよねと思ってたら、どんどん面白くなっていた

[tagomoris]

実際に運用するときに文書シグネチャのサイズのチューンが大変そうだな。リサイズにコストかかるし。運用にひと工夫必要……なのは、大規模ならどれでもそうか。

[cider_kondo]

面白かったけど、検索技術に疎い自分的には前半だけで十分満足して『BitFunnel アルゴリズムの詳細』にたどり着いたところで「続きは今は読まなくてもいいか」とか思ってしまった。申し訳ない

[naari_3]

ゆっくり読もう

[igrep]

くそ、肝心のBit-Slicedよりあとの話がイマイチ分からなかった。動画も一緒に見直そう。

[Windymelt]

“small crazy dog”

[nilab]

Bing検索の裏側―BitFunnelのアルゴリズム - Hatena Developer Blog

[murashit]

この手の誤差（と言えばいいのか）のあるアルゴリズムってわりとおもしろいな

[efcl]

誤検出 (false positive) はするが取りこぼし (false negative) はしない検索アルゴリズムの最適化。 転置インデックスとシグネチャファイル方式

[adsty]

検索エンジンBingで採用されたBitFunnelアルゴリズムを紹介。

[dekokun]

面白い

[t_f_m]

あとで

[lyiase]

ハッシュ関数を掛けた値を合成し、転置インデックスを使うことができ、更にはそれを圧縮できると。検索では「ある程度の絞り込み」ができるのがとても重要だから、この方法は確かに非常に早そうだ。

[fcicq]

bloom filter per word but using or & other techniques. "Higher Rank Rows" is interesting. collapse dense hash / simhash -> wavelet?

[tumo300-500]

おもろい

[castaneai]

全文検索のアルゴリズム的な話、とても長く詳しい解説

[yoshikidz]

“スコアリングの効率 ”かー。文書リストを全て渡さなくていい方法が正解に近い効率なのかな。先にスコアとランクあれば、切り捨てて丸め込めたりはできそうやな。

[sugyan]

面白いし解説がすごく丁寧で良い

[kabuquery]

良記事

[send]

えーシグネチャ法じゃどうやっても厳しくない？と思って読みはじめたらまんまと面白かった

[otihateten3510]

検索に詳しいアプリケーションエンジニア、強キャラ感ある

[Makots]

ボリューム、やばい

[nikkatsu]

bingは地図がびっくりするほどウンコなので使わない。

[airj12]

あとで続き読む(と思う)

[kitaj]

すげー面白い

[ntstn]

あとで読む

[FutureIsWhatWeAre]

無粋を承知で書くとガンダムのファンネルから名前をとったのではなく語源が共通なだけ (Funnel=漏斗)

[MonMonMon]

全文検索アルゴリズムの説明

[zensoku00]

すごい(小並感

[aki03]

検索アルゴリズム入門の大作！