DEIM Forum 2017 C8-4

Max/Min Aggregate Reverse Rank Query に対する効率的な検索手法
俊†千田董于洋†漢雄†

陳古瀬一隆†† 筑波大学 〒 305-8571 茨城県つくば市天王台１丁目１−１
E-mail: †s1513107@u.tsukuba.ac.jp, ††tou@dblab.is.tsukuba.ac.jp, †††{chx,furuse}@cs.tsukuba.ac.jp
あらまし

近年、一つの商品がクエリとして与えられたとき、その商品を最も好む k 人のユーザーを求める Reverse

rank query という検索が注目を集めている。その発展として、複数の商品をバンドルして販売するケースの検索方法、
Aggregate Reverse Rank Query（ARkR）が提案されている。ARkR では集約関数 Sum についての検索アルゴリズムが提案されている。本研究では集約関数 Max/Min について効率的な検索手法を提案する。先行研究の手法と比較した結果、本手法は従来の手法より 3 倍以上の処理速度が確認された。
キーワード

Aggregate Reverse Rank Query, ARkR, 問い合わせ処理, データマイニング
表 2 パソコンのレート

1. は じ め にパソコン

性能 価格

デザイン

Top-k Query [1] [2] と Reverse Rank query [3] はマーケティ

p1

9

1

6ングにおいて２つの有効なアップローチである。Top-k Query

p252

7p3

648p4

788p5

339

はユーザーの視点からアプローチし、一人のユーザーの好みをクエリとして与え、そのユーザーに対して各商品のスコアを計算して商品のランク付けを行う。ユーザーが最も好みそうな k 個の商品を解として返す。一方、Top-k Query の逆の意味
で Reverse rank query は販売者の視点からアプローチし、商品のレートからその商品を最も好みそうなユーザーを探索する

表3

パソコンによるユーザーのスコアと r-1rank
u1 による u2 による u3 によるパソコン u1 u2 u3
ランク
ランク
ランク

r-1rank

p1

487057

143u1

クエリである。一つの商品をクエリとして与え、ユーザーそれ

p2535547221u3

ぞれの Top-k ランク付けを行い、クエリとして与えられた商

p3666660334u1

品を最も上位にランク付けする k 人のユーザーを解として返p4797576

555u1す。[4] [5] [6] [7] このクエリを用いて、商品の販売者は潜在的なp566

5448

4

12u2

顧客を特定してより効率なマーケティングが可能になる。
表 1〜表 3 では、Reverse Rank Query の k=1 の例を示している。表 1 では 3 人のユーザー（u1〜u3）がパソコンに関するため、Aggravate Reverse Rank Query（ARkR）が提案された [8]。

好みを示し、好みは性能、価格、デザインに分けて合計 10 とARkR は複数の商品をバンドルした商品セットをクエリとしする。表 2 では 5 つのパソコン (p1〜p5) について性能、価格、て与え、その商品セットを最も上位にランク付けする k 人のデザインのレートを示している。表 3 では Reverse rank query

ユーザーを返す。ARkR の評価方法は複数定義されているが、の結果を示している。ユーザーによる商品のスコアはユーザー

表 4 では商品セット内の最もランクが高い商品を全体のランクの好みベクトルと商品のレートベクトルの内積で計算される。

として評価した結果を示している。

また、スコアは小さい順でランク付けされる。例えば、ユー
ザー u1,u2,u3 による p1 のランキング順位はそれぞれ 1,4,3 となり、u1 による p1 のランキング順位が最も高いので、p1 のr-1rank の解は u1 となる。
表1
ユーザー

ユーザーの好み
性能 価格

デザイン

u1136u2514u3433

表 4 AR-1rank
u1 による
u2 による
u3 による
商品セット max ランク max ランク max ランク AR-1rank

p1, p3134u1p2, p3221u3p2, p4221u3p4, p5

412u2

