DEIM Forum 2017 E5-5

ARkR ΫΤϦॲཧͷΫϥελϦϯάʹΑΔޮ཰ԽࢁԼխ߂†౹ဋ༸†‫׽‬༤††௠‫ ੉ݹ‬Ұོ††† ஜ೾େֶӃγεςϜ৘ใ޻ֶ‫ڀݚ‬ՊίϯϐϡʔλαΠΤϯεઐ߈ ˟ 305–8573 ҵ৓‫ͭ͘ݝ‬͹ࢢఱԦ୆ 1–1–1†† ஜ೾େֶγεςϜ৘ใ‫ ˟ ܥ‬305–8573 ҵ৓‫ͭ͘ݝ‬͹ࢢఱԦ୆ 1–1–1
E-mail: †{yamasy,tou}@dblab.is.tsukuba.ac.jp, ††{chx,furuse}@cs.tsukuba.ac.jp͋Β·͠ ຊ࿦จͰ͸ɺू໿‫ ٯ‬k ϥϯΫΫΤϦ (ҎԼ,ARkR) ͱ‫ݺ‬͹ΕΔ‫ࡧݕ‬ख๏ΛΫϥελϦϯάΛ༻͍ͯޮ཰Խ͢Δ͜ͱΛ໨తͱ͢ΔɻARkR ͸ɺෳ਺ͷ঎඼σʔλΛΫΤϦͱͯ͠ड͚औΓɺΫΤϦ঎඼ͱશͯͷϢʔβ‫ͼٴ‬ɺଞͷ঎඼ͱશͯͷϢʔβʹ͍ͭͯείΞΛ‫͠ࢉܭ‬ɺΫΤϦ঎඼͕ଞͷ঎඼ΑΓ΋ྑ͍είΞͱͳ͍ͬͯΔ্Ґ k ਓͷϢʔβΛղͱͯ͠ฦ͢‫ࡧݕ‬ख๏Ͱ͋ΔɻARkR ͸ɺΫΤϦͱͯ͠ड͚औΔ঎඼ͷ෼෍͕޿͍৔߹ʹɺ‫ط‬ଘͷख๏Ͱ͸‫ࡧݕ‬ޮ཰͕ஶ͘͠௿Լ͢Δɻ͜ΕʹରԠ͢ΔͨΊɺΫΤϦͱͯ͠༩͑ΒΕͨσʔλΛෳ਺ͷΫϥελʹ෼ׂ͠ɺͦΕͧΕͷΫϥελʹରͯ͠‫ط‬ଘͷख๏Λద༻͢Δɻ͜ΕʹΑΓɺ঎඼ͷ෼෍ʹؔΘΒͣޮ཰Α͘ ARkR ΛॲཧͰ͖ΔΑ͏ʹͳΔɻΩʔϫʔυ ARkR, ΫϥελϦϯά1. ͸ ͡ Ί ʹυϧ͞Εͨ঎඼ {p1, p2} ͕ΫΤϦͱͯ͠༩͑ΒΕͨͱ͢Δɻ

Top-k ΫΤϦ [1] ΍‫ ٯ‬k ϥϯΫΫΤϦ [2] ͱ‫ݺ‬͹ΕΔ‫ࡧݕ‬ख࿨Λͱͬͨ΋ͷʹͳΔɻJack ͷ৔߹͸ 5, Dave ͷ৔߹͸ 6 ͱ{p1, p2} ͷू໿ϥϯΫ͸ɺ֤Ϣʔβʹ͍֤ͭͯ঎඼ͷϥϯΫͷ๏͸ɺΫΤϦͱͯ͠ҰͭͷσʔλΛ౉͢Α͏ͳ‫ࡧݕ‬ख๏Ͱ͋ΔɻͳΔͷͰɺAR1R ͸ Jack ͕ϢʔβͷதͰ࠷΋޷Ήͱͯ͠ Jackલऀ͸ɺϢʔβͷ޷ΈΛΫΤϦͱͯ͠ɺϢʔβͷ޷Έͱ঎඼ҰΛղͱͯ͠‫ٻ‬ΊΔɻͭҰͭͱͷείΞΛ‫ͯ͠ࢉܭ‬είΞͷ௿͍ॱʹϥϯΫ෇͚Λߦ͍ɺ্Ґ k ‫ݸ‬ͷ঎඼Λղͱͯ͠ฦ͢ɻ͜Ε͸ɺϢʔβࢹ఺ͷ‫ݕ‬useru[smart]u[rating]RanksࡧϞσϧͰ͋ΓɺϢʔβͷ޷ΈʹԠͨ͡঎඼Λ‫͢ࡧݕ‬Δͱ͍͏

Jack

0.80.2p3,p2,p1,p4,p5࢖͍ํ͕Ͱ͖Δɻ‫ऀޙʹٯ‬͸ɺ͋Δ঎඼ΛΫΤϦͱͯ͠༩͑ΔDave0.30.7

p2,p5,p3,p4,p1

ද 1: Ϣʔβͷ޷Έͱ‫ܞ‬ଳͷϥϯΫ෇͚ͷྫͱɺͦͷ঎඼ͱ͢΂ͯͷϢʔβ‫ͼٴ‬ଞͷ঎඼ͱ͢΂ͯͷϢʔβʹ͍ͭͯείΞΛ‫͠ࢉܭ‬ɺΫΤϦͱͯ͠༩͑ΒΕͨ঎඼͕ଞͷ঎඼ΑΓ΋ྑ͍είΞͱͳ͍ͬͯΔ্Ґ k ਓͷϢʔβΛղͱ͠

Score

Score

RankRankͯฦ͢ɻͪ͜Βͷख๏͸ɺϝʔΧʔࢹ఺ͷ‫ࡧݕ‬ϞσϧͰɺજࡏp[smart] p[rating] on Jack

onin Jackin Dave R-1Rank

తͳফඅऀͷൃ‫ݟ‬΍঎඼ͷϚʔέςΟϯάʹԠ༻͢Δ͜ͱ͕Ͱ͖Δɻ
ද 1,2 ͸ɺ‫ ٯ‬k ϥϯΫΫΤϦͰ k=1 ͷͱ͖ͷྫΛ͍ࣔͯ͠Δɻද 1 ͸ೋਓͷϢʔβͷ‫ܞ‬ଳి࿩ʹؔ͢Δ޷ΈΛ͓ࣔͯ͠Γɺ·ͨද 2 ʹࣔ͞Ε͍ͯΔ 5 ͭͷҟͳΔ‫ܞ‬ଳి࿩ (p1 − p5) ͕ͦΕͧΕͷϢʔβʹ͍ͭͯ”Ranks”ͷཝͰॱҐ෇͚͞Ε͍ͯΔɻ

