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

Research paper introduction (2019-11-12)

Takuya Asano
November 12, 2019

Research paper introduction (2019-11-12)

Fast Approximate Filtering of Search Results Sorted by Attribute (SIGIR 2019)

Takuya Asano

November 12, 2019
Tweet

More Decks by Takuya Asano

Other Decks in Research

Transcript

  1. 'BTU"QQSPYJNBUF'JMUFSJOHPG4FBSDI 3FTVMUT4PSUFECZ"UUSJCVUF 4*(*3 w 63- w IUUQTEMBDNPSHDJUBUJPODGN JE w 1SPCMFNTFUUJOH

    w %JSFDUMZNBYJNJ[FUIF%$(PGUIFSFTVMUMJTUXIJMFQSFTFSWJOHUIFTPSUPSEFSCZ BUUSJCVUF w 3FTVMUTPGUIJTSFTFBSDI w 1SPQPTFBOBMHPSJUINЏ'*MUFSJOHUIBUSFUVSOTBMNPTUPQUJNBMSFTVMUTBUIJHITQFFE w "QQSPYJNBUFFSSPSBOEXPSTUDBTFDPNQMFYJUZBSFHVBSBOUFFECZBQQSPYJNBUJPO w &YQFSJNFOUTTIPXUIBUUIFCBMBODFCFUXFFOTQFFEBOEBQQSPYJNBUJPOFSSPSJT HPPE
  2. 1SPCMFNTFUUJOH 'JMUFSJOH!L w /PSNBMMZ XIBUVTFSTXBOUUPTFBSDIJT 4&31XJUINBYJNJ[FESFMFWBODF w 8FCTFBSDI 4/4 TUSFBNJOHTFSWJDF

     &$ FUD w .BOZTFSWJDFTTVQQPSUTPSUJOHCZ BUUSJCVUFT UJNF QSJDF FUD  w 'PSFYBNQMF UIF4&31PGlJQIPOFzPO "NB[POJOUIFPSEFSPGUIFMPXFTUQSJDF w *UFNTXJUIMPXSFMFWBODFXJMMCFPO UPQ XIJDIXJMMMFBEQPPS69 4&31PGlJQIPOFzJOUIFPSEFSPGUIFMPXFTUQSJDF
 POBNB[PODPKQ
  3. .FUIPETCZ/BÏWF)FVSJTUJDT w $VUP⒎015<> w 'JMUFSXJUIQSFEFUFSNJOFESFMFWBODFUISFTIPME w 5IFO pMUFSJUXJUI015 PQUJNBMpMUFSJOH 

    w *OUIFXPSTUDBTF UIFSFJTOPHVBSBOUFFPGBQQSPYJNBUJPOFSSPS BDDVSBDZ  w #FDBVTFJUEFQFOETPOUIFUISFTIPMETFUUJOH w 5JNFDPNQMFYJUZEPFTOPUJNQSPWF w *OUIFXPSTUDBTF  ZFU w 5PQL015<> w $BMDVSBUFGPSBMJTUPGUPQL w 5IFO pMUFSJUXJUI015 PQUJNBMpMUFSJOH  w 5IFNFUSJDNBZCFNBYJNJ[FECZNBLJOHUIFMJTUMFTTUIBOL w $BOQSPWFPQUJNBM BQQSPYJNBUFFSSPSJT  w *OUIFXPSTUDBTF UIFUJNFDPNQMFYJUZJT Θ(nk) Θ(n log k + k2) [14] Spirin+ 2015. Relevance-aware Filtering of Tuples Sorted by an Attribute Value via Direct Optimization of Search Quality Metrics
  4. Џ'JMUFSJOH w )FVSJTUJDTBT$VUP⒎015BOE5PQL015DBOOPUDPOUSPMUIFBQQSPYJNBUF FSSPS w Џ'JMUFSJOHpOETBOBQQSPYJNBUFTPMVUJPOXJUIBHVBSBOUFFEFSSPSMFTTUIBO HJWFOFSSPSЏ  w 5JNFDPNQMFYJUZJT

     w Џ'JMUFSJOHJTTUFQTBTGPMMPXT w 3JHIU1SVOJOH w %JTDSFUJ[BUJPO w 5ISFTIPMEJOH 0 < ϵ < 1 Θ(n + k2 log(1−ϵ) (ϵ/k))
  5. 3JHIU1SVOJOH w &YBNQMF w 0SJHJOBMMJTUJT BOE  w %SPQ BOEMFBWFPOMZ

     w *OEFFE UIFMBSHFTU%$(TPMVUJPOJT  w 5IFFMFNFOUMFGUCZ3JHIU1SVOJOHJTDBMMFESJHIULNBYJNBM w 5IFPQUJNBMTPMVUJPODPOTJTUTPOMZPGSJHIULNBYJNBM FMFNFOUT -FNNB R = [0.9,1.0,1.0,1.0] k = 3 0.9 [1.0,1.0,1.0] [1.0,1.0,1.0]
  6. 5IF8PSTU$BTFPG
 3JHIU1SVOJOH w 8IFOUIFMJTUJTTVDIUIBUUIFSFMFWBODFJTHSBEVBMMZ SFEVDFE JUDBOOPUCFpMUFSFEBUBMM w &Y BOE 

    w "MMFMFNFOUTPG3BSFSJHIUNBYJNBM w *NQSPWFUIFTFDBTFTXJUIUIFOFYUTUFQPG %JTDSFUJ[BUJPO R = [1.2,1.1,1.0,0.9] k = 3
  7. %JTDSFUJ[BUJPO w &Y  FMFNFOUTJO3  w 8IFOUIF%JTDSFUJ[BUJPOTUFQJTBQQMJFE UIFGPMMPXJOHJOUFSWBMTBSFDSFBUFE w

     w  w ʜ w  w  w %JTDSFUJ[FEMJTU JT  w 4P %JTDSFUJ[BUJPOJOUIJTXBZDBVTFTFMFNFOUTUPCFpMUFSFECZ3JHIUQSVOJOH R = [3.00,2.99,2.98,...,0.01] [0.01,0.019) [0.019,0.039) [1.45,2.17) [2.17,3.0) Rϵ [2.17,...,2.17,1.45,...,1.45,...,0.01]
  8. 5IF8PSTU$BTFPG %JTDSFUJ[BUJPO w 'JYJOH BOENBLJOH MBSHFFOPVHITPUIBUN OVNCFSPGJOUFSWBMT JTFRVBMUPO MFOHUIPGMJTU 

    w &Y  w "UUIJTUJNF BMMFMFNFOUTBSFTFMFDUFEFWFOJG %JTDSFUJ[BUJPO3JHIU1SVOJOH rmin rmax R = [100000000,10000,1]
  9. 5ISFTIPMEJOH w 'JMUFSFMFNFOUTCFMPXUISFTIPME  w #ZpMUFSJOHFMFNFOUTCFMPXUIFUISFTIPME UIFWBMVFPG DBOCFJODSFBTFE  BOEBTBSFTVMU

    OVNCFSPGJOUFSWBMTNDBOCFEFDSFBTFE w ˠ3JHIU1SVOJOHXPSLTXFMM w  FMFNFOUT  w %$(PG3JT w 'JMUFSBMMFMFNFOUT %$(JTBSPVOE w "DIJFWFTBQQSPYJNBUJPO w "OEGBTUFSRVFSZQSPDFTTJOH t = g−1(ϵg(rmax /k)) rmin R = [5,0.1,...,0.1]
  10. &YQFSJNFOUBM4FUVQ w %BUBTFU w (PPHMF-PDBM3FD w  VTFST w 

    QPJOUTSFDPNNFOEBUJPOGPSFBDIVTFS w "NB[PO3FM w RVFSJFT w  JUFNT BWFSBHF GPSFBDIRVFSZ w .FUSJD w %$(  w %$(-; Σn p=1 2rp − 1 log2 p + 1 Σn p=1 rp p