1. 1 問 題 定 義
Reverse rank Query は一つの商品に対する問い合わせであるが、実際マーケティングでは複数の商品をバンドルして販売するパターンも多く存在する。そういう販売形式を支援する商品のデータ集合を P、ユーザー好みのデータ集合を U、各
商品 p ∈ P が d 次元のベクトルで d 個のレートを持ち、商品 p の各レートは p[1], p[2], ..., p[d] とする。そして、各ユーザー u ∈ U が d 個の好みをもつ d 次元のベクトルであり、ユー∑dザーの好みは u[1],u[2],...u[d] として、i=1

u[i] = 1 とすると、Reverse Rank Query は以下に定義される。
定義 1. (rank(u, q))：商品のデータ集合を P、ユーザーの好みを u、クエリとしてを q 与えた場合、u による q のランク付
けは rank(u, q) = |S| である。ただし、S ⊆ P かつ∀ pi ∈ S :f (u, pi ) < f (u, q) ∧∀ pj ∈ (P − S) : f (u, pj ) >= f (u, q) が成り立つ.

2. 関 連 研 究
先行研究では ARkR の集約関数 sum が注目され、TPM とDTM という 2 種類の手法が提案された。これらの手法は R 木を用いて、商品集合をレートの近い物でクラスタリングしてインデックス化を行う。インデックスされた商品集合の極大値と極小値を用いて必要のない計算を探索から除外し、計算コストの削減を図った。

2. 1 TPM

定義 2. (reverse k-ranks query)： 商品のデータ集合を P,

TPM では R 木を用いて類似する商品の最小包囲矩形（MBR）

ユーザーの好みデータ集合 U、正整数 k、クエリ商品 q を与を作成し、商品集合 P をインデックス化する。そして、計算すえた場合。Reverse k-Rank Query はデータ集合 S を返す。たる必要がない MBR を探索から除外することで計算コストを削だし、S ⊆ U, |S| = k であり, ∀ ui ∈ S, ∀ uj ∈ (U − S) :減する。

rank(ui , q) <= rank(uj , q) が成り立つ.
商品集合をクエリとした問い合わせを解決するため、ARkR
では以下の定義を行っている。

図 1 では TPM の 2 次元の場合の例を示す。TPM ではまずQ に対して MBR を作成し、その MBR の右上の点を Qup 、左下の点を Qlow として、各ユーザーの好みベクト ui ∈ U から、Qup と Qlow に垂線を引く。それによって、図 1 のように 2 次

定義 3. (Aggregate Reverse Rank Query, AR-k)： 商品のデー

元空間は BelowQ、InQ、AboveQ の 3 つのサブ空間に分けらタ集合を P, ユーザーの好みデータ集合 U、正整数 k、クエれる。この例の場合、e2 は BelowQ に、e3 は InQ に含まれ、リされた商品集合 Q を与えた場合。ARkR はデータ集合 S

e5 は AboveQ に含まれる。また、e1 、e4 のは複数のサブ空間を返す。ただし、S ⊆ U, |S| = k であり, ∀ ui ∈ S : ∀ ujに含まれる。この場合、BelowQ に含まれるデータの u による∈ (U − S) : ARank(ui , Q) <= ARank(uj , Q) が成り立つ.

ランク付けは必ず Q に含まれるデータの u によるランク付けより上位になり、AboveQ に含まれるデータの u によるランク付

ARkR は商品集合をクエリとした問い合わせ問題に３つの評

けは必ず Q に含まれるデータの u によるランク付けより下位価方法を提案した。それぞれは下記の Sum、Max、Min の 3になる。この性質を用いて、TPM は BelowQ に含まれるデーつ集約関数に対応する。

タをランキングの下限として数えあげて、AboveQ に含まれる∑•

Sum : ARank(u, Q) =•M ax : ARank(u, Q) = M axqi ∈Q {rank(u, qi )}•リングを行う。したがって、BelowQ と AboveQ の範囲が大き

M in : ARank(u, Q) = M inqi ∈Q {rank(u, qi )}くなるほどフィルタリングの効果が良い。さらに、InQ に含まqi ∈Qrank(u, qi )データを計算せずに探索から除外することで、計算のフィルタ

1. 2 モチベーションれるデータをそれぞれの q に対するランクを計算し、BelowQ

集約関数 Sum は、商品セット Q のぞれぞれの商品のランクで求められたランキングの下限に加算することで、商品セットの和をその商品集合の評価とする。実際の買い物の場合、ユーQ の ARrank を算出する。