Dave
p1

67

6.2

6.7

3rd

5th

Jack

p2

23

2.2

2.7

2nd

1st

Dave

p3

16

2.0

4.5

1st

3rd

Jackp4

75

6.6

5.6

4th

4th

Jack

p5

82

6.8

3.8

5th

2nd

Dave

ද 2: ϢʔβʹΑΔ‫ݸ‬ʑͷ‫ܞ‬ଳి࿩ͷϥϯΫ෇͚ͱ‫ ٯ‬k ϥϯΫΫΤϦ (k=1) ͷྫද 2 Ͱ͸ͦΕͧΕͷ‫ܞ‬ଳి࿩ʹؔ͢Δ৘ใͱϢʔβ͝ͱͷείΞͱϢʔβ͕͚ͭͨॱҐɺͦͯ͠‫ ٯ‬k ϥϯΫΫΤϦͷ݁ՌΛද͍ͯ͠Δɻ‫ ٯ‬k ϥϯΫΫΤϦͰ͸ɺͲͷϢʔβ͕࠷΋ߴ͍ධՁ|Q|=2ΛԼ͔͢Λ‫ٻ‬ΊΔͷͰɺ͜ͷྫͷ৔߹ɺk=1 ͳͷͰϢʔβΛҰ

p1,p2ਓ୳͠ग़͢ɻͦͷ݁Ռ͸ɺද 2 ͷ࠷΋ӈͷཝʹࣔ͞Ε͍ͯΔɻ

p4,p5‫ ٯ‬k ϥϯΫΫΤϦ͸ɺҰͭͷ঎඼ʹରͯ͠ͷ‫ࡧݕ‬ख๏Ͱ͋Δ

sum Rank in

sum Rank inJackDave

5 (3 + 2)

6 (5 + 1)

Jack

9 (4 + 5)

6 (4 + 2)

DaveAR-1Rank

ද 3: ARkR ͷྫ (k=1)ͨΊɺෳ਺ͷ঎඼ΛҰͭͷ঎඼ͱͯ͠ചΓग़͢όϯυϦϯάͱ͍͏঎๏ΛऔΔΑ͏ͳϝʔΧʔʹରͯ͠͸༻͍Δ͜ͱ͕Ͱ͖ͳઌߦ‫Ͱڀݚ‬͸ɺARkR ΫΤϦΛఏҊ͢Δͱͱ΋ʹɺTPM ͱ͔ͬͨɻ͜͜Ͱɺू໿‫ ٯ‬k ϥϯΫΫΤϦ (Aggregate Reverse‫ݺ‬͹ΕΔ R ໦Λ༻͍ͨޮ཰Խख๏΋ఏҊͨ͠ɻ͔͠͠ɺTPMk-Ranks Query: ARkR) ͱ‫ݺ‬͹ΕΔ‫ࡧݕ‬ख๏͕ఏҊ͞Εͨ [3]ɻ͸ΫΤϦ্͕ۭؒʹ޿͘෼ࢄ͍ͯ͠ΔΑ͏ͳΫΤϦ෼෍ͷ৔߹

ARkR ΫΤϦ͸ɺ‫ ٯ‬k ϥϯΫΫΤϦͱಉ༷ͷ‫ࡧݕ‬ख๏Ͱ͋ΔͰ͸ੑೳ͕ѱ͘ͳΔ͜ͱ͕Θ͔͍ͬͯΔɻͦ͜Ͱɺຊ‫Ͱڀݚ‬͸͕ɺΫΤϦͱͯ͠ෳ਺ͷ঎඼Λ༩͑Δͱ͍͏఺͕ҟͳΔɻ

ARkR ΫΤϦʹର͢ΔΫΤϦΛΫϥελϦϯά͠ɺͦΕͧΕͷද 3 ͸ ARkR ʹ͓͍ͯ k=1 ͷ࣌ͷ؆୯ͳྫͰ͋ΔɻόϯΫϥελʹରͯ͠ TPM Λద༻͢Δ͜ͱʹΑͬͯΫΤϦ͕޿͘෼ࢄ͍ͯͯ͠΋‫ࢉܭ‬Λޮ཰Խ͢Δํ๏ΛఏҊ͢Δɻຊ࿦จͰ͸ɺ·ͣ ARkR ʹؔΘΔ‫ط‬ଘͷ‫ڀݚ‬΍ख๏ʹ͍ͭͯ·ͱΊɺ‫ط‬ଘͷख๏Ͱͷ໰୊఺Λࢦఠ͢Δɻଓ͍ͯɺͦͷ໰୊఺Λղܾ͢ΔͨΊʹఏҊͨ͠ख๏ͱͦͷࠜ‫ڌ‬Λࣔ͢ɻ࠷‫ʹޙ‬ɺ·ͱΊͱࠓ‫ޙ‬ͷ՝୊Λࣔ͠ɺࠓ‫ޙ‬ͷ‫ڀݚ‬ͷํ޲ੑΛࣔ͢ɻ

2. ؔ ࿈ ‫ڀ ݚ‬ΒΕΔɻ͜ͷ࿦จʹ͓͍ͯ͸ɺSum ʹ͍ͭͯߟ͑ɺ࣍ͷΑ͏ʹఆٛ͢Δɻ
ఆٛ 3. ARank(u, Q) =!

qi ∈Q rank(u, qi )3. 2 TPM (Tree Pruning Method)
TPM ͸ɺR ໦ [8] ʹΑΔσʔλू߹ P ͷΠϯσοΫεԽʹΑͬͯ࡞ΒΕΔ R ໦ͷϊʔυ (ΤϯτϦ) ‫ͼٴ‬ɺ֤ u ∈ U ʹΑϥϯΫ෇͚͸ɺ঎඼ͷධՁࢦඪͱͯ͠ॏཁͳ໾ׂΛՌͨ͢ɻΔΫΤϦू߹ Q ͷ্ք (Q.up) ͱԼք (Q.low) Λར༻͢Δ͜ϥϯΫΛ༻͍ͨΫΤϦॲཧ͸͜Ε·Ͱ΋޿͘‫͞ڀݚ‬Ε͖ͯͨɻͱʹΑΓ ARkR ͷޮ཰ԽΛਤΔΞϧΰϦζϜͰ͋Δɻਤ 1 ͸ͦͷதͰ΋ຊ‫ؔͱڀݚ‬ΘΓͷਂ͍ɺ‫ٯ‬ϥϯΫΫΤϦʹ͍ͭͯड़

