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

Research Paper Introduction in IR Reading 2021 ...

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

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 Կʹ͕͔͔͍࣌ؒͬͯΔͷ͔