転置インデックスの圧縮技法
転置インデックスは、検索エンジンの実装において、中心的な役割を果たすデータ構造である。 転置インデックスのデータ構造とアルゴリズムは、クエリ処理アルゴリズムとともに、検索エンジンの性能に直結する。とくに大規模な検索エンジンにおいては、キャッシュ効率を高めてクエリ処理を高速化するために、転置インデックスの圧縮は必要不可欠となっている。 この記事では、転置インデックス、とくにポスティングリストの圧縮について、近年の手法を簡単にまとめる。 目次 転置インデックスの基本 転置インデックスのデータ構造と特性 転置インデックスのアクセスパターン 近年のインデックス圧縮技法 Variable-Byte Family VByte Varint-GB Varint-G8IU Masked-VByte Stream-VByte Opt-VByte Simple Family Simple9 Simple16
Introducing Natural Language Search for Podcast Episodes - Spotify Engineering
March 17, 2022 Published by Alexandre Tamborrino, Machine Learning Engineer Beyond term-based Search Until recently, Search at Spotify relied mostly on term matching. For example, if you type the query “electric cars climate impact”, Elasticsearch will return search results that contain everything that has each of those query words in its indexed metadata (like in the title of a podcast episode).
英語論文執筆のために arXiv からの例文検索サービスを作った話
arXiv の論文から例文を検索する Hyper Collocation というサービスを公開しました． 以下はあまり整理されていない製作の記録です． 英語論文執筆用の例文検索サービス 英語での論文執筆の際に，専門用語を含む例文や言い回しのパターンを知りたいことが多々あります．有用なサービスとしては ライフサイエンス辞書のコーパス検索 Springer Exemplar (2018/2/1頃に終了) がありますが， データがライフサイエンス系の論文に限られている（ライフサイエンス辞書） ソートの基準が頻度順ではないため典型的な例文が上位にこない ストップワードに近い頻出語を検索した際の 検索が重い（Springer Exemplar） 表示可能な検索結果が偏る（ライフサイエンス辞書） という不満点があったので，並行して個人的な資料から検索を行うプログラムを作って使っていました． しかし，個
AIに「Clova、今日の天気は？」を理解させることの面白さ - LINE ENGINEERING
LINEのData Labsに所属している佐藤敏紀（@overlast）です。この記事はLINE Advent Calendar 2017の23日目の記事です。 この記事では、スマートスピーカーで対処を求められる自然文クエリの言い換えがどれほど多様であるかを示し、「スマートスピーカーを実現するための自然言語処理の楽しさ」をお伝えしたいと思います。 はじめに みなさんはスマートスピーカーを家に置いていますか？ 私は自宅のリビングに弊社が販売しているClova FriendsとClova WAVEを置いていますし、それ以外に、Google HomeとAmazon Echo Dotも設置しています。 ちょっと多すぎでしょうか (;^_^A これらのスマートスピーカーは、主に人間の言葉を聞いてその内容に基づいた動作をします。たとえばClova Friendsに「Clova！小町さんに電話して（クロ
The open big data serving engine：VESPAの紹介
ヤフー株式会社は、2023年10月1日にLINEヤフー株式会社になりました。LINEヤフー株式会社の新しいブログはこちらです。LINEヤフー Tech Blog はじめに こんにちは。メディアカンパニープラットフォーム開発本部サーチテクノロジー部の朴と申します。 2017年9月にOath（Verizon社で、Yahoo, AOL等50以上のテクノロジーとメディアを運営する子会社）からVESPAがOSSとして公開されました。VESPAは検索エンジンを代表とした大規模なデータをハイトラフィック状況下で高速に配信できるビッグデータサービングエンジンです。実はYahoo! JAPANでもメディア、コマース、広告を中心とした多くの検索システムでVESPAを長年採用しており、この度Apache License 2.0のOSSとして公開されました。 Yahoo! JAPANでの利用事例 VESPAを利用
形態素解析とNgramを併用したハイブリッド検索をSolrで実現する方法 - ZOZO TECH BLOG
こんにちは、バックエンドエンジニアの塩崎です。 今まではiQONの全文検索用のインデックスには形態素解析だけを用いていましたが、先日Ngramも併用することで検索を改善しました。 その結果、検索結果のヒット数が向上し、なおかつ検索ノイズの増加を軽微なものに抑えることができました。 この記事では、Ngramを併用することのメリット、およびそれをApache Solrで利用する方法について紹介します。 欲しい情報が見つからないとは そもそも、「検索したけど欲しい情報が見つからない状態」とはどのような状態でしょうか？ ここではその状態を以下の2つの状態に分解して考えてみます。 欲しい情報の数が少ない 1つ目の状態は「欲しい情報が検索結果中に少ない」状態です。 例えば、旅行情報サイトで「東京」と検索した時にDBの中には数千件のデータがあるのに検索結果数がわずか数件しかないような状態です。 欲しくな
多腕バンディットによる表示コンテンツの最適化 - クックパッド開発者ブログ
こんにちは。技術部検索グループの原島です。 上の画像は、スマートフォン（ブラウザ版）で見たクックパッドの検索結果ページです。レシピだけでなく、ニュースも表示されていますね。献立や掲示板のスレッドなどが表示されることもあります。 クックパッドでは、検索結果ページに表示するコンテンツをクエリなどに応じて最適化しています。最適化は、膨大なログデータと最新の機械学習を用いることで、実現しています。このエントリでは、クックパッドにおけるコンテンツ最適化の裏側を紹介します。 最適化の背景 スマートフォンの普及に伴って、ユーザが利用するプラットフォームは PC からモバイルにシフトしつつあります。クックパッドにおけるモバイル利用者の割合も、ここ 2 年で 10% 以上増加しました。最近では、60% 以上のユーザがモバイルからアクセスしています。 ユーザの利用形態が変化すれば、検索結果ページもその変化に対
ON KAGGLE RE-RANKING CONTEST TOKYO WEBMINING - 36TH
On Kaggle Re-ranking contest Tokyo Webmining - 36th Who am I? Software engineer at Dataiku Former foreign student in Tokyo (情報理工学) http://fulmicoton.com @fulmicoton Dataiku ? French startup. We develop a datascience platform Clean / process / visualize with small to big data in R, python, cascading, Hive, Pig, SQL, pandas, all in one place ! “ Oh great a 25mn commercial !!! ” Not gonna happen. Bug
Personalized Web Search Challenge | Kaggle
Re-rank web documents using personal preferences
Personalized Search on the Largest Flash Sale Site in America
This talk provides a tour of how Apache Solr is used to power search for America's largest flash sale site, www.gilt.com. We show how to address the challenges of providing listings for fast moving inventory in a search space personalized for each of our members. The solution, built on Play Framework comprises less than 4,000 lines of code, and provides response times of 40ms on average.Read less
Interleavingについて - tsubosakaの日記
情報検索において検索手法の結果を評価する方法の手法の一つにInterleavingという方法がある。最近その辺についてちょっと読んでいたのでまとめておく。 検索エンジンにおいては何らかのRanking Function(http://en.wikipedia.org/wiki/Ranking_function)を用いて、与えられたクエリに対する検索結果を並び替える。 例えば"餃子 レシピ"というクエリでGoogleで今検索したところ 1. http://cookpad.com/recipe/316319 (☆ほっぺが落ちちゃう 餃子☆) 2. http://cookpad.com/category/836 (餃子・シュウマイ レシピ 306品) 3. http://matome.naver.jp/odai/2133424266153597701 (絶品餃子！！肉汁がやばい究極のギョーザのレ
ウェーブレット行列とウェーブレット木の性能比較をしてみた - EchizenBlog-Zwei
FM-Indexで用いる簡潔データ列としてウェーブレット行列とウェーブレット木のどちらがいけてるのかを調べてみた。 データは以下の実験で用いた住所データを使った。 http://d.hatena.ne.jp/echizen_tm/20120215/1329315913 データサイズは ウェーブレット行列: 5, 693, 256 byte ウェーブレット木: 5, 709, 560 byteとなった。ビット列のセパレータ数が少ないぶんウェーブレット行列のほうがやや小さい。 速度についてはsample/search_fm_indexを用いてインデックスした住所データ(118,073件)をシャッフルしたものをクエリとして全件検索にかかる時間を測った。 $$ time sample/search_fm_index var/zenkoku.key.fm.wm m y < var/zenkoku.s
連想配列はトライでしょ的な話がでていたので入門記事を書いてみた - EchizenBlog-Zwei
なにやらDan Kogai氏の以下の記事が話題になっている様子。 404 Blog Not Found:Algorithm - 連想配列の実装としてのハッシュはオワコン? 連想配列(キーワードを投げると対応する値が返ってくるデータ構造)はハッシュテーブルで実装するのではなく、これからはトライ(trie)木を使うのがイケてる！(意訳)という内容だった。 連想配列にハッシュテーブルを使うのが良いか悪いかについては色々と意見があると思うので特にこの記事では触れない。 今回は連想配列として使えると話題のトライ木とはなんぞ、という入門的な記事にしようと思う。 トライ木が持つ機能 最初にトライが持つ以下の3つの機能について説明する。 - lookup - common-prefix-search - predictive-searchまずトライは連想配列として利用できる。つまりキーワードと値のペアを登
EMアルゴリズムによるスペル訂正エンジン - nokunoの日記
以下の論文が面白かったので紹介したいと思います。Learning a Spelling Error Model from Search Query Logs Noisy Channel Modelによるスペル訂正エンジンスペル訂正には標準的なNoisy Channel Modelを使うことができます（最近は識別モデルも流行りのようです）。A Spelling Correction Program Based on a Noisy Channel ModelNoisy Channel Modelでは、入力が与えられたときの訂正候補の確率を以下のようにモデル化します。言語モデル はコーパスやクエリログから単語N-gram、文字N-gramなどを推定し、スムージングして利用することが一般的です。エラーモデル は入力と出力候補の編集距離をもとに計算することが多いです（他に共起頻度やクリックログを利
全文検索エンジンgroongaについての発表資料を公開しました。
2010年末に、３つに勉強会にて「全文検索エンジンgroonga」の紹介をさせていただきました。 第4回Solr勉強会 groongaを囲む夕べ ドワンゴ技術勉強会(2) MySQLについて それぞれの勉強会にて用いた発表資料を公開いたします。 groongaの紹介部分については使いまわしがバレバレですが、それぞれの勉強会の特性に合わせた味付けをしているので、ぜひご覧になっていただければ嬉しいです。勉強会当日のレポートをされている方もいらっしゃるようなので、興味のある方は検索してみるとよいでしょう。 また、groongaを囲む夕べに関しては、他の発表者さんの資料も以下のリンクから見ること...
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
partake.in
Sigir2013 retrieval models-and_ranking_i_pub
overlasting.net
『ブッチャーばんざい！「Information Retrieval(Buttcher本)」を読み始めたよ - EchizenBlog-Zwei』へのコメント
Media Does Not Need To Be "Saved" From Google Search