TPM ͷ࣮ߦաఔʹ͍ͭͯೋ࣍‫ͨࣔ͠Ͱۭؒݩ‬΋ͷͰ͋Δɻ·΂ΔɻͣɺQ ʹ͍ͭͯͷ MBR Λ‫͢ࢉܭ‬Δɻͦͯ͠ɺ͋ΔॏΈ෇͖ϕɹ‫ٯ‬ϥϯΫΫΤϦ (RkR): ‫ٯ‬ϥϯΫΫΤϦ͸ɺຊ‫ڀݚ‬ͷର৅ͰΫτϧ ui ʹରͯ͠ਨ௚ͳ௚ઢʹΑΓ Q ͷ্քͱԼքΛ‫͠ࢉܭ‬ɺ

͋Δ ARkR Λ‫ؚ‬Ίɺ‫ ٯ‬top-k ΫΤϦɺ‫ ٯ‬k ϥϯΫΫΤϦͳͲͦΕͧΕ Q.up, Q.low ͱ‫͢ه‬ɻQ Λ্քͱԼքʹ෼͚ΔਨઢΛͰ‫ݟ‬ΒΕΔɺ঎඼ʹ͍ͭͯϢʔβΛϥϯΫ෇͚͠ධՁΛߦ͏ΫਤதͰ͸ഁઢͰද͍ͯ͠Δɻ͜ͷഁઢʹΑΓۭؒ͸̏ͭͷྖҬΤϦॲཧͷ૯শͰ͋ΔɻҎԼʹɺ‫ ٯ‬top-k ΫΤϦ‫ ٯͼٴ‬k ϥϯʹ෼͚ΒΕɺͦΕͧΕ BelowQ, AboveQ, ͦΕҎ֎ͱ͢Δɻ͜ΫΫΤϦʹ͍ͭͯ؆ܿʹઆ໌͢Δɻͷྫͷ৔߹ɺϊʔυ e2 ͸ BelowQ ʹ‫·ؚ‬Ε͓ͯΓɺϊʔυ e5‫ ٯ‬top-k ΫΤϦ [1,4]: ΫΤϦͱͯ͠༩͑ΒΕͨ঎඼Λଞͷ঎͸ AboveQ ʹ‫·ؚ‬Ε͍ͯΔɻBelowQ ͱ AboveQ ʹ‫·ؚ‬ΕΔ඼ͱൺ΂ͨࡍʹɺ্Ґ k ҐҎ಺ʹධՁ͢ΔΑ͏ͳϢʔβΛ୳͢ϊʔυ͸ͦΕͧΕͷ্քͱԼքΛௐ΂Δ͜ͱʹΑͬͯϑΟϧλख๏Ͱ͋Δɻ ‫ ٯ‬top-k ΫΤϦΛޮ཰Խ͢Δख๏ͱͯ͠ VlachouϦϯά͢Δ͜ͱ͕Ͱ͖ΔɻͦͷϧʔϧΛҎԼʹࣔ͢ɻΒ [5] ͸ɺ໦ߏ଄‫ͼٴ‬ɺ‫ڥ‬քʹ‫͍ͨͮج‬ҐஔܾΊʹΑΔ෼ࢬ‫ݶ‬ఆ๏Λ༻͍ͨΞϧΰϦζϜΛఏҊͨ͠ɻ·ͨɺVlachou Β͸ɺ[6, 7] ‫ ٯ‬top-k ΫΤϦʹ͓͚ΔԠ༻ྫΛଟ਺‫͍ͯ͛ڍ‬Δɻ‫ ٯ‬k ϥϯΫΫΤϦ [2]: ‫͍ڧ‬Ө‫ྗڹ‬ͷ͋Δ঎඼ͷΈ͕ϢʔβΛ֫ಘ͢ΔΑ͏ͳ‫ ٯ‬top-k ΫΤϦʹରͯ͠ɺ͍͔ͳΔ঎඼ʹରͯ͠΋ͦͷ঎඼ΛଞͷϢʔβΑΓ΋૬ରతʹߴ͘ධՁ͢Δ্Ґk ਓͷϢʔβΛ୳͢͜ͱͰɺ঎඼ͷӨ‫ؔʹྗڹ‬ΘΒͣϢʔβΛ୳ͤΔΑ͏ʹͨ͠ख๏Ͱ͋Δɻ

3. ू໿‫ ٯ‬k ϥϯΫΫΤϦ (ARkR)
ARkR ͸ɺલষͰ΋৮Εͨ‫ ٯ‬k ϥϯΫΫΤϦΛ֦ுͨ͠΋ͷͰ͋Δɻ‫ ٯ‬k ϥϯΫΫΤϦͰ͸ɺҰͭͷΫΤϦʹରͯ͠ͷΈϥϯΫΛ‫͠ࢉܭ‬ղΛ‫ٻ‬Ί͍ͯͨ΋ͷΛɺARkR Ͱ͸ɺෳ਺ͷΫΤਤ 1: ೋ࣍‫ݩ‬σʔλू߹ P ͷۭؒʹ͓͚Δ ui ͱ Q ͷ্քͱԼϦʹରͯ͠ͷϥϯΫΛ‫͠ࢉܭ‬ɺղΛ‫ٻ‬ΊΕΔΑ͏ʹͨ͠΋ͷͰքʹΑΔۭؒ෼ׂͷྫ

͋Δɻ͜ΕʹΑͬͯɺྫ͑͹ෳ਺ͷ঎඼ͳͲΛҰͭͷηοτͱͯ͠ൢച͢ΔΑ͏ͳൢചऀʹରͯ͠ɺͲͷΑ͏ͳফඅऀ͕ͦͷʢ 1 ʣ (ep ͕ BelowQ ʹ‫·ؚ‬ΕΔ)

঎඼Λߪೖ͢Δͷ͔λʔήοτΛߜΓࠐΉ͜ͱ͕Ͱ͖ɺͦͷΑf (u, ep .up) < f (u, Q.low) ͕੒ཱ͢ΔͳΒ͹ɺ∀p ∈ ep , ∀q ∈͏ͳফඅऀʹର͢ΔΞϓϩʔνΛߟ͑ΕΔΑ͏ʹͳΔͱ͍͏Ԡ༻ྫ͕ߟ͑ΒΕΔɻ

3. 1 ARkR ͷఆٛఆٛ 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. (Aggregate Reverse k Rank query, ARkR): σ ʔλू߹ P , ॏΈ෇͖ϕΫτϧू߹ U , ਖ਼ͷ੔਺ k, ΫΤϦू߹ Q ͕༩͑ΒΕͨ࣌ɺARkR ΫΤϦ͸ S ⊂=U, |S| = k ͔ͭ∀ui ∈ S, ∀uj ∈ (U − S), ARank(ui , Q) <= ARank(uj , Q) Λຬͨ͢Α͏ͳ S Λฦ͢ɻ͜ͷ࣌ɺARank ͸ Sum, Max, Min ͳͲͷू໿‫͑ߟ͕ࢉܭ‬Q, f (u, q) > f (u, p) ΋੒ཱ͢ΔͨΊɺep ʹ‫·ؚ‬ΕΔσʔλΛ਺্͑͛Δɻʢ 2 ʣ (ep ͕ AboveQ ʹ‫·ؚ‬ΕΔ)

