Upgrade to Pro — share decks privately, control downloads, hide ads and more …

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

Avatar for kotaroooo0 kotaroooo0
November 19, 2020

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

Avatar for kotaroooo0

kotaroooo0

November 19, 2020
Tweet

More Decks by kotaroooo0

Other Decks in Technology

Transcript

  1. ୯ޠͷҐஔ৘ใͳʹʹ࢖͏? - ϑϨʔζΛ୳͢৔߹ - ʮAmazon Primeʯͱݕࡧͨ͠৔߹ - D1: “a prime

    concern of Amazon” - D2: “Amazon Prime movies” - Ґஔ৘ใ͕͋Ε͹୯ޠͷॱংΛߟྀ͢Δ͜ͱ͕Ͱ͖ΔͷͰɺD2ͷΈΛώοτ͞ ͤΔ͜ͱ͕Ͱ͖ͨΓɺD2ͷείΞΛେ͖ͨ͘͠Γ͢Δ͜ͱ͕Ͱ͖Δ
  2. φΠʔϒͳݕࡧઓུ - ϙεςΟϯάϦετΛ૸ࠪ͢Δํࣜ - TAAT(Term At A Time) - ϙεςΟϯάϦετΛ̍ͭͣͭॲཧ͢Δɻಉ࣌ʹ։͘ϙεςΟϯάϦετͷΧʔι

    ϧ͸͚̍ͭͩɻ - ୯ޠ͝ͱʹ૸ࠪ͢Δ - DAAT(Document At A Time) - શ୯ޠͷϙεςΟϯάϦετΛಉ࣌ʹॲཧ͢ΔɻΫΤϦʹؚ·ΕΔ୯ޠͷϙε ςΟϯάϦετͷΧʔιϧΛ͢΂ͯ։͖ɼಉ࣌ʹਐΊ͍ͯ͘ɻ - υΩϡϝϯτ͝ͱʹ૸ࠪ͢Δ
  3. DAATͰͷANDݕࡧ - Amazon AND prime - Accumulated = [] netflix

    prime amazon 1;2 1;3 2;3 4;1 5;2 5;3 2;5
  4. DAATͰͷANDݕࡧ - Amazon AND prime - Accumulater = [2] netflix

    prime amazon 1;2 1;3 2;3 4;1 5;2 5;3 2;5
  5. 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
  6. DAATͱTAAT - DAATͷϝϦοτ - DAATͷํ͕ɺলϝϞϦͰࡁΉ(ྫ: τοϓ10݅ݕࡧ) - DAATͷํ͕ɺΫΤϦ༻ޠ͕จॻ಺ͷಛఆͷ৚݅Λຬ͍ͨͯ͠Δ͔Ͳ͏͔Λ؆୯ʹࣝ ผͰ͖Δ(ྫ: ϑϨʔζݕࡧɺϑΟϧλϦϯά)

    - ElasticsearchͰར༻͞Ε͍ͯΔLucene͸DAATํࣜ - ORݕࡧ͸ݪ࢝తͳ࢓૊ΈͰ͋ΓɺANDݕࡧΑΓ΋ଟ͘ͷυΩϡϝϯτΛ૸ࠪ͢ΔͨΊɺ ॏ͍ͨ - ݕࡧΤϯδϯ͸ORݕࡧʹ࠷దԽ͞Ε͍ͯΔ
  7. 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
  8. 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
  9. ·ͱΊ - సஔΠϯσοΫε͸༷ʑͳϝλ৘ใΛ௥Ճ͢Δ͜ͱͰ֦ு͞ΕΔ(୯ޠͷΦϑηοτɺε ίΞɺϙΠϯλ) - సஔΠϯσοΫεʹରͯ͠ANDݕࡧɺORݕࡧ͢ΔࡍͷφΠʔϒͳํ๏ - TAAT: ୯ޠ͝ͱʹ૸ࠪ͢Δ -

    DAAT: จॻ͝ͱʹ૸ࠪ͢Δ - DAATʹର͢ΔORݕࡧʹ࠷దԽ - max-score: ୯ޠ͝ͱͷ࠷େείΞͱݱࡏͷ࠷େείΞΛอ࣋͢Δ͜ͱͰࢬמΓΛߦ ͍୳ࡧΛεΩοϓ͢Δ - LuceneͰ͸DAAT͕࠾༻͞Ε͓ͯΓɺݱࡏͰ΋ΞϧΰϦζϜ͕վળ͞Ε͍ͯΔ