ザーが商品セットのそれぞれの商品について考えてた上、商品セットの全体価値が他の商品セットより良いかどうかで判断する購買パターンに対応する。一方、ユーザーは商品セットの中にとても好きな商品が入っていればそのセットを全部買う、嫌いの商品がなければその商品を買うというパターンも多く存在する。例えば、福袋に一つとても気に入る商品があれば、或いは全然使えない商品がなければユーザーがその福袋を買ってよかったと思う。そういうパターンに対応するのは集約関数 Maxと Min である。集約関数 Max は商品集合 Q の中の最もランクの高い商品のランクを商品集合の評価とする。ユーザーが商品セットの中一つとても好きな商品があれば、その商品セットを買うという購買パターンに対応する。集約関数 Min は Max の逆のアプローチをして、ユーザーが商品セットの中嫌いな商品がなければその商品集合を買うという購買パターンに対応する。

図 1 TPM の 2 次元のイメージ先行研究では Sum に対して 2 種類の効率的な検索手法が提案されたが、それらの手法は Max/Min に応用すると非効率でTPM は初期化を行う必要がある。まずはユーザーの好みベある。そのため、本研究では Max/Min に対する効率的な検索

クトル集合 U の最初の k 個 U1 = u[1]、u[2]、...u[k] ∈ U を取手法を提案する。

り出し、その k 人のランキングを作り、heap の初期値とする。

その中の最も順位が低い人のランク heap[k-1] を minRank とする。そして、残った人 U2 = U - U1 を上記フィルタリングのルールを用いて各 u による Q のランクを計算する。u による Qの ARrank が minRank より大きい場合、u を heap に挿入し、minRank を更新する。u による Q の ARrank が minRank より小さい場合、次の u について計算する。U2 に含まれるすべてのデータについて計算後、heap に残った k 人のランキングが最終的な ARrank となる。

2. 2 DTM
DTM は TPM を発展したアルゴリズムである。TPM は R木を用いて類似する p を分類し、計算する必要がない MBR を探索から除外して、u による Q のランク付けを計算するコストを大幅に削減できたが、各 u については逐次計算する必要があるため、|U | の数が大きくなるほどその効率が低くなる。DTM

図 2 TPM、DTM が非効率になる Q

では U 対しても R 木を用いて類似する u を MBR で分類し、MBR ごとに探索を行った。一回に複数の u をフィルタリング検索から除外できるサブ空間を拡大して探索の効率化を行う。
図 3 では 2 次元の Q に対する前処理を示している。ただすることで計算効率を更に向上させた。

し、使用する集約関数は Max である。クエリ集合 Q が与え

2. 3 TPM、DTM の効果
表 5 ではネーティブ手法、TPM、DTM の計算量を示しられた時、まずは Q の凸包 CH(Q) を作成する。CH(Q) にている。全体的にネーティブ手法は最も計算コストが高く、含まれるデータはすべて Q の境界点なので、u によるランO(|P |・|U |) が必要だった。TPM と DTM はインデックス化

ク付けする時の最大、最小になる q は必ず CH(Q) に含まれするための時間がかかるが、ランキングを計算するためのコスる。したがって、ARrank(Q) = ARrank(CH(Q)) が成り立トが激減した。

つ。この例の場合、u によるランク付けが最も高い q は必ずCH(Q) = {q1 , q2 , q4 , q5 , q9 , q10 } に含まれる。
表 5 ネーティブ手法、TPM と DTM の効率まとめ
ランキングをインデックス
手法
インデックス
計算コスト
化コスト

次に、TPM や DTM を適用する場合と同様に Q の最小包囲
矩形 M BR(Q) を作成する。この場合 Qlow は必ず M BR(Q) のNAなし

O(|P |・|U |)O(k)中の u によるランク付けする時の下限であり、Qup は必ず集TPM

RtreeP

O(|U |・log|P |)O(log|P |)合 M BR(Q) の中の u によるランク付けする時の上限であDTM RtreeP、RtreeU O(log|U |・log|P |) O(log|U | + log|P |)る。從って、Max/Min 集約関数で ARrank を求める場合、uによるランク付けが最も高い q は Qlow /Qup の付近に存在