f (u, ep .low) > f (u, Q.up) ͕੒ཱ͢ΔͳΒ͹ɺ∀p ∈ ep , ∀q ∈Q, f (u, q) < f (u, p) ΋੒ཱ͢ΔͨΊɺep ʹ‫·ؚ‬ΕΔσʔλΛ੾ΓࣺͯΔɻ
ʢ 3 ʣ (1,2 Ҏ֎ͷ৔߹)f (u, ep .low) > f (u, Q.low) ͔ͭ f (u, ep .up) < f (u, Q.up) ͕੒ཱ͢ΔͳΒ͹ɺep ͸ղͷީิͱͯ͠อ࣋͠ɺਫ਼ࠪ͢Δඞཁ͕͋Δɻ·ͨɺTPM ͸֤ u ∈ U ʹ͍ͭͯͷϥϯΫΛ‫͢ࢉܭ‬Δࡍʹɺ

minRank ͱ‫ݺ‬͹ΕΔᮢ஋Λ΋͍ͪͯɺR ໦ͷ୳ࡧΛ୹ॖ͢Δํ๏Λͱ͍ͬͯΔɻ͜ͷΞϧΰϦζϜ͸ɺARank-P [3] ͱ‫ݺ‬͹ΕΔɻ

3. 3 TPM ʹ͓͚Δ໰୊఺ΫΤϦू߹શମͷԼքҎԼͷσʔλͷΈΛ༻͍ͯ࠷௿ϥϯΫΛ

3. 2 Ͱड़΂ͨϑΟϧλϦϯάͷୈ 3 ͷϧʔϧʹ͓͚Δਫ਼ࠪͱ‫͕͍ͨͯ͠ࢉܭ‬ɺΫϥελϦϯάΛߦ͏͜ͱʹΑͬͯɺΫϥε͸ɺϊʔυ ep ʹ‫·ؚ‬ΕΔ͢΂ͯͷσʔλʹ͍֤ͭͯ q ∈ Q ͱλ͝ͱͷԼքҎԼͷσʔλΛ߹‫ͨ͠ܭ‬΋ͷΛ࠷௿ϥϯΫͱͯ͠ͷείΞΛ‫͢ࢉܭ‬Δ͜ͱͰ͋ΔɻͦͷͨΊɺ‫͢ূݕ‬Δ΂͖ϊʔѻ͏͜ͱ͕Ͱ͖ɺ‫ݩ‬ͷԼքͷσʔλΑΓ΋େ͖͘ͳΔ (ਤதͷυ͕૿͑Ε͹૿͑Δ΄Ͳ‫͑૿͕ྔࢉܭ‬Δ͜ͱͱͳΔɻ‫͢ূݕ‬Δബփ৭ͷྖҬ)ɻ͜ΕʹΑͬͯɺTPM ʹ͓͚Δ minRank ͱͷ΂͖ϊʔυ͕૿͑Δ‫ݪ‬Ҽͱͯ͠ɺΫΤϦ͕ਤ 2a ͷΑ͏ʹɺۭൺֱ൑ఆʹ͓͍ͯ‫ݩ‬ͷख๏ΑΓ΋ૣ‫ʹظ‬໦ߏ଄ͷ୳ࡧΛࢭΊɺ্ؒʹେ͖͘෼ࢄ͍ͯ͠Δ৔߹͕ߟ͑ΒΕΔɻ‫ط‬ଘͷख๏Ͱ͸ɺ‫ྔࢉܭ‬Λ࡟‫͢ݮ‬Δ͜ͱ͕Ͱ͖Δɻৄ͍͠ΞϧΰϦζϜͷઆ໌͸ɺ͜ͷΑ͏ͳ৔߹ʹ‫͕ྔࢉܭ‬େ෯ʹ૿͑ͯ͠·͏ͱ͍͏໰୊఺Λ

4. 2 અͷ CARank-P ΞϧΰϦζϜͰߦ͏ɻ

๊͍͑ͯΔɻͦ͜Ͱɺຊ‫Ͱڀݚ‬͸ΫΤϦΛΫϥελϦϯά͢Δ͜ͱʹΑͬͯ‫ط‬ଘͷख๏Λ༻͍ͯ΋ɺ‫ྔࢉܭ‬Λ࡟‫͢ݮ‬Δ͜ͱͷͰ͖Δख๏ΛఏҊ͢Δɻ

4. ఏ Ҋ ख ๏͜͜Ͱ͸ɺΫΤϦΛΫϥελϦϯά͢Δ͜ͱʹΑΔ TPM ͷॲཧೳྗͷ޲্ͷ‫ݪ‬ཧΛઆ໌͢Δɻ4. 1 Ͱ͸ɺΫΤϦͷΫϥελϦϯάʹΑΔϑΟϧλϦϯάͷվળͷ‫ݪ‬ཧΛྫΛަ͑ͯઆ໌
͠ɺ4. 2 Ͱ͸ɺఏҊख๏ͷΞϧΰϦζϜͷ঺հ‫ͦͼٴ‬ΕͧΕͷಈ࡞ʹ͍ͭͯৄ͍͠આ໌Λߦ͏ɻ(a) ༩͑ΒΕͨΫΤϦͱͦͷ MBR(b) ‫͢ࢉܭ‬Δ΂͖ؒͷྖҬਤ 2: TPM ʹ͓͚ΔΫΤϦͷ MBR ͱϑΟϧλෆՄೳͳྖҬ

4. 1 Q ͷΫϥελϦϯάʹΑΔϑΟϧλϦϯάͷվળຊख๏Ͱ͸ɺΫΤϦू߹ Q Λෳ਺ͷΫϥελʹ෼ׂ͠ɺͦΕͧΕͷΫϥελʹ͍ͭͯɺ‫ط‬ଘͷޮ཰ԽΛߦ͏ΞϧΰϦζϜͰ
͋Δ TPM Λվྑ͠ɺͦΕΛద༻͢Δ͜ͱͰ͞ΒͳΔޮ཰ԽΛਤΔɻ͜ͷख๏Λ CTPM(Clustered TPM) ͱ‫͢ͱͱ͜Ϳݺ‬Δɻ
ྫͱͯ͠ਤ 2a ͷΑ͏ʹΫΤϦ {q1-q4} ͕༩͑ΒΕͨ৔߹ɺਤ

