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 *  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