2. 4 TPM、DTM の課題

すると予想できる。そこで、それぞれの次元の Qlow に最もTPM、DTM はクエリ集合 Q を用いて、商品集合 P の空間近いデータを求めて Q′ とし M RB(Q′) を作成すると、u にを 3 つのサブ空間に分割し、BelowQ と InQ に含まれる商品よるランク付けが最も高い q は必ず M BR(Q′) に含まれる。

をフィルタリングする事によって計算コストを削減した。しかしたがって、ARrank(u, Q) = ARrank(u, M BR(Q′)) が成りし、実際の販売では評価の人気商品とそうでもない商品のよう立つ。この例の場合、Qlow を原点として p1 軸と p2 軸の方なレートが大きく異る商品をバンドルして販売するケースも多向に探索し、それぞれの軸で出会った一つ目の q を用いてく存在する。そういった場合は図 2 に示したように商品集合 QM BR(Q′) を作成する。u によるランク付けが最も高い q は必の中各 q のレートが大きく異り、BelowQ と InQ の領域が小さず M BR(Q′) = {q1 , q2 , q3 , q5 , q6 } に含まれる。

くなりフィルタリングできる計算も大幅に下がってしまう。

3. 提 案 手 法以上より、u によるランク付けが最も高い q は必ず CH(Q)に含まれるデータであり、かつ、M BR(Q′) に含まれるデータである。したがって、u によるランク付けが最も高い q はクエリ

本研究では、クエリ集合 Q に対して前処理を行うことで探索

集合 Qm = CH(Q) ∩ M BR(Q′) に含まれ、ARrank(u, Q) =の効率化を図る。集約関数 Sum で評価する場合、各商品のランARrank(u, Qm ) が成り立つ。この例の場合、Qm = {q1 , q2 , q5 }クの和を ARrank 評価とするため、商品集合に含まれる各デーとなり、Qm = {q1 , q2 , q5 } を用いて求めた ARrank の結果はタのランクを調べる必要がある。しかし、Max/Min の集約関ARrank(u,Q),Q = {q1 , q2 , ..., q10 } の結果である。

数は集約関数 Sum と違い、ユーザーによって最もランク付け

図 3 に示される AboveQ は前処理を行わずに TPM を用いが高い商品或いは最もランク付けが低い商品のランクが分かれて u のランクを計算する時、探索から除外できる領域であり、ば ARrank を算出できる。この特性を用いて、本研究では商品

AboveQ′ は前処理を行なってから TPM を用いて u のランクを集合 Q の境界点となるデータを絞る事に注目した。極値以外の計算する時、探索から除外できる領域である。前処理を加える

商品を除外することによって |Q| を減らし、TPM や DTM でことで、探索から除外できる領域が大幅に拡大され、各 u に対して計算すべき q のランクの数も減らされた。省略できる領域

Algorithm 1 クエリされた商品集合 Q の前処理が拡大することで、TPM や DTM の Q の分布が広いと検索効

Require: Q

率が悪くなる課題が解決され、計算速度が大幅に上がる。

Ensure: Qm
1: Q′ ⇐ newArray, Qm ⇐ newArray
2: CH(Q) ⇐ makeCHof Q
3: M BR(Q) =⇐ makeM BRof Q
4: Qlow ⇐ M BR(Q).lowerLef tConner
5: for i ∈ dimension(Q) do
6:min ⇐ ∞7:for q ∈ Q do

8:
9:
10:

if q[i] − Qlow [i] < min thenq′ ⇐ qQ′.push(q′)

11:

end if

12:

end for

13: end for

図 3 Q の前処理

上記手法の擬似コードをアルゴリズム 1 に示す。入力を商品

14: M BR(Q′) ⇐ makeM RBof Q′
15: rangelow ⇐ M BR(Q′).lowerLef tConner
16: rangeup ⇐ M BR(Q′).upperRightConner
17: for q ∈ CH(Q) do

集合 Q として、出力を前処理を加えた後の商品集合 Qm とす

18:

