---
title: 広告配信のための高速疎ベクトル検索エンジンの開発@WebDBフォーラム2015 #webdbf2015
tags:  #webdbf2015  
author: [Yahoo!デベロッパーネットワーク](https://www.docswell.com/user/ydnjp)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/LE1VMW1L7G.jpg?width=480
description: 本年のWebDBフォーラム2015　http://db-event.jpn.org/webdbf2015/　 技術報告セッションにおけるYahoo! JAPAN発表資料を公開します。
published: November 26, 15
canonical: https://www.docswell.com/s/ydnjp/564V4Z-2015-11-26-153417
---
# Page. 1

![Page Image](https://bcdn.docswell.com/page/LE1VMW1L7G.jpg)

広告配信のための
高速疎ベクトル検索エンジンの開発
ヤフー株式会社 宇野秀平


# Page. 2

![Page Image](https://bcdn.docswell.com/page/GEWL368Q72.jpg)

自己紹介
• 宇野秀平
– Yahoo! JAPAN 2006年入社
– 情報検索黒帯(2015)
– 仕事内容
• 検索関連の仕事がメイン
• 広告検索、商品検索、記事レコメンド、検索基盤etc


# Page. 3

![Page Image](https://bcdn.docswell.com/page/47ZMVY83E3.jpg)

概要
• 検索エンジンは広告配信アーキテクチャの中
心
• 性能の良し悪しが収益に大きな影響を与える
• 性能改善・機能追加のために先端理論を試
行錯誤し、自社製検索エンジンを磨きこんで
いる


# Page. 4

![Page Image](https://bcdn.docswell.com/page/YJ6N5DPZJV.jpg)

アジェンダ
1. YDNにおける検索エンジンの役割
2. LuceneでのYDN実現性
3. Senju概要
4. まとめ


# Page. 5

![Page Image](https://bcdn.docswell.com/page/GJ55Y3K9J4.jpg)

YDNにおける検索エンジンの役割


# Page. 6

![Page Image](https://bcdn.docswell.com/page/LE3N56Z2E5.jpg)

YDNとは
• Yahoo!ディスプレイアドネットワーク
– Yahoo! JAPANのコンテンツページの他、さまざま
な提携サイトのコンテンツページに広告を表示


# Page. 7

![Page Image](https://bcdn.docswell.com/page/8EDWDVR67G.jpg)

YDNの立ち位置
• 2015Q2売上
・広告売上の33%がYDN
ヤフー全体で広告事業の売上は53％
広告商品別 売上高推移(四半期)
・売上高215億
・前年同期比164%
1000
900
800
700
プレミアム広告
600
YDN
売上(億円) 500
400
ディスプレイ広告
300
検索連動型広告
200
100
0
2014Q2
2015Q2
出典：ヤフー2015年度第2四半期決算より
ヤフー成長の中心事業


# Page. 8

![Page Image](https://bcdn.docswell.com/page/V7P9XVMZJ8.jpg)

YDN
• 広告商品
– インタレストマッチ
• ユーザが興味がある、コンテンツにマッチした広告を
配信
– ターゲティング
• 広告主が特定のユーザに限定して広告を配信
–
–
–
–
–
一度サイトに訪れた事がある
特定の検索ワードを検索した事がある
特定の性別・年齢・地域のユーザ
特定のデバイスを持ったユーザ
配信したいサイト、配信したくないサイトを設定


# Page. 9

![Page Image](https://bcdn.docswell.com/page/2JVMLZ9MJQ.jpg)

YDNおける検索エンジンの役割
検索エンジン
・高速に真に正しい結果を含めた結果を返却
Modeler
Reranker
Re-ranker
・限られた候補に対して複雑なモデルによる高精度
な結果を算出
すべての結果に複雑なモデルは適応出来ない
Searcher
真に正しい結果
Log server
モデルを全体に適応した結果
検索結果
をなるべく包含した結果を高速に返す


# Page. 10

![Page Image](https://bcdn.docswell.com/page/5EGGX4ZXEL.jpg)

YDNおける検索エンジンの重要性
検索エンジンが良い結果を返せないとモデルが高精度でも良い結果が返却出来ない
真の答えが含まれていない
真に正しい結果
モデルを全体に適応した結果
検索結果
検索エンジンが高速であれば複雑なモデルが使用可能になり、精度があがる
真に正しい結果
モデルを全体に適応した結果
モデルが真の答えを包含出来る可能性が上がる
検索結果
検索エンジンの性能向上は売上に大きな影響を与える


# Page. 11

![Page Image](https://bcdn.docswell.com/page/4JQX8GL5EP.jpg)

LuceneでのYDN実現性


# Page. 12

![Page Image](https://bcdn.docswell.com/page/K74625DVE1.jpg)

Luceneの機能
機能
実現
性
YDNへの必要
性
キーワード検索
○
×
複数単語検索
×
○
グループ化
○
△
RangeQuery
○
×
FuzzyQuery
○
×
Boolean Index
×
○
Luceneのキーワード検索機能は十分に充実
しかし、YDNで必要な機能は非搭載


# Page. 13

![Page Image](https://bcdn.docswell.com/page/LJ1VMWZ4EG.jpg)

実現したい事
• コンテンツマッチの実現
– ベクトル空間モデルを使ってコンテンツと類似度
が高い広告を検索
– 文書ベクトルが疎ベクトルになり、高速な疎ベクト
ル検索を実現
tokenize
tokenize
Index：広告の単語ベクトル
クエリ：コンテンツの単語ベクトル
(0.2, 0, 0, ………, 0.13,0.33,…..,0)
(1, 0, 0, ………, 1,1…..0)
クエリと広告のcos類似度が高いTOP-Kを返却


# Page. 14

![Page Image](https://bcdn.docswell.com/page/GJWL369ZE2.jpg)

転置indexによる実現方法
• クエリに出現した単語を重み付きORで検索
• 該当した文書のスコア(内積)を計算
• 上位K件を返却
tokenize
tokenize
Index：広告の単語ベクトル
クエリ：コンテンツの単語ベクトル
(0.2, 0, 0, ………, 0.13,0.33,…..,0)
トヨタ:0.2 or 本気:0.1 or クルマ：0.5 or …
転置index
クエリと広告の内積が高いTOP-Kを返却


# Page. 15

![Page Image](https://bcdn.docswell.com/page/4EZMVY9LJ3.jpg)

Luceneの検索アルゴリズム
『柏木由紀 or 指原莉乃 or 小嶋陽菜』で検索
柏木由紀
1, 3, 6, 8, 9, 10, 12, … , 909999
指原莉乃
1, 4, 6, 7, 9, 11, 16, … , 909779
小嶋陽菜
1, 4, 6, 7, 9, 11, 16, … , 909779
辞書
Result = [1(31)]
柏木由紀が存在する文書ID
ポスティングリスト
文書1を登録して文書のスコアを計算


# Page. 16

![Page Image](https://bcdn.docswell.com/page/Y76N5DKM7V.jpg)

Luceneの検索アルゴリズム
『柏木由紀 or 指原莉乃 or 小嶋陽菜』で検索
柏木由紀
1, 3, 6, 8, 9, 10, 12, … , 909999
指原莉乃
1, 4, 6, 7, 9, 11, 16, … , 909779
小嶋陽菜
1, 4, 6, 7, 9, 11, 16, … , 909779
辞書
Result = [1,3]
ポスティングリスト
柏木由紀が存在する文書ID


# Page. 17

![Page Image](https://bcdn.docswell.com/page/G755Y3PQ74.jpg)

Luceneの検索アルゴリズム
『柏木由紀 or 指原莉乃 or 小嶋陽菜』で検索
柏木由紀
1, 3, 6, 8, 9, 10, 12, … , 909999
指原莉乃
1, 4, 6, 7, 9, 11, 16, … , 909779
小嶋陽菜
1, 4, 6, 7, 9, 11, 16, … , 909779
辞書
Result = [1,3,4]
ポスティングリスト
柏木由紀が存在する文書ID


# Page. 18

![Page Image](https://bcdn.docswell.com/page/9J2NGZ6WER.jpg)

Luceneの検索アルゴリズム
『柏木由紀 or 指原莉乃 or 小嶋陽菜』で検索
柏木由紀
1, 3, 6, 8, 9, 10, 12, … , 909999
指原莉乃
1, 4, 6, 7, 9, 11, 16, … , 909779
小嶋陽菜
1, 4, 6, 7, 9, 11, 16, … , 909779
クエリ数
辞書
ポスティングリストの長さ
Result = [1,3,4]
速度は(クエリ数 × ポスティングリスト数)に依存
クエリ数が多いとレスポンスタイムが大きく劣化


# Page. 19

![Page Image](https://bcdn.docswell.com/page/DEYPVR99EM.jpg)

Luceneで実現出来ない理由
• コンテンツマッチのクエリ数はコンテンツの単
語
– 30単語以上使用
• Luceneはクエリ数にレスポンスタイムが依存
– 要件を満たすためには万オーダーでサーバが必
要になりそう
そこで自社で高速な検索エンジンを実装


# Page. 20

![Page Image](https://bcdn.docswell.com/page/VJN5MDLD78.jpg)

ターゲティング
• 広告主が設定した条件にマッチしたユーザに
広告を出す
ユーザ情報
ユーザ情報
・40代
・北海道出身
・男性
広告主が設定した条件にマッチした広告


# Page. 21

![Page Image](https://bcdn.docswell.com/page/YE9YNG48J3.jpg)

既存の検索エンジン
広告1 出身(東京) and 趣味(野球) and 年代(40代)
広告2 出身(北海道) and 年代(40代)
40代, 北海道出身
Query(40代 and 北海道)
広告3 趣味(盆栽) and 年代(40代)
出身：東京
1, 3
出身：北海道
2
年代：40代
1, 2, 3
趣味：盆栽
3
辞書
ポスティングリスト
広告2はクエリの条件を満たす


# Page. 22

![Page Image](https://bcdn.docswell.com/page/GE86KVQZ7D.jpg)

条件を複雑にすると
入れ子を作ると
広告1 出身(東京) and 趣味(野球) and 年代(40代)
広告2 出身(北海道) and {年代(40代) or 性別(女性)}
40代, 北海道出身, 男性
広告3 趣味(盆栽) and 年代(40代) and 性別(男性)
クエリの条件に2がマッチしなくなってしまう
出身：東京
1, 3
出身：北海道
2
年代：40代
1, 2, 3
趣味：盆栽
3
性別：男性
性別：女性
3
2
Query(40代 and 北海道 and 男性)
辞書
ポスティングリスト


# Page. 23

![Page Image](https://bcdn.docswell.com/page/LEL9Z5X1JR.jpg)

Luceneでは実現出来ない理由
• 複雑な条件を持った検索が出来ない
– 入れ子はビジネス要件として存在
– 検索条件をindex側に持つBoolean Indexが必要
• Luceneはクエリ側に検索条件
自社でビジネス要件を満たすエンジンを実装


# Page. 24

![Page Image](https://bcdn.docswell.com/page/4JMZV3L5EW.jpg)

Senjuの概要


# Page. 25

![Page Image](https://bcdn.docswell.com/page/PJR62QKZ79.jpg)

Senju
• Yahoo! JAPAN独自の転置Index型の検索ライ
ブラリ
• 主な特徴
– コンテンツマッチを高速検索する仕組みを実現
• WANDの導入
– Broder CIKM2003
– 複雑なターゲット条件による検索機能を実現
• Boolean Indexの導入
– Marcus SIGMOD2010


# Page. 26

![Page Image](https://bcdn.docswell.com/page/PEXMD5L17X.jpg)

Senju
• Yahoo! JAPAN独自の転置Index型の検索ライ
ブラリ
• 主な特徴
– コンテンツマッチを高速検索する仕組みを実現
• WANDの導入
– Broder CIKM2003
– 複雑なターゲット条件による検索機能を実現
• Boolean Indexの導入
– Marcus SIGMOD2010


# Page. 27

![Page Image](https://bcdn.docswell.com/page/3EKGX6LMJD.jpg)

WAND
• WAND
– WeakANDの略
– ORクエリにANDクエリのような振る舞いをさせる
• ANDクエリは高速に検索可能


# Page. 28

![Page Image](https://bcdn.docswell.com/page/L73N563275.jpg)

ANDが高速な理由
Query(柏木由紀 and 指原莉乃 and 小嶋陽菜 and 島崎遥香)
クエリに該当したポスティングリストすべてに同じ文書ID存在した場合、そのIDは成立
この場合1は全リストに存在してるので成立
柏木由紀
1, 3, 6, 7, 8, 10, 19, … , 909999
指原莉乃
1, 4, 6, 7, 9, 11, 19, … , 909779
小嶋陽菜
1, 2, 6, 7, 18, 19, 55, … , 909779
島崎遥香
1, 19, … , 999999
Result = [1]


# Page. 29

![Page Image](https://bcdn.docswell.com/page/87DWDV46JG.jpg)

ANDが高速な理由
Query(柏木由紀 and 指原莉乃 and 小嶋陽菜 and 島崎遥香)
次に一致してるIDを探す
最大の19が他のリストに存在しているか探す
柏木由紀
1, 3, 6, 7, 8, 10, 19, … , 909999
指原莉乃
1, 4, 6, 7, 9, 11, 19, … , 909779
小嶋陽菜
1, 2, 6, 7, 18, 19, 55, … , 909779
島崎遥香
1, 19, … , 999999
Result = [1]


# Page. 30

![Page Image](https://bcdn.docswell.com/page/VJP9XVVZE8.jpg)

ANDが高速な理由
Query(柏木由紀 and 指原莉乃 and 小嶋陽菜 and 島崎遥香)
この部分の文書の評価をSKIPできる
ORより高速に動作
柏木由紀
1, 3, 6, 7, 8, 10, 19, … , 909999
指原莉乃
1, 4, 6, 7, 9, 11, 19, … , 909779
小嶋陽菜
1, 2, 6, 7, 18, 19, 55, … , 909779
島崎遥香
1, 19, … , 999999
Result = [1, 19]


# Page. 31

![Page Image](https://bcdn.docswell.com/page/2EVMLZZMEQ.jpg)

WAND
UB ポスティングリスト内で最大のスコアを保存
柏木由紀 : 43
1, 3, 6, 7, 8, 10, 12, … , 909999
指原莉乃 : 13
1, 4, 6, 7, 9, 11, 16, … , 909779
小嶋陽菜 : 67
1, 2, 6, 7, 18, 19, 55, … , 909779
島崎遥香 : 21
1, 4, 6, 7, 8, 10, 16, … , 909779
Top-3が欲しい
Result = [7(142), 1(141), 6(138)]
3件分の候補をスコア順に並べる
7以降の文書はスコアが138以上必要、つまり、UBの合計値が138以上になる事が条件
柏木由紀 and 指原莉乃 and 小嶋陽菜 and 島崎遥香
スコアの下限値を利用して擬似的にANDを生み出して高速化させる


# Page. 32

![Page Image](https://bcdn.docswell.com/page/57GGX44X7L.jpg)

Senju
• Yahoo! JAPAN独自の転置Index型の検索ライ
ブラリ
• 主な特徴
– コンテンツマッチを高速検索する仕組みを実現
• WANDの導入
– Broder CIKM2003
– 複雑なターゲット条件による検索機能を実現
• Boolean Indexの導入
– Marcus SIGMOD2010


# Page. 33

![Page Image](https://bcdn.docswell.com/page/4EQX8GG57P.jpg)

Interval algorithm
クエリが下記を満たせば成立
・intervalがstartからgoalまで辿りつける
文書の条件 = (A and B) or C or (D and E and F) の場合
interval
クエリがA, Bの時
A：1
B：2−10
1〜10を満たすので成立
クエリがB, Dの時
B：2-10
D：1-4
1-4だと2-10に接続出来ないた
め不成立


# Page. 34

![Page Image](https://bcdn.docswell.com/page/KJ46255V71.jpg)

さらなる磨き込み
• WANDの後継
– Block Max WAND
• S. Ding and T. Suel SIGIR2011
• プロトタイプ実装
– 論文読み
• 2014年以降、枝刈りアルゴリズムがあまり出ない
• Boolean Index
– 各種論文を読み問題に対応出来る解決策か調
査


# Page. 35

![Page Image](https://bcdn.docswell.com/page/LE1VMWW47G.jpg)

まとめ
• 検索エンジンは広告配信アーキテクチャの中
心
• 性能の良し悪しが収益に大きな影響を与える
• 性能改善・機能追加のために先端理論を試
行錯誤し、自社製検索エンジンを磨きこんで
いる


# Page. 36

![Page Image](https://bcdn.docswell.com/page/GEWL366Z72.jpg)

ご静聴有難うございました！