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

Research Paper Introduction in IR Reading 2021 ...

Sponsored · Your Podcast. Everywhere. Effortlessly. Share. Educate. Inspire. Entertain. You do you. We'll handle the rest.
Avatar for Takuya Asano Takuya Asano
October 30, 2021

Research Paper Introduction in IR Reading 2021 Fall

PTHash: Revisiting FCH Minimal Perfect Hashing (SIGIR 2021)
https://dl.acm.org/doi/10.1145/3404835.3462849

Avatar for Takuya Asano

Takuya Asano

October 30, 2021
Tweet

More Decks by Takuya Asano

Other Decks in Research

Transcript

  1. ,OPXO.1)'"MHPSJUINT '$) 
 'PY $IFO )FBMUI $POTUSVDUJPOUJNFJTTMPXGPSBTNBMMQBSBNFUFSD -BSHFWBMVFPGDXBTUFTQBDF 7FSZGBTUMPPLVQ $)%

    
 DPNQSFTTFEIBTIBOEEJTQMBDF $POTUSVDUJPOUJNFJTTMPXGPSBMBSHFQBSBNFUFSЕ 4VDDJODU .PTUTMPXMPPLVQJOUIJTMJTU &.1)' & ffi DJFOUDPOTUSVDUJPOVTJOHSBOEPNIZQFSHSBQI 4MPXMPPLVQ (07 4PMWFSBOEPNMJOFBSTZTUFNTUPDPOTUSVDU.1)' 6TF(BVTTJBOFMJNJOBUJPOUPTPMWFJU .PEFSBUFMPPLVQTQFFE ##)BTI 7FSZGBTUDPOTUSVDUJPO .PEFSBUFMPPLVQ *ODSFBTFQBSBNFUFSЍ TQFFEVQDPOTUSVDUJPOBOEMPPLVQUJNF 3FD4QMJU 
 SFDVSTJWFTQMJU 4QMJUUIFLFZTJOUPBUSFFPGCVDLFUTSFDVSTJWFMZ 4VDDJODU WFSZDPNQBDUSFQSFTFOUBUJPO .PEFSBUFTMPXMPPLVQ 1BSBNFUSJ[FECZM CMDLTJ[FPGCVDLFU BOEC CVDLFUBWFSBHFTJ[F UIBUUSBEFTDPOTUSVDUJPO UJNF TQBDF BOEMPPLVQUJNF
  2. .1)'1SPT$POT 1SPT w 4QBDFF ffi DJFOU w /FFEBOBEEJUJPOBMGFXCJUTLFZUPSFQSFTFOU.1) w 'BTUMPPLVQUJNF

    w 0  BOETNBMMDPOTUBOUUJNF OTLFZ  $POT w *NNVUBCMF TUBUJD  w %ZOBNJDDPOTUSVDUJPOPG.1)'JTEJ ff i DVMU w 7FSJGZOFFEFE w 6OBCMFUPEFUFDUJGBLFZFYJTUTPSOPU w /FFEUPTUPSFLFZTJUTFMGGPSWFSJGZJOHLFZT
  3. 15)BTI  3BOEPN%JTQMBDFNFOUCZ903 w 15)BTI͸'$)ͷ4FBSDIJOHεςο ϓΛվྑ w όέοτJͷΩʔYͷϋογϡςʔϒϧ ্ͷҐஔΛܭࢉ͢ΔͷʹҎԼΛ࢖͏ w

    Ϗοτ903ԋࢉ w όέοτ͝ͱͷύϥϝʔλLJΛ୳ࡧ w LJ͸   ʜͱ͍͏ॱ൪Ͱ୳ࡧ w 903ʹΑͬͯΩʔ͕޿͍ൣғʹ෼ࢄ ͢ΔͷͰLJͷظ଴஋͸খ͘͞ͳΔ w Τϯτϩϐʔ͕খ͘͞ͳΓɺΑΓѹ ॖͰ͖Δ
  4. 15)BTI  &ODPEJOH w LJͷΤϯτϩϐʔ͕খ͍͞ͷͰɺࣙॻࣜͷූ߸ԽํࣜΛ࢖͏ͱখ͘͞ͳΔ w LJͷϢχʔΫͳ஋ͷࣙॻΛผʹอଘ w ഑ྻ1͸͜ͷࣙॻ%΁ͷࢀরͷ഑ྻͱͳΔ w

    ࣙॻ%͸े෼খ͘͞ͳΔͷͰɺ$16ͷΩϟογϡʹ৐Δ͜ͱ͕ظ଴Ͱ͖Δ w ݕࡧύϑΥʔϚϯε΁ͷӨڹ͸খ͍͞ w ·ͨɺ͖͞΄ͲͷGSPOUCBDLѹॖͱ΋ซ༻Ͱ͖Δ w ࣙॻࣜූ߸ԽҎ֎ʹ΋&MJBT'BOP΍4JNQMF%FOTF$PEJOH 4%$ ͳͲ΋ߟ͑ΒΕΔ w ѹॖ཰͸ߴ͍͕ݕࡧ͸஗͘ͳΔ
  5. 15)BTI  -JNJUJOHUIF-PBE'BDUPS w ࠷ޙͷ΄͏ͷόέοτͰͷLJͷ୳ࡧ͕஗͍ w ϋογϡςʔϒϧ্ʹ༨৒ͷྖҬΛ֬อ w ͜ͷ༨৒ྖҬʹࣸ૾͞ΕΔΩʔΛϓϩΩγ͢Δ w

    ͜ͷσʔλߏ଄Λ഑ྻGSFFͱͯ͠อଘ w ΞϧΰϦζϜ্ɺ෼ذ͸૿͑Δ͕ɺ͜ͷ༨৒ ྖҬ͸খͯ͘͞ྑ͍ʢOͷ਺ͱ͔ʣͷͰɺ෼ ذ༧ଌ͕΄ͱΜͲ౰ͨΔͨΊݕࡧ଎౓΁ͷӨ ڹ͸খ͍͞
  6. .Z5IPVHIUT w Ωʔ͕࣮֬ʹࣙॻʹೖ͍ͬͯΔ͜ͱ͕Θ͔͍ͬͯΔϢʔεέʔε͸গͳ͍Α͏ʹࢥ͏ w ͢ΔͱΩʔ΍Ωʔ΁ͷΦϑηοτΛผ్อଘ͢Δ͜ͱʹͳΓɺ.1)'͕খ͍͜͞ͱʹΑΔϝϦοτ͕ബΕͯ͠·͏ w ͜Ε͸.1)'ͦͷ΋ͷͷϢʔεέʔεͷ࿩ w ͱ͸͍͑஌͍ͬͯΔͱ࢖͍ॴ͕͋Δ͔΋ w

    ݕࡧ͕଎͍ͷ͸͏Ε͍͠ w ࣮ݧͰ͸OTLFZҎԼͰݱঢ়τοϓΫϥεͷ଎౓ w ߏங͕஗͘େن໛ͳΩʔू߹ʹର࣮ͯ͠༻తͰͳ͍'$)Λআ͘ͱ࠷΋଎͍ w ͕ɺOBOPTFDΦʔμʔͷϨΠςϯγ͕ٻΊΒΕΔϢʔεέʔε͕ͲΕ΄Ͳ͋Δͷ͔ w ݕࡧ͕͢͜͠஗ͯ͘΋͍͍ͳΒ3FD4QMJUʢ࠷΋খ͘͞Ͱ͖Δʣ΍##)BTIʢߏங͕࠷΋଎͍ʣͰे෼ 
 ʢ஗͍ͱݴͬͯ΋OTLFZఔ౓ͳͷͰे෼଎͍ʣ w ͱʹ͔͘ݕࡧ଎౓͕ٻΊΒΕΔ৔߹ʹ͸ҖྗΛൃش͢ΔͷͰɺ͓͍֮͑ͯͯଛ͸ͳͦ͞͏ w Ωʔͷ਺͕΋ͬͱଟ͘ͳͬͨͱ͖ʹߏங͕஗͘ͳΒͳ͍͔ʁ w O?͔ΒO?ʹ૿΍ͨ͠ͱ͖ʹɺ3FD4QMJU͸ߏங͕࣌ؒͪΐ͏Ͳഒ͘Β͍ʹͳ͍ͬͯΔ͕ɺ15)BTI͸਺ेഒʹͳ͍ͬͯΔ w Կʹ͕͔͔͍࣌ؒͬͯΔͷ͔