Reducing update packets in distributed interactive applications using a hybrid approach

5('8&,1*83'$7(3$&.(76,1',675,%87(',17(5$&7,9($33/,&$7,21686,1* $+<%5,'$3352$&+ 'HFODQ'HODQH\ 'HSDUWPHQWRI&RPSXWHU6FLHQFH1DWLRQDO8QLYHUVLW\RI ,UHODQG0D\QRRWK&R.LOGDUH,UHODQG GHFODQG#FVPD\LH 7RPiV:DUG6pDPXV0F/RRQH 'HSDUWPHQWRI(OHFWURQLF(QJLQHHULQJ1DWLRQDO 8QLYHUVLW\RI,UHODQG0D\QRRWK&R.LOGDUH,UHODQG ^WRPDVZDUGVHDPXVPFORRQH`#HHQJPD\LH $%675$&7 'LVWULEXWHG ,QWHUDFWLYH $SSOLFDWLRQV ',$V VXFK DV QHWZRUNHG JDPHV RU 'LVWULEXWHG ,QWHUDFWLYH 6LPXODWLRQV ',6 GHSHQG RQ WKH XQGHUO\LQJ QHWZRUN $Q LPSRUWDQW DVSHFWLVWKHQXPEHURIGDWDSDFNHWVWUDQVPLWWHGDFURVVWKH FRQQHFWHG QHWZRUNV  7R UHGXFH WKH QXPEHU RI SDFNHWV WUDQVPLWWHG ',$V HPSOR\ FOLHQWVLGH SUHGLFWLYH FRQWUDFWV 7KH PRVW FRPPRQO\ XVHG FOLHQW VLGH SUHGLFWLYH FRQWUDFW WHFKQLTXH LV SXUH GHDG UHFNRQLQJ ,Q WKLV SDSHU DQ DOWHUQDWLYHPHWKRGLQWKHIRUPRIDQRYHOK\EULGPXOWLSOH VWUDWHJ\WHFKQLTXHLVSURSRVHG7KLVWHFKQLTXHFKRRVHVRQH RI VHYHUDO PRGHOV HLWKHU D GHWHUPLQLVWLF GHDG UHFNRQLQJ PRGHO RU RQH RI QXPHURXV VWUDWHJ\EDVHG PRGHOV  7KLV QHZDSSURDFKLVFRPSDUHGWRWKHILUVWRUGHUGHDGUHFNRQLQJ PHWKRG XVLQJ WZR JDPHW\SH HQYLURQPHQWV,W LV VKRZQ WKDW WKH SURSRVHG WHFKQLTXH UHVXOWV LQ D VLJQLILFDQW UHGXFWLRQ LQ WKH QXPEHU RI HQWLW\ SDFNHWV WKDW QHHG WR EH WUDQVPLWWHG WR PDLQWDLQ HQWLW\VWDWH ILGHOLW\ DFURVV WKH QHWZRUNHGDSSOLFDWLRQ .(<:25'6 1HWZRUN /DWHQF\ +\EULG 0RGHOV 'LVWULEXWHG ,QWHUDFWLYH $SSOLFDWLRQV'HDG5HFNRQLQJ ,1752'8&7,21 'LVWULEXWHG ,QWHUDFWLYH $SSOLFDWLRQV ',$V VXFK DV QHWZRUNHG JDPHV RU 'LVWULEXWHG ,QWHUDFWLYH 6LPXODWLRQ ',6LQYROYH PXOWLSOHSDUWLFLSDQWV FRPPXQLFDWLQJ RYHUD FRPSXWHU QHWZRUN >@>@ %\ GHILQLWLRQ D ',$ PXVW SURYLGHDUHDOLVWLFLQWHUDFWLYHH[SHULHQFHWRWKHSDUWLFLSDQWV +RZHYHUDQXPEHURIWHFKQLFDOSUREOHPVFRPELQHWRPDNH GHOLYHU\ RI VXFK DQ H[SHULHQFH GLIILFXOW >@>@>@  2QH PDMRUSUREOHPLVQHWZRUNODWHQF\ZKLFKLVWKHWLPHLWWDNHV IRU LQIRUPDWLRQ WR SURSDJDWH DFURVV WKH QHWZRUN WR DOO SDUWLFLSDQWV$QRWKHU FORVHO\ UHODWHGLVVXHLV WKHSUREOHP RIQHWZRUNEDQGZLGWK  :LWKLQD',$ WKHVH SUREOHPV DUH UHIHUUHG WR DV WKH LQIRUPDWLRQ XSGDWLQJ LVVXH  6HYHUDO PHWKRGVKDYHEHHQGHYLVHGWRUHGXFHWKHTXDQWLW\ RI GDWD WKDWQHHGVWREHWUDQVPLWWHGEHWZHHQSDUWLFLSDQWV>@>@>@ 7KH ',6 VWDQGDUG GHILQHV D FOLHQW SUHGLFWLYH FRQWUDFW PHFKDQLVPFDOOHGGHDGUHFNRQLQJ>@ 7KLV SDSHU SURSRVHV D K\EULG PXOWLSOHVWUDWHJ\ WHFKQLTXH  7KLV LQYROYHV G\QDPLFDOO\ VZLWFKLQJ EHWZHHQ RQH RI VHYHUDO PRGHOV HLWKHU D GHDG UHFNRQLQJ PRGHO RU RQHRIDQXPEHURIVWUDWHJ\PRGHOV7KLVWHFKQLTXHUHVXOWV LQ D UHGXFWLRQ LQ WKH QXPEHU RI SDFNHWV WKDW PXVW EH FRPPXQLFDWHG WR PDLQWDLQ UHPRWH ILGHOLW\ RI ORFDO HQWLW\ PRYHPHQWFRPSDUHGWRDSXUHO\GHDGUHFNRQLQJFRQWUDFW 7KHNH\FRQWULEXWLRQKHUHLVWKDWDSULRULNQRZOHGJHRI XVHU EHKDYLRULV LQWHJUDWHGLQWRWKHSURSRVHGWHFKQLTXHLQ RUGHUWRUHGXFHHQWLW\VWDWHXSGDWHSDFNHWV,QWKHDEVHQFH RI VXFK UHOLDEOH XVHUEHKDYLRUDO LQIRUPDWLRQ FRQYHQWLRQDO GHDGUHFNRQLQJSURWRFROVDUHHPSOR\HG6XFKDQDSSURDFK LVIOH[LEOHSRZHUIXODQGQHFHVVDU\IRUWRGD\¶VLQFUHDVLQJO\ FRPSOH[',$V 7ZR GLIIHUHQW JDPHW\SH HQYLURQPHQWV DUH XVHG WR LOOXVWUDWHRXUSURSRVHGWHFKQLTXH WKHUHVXOWV RI ZKLFK DUH FRPSDUHGWRWKDWRISXUHGHDGUHFNRQLQJ+HUHWKHK\EULG PXOWLSOHVWUDWHJ\ PHWKRG G\QDPLFDOO\ VHOHFWV WKH PRVW VXLWDEOHRIIRXUPRGHOVEDVHGRQGHDGUHFNRQLQJDQGWKUHH VWUDWHJ\PRGHOV5HVXOWVLOOXVWUDWHWKHYDOLGLW\RIWKHQHZ DSSURDFK 7KH QH[W VHFWLRQ RXWOLQHV WKH LQIRUPDWLRQ XSGDWLQJ LVVXH DV LW DSSOLHV WR 'LVWULEXWHG ,QWHUDFWLYH $SSOLFDWLRQV DQGGHVFULEHVH[LVWLQJVROXWLRQVLQFOXGLQJGHDGUHFNRQLQJ 6HFWLRQ WKUHH WKHQ GHVFULEHV RXU QRYHO K\EULG PXOWLSOH VWUDWHJ\ DSSURDFK  ,Q VHFWLRQ IRXU ZH GHWDLO WKH FRQVWUXFWLRQRIWKHPXOWLSOHPRGHOIRUDSXUSRVHEXLOWWHVW HQYLURQPHQW5HVXOWVDUHSUHVHQWHGLQVHFWLRQILYHIRUGHDG UHFNRQLQJ K\EULG VLQJOHVWUDWHJ\ DQG K\EULG PXOWLSOH VWUDWHJ\WHFKQLTXHV7KHSDSHUHQGVZLWKFRQFOXVLRQVDQG VXJJHVWLRQVIRUIXWXUHUHVHDUFK 7+(,1)250$7,2183'$7,1*,668( 1HWZRUNODWHQF\DQGEDQGZLGWKUHVWULFWLRQVFDQFRPELQH WR SURYLGH SRRU LQWHUDFWLYH H[SHULHQFH LQ D GLVWULEXWHG DSSOLFDWLRQ  7KH ,QIRUPDWLRQ 8SGDWLQJ ,VVXH UHIHUV WR PDLQWDLQLQJ D FRQVLVWHQW YLHZ RI WKH VKDUHG HQYLURQPHQW DPRQJ DOO SDUWLFLSDQWV RI D 'LVWULEXWHG ,QWHUDFWLYH $SSOLFDWLRQ>@ 7KHPRVW FRPPRQ VROXWLRQ WR WKHLQIRUPDWLRQ XSGDWLQJ LVVXHLQYROYHVDFOLHQWVLGHSUHGLFWLRQFRQWUDFWPHFKDQLVP FDOOHGGHDGUHFNRQLQJ>@DOOSDUWLFLSDWLQJFOLHQWVDJUHHWR PDLQWDLQWKHVDPHORZRUGHUORFDOPRGHOVRIWKHG\QDPLFV RIDOORWKHUSDUWLFLSDWLQJHQWLWLHV7KLVLVWKHFRQWUDFW(DFK SDUWLFLSDQW DOVR PDLQWDLQV D PRGHO RI LWV RZQ HQWLW\ G\QDPLFV ZKLFK LW FRQWLQXRXVO\ FRPSDUHV WR LWV DFWXDO G\QDPLFV  :KHQ WKHVH GLIIHU E\ D SUHGHILQHG WKUHVKROG XSGDWH LQIRUPDWLRQ LV EURDGFDVW WR DOO RWKHU SDUWLFLSDQWV 7KHVH WKHQ XSGDWH WKHLU PRGHOV IRU WKDW HQWLW\ &RQYHUJHQFH DOJRULWKPV DUH QHFHVVDU\ WR DOORZ D QDWXUDO WUDQVLWLRQWRRFFXUEHWZHHQWKHPRGHOHGDQGDFWXDOPRWLRQ ZKHQ XSGDWH GDWD LV UHFHLYHG >@ :H GR QRW GHDO ZLWK FRQYHUJHQFHDOJRULWKPVLQWKLVSDSHU $OWHUQDWLYHPHWKRGV KDYHDOVREHHQH[SORUHGDQGWKHVH LQFOXGH x5HOHYDQFH)LOWHULQJWHFKQLTXHV7KHVHVHHNWRUHGXFH WKHLQIRUPDWLRQEHLQJWUDQVPLWWHGRYHUWKHQHWZRUNE\ ILOWHULQJ WKH GDWD EDVHG RQ FULWHULD VXFK DV JHRJUDSKLFDOSUR[LPLW\RUUDWHRIFKDQJH>@ x1HWZRUN WUDQVPLVVLRQ SURWRFRO 0XOWLFDVWLQJ DQG UHOLDEOH PXOWLFDVWLQJ DOORZ KRVWV WR VXEVFULEH DQG XQVXEVFULEH WR DQ\ RI SRVVLEO\ VHYHUDO PXOWLFDVW JURXSV0XOWLFDVW JURXSV PLJKW EHFUHDWHGEDVHGRQ HQWLW\ W\SH RU JHRJUDSKLFDO ORFDWLRQ LQ WKH YLUWXDO HQYLURQPHQW>@ x3DFNHW EXQGOLQJ 7KLV LQYROYHV FRPELQLQJ D QXPEHU RIGDWDSDFNHWVWRFUHDWHDODUJHUGDWDSDFNHWEHFDXVH QHWZRUNGHYLFHVFDQRQO\SURFHVVDOLPLWHGQXPEHURI SDFNHWVSHUXQLWWLPH>@ x'DWD &RPSUHVVLRQ 7KHVH WHFKQLTXHV DOORZ WKH UHGXFWLRQLQWKHVL]HRI WKHLQIRUPDWLRQSDFNHWEHLQJ WUDQVPLWWHG  2QH WHFKQLTXH LV WR HQFRGH GLIIHUHQFHV EHWZHHQ VXFFHVVLYH GDWD SDFNHWV LQVWHDG RI WUDQVPLWWLQJWKHDEVROXWHVWDWH>@ x7LPH0DQDJHPHQW7KLVLQYROYHVSUHHPSWLQJHYHQWV DQGWKHQORFNLQJXSWKHV\VWHP VRWKDWWKHHYHQWFDQ RFFXU$OWHUQDWLYHO\WKHH[HFXWLRQRIORFDOXVHULQSXW LV GHOD\HG DQG GLVJXLVHG DV VRPHWKLQJ HOVH XQWLO WKH ORFDO XVHU LQSXW FDQ EH UHOD\HG WR DOO SDUWLFLSDQWV >@>@ x3ULRULW\ 6FKHGXOLQJ $ WUDQVPLVVLRQ SULRULW\ FDQ EH DVVLJQHG WR LQIRUPDWLRQ EDVHG RQ FULWHULD VXFK DV VSHHGRIPRYHPHQWRUUDWHRIHUURUFKDQJH>@7KLV DOVRLQFOXGHV4XDOLW\RI6HUYLFHSURWRFROV>@ x9LVLELOLW\ &XOOLQJ 7KH HQYLURQPHQW LV GLYLGHG LQWR FHOOV DQG PXOWLFDVWLQJ XSGDWHV DUH SURYLGHG WR DOO HQWLWLHVWKDWDUHYLVLEOHWRHDFKRWKHULQHDFKFHOO>@ x4XDOLW\ RI 6HUYLFH 7HFKQLTXHV 4R6 4R6 4XDOLW\ RI 6HUYLFH LV WKH LGHD WKDW WUDQVPLVVLRQ UDWHV HUURU UDWHV DQG RWKHU QHWZRUN FKDUDFWHULVWLFV FDQ EH PHDVXUHGLPSURYHGDQGWRVRPHH[WHQWJXDUDQWHHG LQDGYDQFH7KHUHKDYH EHHQ DWWHPSWV WR GHILQH4R6 PHDVXUHVVXLWDEOHIRU',6>@ 7KHDERYHWHFKQLTXHVDUHEDVHGRQQHWZRUNPDQDJHPHQW DQGQHWZRUNSDUWLWLRQLQJSROLFLHV:HDUHJRLQJWRORRNDW D SDFNHWUHGXFWLRQ PHWKRG EDVHG RQ FOLHQW EHKDYLRUDO PRGHOLQJ ZKHUH ZH VZLWFK EHWZHHQ D VKRUWWHUP GHDG UHFNRQLQJPRGHODQGDORQJWHUPVWDWLVWLFDOEDVHGPXOWLSOH VWUDWHJ\ PRGHO  ,W VKRXOG EH SRLQWHG RXW DW WKLV MXQFWXUH WKDW RXU WHFKQLTXH RU LQGHHG DQ\ RWKHU FOLHQWSUHGLFWLYH FRQWUDFWFDQHDVLO\EHFRPSOHPHQWHGWKURXJKWKHXVHRIDQ\ RIWKHWHFKQLTXHVPHQWLRQHGDERYH 7+(+<%5,'$3352$&+ 7(50,12/2*< )RU WKH FRQYHQLHQFH RI WKH UHDGHU ZH GHILQH WKH IROORZLQJWHUPV$ JRDO LV WKH DLP RUREMHFWLYHDSHUVRQ KDVLQPRYLQJWKURXJKDQHQYLURQPHQW)RUH[DPSOHWKH JRDOPLJKWEHWRJRIURPSRLQW$WRSRLQW%,QDFKLHYLQJD JRDODSHUVRQFDQDGRSWDQXPEHURIVWUDWHJLHVVRWKDWDQ\ RQHVWUDWHJ\LVDQH[SUHVVLRQRIWKHJRDO6WUDWHJLHVFDQEH HLWKHUVWHDG\VWDWHRUWUDQVLHQW$VWHDG\VWDWHVWUDWHJ\ LVD XVHUSUHIHUUHGPHWKRGIRUDFKLHYLQJDVHWJRDO$WUDQVLHQW VWUDWHJ\ LVDQH[SORUDWRU\PHWKRGLQDQDWWHPSWWRUHDFKD VWHDG\VWDWHVWUDWHJ\ 7KHLGHD XQGHUO\LQJ WKH KXQW IRU VWUDWHJLHV LV WR WUDLQ D V\VWHP WR H[SHFW FHUWDLQ VWUDWHJLHV EDVHG RQ SDVW XVHU EHKDYLRU RU EDVHG RQ H[SHFWHG XVHU EHKDYLRU  (DFK VWUDWHJ\ FRPSULVHV RQH RU PRUH WUDMHFWRULHV ± D VHW RI WUDMHFWRULHV FDQ EH DVVRFLDWHG ZLWK DQ\ VWUDWHJ\ $ WUDMHFWRU\ LV D SDUWLFXODU H[SUHVVLRQ RI D VWUDWHJ\ 0XOWLSOLFLW\FDQUHIHUWRHLWKHUVWUDWHJLHVRUJRDOV6WUDWHJ\ 0XOWLSOLFLW\ ,QGH[ 60, UHIHUV WR WKH QXPEHU RI JRDOV D VWUDWHJ\OHDGVWR*RDO0XOWLSOLFLW\,QGH[ *0,UHIHUVWR WKHQXPEHURIVWHDG\VWDWHVWUDWHJLHVWKDWOHDGWRWKHJRDO 7KLVWHUPLQRORJ\LVLOOXVWUDWHGLQ)LJXUH,QWKLVSDSHUZH SUHVHQWUHVXOWVIRUD*0,RI )LJXUH 7HUPLQRORJ\±6WR6DUHVWUDWHJLHV*WR*DUH JRDOV7LVDVDPSOHWUDMHFWRU\*0,LVWKH*RDO0XOWLSOLFLW\ ,QGH[±KRZPDQ\VWUDWHJLHVUHDFKWKDWJRDO60, 6WUDWHJ\ 0XOWLSOLFLW\,QGH[±KRZPDQ\JRDOVWKLVVWUDWHJ\OHDGWR 7+(+<%5,'02'(/ 7KH K\EULG PRGHO 0IRU HQWLW\ G\QDPLFV LV RI WKH IROORZLQJIRUP *      S S 0 F  *RDO 6 6 6 6 6 * * * 6 6 6 6 6 6WDUWLQJ3RLQW 6 *0,  60,  * * * * * * 7 ZKHUH FLV DQ\ FRQYHQWLRQDO GHDG UHFNRQLQJ PRGHO **LV RQHRIVHYHUDOORQJWHUPHQWLW\VWUDWHJ\PRGHOVDQGSLVD ELQDU\ZHLJKWLQJIDFWRUJRYHUQHGE\ S IRU T t *  0 RWKHUZLVH  ZKHUHTUHSUHVHQWVDGLVWDQFHPHDVXUHWKUHVKROGEHWZHHQ WKHPRGHOHGEHKDYLRUDQGWKHORQJWHUP PRGHO*,QWKLV ZD\ D PRGHO *EDVHG RQ D SULRUL GDWD FDQ EH HPSOR\HG ZKHQWKHHQWLW\PRYHPHQWLVµFORVH¶WRVXFKWUDMHFWRULHV,Q WKLV SDSHU ZH H[SORUH WKH LGHD WKDW ZH PD\ KDYH VHYHUDO PRGHOVIURPZKLFKWRSLFN*EDVHGRQDSULRUL LQIRUPDWLRQ 7KH SDUWLFXODU PRGHO XVHG LV G\QDPLFDOO\ FKRVHQ VR WKDW LPSURYHG ILWV FDQ EH REWDLQHG RYHU VLQJOH PRGHO DSSURDFKHV$WDQ\LQVWDQWLQWLPHWKHQHDUHVWPRGHOIURP WKHVHWDYDLODEOHLVXVHGLQHTXDWLRQ 3DUWLFLSDWLQJFOLHQWVLQD',$XVHWKHPRGHOJLYHQE\0 7KH SDUDPHWHUV DQG LQLWLDO HQWLW\ VWDWH XVHG E\ WKH PRGHO DUHXSGDWHGHYHU\WLPHWKHVWDWHGHYLDWHVIURPWKHWUXHVWDWH E\DSUHGHILQHGWKUHVKROGDPRXQW7P :KLOH DOWHUQDWLYH VRIW PRGHO EOHQGLQJ WHFKQLTXHV FRXOG EH HPSOR\HG KHUH ZH KDYH RSWHG IRU D VLPSOH VZLWFKLQJ WHFKQLTXH EHWZHHQ PRGHOV WR LOOXVWUDWH WKH SULQFLSOHV LQYROYHG 6HFWLRQ IRXU GHVFULEHV LQ GHWDLO WKH VWUDWHJ\ PRGHO* &216758&7,1*7+(675$7(*<02'(/ 7+(7(67(19,5210(17 7KHORQJWHUPVWUDWHJ\PRGHOV*HPSOR\HGLQWKHK\EULG SUHGLFWLRQ WHFKQLTXH FDQ EH FRQVWUXFWHG LQ YDULRXV ZD\V D E\ UHFRUGLQJ SDVW DFWXDO HQWLW\ PRYHPHQWV LQ WKH HQYLURQPHQW DQG SHUIRUPLQJ VWDWLVWLFDO DQDO\VLV E E\ KHXULVWLFDOO\ LGHQWLI\LQJ SRVVLEOH VWUDWHJLHV EDVHG RQ WKH H[DPLQDWLRQ RI WKH HQYLURQPHQW DQG F E\ HPSOR\LQJ DXWRPDWLFSDWKILQGLQJWHFKQLTXHV)RUWKLVSDSHUZHFKRVH WKHILUVW PHWKRGGHYHORSLQJDJDPHW\SH-DYDDSSOLFDWLRQ WKDW UHFRUGV XVHU WUDMHFWRULHV LQ D FRQWUROOHG WZR GLPHQVLRQDOHQYLURQPHQW 8VHUV ZHUH DVNHG WR QDYLJDWH IURP D IL[HG VWDUWLQJ SRVLWLRQ WR D IL[HG WDUJHW SRVLWLRQ LQ DV VKRUW D WLPH DV SRVVLEOH 7KHLU YLHZ RI DQ\ REVWDFOHV LQ WKHLU SDWK ZDV UHVWULFWHGWRDFLUFXODUDUHDDURXQGWKHLULPPHGLDWHSRVLWLRQ 7KHXVHU EHJDQ ZLWK QR NQRZOHGJH RI WKH ORFDWLRQ RI WKH WDUJHWDQGUHSHDWHGWKHH[HUFLVHIRUDVHWQXPEHURIWULDOV (DFKDWWHPSWFRQVWLWXWHG D WUDMHFWRU\  'DWD ZDV FROOHFWHG DQGVWRUHGIRUHDFKWUDMHFWRU\7KLV SURYLGHGWKHEDVLVRI WKH VWDWLVWLFDOEDVHG VWUDWHJ\ PRGHOV WKDW ZH XVHG LQ WKH K\EULGFRQWUDFWWHFKQLTXH2QHRIWKHWZRPD]HVHPSOR\HG LVVKRZQLQ)LJXUH )LJXUH$VFUHHQVKRWRIWKHWUDMHFWRU\UHFRUGLQJVRIWZDUH 7KHEODFNDUHDVDUHREVWDFOHVWKDWGRQRWDOORZXVHUVWRSDVV &+226,1*7+(675$7(*<02'(/ 8VLQJ WKH VRIWZDUH DSSOLFDWLRQ D PLQLPXP RI ILYH DQG PD[LPXP RI IRXUWHHQ WUDMHFWRULHV ZHUH UHFRUGHG IURP IRXUWHHQGLIIHUHQWXVHUV7KHILQDOWUDMHFWRULHVIRUHDFKXVHU PD\EHFRQVLGHUHGVWHDG\VWDWHWUDMHFWRULHV)LJXUHSORWV WKHVHWUDMHFWRULHVIRUWHQXVHUV 150 200 250 300 350 400 450 500 550 600 0 50 100 150 200 250 300 350 400 )LJXUH$SORWRIWKHILQDOXVHUWUDMHFWRU\IRUGLIIHUHQWXVHUV 7KHWKUHHVWUDWHJ\PRGHOVIRUDWKUHVKROGRIDUHLQGLFDWHGDV GRWWHGOLQHV )URP WKLV SORW ZH FDQ LGHQWLI\ D VXLWDEOH VWHDG\VWDWH VWUDWHJ\,QWKLVSDSHUZHXVHDPXOWLSOHVWUDWHJ\PRGHOWR UHSUHVHQWWKHJLYHQ GDWD2QHXVHU¶V VWHDG\VWDWH VWUDWHJ\ ZDV FKRVHQ WR UHSUHVHQW WKH FHQWUDO VWUDWHJ\ PRGHO  7ZR DGGLWLRQDO VWUDWHJLHV ZHUH JHQHUDWHG E\ VSDWLDOO\ VKLIWLQJ WKH VWHDG\VWDWH VWUDWHJ\ E\ D IL[HG DPRXQW WR JHQHUDWH WKUHHSDUDOOHOVWUDWHJLHV7KHVKLIWHGVWUDWHJLHVZHUHFUHDWHG DVHGRQWKHWULJRQRPHWULFFRQVLGHUDWLRQVRI)LJXUH 7$5*(7 7UDLORI8VHU 7UDMHFWRU\ ;&RRUGLQDWH <&RRUGLQDWH ««0RGHO6WUDWHJLHV 8VHUWUDMHFWRULHV )LJXUH'LDJUDPLOOXVWUDWLQJKRZWKHDGGLWLRQDOVWUDWHJLHVDUH FUHDWHG7KHVROLGOLQHUHSUHVHQWVWKHVWHDG\VWDWHVWUDWHJ\DQGWKH GDVKHGOLQHUHSUHVHQWVRQHRIWKHJHQHUDWHGVWUDWHJLHV 7KHFDOFXODWLRQVDUHJLYHQLQWKHIROORZLQJHTXDWLRQV      WDQ [ [ \ \    I I S T    T V &RV [ ' DQG T V 6LQ \ '  7KH[L\LFRRUGLQDWHVIRUWKHVLGHVWUDWHJLHVDUHJLYHQ E\[L'[L\L'\LDQG[L'[L\L'\LZKHUH[L\LDUHWKH FRRUGLQDWHVRIWKHFHQWUDOVWUDWHJ\  VLV FKRVHQ WR EH  WLPHVWKHWKUHVKROGYDOXH7P7KLVHQVXUHVWKDWZKHQWKH HQWLW\ OLHV ZLWKLQ WKH DUHD FRQWDLQHG EHWZHHQ WKH VWUDWHJ\ PRGHOV GHDG UHFNRQLQJ ZLOO QHYHU EH QHHGHG  ,W DOVR SURYLGHVDVOLJKWK\VWHUHVLVVRWKDWPXOWLSOHVZLWFKLQJZLOO QRW RFFXU RQ WKH ERXQGDULHV EHWZHHQ VWUDWHJ\ FRYHUDJH DUHDV 5(68/76 7KH UHVXOWV SUHVHQWHG DUH EDVHG RQ WZR GLIIHUHQW HQYLURQPHQWV VLPLODU WR WKH RQH LOOXVWUDWHG LQ )LJXUH  DERYH 7KHVH DUH JLYHQ LQ VHFWLRQV  DQG  UHVSHFWLYHO\  %RWK SXUH GHDG UHFNRQLQJ '5 DQG RXU K\EULGPXOWLSOHVWUDWHJ\+06DUHFRQVLGHUHG5HVXOWVIRU D K\EULG VLQJOHVWUDWHJ\ +66 DUH SUHVHQWHG IRU FRPSDULVRQ SXUSRVHV ZKHUH WKH VLQJOH VWUDWHJ\ LV WKH FHQWUDOVWUDWHJ\IURPWKH+06 &$6(678'< 2I IRXUWHHQ GDWD VHWV UHFRUGHG IRU WKLV WHVW FDVH WHQ ZHUHXVHGWRJHQHUDWHDVWUDWHJ\PRGHO2IWKHUHPDLQLQJ IRXU XVHUV ZHUH UDQGRPO\ FKRVHQ DV UHSUHVHQWDWLYH WHVW GDWDVHWV 7DEOHFRPSDUHV WKH QXPEHU RI SDFNHWV VHQW IRU DOO WULDO WUDMHFWRULHV IRU WKHVH WZR XVHU GDWDVHWV XVLQJ WKH WKUHH PRGHOVILUVWRUGHU'5+66DQG+067KHWKUHVKROG7P ZDVVHWDWLQHDFKFDVH7DEOHVKRZVWKHUHVXOWVIRUWKH VDPHWHFKQLTXHVEXWWKLVWLPHZLWKDWKUHVKROG7PRILQ HDFKFDVH 3XUH'5 +66 +06 7ULDO 8VHU8VHU8VHU8VHU8VHU8VHU                                                         7DEOH7KHQXPEHURISDFNHWVWUDQVPLWWHGIRUWZRXVHUVHWVIRU SXUHGHDGUHFNRQLQJWKHVLQJOHVWUDWHJ\K\EULGPHWKRGDQGWKH PXOWLSOHVWUDWHJ\K\EULGPHWKRG7ULDOLVWKHLQLWLDOWULDO 7KUHVKROGYDOXH 3XUH'5 +66 +06 7ULDO 8VHU8VHU8VHU8VHU8VHU8VHU                                                         7DEOH7KHQXPEHURISDFNHWVWUDQVPLWWHGIRUWZRXVHUVHWVIRU SXUHGHDGUHFNRQLQJWKHVLQJOHVWUDWHJ\K\EULGPHWKRGDQGWKH PXOWLSOHVWUDWHJ\K\EULGPHWKRG7ULDOLVWKHLQLWLDOWULDO 7KUHVKROGYDOXH 150 200 250 300 350 400 450 500 550 600 0 50 100 150 200 250 300 350 400 )LJXUHD$SORWRIWKHILUVWWUDMHFWRU\DWWHPSWIRUXVHUWZR7KH XVHUZDQGHUVDWWHPSWLQJWRORFDWHWKHWDUJHWWRWKHWRSULJKW 7KHWKUHVKROGLVVHWWR '[ '\ I T 0DLQ8VHU6WUDWHJ\ &UHDWHG8VHU 6WUDWHJ\ 6DPSOHGGDWD SRLQWV [\ [\ V 3DFNHW7UDQVPLWWHG « 6WUDWHJ\PRGHO 8VHUWUDMHFWRU\ ;&RRUGLQDWH <&RRUGLQDWH 150 200 250 300 350 400 450 500 550 600 0 50 100 150 200 250 300 350 400 )LJXUH E $ SORWRI WKH IRXUWK WUDMHFWRU\ DWWHPSW IRU XVHU WZR 7KH XVHU WUDMHFWRU\ UHDFKHV WKH WDUJHW  7KH VWUDWHJ\ PRGHOV DUH XVHGZLWKRXWDQ\GHDGUHFNRQLQJ7KHWKUHVKROGLVVHWWR 7ZRWULDOVIRUXVHUDQGDWKUHVKROGRIDUHVKRZQ LQ)LJXUHVDDQGE(DFKSORWVKRZVWKHVWUDWHJ\PRGHOV WKHXVHUWUDMHFWRU\DQGWKHSDFNHWVWUDQVPLWWHG 7KHLQLWLDOWUDMHFWRU\RIXVHUWZRLVVKRZQLQ)LJXUHD 7KLVLVDW\SLFDOH[DPSOHRIDWUDQVLHQWVWUDWHJ\DVWKHXVHU ZDQGHUVDURXQGWKHHQYLURQPHQWVHHNLQJWKHWDUJHW,QWKLV FDVHWKHWDUJHWLVORFDWHGDWWKHWRSULJKWHQGRIWKHVWUDWHJ\ PRGHO FXUYH  +HUH '5 LV PRVWO\ XVHG DQG WKH +06 PHWKRGLVUDUHO\HPSOR\HG7KLVLVWREHH[SHFWHGDVWKH XVHUKDVQRW\HWIRUPHGDVWHDG\VWDWHVWUDWHJ\ ,Q)LJXUHEWUDMHFWRU\IRXURIXVHULVGLVSOD\HG,Q WKLV FDVH WKH XVHU KDV KDG WKUHH SUHYLRXV DWWHPSWV DQG LV PRUHIDPLOLDUZLWKWKHHQYLURQPHQW7KHWUDMHFWRU\LVPXFK PRUH PDWXUH DQG SXUSRVHIXO DQG UHIOHFWV D VWHDG\VWDWH VWUDWHJ\,QVXFKFDVHVGHDGUHFNRQLQJLVUDUHO\XVHG )RU D WKUHVKROG RI  ERWK K\EULG PHWKRGV SHUIRUP EHWWHULQJHQHUDOWKDQSXUHGHDGUHFNRQLQJZLWKWKH+06 WHFKQLTXHJLYLQJ WKH EHVW UHVXOWV5HGXFLQJ WKH WKUHVKROG YDOXHLPSURYHVWKHUHPRWHHQWLW\VWDWHILGHOLW\EXWUHTXLUHV PRUH SDFNHWV WR EH WUDQVPLWWHG LQ DOO WKUHH FDVHV 1HYHUWKHOHVV WKH K\EULG PXOWLSOHVWUDWHJ\ WHFKQLTXH VWLOO SHUIRUPVVLJQLILFDQWO\EHWWHUWKDQSXUHGHDGUHFNRQLQJ &$6(678'< +HUHDPRUHFRPSOH[HQYLURQPHQWZDVXVHGWRIXUWKHU LOOXVWUDWHWKHDGYDQWDJHV RI WKH +06 DSSURDFK 7DEOHV  DQG  VKRZ WKH UHVXOWV IRU HDFK PRGHOLQJ WHFKQLTXH IRU WKUHVKROGYDOXHVRIDQGUHVSHFWLYHO\ 7KHVHUHVXOWVLOOXVWUDWHWKDW GXULQJ LQLWLDODWWHPSWV WKH YDULRXV XVHUV GR QRW DGRSW DQ\ RI WKH FKRVHQ VWUDWHJ\ PRGHOV±VHH)LJXUHD6LPLODUUHVXOWVZHUHREVHUYHGIRU FDVHVWXG\2QFHWKH\KDYHORFDWHGWKHWDUJHWZLWKLQWKH HQYLURQPHQWWKH\UDSLGO\DGRSWDVWHDG\VWDWHVWUDWHJ\WKDW ZLOODOORZWKHPWRPLQLPL]HWKHWLPHUHTXLUHGWRUHWXUQWR WKH WDUJHW DV VKRZQ LQ )LJXUH E  ,Q VRPH LQVWDQFHV WKH XVHUVH[SORUHWKHPD]HWRGLVFRYHUDQDOWHUQDWLYHURXWHRUWR EHWWHUIDPLOLDUL]HWKHPVHOYHVZLWKWKHHQYLURQPHQW±VHHIRU H[DPSOHXVHUWULDO $JDLQWKHUHVXOWVVKRZWKDWWKH+06SHUIRUPVEHWWHU WKDQ'5IRUERWKYDOXHVRIWKUHVKROG 3XUH'5 +66 +06 7ULDO 8VHU8VHU8VHU8VHU8VHU8VHU                                           7DEOH7KHQXPEHURISDFNHWVWUDQVPLWWHGIRUWZRXVHUVHWVIRU SXUHGHDGUHFNRQLQJWKHVLQJOHVWUDWHJ\K\EULGPHWKRGDQGWKH PXOWLSOHVWUDWHJ\K\EULGPHWKRG7ULDOLVWKHLQLWLDOWULDO 7KUHVKROGYDOXH 3XUH'5 +66 +06 7ULDO 8VHU8VHU8VHU8VHU8VHU8VHU                                           7DEOH7KHQXPEHURISDFNHWVWUDQVPLWWHGIRUWZRXVHUVHWVIRU SXUHGHDGUHFNRQLQJWKHVLQJOHVWUDWHJ\K\EULGPHWKRGDQGWKH PXOWLSOHVWUDWHJ\K\EULGPHWKRG7ULDOLVWKHLQLWLDOWULDO 7KUHVKROGYDOXH 0 100 200 300 400 500 600 0 50 100 150 200 250 300 350 400 )LJXUHD$SORWRIWKHILUVWWUDMHFWRU\DWWHPSWIRUXVHUWZR7KH WUDMHFWRU\ZDQGHUVDQGH[SORUHVGLIIHUHQWGHDGHQGVZLWKLQWKH HQYLURQPHQW7KHWKUHVKROGLVVHWWR 3DFNHW7UDQVPLWWHG « 6WUDWHJ\PRGHO 8VHUWUDMHFWRU\ 3DFNHW7UDQVPLWWHG « 6WUDWHJ\PRGHO 8VHUWUDMHFWRU\ ;&RRUGLQDWH <&RRUGLQDWH ;&RRUGLQDWH <&RRUGLQDWH 0 100 200 300 400 500 600 0 50 100 150 200 250 300 350 400 )LJXUHE$SORWRIWKHIRXUWKWUDMHFWRU\DWWHPSWIRUXVHUWZR 7KHWUDMHFWRU\LVVWHDG\DQGSURJUHVVHVGLUHFWO\WRWKHWDUJHW LOOXVWUDWLQJDVWHDG\VWDWHXVHUVWUDWHJ\7KHWKUHVKROGLVVHWWR &21&/86,216$1')8785(:25. 7KH UHVXOWV SUHVHQWHG LQ WKLV SDSHU VKRZ WKDW H[SHULHQFHGXVHUVLQDVLPSOHJDPHOLNHHQYLURQPHQWZLWK ZHOOGHILQHG JRDOV YHU\ TXLFNO\ FRQYHUJH RQ FRPPRQ VWUDWHJLHVWRDFKLHYHWKHP%\LQWHJUDWLQJWKLVLQIRUPDWLRQ LQWR D QRYHO K\EULG PXOWLSOHVWUDWHJ\ DSSURDFK WKLV SDSHU KDV VKRZQ WKDW WKHUH LV D UHGXFWLRQ LQ WKH QXPEHU RI WUDQVPLVVLRQSDFNHWVUHTXLUHGWRPDLQWDLQILGHOLW\ DFURVVD 'LVWULEXWHG,QWHUDFWLYH$SSOLFDWLRQ )XWXUH ZRUN ZLOO LQYROYH ORRNLQJ DW DOWHUQDWLYH WHFKQLTXHVIRUH[WUDFWLQJWKHORQJWHUPVWUDWHJ\PRGHOV,Q WKH FDVH RI QRYLFH XVHUV ZH DUH KRSLQJ WKDW DUWLILFLDO LQWHOOLJHQFHWHFKQLTXHVPD\KHOSXVEHWWHUJXHVVZKDWWKH\ PD\GRLQSDUWLFXODUHQYLURQPHQWV0RGHOEOHQGLQJLVDOVR EHLQJ LQYHVWLJDWHG LQ RUGHU WR DFKLHYH PRUH QDWXUDO FRQYHUJHQFH RI HQWLWLHV ZKHQ VWDWHXSGDWH LQIRUPDWLRQ UHTXLUHVDFRUUHFWLRQWREHPDGH$QRWKHUDUHDRIUHVHDUFK LV WR FRQVLGHU WHFKQLTXHV IRU WKH TXDQWLILFDWLRQ DQG DVVHVVPHQW RI WKH SV\FKRSHUFHSWXDO HIIHFWV RI WKHVH DOJRULWKPVRQXVHUV $&.12:/('*(0(17 7KLVZRUNZDVIXQGHGE\(QWHUSULVH,UHODQG6& 5()(5(1&(6 >@ 6,1*+$/6.$1'=<'$0 1HWZRUNHG9LUWXDO (QYLURQPHQWV66SHQFHU$&03UHVV >@ ',27&$1'*$87,(5/ $'LVWULEXWHG$UFKLWHFWXUH IRU0XOWLSOD\HU,QWHUDFWLYH$SSOLFDWLRQVRQWKH,QWHUQHW ,(((1HWZRUN-XO\$XJXVW >@ )$,6671$8(5&6&+0$/67,(*'$1'385*$7+2)(5: 6FKHGXOLQJIRUYHU\ODUJH9LUWXDO(QYLURQPHQWVDQG 1HWZRUNHG*DPHVXVLQJ9LVLELOLW\DQGSULRULWLHV,Q 3URFHHGLQJVRIWKHWK,(((,QWHUQDWLRQDO:RUNVKRSRQ 'LVWULEXWHG6LPXODWLRQDQG5HDO7LPH$SSOLFDWLRQV 6DQ )UDQFLVFR&DOLIRUQLD$XJXVW >@ /,$1*/$+&$,:/((86$1'7851(56- 3HUIRUPDQFH$QDO\VLVRI3DFNHW%XQGOLQJ7HFKQLTXHVLQ ',6,Q3URFHHGLQJVRIWKHUG,(((,QWHUQDWLRQDO :RUNVKRSRQ'LVWULEXWHG,QWHUDFWLYH6LPXODWLRQDQG5HDO 7LPH$SSOLFDWLRQV0DU\ODQG2FWREHU >@ 7$11(1%$80$6 &RPSXWHU1HWZRUNV7KLUG (GLWLRQ 3UHQWLFH+DOO >@ &$,:/(()%6$1'&+(1/$Q$XWRDGDSWLYH 'HDG5HFNRQLQJ$OJRULWKPIRU'LVWULEXWHG,QWHUDFWLYH 6LPXODWLRQ,Q3URFHHGLQJVRIWKHWK:RUNVKRSRQ3DUDOOHO DQG'LVWULEXWHG6LPXODWLRQ$WODQWD0D\ >@ 9$/(17,12*-7+20362167.1,2/$7$1' &$5/,6/(&- $Q603EDVHG/RZODWHQF\1HWZRUN ,QWHUIDFH8QLWDQG/DWHQF\PHDVXUHPHQW6\VWHPWKH 61$3S\V\VWHP,Q3URFHHGLQJVRIWKHQG ,((( ,QWHUQDWLRQDO:RUNVKRSRQ'LVWULEXWHG,QWHUDFWLYH 6LPXODWLRQDQG5HDO7LPH$SSOLFDWLRQV-XO\ >@ %$66,281,0$0,1*+6,1*&/23(50*$516(< 0$1':,//,$06-3HUIRUPDQFHDQGUHOLDELOLW\ DQDO\VLVRIUHOHYDQFHILOWHULQJIRUVFDODEOHGLVWULEXWHG LQWHUDFWLYHVLPXODWLRQ$&07UDQVDFWLRQVRQPRGHOLQJDQG FRPSXWHUVLPXODWLRQ-XO\ >@ ,(((,(((6WDQGDUGIRU'LVWULEXWHG,QWHUDFWLYH 6LPXODWLRQ$SSOLFDWLRQ3URWRFROV,(((6WG >@''(/$1(<7:$5'60&/221(µ2Q5HGXFLQJ (QWLW\6WDWH8SGDWH3DFNHWVLQ'LVWULEXWHG,QWHUDFWLYH 6LPXODWLRQVXVLQJD+\EULG0RGHO¶3URFHHGLQJRIWKHVW ,$67(',QWHUQDWLRQDO0XOWLFRQIHUHQFHRQ$SSOLHG ,QIRUPDWLFV ,6%1)HEUXDU\ >@'85%$&+&$1')2851($8-03HUIRUPDQFH HYDOXDWLRQRIDGHDGUHFNRQLQJPHFKDQLVP,Q3URFHHGLQJV RIWKHQG,(((,QWHUQDWLRQDO:RUNVKRSRQ'LVWULEXWHG ,QWHUDFWLYH6LPXODWLRQDQG5HDO7LPH$SSOLFDWLRQV $WODQWD *HRUJLD0D\ >@38//(1-0 5HOLDEOH0XOWLFDVWQHWZRUN7UDQVSRUW IRU'LVWULEXWHG9LUWXDO6LPXODWLRQ,Q3URFHHGLQJVRIWKHUG ,(((,QWHUQDWLRQDO:RUNVKRSRQ'LVWULEXWHG,QWHUDFWLYH 6LPXODWLRQDQG5HDO7LPH$SSOLFDWLRQV &ROOHJH3DUN 0DU\ODQG2FWREHU >@:257+,1*721%*$1'52%(576'-  (QFDSVXODWLQJ1HWZRUN/DWHQF\&RPSHQVDWRUVLQ950/,Q 3URFHHGLQJVRI9:6,09LUWXDO:RUOGVDQG6LPXODWLRQ &RQIHUHQFH,QW&RQI6&6:HVWHUQ0XOWLFRQIHUHQFH 6DQ 'LHJR86$-DQXDU\ >@52%(576'-$1'6+$5.(<30 0D[LPLVLQJ &RQFXUUHQF\DQG6FDODELOLW\LQD&RQVLVWHQW&DXVDO 'LVWULEXWHG9LUWXDO5HDOLW\6\VWHPZKLOVWPLQLPLVLQJWKH HIIHFWRI1HWZRUN'HOD\V,Q3URFHHGLQJVRIWKHWK ,((( :RUNVKRSRQ(QDEOLQJ7HFKQRORJLHV,QIUDVWUXFWXUHIRU &ROODERUDWLYH(QWHUSULVHV-XQH >@)$,6671$8(5&6&+0$/67,(*'$1'385*$7+2)(5: 3ULRULW\5RXQG5RELQ6FKHGXOLQJIRUYHU\ODUJH9LUWXDO (QYLURQPHQWV,Q3URFHHGLQJVRIWKH,(((9LUWXDO5HDOLW\ &RQIHUHQFH1HZ-HUVH\0DUFK >@&+$6627&/2=(6$*$5&,$)',$=0'$,5$,1($1' /52-$6/4R6UHTXLUHGE\D',6DSSOLFDWLRQLQD QHZJHQHUDWLRQ,QWHUQHW,(((6SULQJ6LPXODWLRQ ,QWHURSHUDELOLW\:RUNVKRS2UODQGR0DUFK 3DFNHW7UDQVPLWWHG « 6WUDWHJ\PRGHO 8VHUWUDMHFWRU\ ;&RRUGLQDWH <&RRUGLQDWH