3a ʹࣔ͢Α͏ʹ̎ͭͷΫϥελ {QC1 , QC2 } ʹΫϥελϦϯά͕Ͱ͖ͨͱ͢Δɻ֤ͦͯ͠Ϋϥελʹ͍ͭͯͦΕͧΕͷ্քͱԼքΛ‫͠ࢉܭ‬ɺ֤ʑͷΫϥελʹରͯ͠ TPM Λ༻͍ͯ ARkR(a) ΫΤϦͷΫϥελϦϯάΛߦͬΛ‫͢ࢉܭ‬Δɻ͜Ε͕ɺຊఏҊख๏ͷ͓͓·͔ͳྲྀΕͰ͋Δɻͨྫ

ຊདྷɺਤ 2a ͷΑ͏ʹΫΤϦͷ MBR ͕େ͖͘޿͕͍ͬͯΔ(b) ‫͢ࢉܭ‬Δ΂͖ؒͷྖҬਤ 3: CTPM ʹ͓͚ΔΫΤϦͷ MBR ͱϑΟϧλෆՄೳͳྖҬঢ়ଶͰ͸ɺ͜ͷ MBR ͷ্ք (Q.up) ͱԼք (Q.low) ͷ఺͔ΒϢʔβ ui ʹਨઢΛҾ͍ͨ৔߹ͷؒͷۭؒ (ਤ 2b) ʹଘࡏ͢Δσʔλ p ʹ͍ͭͯ͸ஞ࣍‫ࢉܭ‬ΛߦΘͳ͚Ε͹ͳΒͳ͔ͬͨɻ͠
͔͠ɺਤ 3a ͷΑ͏ʹΫΤϦΛΫϥελϦϯά͢Δ͜ͱʹΑͬ
ͯɺਤ 3b ʹࣔ͢Α͏ʹɺ֤Ϋϥελʹ͓͍ͯͷ্ք‫ͼٴ‬Լքͷ఺ͰॲཧΛ෼͚Δ͜ͱ͕ՄೳʹͳΔͨΊɺ‫͢ࢉܭ‬Δ΂͖ؒͷྖҬ͕ TPM ʹൺ΂ͯখ͘͞ͳ͍ͬͯΔ͜ͱ͕Θ͔Δ (ਤதͷփ৭ͷྖҬ)ɻҎ্ͷཧ༝ʹΑΓɺTPM Λ༻͍ͨࡍʹ‫͕ࢉܭ‬ඞਢͰ্͋ͬͨքͱԼքͷؒͷۭؒʹଘࡏ͢Δσʔλ p ͱͷ‫ࢉܭ‬Λ CTPM Ͱ͸େ෯ʹ࡟‫͖Ͱݮ‬Δ͜ͱ͕‫͑ݴ‬Δɻৄ͍͠ΞϧΰϦζϜͷઆ໌͸ɺ4. 2 અͷ CTPM ΞϧΰϦζϜͰߦ͏ɻਤ 4: ΫϥελϦϯάʹΑΔ minRank ͷ൑ఆʹ༻͍ΒΕΔ࠷௿ϥϯΫͷ෯ͷ޿͕Γ

4. 2 CTPM ΞϧΰϦζϜߋʹɺΫϥελ͝ͱʹ‫ݟ‬Δͱɺ্քҎ্ͷ఺ɺ͋Δ͍͸Լք

CARank-P ΞϧΰϦζϜ: ΞϧΰϦζϜ 1 ʹࣔ͢Α͏ʹɺҎԼͷ఺΋૿͑ΔͨΊɺϑΟϧλϦϯάՄೳͳྖҬΛ૿΍͢͜ೖྗͱͯ͠ P, u, QC , minRank ͕༩͑ΒΕͨ࣌ɺCARank-Pͱ͕Ͱ͖ɺ‫ྔࢉܭ‬Λ‫ݮ‬Β͢͜ͱ͕Ͱ͖Δɻ·ͨɺTPM ͷઅͰΞϧΰϦζϜ͸ɺશΫϥελ QC ʹ‫·ؚ‬ΕΔΫΤϦʹର͢Δू৮Εͨ minRank ͱͷ൑ఆΛૣΊʹߦ͏͜ͱ΋ՄೳͱͳΔɻͳ໿ϥϯΫ CARank ͕ minRank ΑΓ΋খ͍͔͞Λ֬ೝ͢ΔɻͥͳΒ͹ɺminRank ͱൺֱ͞ΕΔ‫ࢉܭ‬தͷϥϯΫ͕Ϋϥελͦͯ͠ɺCARank(u, QC ) < minRank ͕੒ཱ͢Δ৔߹ɺQCͷԼք͕޿͕Δ͜ͱʹΑͬͯɺΑΓૣ͘େ͖͘‫ੵݟ‬΋Δ͜ͱ͕ͷू໿ϥϯΫΛฦ͢ɻ·ͨɺೖྗͱͯ͠༩͑ΒΕΔ P ͸ࣄલʹͰ͖Δ͔ΒͰ͋ΔɻྫΛ༻͍ͯઆ໌͢ΔɻR ໦ʹΑͬͯΠϯσΫγϯά͞Ε͍ͯΔ΋ͷͱ͢Δɻ͜ͷΞϧਤ 4 ʹࣔ͢Α͏ʹɺΫϥελ͕ 2 ͭʹ෼͚ΒΕ͍ͯΔ৔߹ɺ֤ΫϥελͷԼքʹ͋Δσʔλ p ͷ߹‫ܭ‬஋͕ΫΤϦू߹ͷ࠷௿ϥϯΫʹؔΘΔ (ਤதͷಷ৭ͷྖҬ)ɻͦͷͨΊɺ‫ݩ‬ͷख๏Ͱ͸ΰϦζϜͰ͸ R ໦ͷΤϯτϦʔ (ep ) Λ༻͍ͯɺ֤ MBR ʹ͍ͭͯϑΟϧλϦϯάΛߦ͏ɻ

Algorithm 1 CARank-P͸ɺৗʹ minRank ͱͷൺֱΛߦ͍ɺrnk >= minRank ͱͳͬ

Input: P, u, QC , minRank

ͨ৔߹ɺ−1 Λฦͦ͠ͷ࣌఺Ͱ‫ࢉܭ‬Λऴྃ͢Δɻ͜Ε͸ɺu ͕

Output: rnk; If u is included (−1 otherwise);
1: rnk ⇐ 0, Cand ⇐ ∅2: heapP.enqueue(RtreeP.Root())
3: while heapP.isN otEmpty() do
4:5:

ep ⇐ heapP.dequeue()if ep is non-leaf node

foreach qC ∈ QC do

6:

if ep is under qC

7:

rnk ⇐ rnk + ep .size() × |qC |> minRank
if rnk =8:
9:return -1

10:

end if

11:

else if (ep overlaps qC ) and (ep .children() ̸∈ heapP )12:

heapP.enqueue(ep .children())

13:Ϋ஋Λ minRank ͱͯ͠อ࣋͢Δɻ(1,2 ߦ໨) ࣍ʹɺk-means๏Λ༻͍ͯ Q ΛΫϥελϦϯά͠ɺ֤ u ∈ (U − ࠷ॳʹ༻͍ͨ k ‫ݸ‬ͷཁૉ) ʹରͯ͠ू໿ϥϯΫ rnk Λઌ΄Ͳͷ CARank-PΞϧΰϦζϜΛ༻͍ͯ‫͢ࢉܭ‬Δɻ(3,4,5 ߦ໨) ΋͠ɺrnk ͕ −1Ͱͳ͚Ε͹‫ࢉܭ‬ର৅ͷ u ͸ ARkR ΫΤϦͷղީิͰ͋ΔͷͰheap Λߋ৽͢Δɻ(7 ߦ໨) ߋ৽͞Εͨ heap ͷ k ൪໨ͷϥϯΫͷղू߹ͱͳ͍ͬͯΔ heap Λฦ͢ɻ(9 ߦ໨)

if ep is a leaf node
foreach qC ∈ QC do
if ep is under qC

rnk ⇐ rnk + |qC |if rnk >= minRank

20:
21:

return -1

22:

end if

23:

else

24:

foreach qi ∈ qC do

25:

if f (qi , u) > f (ep , u)26:

rnk ⇐ rnk + 1

27:

end if

28:

end foreach29:

end if30:

32:

u ͱͦΕΒͷ Q ʹର͢Δू໿ϥϯΫͰॳ‫ظ‬Խ͠ɺk ൪໨ͷϥϯ

͏ɻ(4,8 ߦ໨) ͢΂ͯͷ‫͕ࢉܭ‬ऴྃͨ࣌͠఺ͰɺARkR ΫΤϦ

17:

end foreach31:

ର͢Δ ARkR ͷղΛग़ྗ͢Δɻ·ͣɺղީิͷ heap Λ k ‫ݸ‬ͷend foreachend if

19:

CTPM ΞϧΰϦζϜ: CTPM ΞϧΰϦζϜ͸ɺΞϧΰϦζ
Ϝ 2 ʹࣔ͢௨ΓɺP, U, Q Λೖྗͱͯ͠ड͚औΓɺΫΤϦ Q ʹ஋Λ minRank ʹ୅ೖ͠ɺҎ֤߱ u ʹର͠‫܁‬Γฦ͠‫ࢉܭ‬Λߦ

16:

18:

͸ɺrnk Λू໿ϥϯΫ஋ͱͯ͠ฦ͢ɻ

end if

14:
15:

ARkR ͷղͰͳ͍͜ͱΛࣔ͢ɻ‫ʹٯ‬ɺrnk <= minRank ͷ৔߹

end if

33: end while

Algorithm 2 Clustered Tree-Pruning Method (CTPM)
Input: P, U, Q
Output: result set heap
1: initialize heap with first k weighting vectors and aggregate

ranks of Q
2: minRank ⇐ heap.lastRank
3: QC ⇐ KM eans(Q)4: foreach u ∈ U − {first k element in U } do
5:
6:
7:
8:
9:rnk ⇐ ARank-P(P, u, QC , minRank)
if rnk =| −1

heap.insert(u, rnk)
minRank ⇐ heap.lastRank

end if

10: end foreach
11: return heap

34: if rnk <= minRank
35:

return rnk

36: else
37:

return -1

38: end if

5. ࣮‫ݧ‬ɾߟ࡯࣮ࡍʹɺ༩͑ΒΕͨΫΤϦΛΫϥελϦϯά͢Δ͜ͱʹΑͬͯ ARkR ͷ‫্͍ͯ͠޲͕཰ޮࡧݕ‬Δ͔Λ‫͢ূݕ‬ΔͨΊɺ্‫ه‬

1 ߦ໨ʹࣔ͢ rnk ͸ɺશΫϥελ QC ͷू໿ϥϯΫ CARankͷΞϧΰϦζϜΛ΋ͱʹ࣮‫ݧ‬Λߦͬͨɻ5. 1 અͰ͸ɺ࣮‫༻ʹݧ‬ͷҰ࣌Χ΢ϯλʔͱͯ͠༻͍Δม਺Ͱ͋Δɻ࣍ʹɺΞϧΰϦζ͍ͨϚγϯͷੑೳͱσʔλʹ͍ͭͯઆ໌͠ɺ5. 2 અͰ͸ɺ࣮‫ݧ‬Ϝ͸ R ໦ʹ֨ೲ͞Ε͍ͯΔ P ͷ root ͔Βஞ࣍తʹΤϯτϦʔ݁ՌΛఏࣔ͠ɺͦΕͧΕύϥϝʔλΛมߋͨ͠৔߹ʹ͍ͭͯߟep Λ heapP ʹૠೖ͠ɺep ͕༿ϊʔυ͔൱͔ͰॲཧΛ෼͚Δ࡯Λड़΂Δɻ

(2,3,4,5,18 ߦ໨)ɻ ͔͜͜Β֤ΫΤϦΫϥελ qC ∈ QC ʹͭ

5. 1 ࣮‫ڥ؀ݧ‬ɾઃఆ͍ͯɺep ͕༿ϊʔυͰͳ͍৔߹ɺep ͷ্ք͕ qC ͷԼքΑΓ΋ຊ࣮‫ݧ‬͸ɺଟ༷ͳσʔληοτʹରͯ͠ɺTPM ͱ CTPM

