転置インデックスでどう検索しているか

1. 2020/11/19 @kotaroooo0 సஔΠϯσοΫεͰ Ͳ͏ݕࡧ͍ͯ͠Δ͔
2. ࣗݾ঺հ
3. సஔΠϯσοΫεɺ΋ͪΖΜ஌ͬͯΔΑ? grepΈͨ͘ஞ࣍ݕࡧͯ͠ΔͱΊͪΌͪ͘Ό͕͔͔࣌ؒΔ͔ ΒɺݕࡧΛૣ͘͢ΔͨΊʹࣄલʹຊͷ໨࣍Έ͍ͨͳ΋ͷΛ ࡞͓ͬͯ͘ΜͰ͠ΐ? Ͱ΋ɺͲ͏΍ͬͯݕࡧ͍ͯ͠Δ͔·Ͱ͸… ૝ఆฉ͖ख
4. సஔΠϯσοΫεΛ ஌Δ
5. సஔΠϯσοΫε netflix prime amazon - సஔΠϯσοΫε = ࣙॻ + సஔϦετ 1 1 2 3 4 5 5 ࣙॻ సஔϦετ ϙεςΟϯάϦετ
6. సஔΠϯσοΫε netflix prime amazon - Word-level inverted list ͱݺ͹Εɺ୯ޠ͕จॻͷԿ୯ޠ໨͔อଘ͢Δ͜ͱ΋͋Δ - DocID;offset1,ofset2… 1;2 1;3 2;3 3;5 4;1 5;2 5;3 2;5
7. ୯ޠͷҐஔ৘ใͳʹʹ࢖͏? - ϑϨʔζΛ୳͢৔߹ - ʮAmazon Primeʯͱݕࡧͨ͠৔߹ - D1: “a prime concern of Amazon” - D2: “Amazon Prime movies” - Ґஔ৘ใ͕͋Ε͹୯ޠͷॱংΛߟྀ͢Δ͜ͱ͕Ͱ͖ΔͷͰɺD2ͷΈΛώοτ͞ ͤΔ͜ͱ͕Ͱ͖ͨΓɺD2ͷείΞΛେ͖ͨ͘͠Γ͢Δ͜ͱ͕Ͱ͖Δ
8. ݕࡧ͢Δ
9. ANDݕࡧͱORݕࡧ -ΫΤϦ: “pink orange blue” -ANDݕࡧ: 3 -ORݕࡧ: 1,2,3,4,5,6 pink Orange blue 6 3 4 5 2 1
10. φΠʔϒͳݕࡧઓུ - ϙεςΟϯάϦετΛ૸ࠪ͢Δํࣜ - TAAT(Term At A Time) - ϙεςΟϯάϦετΛ̍ͭͣͭॲཧ͢Δɻಉ࣌ʹ։͘ϙεςΟϯάϦετͷΧʔι ϧ͸͚̍ͭͩɻ - ୯ޠ͝ͱʹ૸ࠪ͢Δ - DAAT(Document At A Time) - શ୯ޠͷϙεςΟϯάϦετΛಉ࣌ʹॲཧ͢ΔɻΫΤϦʹؚ·ΕΔ୯ޠͷϙε ςΟϯάϦετͷΧʔιϧΛ͢΂ͯ։͖ɼಉ࣌ʹਐΊ͍ͯ͘ɻ - υΩϡϝϯτ͝ͱʹ૸ࠪ͢Δ
11. TAATͰͷANDݕࡧ 1. ϙεςΟϯάϦετͷαΠζ͕࠷খͷ΋ͷ(prime)Λબ୒͠ΛɺAccumulator࡞੒ [2, 5] 2. amazonͷϦετΛ૸ࠪ ɾ2͸ؚ·Ε͍ͯΔ͔?5͸ؚ·Ε͍ͯΔ͔?ͷΈͷνΣοΫͰOK netflix prime amazon 1;2 1;3 2;3 4;1 5;2 5;3 2;5
12. TAATͰͷORݕࡧ 1. ͲͷΩʔͰ΋ྑ͍ͷͰAccumlatorΛ࡞੒ [1,2,5] (amazon) 2. ॏෳ͠ͳ͍શͯͷΩʔΛݟͯϚʔδ ✌(‘ω'✌ ) ݪ࢝త ( ✌'ω')✌ netflix prime amazon 1;2 1;3 2;3 4;1 5;2 5;3 2;5
13. DAATͰͷANDݕࡧ - Amazon AND prime - Accumulated = [] netflix prime amazon 1;2 1;3 2;3 4;1 5;2 5;3 2;5
14. DAATͰͷANDݕࡧ - Amazon AND prime - Accumulater = [2] netflix prime amazon 1;2 1;3 2;3 4;1 5;2 5;3 2;5
15. DAATͰͷANDݕࡧ - Amazon AND prime - Accumulate = [2, 5] netflix prime amazon 1;2 1;3 2;3 4;1 5;2 5;3 2;5
16. DAATͰͷORݕࡧ - ΧʔιϧΛಈ͔ͯ͠ɺશͯͷཁૉΛॏෳͳ͘Accumulatorʹ௥Ճ ✌(‘ω'✌ ) ݪ࢝త ( ✌'ω')✌ netflix prime amazon 1;2 1;3 2;3 4;1 5;2 5;3 2;5
17. DAATͱTAAT - DAATͷϝϦοτ - DAATͷํ͕ɺলϝϞϦͰࡁΉ(ྫ: τοϓ10݅ݕࡧ) - DAATͷํ͕ɺΫΤϦ༻ޠ͕จॻ಺ͷಛఆͷ৚݅Λຬ͍ͨͯ͠Δ͔Ͳ͏͔Λ؆୯ʹࣝ ผͰ͖Δ(ྫ: ϑϨʔζݕࡧɺϑΟϧλϦϯά) - ElasticsearchͰར༻͞Ε͍ͯΔLucene͸DAATํࣜ - ORݕࡧ͸ݪ࢝తͳ࢓૊ΈͰ͋ΓɺANDݕࡧΑΓ΋ଟ͘ͷυΩϡϝϯτΛ૸ࠪ͢ΔͨΊɺ ॏ͍ͨ - ݕࡧΤϯδϯ͸ORݕࡧʹ࠷దԽ͞Ε͍ͯΔ
18. ORݕࡧͷ ࠷దԽ४උ
19. Ͳ͏ߴ଎Խ͢Δ͔ - DAATΛϕʔεʹվળ͢Δ - ݕࡧ݁Ռ্͕Ґ਺͚݅ͩඞཁͰ͋Δ͹ɺ্ҐʹདྷΔՄೳੑ͕ͳ͍จষͷධՁΛεΩοϓ ͢Δ͜ͱʹΑΓɺॲཧͷߴ଎Խ͕Մೳ - ໰͍߹Θͤʹର্ͯ͠Ґk݅ͷΈΛऔΓग़͢͜ͱΛtop-k query processingͱݺͿ
20. จষͷϥϯΫ෇͚ - ্Ґk݅Λग़ྗ͢ΔͨΊʹɺΫΤϦʹରͯ͠ͲͷจষͷॱҐ͕ߴ͍͔Λܾఆ͢Δඞཁ͕͋ Δ - TF-IDF, Okapi BM25
21. సஔΠϯσοΫεͷ֦ு - సஔΠϯσοΫεʹରͯ͠ɺ֤୯ޠͷείΞ࠷େ஋ͱυΩϡϝϯτ͝ͱͷ୯ޠͷείΞ Λ෇༩͢Δ - ܗࣜ DocID;Score netflix prime amazon 1;5 1;3 2;1 3;2 4;1 5;2 5;1 2;3 max_score=5 max_score=3 max_score=2
22. Top-k Query ɾmax-score ɾinterval-based running
23. max-score - ্ҐkҐʹೖΔͨΊͷείΞ5ඞཁͱ͢Δͱɺ”amazon”,”prime”ͷmax_score͸5ະຬͳͷ Ͱɺ”amazon”ͷΈ”prime”ͷΈΛؚΉจষ͸ީิ͔Β֎ΕΔ netflix prime amazon max_score=5 max_score=3 max_score=2 1;5 1;1 2;1 4;1 5;1 2;3 5;2 5;1 3;3
24. max-score - ্Ґ1݅Λऔಘ͍ͨ͠ - จॻ1: score6 - ඞͣ”netflix”ΛؚΉυΩϡϝϯτ͡Όͳ͍ͱμϝ netflix prime amazon max_score=5 max_score=3 max_score=2 1;5 1;1 2;1 4;1 5;1 2;3 5;2 5;1 3;3
25. max-score - “netflix”ΛؚΉจॻ5·ͰΧʔιϧΛඈ͹͢ - จॻ5͸είΞ4 - จॻ1,5ͷΈΛධՁ͢Δ͚ͩͰऴྃ netflix prime amazon max_score=5 max_score=3 max_score=2 1;5 1;1 2;1 4;1 2;3 5;2 3;3 5;1 5;1
26. Interval-base - max_scoreΑΓ͞ΒʹεΩοϓͰ͖Δ - ͕͜͜Β΁ΜͰྗਚ͖ͨ࣌ؒ͠΋ͪΐ͏Ͳ͍͍ͩΖ͏…
27. LuceneͰ͸ - Lucent 8Ͱ͸max-scoreͷൃలܗͰ͋ΔWAND͕࢖ΘΕ͍ͯ·͢ - Ding, Shuai, and Torsten Suel. "Faster top-k document retrieval using block-max indexes." Proceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval. 2011. - 2019/3/14ϦϦʔεͷLucene 8Ͱ্ͷΞϧΰϦζϜ͕࣮૷͞ΕΔͳͲࠓͰ΋ޮ཰తͳΞϧ ΰϦζϜͷݚڀ͕ଓ͍͍ͯΔ APA
28. సஔΠϯσοΫεͷ ࣮૷
29. ·ͱΊ - సஔΠϯσοΫε͸༷ʑͳϝλ৘ใΛ௥Ճ͢Δ͜ͱͰ֦ு͞ΕΔ(୯ޠͷΦϑηοτɺε ίΞɺϙΠϯλ) - సஔΠϯσοΫεʹରͯ͠ANDݕࡧɺORݕࡧ͢ΔࡍͷφΠʔϒͳํ๏ - TAAT: ୯ޠ͝ͱʹ૸ࠪ͢Δ - DAAT: จॻ͝ͱʹ૸ࠪ͢Δ - DAATʹର͢ΔORݕࡧʹ࠷దԽ - max-score: ୯ޠ͝ͱͷ࠷େείΞͱݱࡏͷ࠷େείΞΛอ࣋͢Δ͜ͱͰࢬמΓΛߦ ͍୳ࡧΛεΩοϓ͢Δ - LuceneͰ͸DAAT͕࠾༻͞Ε͓ͯΓɺݱࡏͰ΋ΞϧΰϦζϜ͕վળ͞Ε͍ͯΔ