f lag ⇐ 1る。1-4 行目では使用する変数の宣言を行う。1 行目で Q′、Qm

19:

for i ∈ dimension(Q′) doを空配列として宣言する。2-3 行目で、Q の凸包 CH(Q) と Q

20:の最小包囲矩形 M BR(Q) を作成し、3 行目で M BR(Q) の左21:

下の点 Qlow の宣言を行う。

22:

5-13 行目では、各次元の Qlow に最も近い点を探して Q′

if q[i] > rangelow [i] or q[i] < rangeup [i] thenf lag ⇐ 0break23:

end if

24:end forに保存し、すべての次元で探した後 Q′ 内のデータを用いて

25:

if f lag = 1 thenMBR(Q′) を作成する。

26:

15-27 行目では MBR(Q′) の範囲内にあり、かつ、CH(Q) に含まれるデータを求める。15-16 行目で MBR(Q′) の範囲を決め

27:

Qm .push(q)end if

28: end for

る左下と右上の点をそれぞれ rangelow 、rangeup に代入する。
そして、17-28 行目で CH(Q) 内のすべてのデータを取り出生成されたデータである。そして、実データは中国のレストラし、それぞれ rangelow 、rangeup と比較し、rangelow より小ン口コミサイト dianping.com から取得したレストランの評価

さい或いは rangeup より大きい場合、そのデータが MBR(Q′)

データであり、環境、サービス、価格、味わいという４次元のに含まれないので、18 行目で宣言した flag を 0 にして、次の値が 0 〜 1 のレートを持つ。

データを比較する。そうでない場合、そのデータが MBR(Q′)

4. 2 合成データの実験結果の範囲内にあり CH(Q) にも含まれるので、出力となる商品集合 Qm に挿入する。

4. 実

験

提案手法の有効性を検証するため、DTM、前処理を加えた合成データを用いて実験した結果は図 4 に示される。実験 の 初 期 値 は 4.1 節 で 示 さ れ た よ う に 、ユ ー ザ ー 好 み 集合 |U | = 100, 000、商 品 集 合 |P | = 100, 000、ク エ リ 集 合|Q| = 10、k=10、クエリのレートの範囲 qrange = 0〜1 、商品のレートの次元 D=3 である。

DTM の 2 つの手法で実験を行なった。全ての手法は C++で実図 4.a では k を変量として、k = 10、20、30、40、50 で実装され、実験環境は macOS Sierra、プロセッサ 2.9GHz intel

験を行った結果である。いずれも従来の DTM より 3 倍以上のCore i5、メモリ 8G である。

効果が示される。また、提案した前処理の効果が k に依存しな

4. 1 実験データいことが示される。

ユーザー好みベクトルの集合 |U | = 100, 000、商品集合

図 4.b では |Q| を変量として、|Q| = 5、10、15、20、25 で実|P | = 100, 000、クエリ集合 |Q| = 10、k=10、クエリのレート験を行った結果 である。こちらもすべて従来の DTM より 3 倍の範囲 qrange = 0〜1 、商品のレイトの次元 D=3 を初期値と以上の効果が示されている。また、提案した前処理の効率がクして、|Q|、k、クエリのレートの範囲 qrange 、次元 D を変量とエリ集合の数 |Q| に依存しないことが示される。

して実験を行なった。ユーザーの好みデータ U はすべて合成

図 4.c ではクエリのレートの範囲を 0〜0.2、0〜0.4、0〜0.6、データを使用し、商品集合 P は合成データと実データ両方を使0〜0.8、0〜1.0 で実験を行った結果である。クエリのレートの用してそれぞれ実験を行った。合成データは一様分布によって範囲が大きほど、従来の DTM と速度の差が大きいことが示される。これは、従来の DTM ではクエリのレートの範囲が広全体的に、実データで行った実験は合成データで行った実験がるほど BelowQ と AboveQ が小さくなり計算効率が悪くなより効率が良かったことが示される。これは商品データの分布るためである。本研究で提案した前処理は u によるランク付に影響された結果だと考えられる。合成データは一様分布にけする時の上限/下限から離れているデータを削除することでよって生成されたため、データが空間上に散在するが、実デーBelowQ/AboveQ が拡大され、高い計算効率が保たされる。