খ͘͞ͳΔ͔Λௐ΂ɺখ͍͞৔߹͸ rnk ʹ ep ʹ‫·ؚ‬ΕΔσʔΞϧΰϦζϜΛ༻͍ͨࡍͷॲཧ࣌ؒΛൺֱ͢Δɻ༻͍ͨϚγϯλ਺ΛՃࢉ͠ɺͦ͏Ͱͳ͍৔߹͸ɺep ͷࢠϊʔυΛ heapP ʹ͸ɺCPU: 2.6GHz Intel Core i7ɺ RAM:16GB ͷ Mac ͰɺΞૠೖ͢Δ (7,8,13,14 ߦ໨)ɻep ͕༿ϊʔυͷ৔߹ɺep ͷ্ք͕ϧΰϦζϜͷ࣮૷‫ޠݴ‬͸૒ํͱ΋ C++Ͱ͋ΔɻqC ͷԼքΑΓ΋খ͘͞ͳΔ৔߹͸ rnk ʹΫϥελ qC ʹ‫·ؚ‬Ε߹੒σʔλͷΫΤϦσʔλ Q ͸ɺΫϥελ (CL) ʹैͬͯੜΔΫϥελ਺ΛՃࢉ͠ɺͦ͏Ͱͳ͍৔߹͸ɺ֤ΫΤϦ qi ∈ qC੒͞ΕɺΫΤϦσʔλͷΫϥελϦϯάʹ͸ɺk-means ๏Λ༻"͍ɺΫϥελ਺͸ 3 |Q| ʹै͏΋ͷͱ͢Δɻ߹੒σʔλͷ঎ʹ͍ͭͯ qi ͱ uɺep ͱ u ͷείΞΛஞ࣍ൺֱ͠ɺrnk Λߋ৽͢Δ (18-33 ߦ໨)ɻ͍ͣΕͷ৔߹ʹ͓͍ͯ΋ rnk Λߋ৽͢Δࡍ඼σʔλ P ͓ΑͼϢʔβͷ޷Έͷσʔλ U ͸ɺਓ‫ޱ‬σʔλΛ༻͍Ұ༷෼෍ (UN) ‫ͼٴ‬Ϋϥελ (CL) ʹैͬͯੜ੒͞ΕΔ΋Ͱ͸େ͖͘ॲཧ͕࣌ؒ૿͍͑ͯͳ͍ͱ͍͏݁Ռ͸ɺ߹੒σʔλͷͱ͢Δɻ‫ط‬ఆ஋͸ɺ |Q| = 20, |P | = |U | = 100k, ύϥϝʔͷ৔߹Ͱ΋‫ݟ‬ΒΕͨ܏޲Ͱ͋Γɺ͖ͪΜͱ࣮σʔλʹ͓͍ͯ΋

λ k = 10, ࣍‫ ਺ݩ‬d = 3 ͱ͢Δɻಉ༷ͷ݁Ռ͕ಘΒΕ͍ͯΔ͜ͱ͕Θ͔Δɻ࣮σʔλͰͷ࣮‫ݧ‬͸ɺ1949 ೥͔Β 2009 ೥·Ͱͷ 20960 ͷNBA બखͷσʔλΛ༻͍ͯɺͦΕΒͷબखͷதͰΫΤϦͰ༩͑ΒΕͨબखͷ૊Έ߹Θͤʹ͍ͭͯɺଞͷϢʔβΑΓ΋͜ͷ૊Έ߹ΘͤΛ޷Ή্Ґ 10 ਓͷϢʔβ͸୭͔ͱ͍͏໰͍߹ΘͤΛߦ͏ɻબखͷσʔλ͸ɺͦΕͧΕͷબखͷಘ఺਺ɺϦό΢ϯυ
਺ɺΞγετ਺ɺϒϩοΫ਺ɺͦͯ͠εςΟʔϧ਺ͷ̑࣍‫͔ݩ‬ΒͳΔɻΫΤϦͰ༩͑ΒΕΔબखͷ૊Έ߹Θͤ͸બखσʔλͷத͔Βແ࡞ҝͰબ͹ΕΔ΋ͷͱ͢ΔɻϢʔβ U ͸߹੒σʔλͱಉ༷ͷํ๏Ͱੜ੒͢Δɻ‫ط‬ఆ஋͸ɺ|P | = 20960, |U | = 100k, ύ(a) |Q|, UN(b) |P |&|U |, UN(c) k, UN(d) d, UNϥϝʔλ k = 10, ࣍‫ ਺ݩ‬d = 5 ͱ͢Δɻ࣮‫Ͱݧ‬͸ɺಉ͡σʔληοτʹରͯ͠ 100 ճΞϧΰϦζϜΛ࣮ߦͨ͠ࡍͷॲཧ࣌ؒͷฏ‫ۉ‬஋Λɺ࠷ऴతͳॲཧ࣌ؒͱͯ͠ѻ͏ɻҰ༷෼෍ͷ߹੒σʔλʹ͍ͭͯύϥϝʔλ Q, P ͱ U, k, dͷ஋Λม͑ͨ৔߹ʹ͓͚ΔɺTPM ͱ CTPM ΞϧΰϦζϜͷॲཧ࣌ؒɺΫϥελͷ߹੒σʔλʹ͍ͭͯ͸ d Λม͑ͨ৔߹ΛҰ༷෼෍ͷσʔλʹ͍ͭͯൺֱΛߦ͏ɻ࣮σʔλʹ͍ͭͯ͸ɺਤ 5: Ұ༷෼෍Ͱੜ੒͞Εͨσʔλʹ͓͍ͯɺ֤ύϥϝʔλΛΫΤϦ਺ |Q| Λม͑ͨ৔߹ʹ͓͚Δ TPM ͱ CTPM ΞϧΰϦมߋͨ͠৔߹ͷॲཧ࣌ؒͷมԽɻ‫ط‬ఆ஋͸ɺ|Q| = 20, |P | =ζϜͷॲཧ࣌ؒʹ͍ͭͯൺֱΛߦ͏ɻ

5. 2 ࣮‫݁ݧ‬Ռɾߟ࡯|U | = 100k, k = 10, d = 3ɻ߹੒σʔλΛ༻͍࣮ͨ‫ݧ‬: ਤ 5 ͸ɺҰ༷෼෍ (UN) Ͱੜ੒͞Εͨਓ‫ޱ‬σʔλʹରͯ͠ಛఆͷ஋Λม͑ͯॲཧ࣌ؒΛ‫ܭ‬ଌͨ݁͠ՌΛࣔͨ͠΋ͷͰ͋ΔɻTPM ͷॲཧ࣌ؒ͸ബ͍փ৭Ͱɺ

CTPM ͷॲཧ࣌ؒ͸ೱ͍փ৭Ͱࣔ͞Ε͍ͯΔɻͲͷΑ͏ͳঢ়‫ʹگ‬ରͯ͠΋ɺCTPM ͕ TPM ΑΓ΋ॲཧ͕࣌ؒૣ͘ͳ͍ͬͯΔ͜ͱ͕Θ͔Δɻ͜ͷதͰ஫໨͢Δ΂͖͸ਤ 5a ʹ͓͍ͯɺΫΤϦ਺ |Q| ͕૿͑ͨ৔߹ʹ͓͍ͯ΋ɺCTPM ͸ TPM ʹൺ(a) d, UN(b) d, CL΂ͯେ͖͘ॲཧ࣌ؒΛ཈͑Δ͜ͱ͕Ͱ͖͍ͯΔ͜ͱͰ͋Δɻ͜ਤ 6: Ұ༷෼෍ͱΫϥελͰੜ੒͞Εͨσʔλʹ͓͚ΔɺॲཧΕ͸ɺΫϥελϦϯάʹΑͬͯϑΟϧλྖҬΛ૿΍͢͜ͱ͕Ͱ࣌ؒͷมԽ͖ͨ݁ՌͰ͋Δͱߟ͑Δ͜ͱ͕Ͱ͖Δɻ5b ͸ɺσʔλ਺ͷมԽʹΑΔॲཧ࣌ؒͷมԽΛද͍ͯ͠Δɻσʔλ਺ͷ૿Ճʹରͯ͠͸ɺTPM ΋ CTPM ΋ॲཧ࣌ؒ΋૿Ճ͍ͯ͠Δ͜ͱ͕Θ͔Δɻਤ 5c ͷύϥϝʔλ k ͷมԽʹ͍ͭͯ͸ɺheap ͷαΠζ͕
େ͖͘ͳΔ͚ͩͰ͋ΔͷͰɺTPM ΋ CTPM ʹ΋େ͖ͳมԽ
͸‫ݱ‬Ε͍ͯͳ͍ɻਤ 5d ͷ࣍‫਺ݩ‬ͷ૿Ճʹରͯ͠͸ɺCTPM ͸TPM ͱ࣍‫ʹ਺ݩ‬ର͢Δॲཧͷ࢓ํʹ͕ࠩͳ͍ͨΊ࣍‫਺ݩ‬ͷ૿Ճʹରͯ͠͸ TPM ΑΓ΋ॲཧ࣌ؒ͸཈͑Δ͜ͱ͕Ͱ͖͍ͯΔ͕ɺ૿͑ํͱͯ͠͸มԽ͕ͳ͍͜ͱ͕Θ͔Δɻਤ 6 ͸ɺҰ༷෼෍ (ਤ 6a) ͱΫϥελ (ਤ 6b) Ͱੜ੒͞Εͨ߹੒σʔλʹ͍ͭͯ࣍‫਺ݩ‬Λม͑ͨ৔߹ͷ݁Ռʹ͍ͭͯࣔͨ͠ਤͰ͋Δɻશମతʹ͸ΫϥελͰੜ੒͞Εͨσʔλͷํ͕Ұ༷ਤ 7: ࣮σʔλʹ͓͍ͯΫΤϦ਺ |Q| Λม͑ͨ৔߹ʹ͓͚Δॲཧ࣌ؒͷมԽ෼෍ΑΓ΋ૣ͘ͳ͍ͬͯΔ͜ͱ͕Θ͔Δɻ͜Ε͸ɺΫϥελͰੜ੒͞Εͨσʔλͷํ͕ɺR ໦ʹΑͬͯΠϯσΫγϯά͞Ε΍͘͢ͳ͍ͬͯΔ͜ͱ͕‫ݪ‬ҼͰ͋Δͱߟ͑Δ͜ͱ͕Ͱ͖Δɻ࣮σʔλΛ༻͍࣮ͨ‫ݧ‬: ਤ 7 ͸ɺ࣮σʔλʹ͍ͭͯΫΤϦ਺Λม͑ͯॲཧ࣌ؒΛ‫ܭ‬ଌͨ݁͠ՌΛ TPM ͱ CTPM ʹ͍ͭͯࣔͨ͠ਤͰ͋Δɻ࣮σʔλʹ͍ͭͯ΋ɺCTPM ͸ TPM ΑΓ΋ૣ͘ͳ͍ͬͯΔ͜ͱ͕Θ͔ΔɻΫΤϦ਺͕૿͑ͯ΋ CTPM

6. ݁࿦ຊ‫Ͱڀݚ‬͸ɺ‫ط‬ଘͷ ARkR ͷޮ཰ԽΛߦ͏ख๏ʹ͓͍ͯಛఆͷΫΤϦͷ෼෍ʹ͓͍ͯޮՌΛൃ‫ͱ͍͜ͳ͖Ͱش‬Λࣔ͠ɺͦͷ໰୊఺Λղফ͢ΔͨΊʹΫΤϦΛΫϥελϦϯάͯ͠‫ط‬ଘͷख๏Λద༻͢Δͱ͍͏ఏҊΛߦͬͨɻ͜ͷఏҊΛ΋ͱʹ࣮‫ݧ‬Λߦ͍ɺ‫ط‬ଘͷख๏Λ༻͍ͨ ARkR ΛΑΓޮ཰తʹ‫͖Ͱࢉܭ‬ΔΑ͏ʹվྑ͢Δ͜ͱ͕Ͱ͖ͨɻࠓ‫ޙ‬ͷ՝୊ͱͯ͠ɺ‫ط‬ଘͷΞϧΰϦζϜΛద༻͢Δࡍʹ༗ޮͳΫϥελϦϯάΛͲͷΑ͏ʹͯ͠ߦ͏͔Λ‫ݕ‬౼͢Δඞཁ͕͋Δɻ·ͨɺ࣍‫͕͞਺ݩ‬Βʹେ͖͘ͳͬͨ৔߹ʹɺޮ཰తʹॲཧͰ͖ΔΑ͏ͳख๏Λߟ͑Δඞཁ͕͋Δɻ͜ΕΒͷ՝୊Λղܾ͠ɺARkR Λ͞Βʹޮ཰Խ͢Δ͜ͱΛ໨ࢦͯ͠Ώ͘ɻจ‫ݙ‬[1] Vlachou, A., Doulkeridis, C., Kotidis, Y., et al.: Reversetop-k queries. In: ICDE, pp. 365-376 (2010)[2] Zhang, Z., Jin, C., Kang, Q.: Reverse k-ranks query.
PVLDB 7(10), 785-796 (2014)[3] Y. Dong, H. Chen, K. Furuse, and H. Kitagawa. Aggregate
Reverse Rank Queries LNCS, 9828:87-101 (DEXA 2016)[4] Vlachou, A., Doulkeridis, C. , Kotidis, Y., et al.: Monochromatic and bichromatic reverse top-k queries, pp. 1215-1229(2011)[5] Vlachou, A., Doulkeridis, C., Kotidis, Y., et al.: Branchand-bound algorithm for reverse top-k queries. In: SIGMOD Conference, pp. 481-492 (2013)[6] Vlachou, A., Doulkeridis, C., Kotidis, Y.: Identifying themost influential data objects with reverse top-k queries, pp.
364-372 (2010)[7] Vlachou, A., Doulkeridis, C., et al.: Monitoring reverse topk queries over mobile devices. In: MobiDE, pp. 17-24 (2011)[8] Antonin Guttman, R-trees: a dynamic index structure forspatial searching, Proceedings of the 1984 ACM SIGMOD
international conference on Management of data, June 1821, 1984, Boston, Massachusetts