タはレストランの環境、サービス、価格、味わいの評価である

図 4.d では商品のレートの次元を変量として、D = 3、4、5ため、データ空間上に集まっている。それによって AboveQ、で行った実験結果である。次元数が増えるほど DTM の計算速

BelowQ に含まれるデータ量の違いが大きく、以上の実験結果度が著しく増加するが、前処理を加えることで計算速度が一定になったと考えられる。に保たされる。

図 5 実データを用いた実験結果
図 4 合成データを用いた実験結果

4. 3 実データの実験結果

5. お わ り に

中国のレストラン口コミサイト dianping.com から取得した

本研究では、ARkR で提案された集約関数 Max/Min に対しデータを用いて実験を行った結果は図 5 に示される。実験の初期て効率的な検索手法を提案した。その手法ではクエリ集合 Q に値は合成データの場合と同じ、ユーザー好み集合 |U | = 100, 000、対して前処理を加え、計算する必要のない q ∈ Q を除外するこ商品集合 |P | = 100, 000、クエリ集合 |Q| = 10、k=10、クエとで、先行研究で提案された TPM、DTM の手法で探索を除リのレートの範囲 qrange = 0〜1 、商品のレートの次元 D=3外できる領域を拡大し、計算コストを削減した。合成データとである。

レストランの口コミサイトから取得したデータで実験を行った

図 5.a では k を変量として、k = 10、20、30、40、50 で実験を行った結果である。合成データの場合と同じく、提案した前処理の効果が k に依存しないことが示される。計算速度は従来の DTM より 7 倍以上の速くなることが示される。
図 5.b では |Q| を変量として、|Q| = 5、10、15、20、25 で実験を行った結果 である。こちらも合成データの場合と同じく、提案した前処理の効率がクエリ集合の数 |Q| に依存しないことが示される。計算速度はいずれも従来の DTM より 5 倍以上の速くなることが示される。
図 5.c ではクエリのレートの範囲を 0〜0.2、0〜0.4、0〜0.6、0〜0.8、0〜1.0 で実験を行った結果である。クエリのレートの範囲が大きほど、従来の DTM と速度の差が大きくなり、合成データの場合と同じような効果が示されている。
図 5.d では商品のレートの次元を変量として、D = 3、4 で行った実験結果である。合成データでの実験結果と同じく、前処理を加えることで計算速度を一定に保つことができる。

結果、提案したアルゴリズムは集約関数 Max/Min に対して従来の DTM 手法より 3 倍以上の効果が確認された。
文

献[1] Chang, Y.-C., Bergman, L.D., Castelli, V., Li, C.-S., Lo,
M.-L., Smith, J.R.: The onion technique: Indexing forlinear optimization queries. In: SIGMOD Conference, pp.
391402 (2000)[2] Ilyas, I.F., Beskales, G., Soliman, M.A.: A survey of topk query processing tech- niques in relational database systems. ACM Comput. Surv. 40(4), 11:111:58 (2008)[3] Vlachou, A., Doulkeridis, C., Kotidis, Y., et al.: Reverse
top-k queries. In: ICDE, pp. 365376 (2010)[4] Vlachou, A., Doulkeridis, C. , Kotidis, Y., et al.: Monochromatic and bichromatic reverse top-k queries, pp. 12151229(2011)[5] Vlachou, A., Doulkeridis, C., Kotidis, Y., et al.: Branchand-bound algorithm for reverse top-k queries. In: SIGMOD Conference, pp. 481492 (2013)[6] Zhang, Z., Jin, C., Kang, Q.: Reverse k-ranks query.

PVLDB 7(10), 785796 (2014)[7] Vlachou, A., Doulkeridis, C., et al.: Monitoring reverse topk queries over mobile devices. In: MobiDE, pp. 1724 (2011)[8] Dong Y., Chen H., Furuse K., Kitagawa H. (2016) Aggregate Reverse Rank Queries. In: Hartmann S., Ma H. (eds)
Database and Expert Systems Applications. DEXA 2016.
Lecture Notes in Computer Science, vol 9828. Springer,Cham