Skip graphs - Computer Science & Engineering

!!"$# 12!346587:9;4 =>?A@CB"DFEG@:HJIKE;DFLENM:O8P"L6QSRT?UIWVFDX?AY:ZTVFLR[R:E8V\ENIVXDFZJ]^VXZ:DFLG_ YJE"IL*R&O"MÌX=>?a@bQA?AIVFI_cVXH E8V@:DFO8P>?ARTLdVFH:LKefZ:QAQ/efZ:MJ]^VX?AOGMJEGQhg ?aVWijO;e EkYJE;QUE;MJ]6LRlVFDXLLm?AMNEnRT?UIWVFDX?AY:ZTVFLR&IXiTIWVFL6oqpSH:LDXL L6QAL6oKLM"V\IrEGDXLsIVXOGDFLR`?AMtIL@JE;D\E8VFLsM:OTRTLIVXHJE;VrosE$iuevE;?AQ E8VE;M>iVX?AoKLGwxyH:LiuE;DFLmRTL*I?ABGMJLRlefO"DZ ILm?aMÌL*E;D\]\H:?aMJB @L6L6DXgzVXO;g{@L6L6D|M:L^VWp}OGDF=TI6_$E;M RY>i@JDXO8P>?URT?aMJByVXH:LyE;Y:?AQA?hVWiVXO @L6DXefOGDFo~"ZJL6DF?aL*I Y EGIXLRsO"Mn="L6iKOGD\RTL6DF?AM:BJ_"VXH:Li?Aod@JDXO8P"L OGML^T?UIWVF?aMJBbIXLEGDF]\HVXO>OGQUIKVFHJE8Vs@:DFO8P>?ARTLlO"M:QaiHJEGIXHV\E8g Y:QALefZ:MJ]^VX?AOGMJEGQa?aVWiGwy,MJQa?A=GLrIX=>?a@lQA?AIVFIOGD,OGVXH:LDSVXDFL6LRJE8VFE IVXDFZJ]VFZ:DXL*I6_I=>?A@sBGD\E;@:H I/E;DFLSH:?aB"H:QAimDFLIX?aQA?AL6MV_GVXOGQAL6D\E8VF?aMJB E`QAEGDXB"LefDFE"]VX?AOGMO;eevE;?AQaL*RM:OTRTLIKpS?aVXH:O"ZTVkQAO"IX?aMJB`]6OGMTg M:L*]VX?AP>?hVWi"w!MkEGR:R:?hVF?aO"M_]6OGMJIVXDFZJ]^VX?AM:BJ_?aM ILDVF?aM:BrM:L6pLQhg L6oKLM"V\I.?AMVXO _$IXLEGDF]\HJ?aM:BEIX=?A@BGD\E;@JHE;MJRR:L^VXL*]VF?aM:BE;M R DFL6@JEG?aDF?aMJBnLDXDFOGD\I?AMNVXH:LR:E;VFElIVXDFZJ]VFZ:DXLK?AMVXDFO>R:ZJ]^L*R&Y>i M:OTRTLevEG?aQAZ:DFLI,]E;MjYLrRTO"M:LZJIX?aMJBI?AoK@:QaLmE;MJRjIVXD\E;?ABGHVg efOGDFpyE;D\RkE;QABGO"DX?aVXHJoKIw ^ 4658|9G4 L 6LDgzVXOGgz@L6LDMJL^VWp}OGDF=>IEGDXLsRT?UIVXDF?aY:Z:VXLRbIXiTIWVFL6osIpS?hVFHTg OGZ:VmE;M>iN]6L6MVXD\E;Q E;ZTVFH:OGDF?hVWi&VXHJE;VmE;DFLsZJIXLRèfO"DL^]^?AL6MV QAO>]E8VF?aO"M&O;e}IHJEGDXL*RjDFLIXOGZ:D\]^L*I6wZJ]\HÌiTIVXLoKIHJE$P"LrYL^g ]Ô"oKL P"L6DFi@OG@JZ:QAEGD.efO"D!M"VFL6DFM:L^V/E;@J@:Qa?U]6E;VX?AOGMJI|?AMdEIH:O"DV @L6DF?aOTROGe,VX?AoKLGwbIXZ:DFPGL6iÒ;eDXL*]^L6MVr@L6LDgzVXOGgz@L6LDrDFL^g IXLE;D\]\H&i>?AL6QUR:IElIQAL6pO;eSRTLIX?aD\E;YJQaLmefLE;VXZ:DFLIefO"DE@L6LDg VXOGgz@L6LDbM:L^VWp}OGDF=IZJ]\HEGI`RTL]6L6MVXD\E;QA?AE8VF?aO"M_KIX]E;QUE;Y:?AQhg ?aVWiG_!evE;ZJQhVXgVFOGQAL6D\E;MJ]6LG_IXL6Qaeg{IVFEGY:?aQA?AE8VF?aO"M_/R:E8V\E&E$P8E;?AQUE;Y:?AQhg ?aVWiG_>QaOEGRsY E;QUE;MJ]6?aM:B _R:iM E;oK?A]EGRJRT?hVF?aO"MkE;M RkRTLQaL6VX?AOGMkOGe @L6L6D/MJO>R:LI_;L^]^?AL6MVE;M Rm]6OGoK@:QAL^r~Z:L6DFiIXLE;D\]\H:?AM:BJ_8?AMTg ]Ô"DX@OGD\E8VF?aMJBSBGL6O"BGD\E;@:H>i,?AMrIXLEGDF]\H:L*IE;M RL^T@:QAOG?aVX?AM:BIX@JE8g VX?UE;Q|EGIyp}L6QAQEGI}VXLoK@ O"DFEGQcQaOT]6EGQa?aVWi?AMjIL*E;D\]\H:LIw/xyH:L?aMJ?hg VX?UE;QIiTIVXLoKI_"IXZJ]\HE"IEG@JIWVFL6D / _>¡M>ZTVFL6QAQAEk ¡ E;M R£¢:DFL6LM:L^VN ¢!¤,¥ _RT?UR£MJO;VnIXZ:@:@OGDXVnoKO"IVnOGeVXH:L*IL efLE;VXZ:DFLI¦E;MJRdp}L6DFL,]^QALE;DFQAiZ:MJIF]6EGQAEGY:QaLSL?hVFH:L6D RTZ:LSVFOVXH:L ZJIXLO;e/Ed]6L6MVXD\E;QcIXL6DFPGLD§EG@JIWVFL6D¨ OGD,RTZ:LVFOsH:?aB"HnoKL*IWg IFE;BGL ]ÔGoK@:QAL^T?aVWiefDXO"o©@L6DXefOGDFoK?aMJBIXLE;D\]\H:L*IY>iªJO>O>R:?aM:B VXHJLM:L^VWp}OGDF=&§¡M>ZTVFL6QAQAE¨w}xyH:L@ LDefO"DXosEGMJ]^LO;e/¢:DFL6LM:L^V ?UIRT?as]6Z:QaVVXOLP$EGQaZ E8VXL"_yY:ZTVk?aV@:DFO8P?URTL*IKM:O@:DFO8P$EGY:QAL

\« ¬W®8¯\°±²SW³6±´\µ ¶´²S®$·*±W°¸6¹º»W³$¹W¼.½¯\¾»¿.³$º À^W°zÁº ±Â6¼.Ã.Ä Å ¯WÀ^W³¼}¶cÆ©ÇÈÉÊÇFËfÌÊÌÉ*¼S¿¸Í Î.Ï ²,¯\º»¾UÐlÑ6ÒÓÔ6Õ6ÒFÖ6×ÒØUÙ^Ñ^Ú\ÕTØÕ\Û\Ü8Î ¸·$®*®G´°v±zWÝÞ^ÂÃ!¸ßsà°z¯\³6±Á¶.¶cácËfâÌÊÇÌÌÌS¯\³$Ý¶.¶cácËfÇÇâÌÇ^ã\Ì*Î ä ¬W®8¯\°±²SW³6±´\µ ¶´²S®$·*±W°¸6¹º»W³$¹W¼.½¯\¾»¿.³$º À^W°zÁº ±Â6¼.Ã.Ä Å ¯WÀ^W³¼8¶ÆkÇÈÉÊÇFËfÌÊÌÉ*¼$¿!¸Í¦Î^Ï²,¯\º»¾UÐJÒå6ÑFå6Ö6×ÒØUÙ^Ñ^Ú\ÕTØÕ\Û\Ü8Î¸·$®*Ë ®;´°±WÝÞ^ÂÃ¸ßKà°{¯\³^±Á!¶¶cáËâÌÊÇÌÌÌS¯\³$Ý¶¶cáËÇÇâÌÇ^ã\Ì*Î

%& '!(*),+.-/-/0 B"ZJE;D\E;MVFL6LO"MkVFH:LIL*E;D\]\HkQUE8VFL6MJ]6iE;MJRn@ LDXoK?aVFI,E"]6]6LIFI?ag YJQaLR:E;VFEmVXOsYLoK?AIFIL*Rcw ¤SL*]^LM"V IiTIVXL6osI Qa?A=GL æ} ¤,¢!çèéJê _ æ HJOGD\R ]E8VF?aO"MZ I?AM:B VXHJL£O8PGLDXQUE$i B"DFEG@:H ?UIR:OGM:Lü?aMôVXH:L*IL©P8E;DF?aO"ZJIIXiTIWVFL6osIY>i ZJIX?aMJB R:? L6DFL6MVlDXO"ZTVX?AM:B[E;QABGOGDF?aVXH:osIw EGIVXDFiE;MJR©x|EG@ L*IWVFDXi Z IL*I QUE8>VXO"M IuE;QABGO"DX?aVXH:o ¤,¤ _mpSH:?A]\H?UIuY EGIXLR O"MH>i>@ LDF]6Z:Y L©DFOGZTVF?aM:B VXH:L oKLIFIFE;BGLÿ?AICefOGDFpyE;D\RTLR R:L^VXLDXoK?AM:?UIWVF?A]E;QAQaiVFOEMJL6?ABGH>Y O"D/pSH:O"IXLy?AR:L6MVX? JL6D/?UI!OGMJL R:?aB"?hVr]6QaOILDVXOlVXHJLKVFE;DFBGL6V?AR:L6MVX? JL6D*wæ} @JE;DXVX?aVX?AOGM I E ;gRT?AoKL6MJIX?aO"MJE;Ql]Ô>O"DFRT?AMJE;VXLÿIX@JEG]6Lÿ?AMVXO VXHJE;V EGDXLCO8pSM:LRY>iM:OTRTLIbpSH:?U]\HýIVXO"DXL=GLiTI&osE;@J@ L*R VFO VFH:L6?ADd6OGMJLGw¤SOGZ:VX?AM:B&?UIKRTOGM:LnY>i`B"DXLLRT?AQAiNefO"DXpyE;D\RT?AM:B oKL*IXIFE;B"LIVXOnVXH:LKM:L?aB"HYOGD]6QaOIL*IWVVXOVXHJLmV\E;DFBGL6VOGM:L"w æ HJOGD\R oKEG@JICM:OTRTLIE;MJRôDXL*IO"Z:D\]^LIVXO?URTLM"VF?hVF?aL*IO;e Y:?aVFIK@JQAE"]^LRCE;DFOGZ:M RtE uó EGMJRôR:OL*IBGDFL6LR:iDFOGZ:VX?AM:BVFOVFH:L©evE;DXVXH:L*IWV[@O"IFI?AY:QAL MJO>R:L[IVXO"DXL*R ?AMVXH:LDFOGZTVF?aMJBÿV\E;Y:QALGw ëjOIWVOGekVXHJLIXL IXiTIWVFL6osIyZJIXL K§fQAOGB .ÿI@JE"]^LEGMJRnVX?AodLefO"D,DFOGZTVF?aM:BsEGMJR K§vQaO"B .¨VX?AoKLefO"DrM:OTRTLn?aMJIXL6DXVX?AOGM.w L*]6EGZJILkHJEGIXH:?AM:B R:LIVXDFO8i>IVXHJLdO"DFR:L6DF?aM:BnOGM`=GLi>I_íçxIiTIVXL6osIRTOlM:OGV IXZ:@:@OGDXVm~Z:LDX?ALIVXHJE;VdIXL6L6=`M:L*E;DosE8V\]\H:LIVXOÈj=GLiNO"D ="L6iTI}pS?hVFH:?AMlEKB"?aP"L6MnDFEGM:BGL"w O"oKLÒGerVFH:LIXLtIiTIVXLoKInVFDXiVFOOG@TVF?aoK?A6Lb@L6DXefOGDXg osEGMJ]^L}Y>iVFE;=>?AM:BQAOT]6EGQa?aVWi?aMVFOE"]6]Ô"Z:MVw EGIVXDFid ¤,íé:êG_ æ}íç¤é"ó E;M RkxE;@LIVXDFil îìrïé:ê8_Jïîìé"ó L^T@:QAOG?aV B"L6OGg B"DFEG@:H:?U]6EGQ;@:DFO$>?AoK?hVWiY>i]\HJOOI?AM:ByVFH:L¦@:H>iTIX?A]E;QAQai]^QAO"IXLIV MJO>R:L¦OGZ:VOGeJE;QAQ"VFH:L}@ OIXIX?aYJQaL M:OTRTLI|pS?hVFHmEGMmE;@J@:DXO"@:DF?AE;VXL ?URTLM"VF? L6DS@:DFL :cwM&æ} ¤¢çè/é:ê _JL*EG]\HM:OTRTLoKLE;g IXZ:DFLI ?hV\ISDFOGZ:MJRTgVFDX?A@nRTLQAE$iKVFOdEKIXL^VSO;e|QAEGMJRTosE;DF=sM:OTRTLI EGMJRkE"]6]6OGD\RT?aMJBGQAid@JQAE"]^LI ?aVFIXL6Qae|?AMkVFH:L]Ô;g{OGD\RT?AMJE8VFLIX@JEG]6L VFOtevE"]^?AQa?aVFE;VXL`DXO"ZTVX?AM:BpS?aVXHüDXL*I@L]^VnVFOM:L6VWp O"DX=[@:DFO$>g ?AoK?hVWi"wxyH:?UIdQAE"IWVKoKL^VXHJO>R?AIdM:OGVKefZ:QaQAitIXL6QaegzO"DXBE;M:?A6?AM:B

!

32

2

654

#"%$&#')(*$ +,'-/.$0-1.'

,4

/7

E;M RmosE$ir]E;ZJIXLy?aomYJE;QUE;M ]^Ly?aMKVFH:L,RT?UIWVFDX?AY:ZTVF?aO"MKO;eM:OTRTLI QALEGR:?aM:BVFOH:O;V\I@O;V\I6w/OGoKLyoKL^VFH:OTR:I!VXOIXOGQAPGL}VFH:LSM:LEGDg LIV|MJL6?ABGH>Y O"D@:DFOGY:QAL6oüefOGDO8PGLDXQUE$i,M:L6VWp O"DX=TIc]E;MYL IXL6LM ?AMb çì¤ïé"ó EGMJRb ì¤é"ó w OGoKL£OGejVXH:L*ILüIiTIVXL6osItEGDXLÿ@JE;DXVXQAiDFLIX?aQA?AL6MVtVXO D\E;MJRTO"oM:OTRTLevE;?AQAZ:DXL*I6_TYJZTVSVXH:L?aD@ LDefO"DXosE;M ]^LoKE$ikY L YJE"RTQaim?aoK@JEG?aDFLRdY>imE"RTPGLDFIFE;DF?UE;Q>RTL6QAL^VF?aO"MsO;eM:OTRTLIw¢?UE8V E;M RCMJEGoK?A]E;QAQaiosEG?aMVFEG?aMlIXZJ]\HjEdIXiTIWVFL6olw x.LDXD\EGí?ADN < yìé"ó ?AIEDFL]6L6MVIXiTIWVFL6oVXHJE;V@:DFO;g P>?AR:LI|QaOT]6EGQa?aVWiE;MJRrosE;?AM"V\E;?AMJI.EH:?AL6D\E;D\]\H:?U]6E;Q"R:E8V\EIVXDFZJ]g VXZJDXLmZJI?AM:Bk]EG]\H:?AM:BkEGMJRjDFL6@:QA?U]6E8VF?aO"Mw,xyH:LDXLdE;DFLrEGIiGL^V M:Ou@JDXO8P8E;YJQaLB"ZJE;D\E;MVFL6LIO"MQaOEGRbYJEGQAEGMJ]^?AM:B&EGMJRèvE;ZJQhV VXO"QaLDFEGMJ]^LefOGDyVFH:?UI,IiTIVXLow !7

v .5 7 58 7:9$ö xyH:LtZ:MJR:L6DFQai>?AM:B£IWVFDXZ ]VXZJDXLtOGe

æ H:O"DFRc_"æ}_;EGMJRrIX?aoK?AQAEGDíçxSI!DFLIXL6omY:QALIE,YJEGQAEGMJ]^L*R VXDFL6L?aMnpSH:?U]\HkYJEGQAEGMJ]^?AM:BrRTL@ LMJR:I}OGMkVXH:LM:L*E;DXgzZ:MJ?hefO"DXo RT?UIWVFDX?AY:ZTVF?aO"MtO;eyVFH:LkO"ZTVX@:Z:VmO;eSVFH:LHJE"IHtefZ:MJ]VF?aO"MwNO VXHJL]6O"IVFI O;e|]6OGMJIVXDFZJ]VF?aMJBJ_oKEG?aMV\E;?AM:?aMJBJ_TE;MJRkIL*E;D\]\H:?aMJB VXHJLIXLkR:E8V\EuIVXDFZJ]VFZ:DXL*I?UIr]6QaOILDVXOuVXH: L d§fQAOGB .¨]6O"IVFI O;e¦VXDFL6LdOG@L6D\E8VX?AOGM ISVXH E;MuVFH:

L d§Wê$¨,]ÔIWV\IO;e/VXD\EGR:?hVF?aO"MJE;Q HJE"IHKV\E;Y:QALIw Z:V¦Y L*]6EGZJIL=GL6iTI E;DFLSHJEGIXH:LR_íçxSI}]6EGM @:DFO8P>?ARTLO"M:QAiH EGIXHlVFE;YJQaLefZJMJ]VF?aO"MJE;QA?hVWi" w Z:DE;@:@:DFO"E"]\H ?UIlVXO£L6T@:QaO"?hVjVFH:LtZ:M RTL6DFQai>?AM:BVXDFL6LtIVXDFZJ]VFZ:DFLbVXO£B"?aP"L VXDFL6L¦efZ:MJ]^VX?AOGMJEGQa?aVWiG_8pSH:?AQAL}EG@:@:QAi?AM:BEIX?aoK@:QAL RT?UIVXDF?aY:Z:VXLR YJEGQAEGMJ]^?AM:BkIF]\H:L6oKLVFOk@:DFLIXL6DFPGLY E;QUE;MJ]6LrE;MJRjR:?AIVXDF?aYJZTVXL QAO"EGRw

LmRTLIF]^DF?aYLEKM:L6p©oKOTRTL6QcefO"D,EK@ LL6DXgVFO;g{@ LL6DSM:L6Vg p}OGDF=uYJEGIXLRÒ"MÈjRT?UIVXDF?aY:Z:VXLRRJE8VFEjIVXDFZJ]^VXZ:DFLdVXHJE;Vrp L ]6EGQaQ E 3 5$7 ö wjxyH:?AImRT?UIWVFDX?AY:ZTVFLRR:E;VFEjIVXDFZJ]VFZ:DXL HJE"IIXL6PGLDFEGQcY LM:L JVFIw,¤SLIXOGZ:D\]^LQAOT]6E8VF?aO"MuE;MJRjR:iM E;oK?A] M:OTRTLsEGRJRT?hVF?aO"MÈGMJR`RTL6QAL^VF?aO"M`]E;M`Y LsRTO"M:LK?aM`QaO"B"EGDX?aVXHTg oK?A]NVF?aoKLG_EGMJR£L*EG]\HÿMJO>R:L`?AM EIX=>?a@üBGD\E;@:HüDXL*~Z:?aDFLI OGMJQai©QaO"B"EGDX?aVXH:oK?U]I@ EG]^LtVXOÿIVXO"DXLt?AMTefO"DXosE8VF?aO"M E;YOGZTV ?aVFI,MJL6?ABGH>Y O"DFIw¦ëjO"DXL?AoK@ O"DV\E;MVXQAiG_JVXH:LDXL?UISM:OsHJE"IHJ?aM:B O;e¦VXH:LKDFLIXOGZ:D\]^L="L6iTIIOnDXLQAE;VXL*RuDFLIXOGZ:D\]^L*IE;DFLr@JDXL*ILM"V M:L*E;DrL*EG]\HOGVXH:LDr?AME&IX=>?a@B"DFEG@:Hw&xyH:?UImoKE$i`YLkZJIXL^g efZ:QsefO"D]^L6DXVFEG?aME;@:@JQa?U]6E;VX?AOGMJIbIXZJ]\HE"I`@:DXL6efL^V\]\H:?aMJB©OGe p}L6Y@ E;BGL*I6_¦L6M:HJEGMJ]^L*RYJDXO8p,IX?aMJBNE;M RL6s]6?aLMVKIXLEGDF]\HTg ?AM:BJw!=>?a@mBGD\E;@:HJI.E;QUIOIXZ:@:@OGDXV 9" øõ c|õ58võ>3 IZ ]\H EGIrDFEGM:BGL~Z:LDX?ALI_?w LGwjQAOT]6E8VF?aMJBuDXL*IO"Z:D\]^LIpSHJO"IXL=GLi>I QA?aLKpS?aVXH:?AMEn]6L6DXVFE;?AMbI@L]6? JL*R&D\E;MJBGLGwmxyH:L6DFLKHJEGIYL6L6M IXOGoKL?aMVXLDXL*IWV,?AMjIZJ@:@ O"DVF?aMJB]ÔGoK@:QAL^l~Z:L6DF?aL*Iy?aMl@L6LDg VXOGgz@L6LDgIXi>IVXLosI çççèéó _}EGMJRCR:LIX?aB"M:?aMJBbEbIXiTIWVFL6o VXH E8VuIZJ@:@ O"DV\IlDFEGM:BGLb~Z:L6DF?ALIHJEGIYL6LM©@O"IXLRüEGIjEGM OG@L6Ml~Z:LIVX?AOGM.w¦=>?a@BGD\E;@:H I}EGDXLDFLIX?aQA?aLMV}VFOKM:OTRTLevE;?AQhg Z:DFLI E,IX=?A@BGD\E;@JHVFOGQAL6D\E8VFLIcDFL6oKO8P8E;Q;OGe:ESQAEGDXB"L!efDFE"]VF?aO"M O;e?aVFI}M:OTRTL*I ]\HJO"IXL6MkE;V D\E;MJRTO"o pS?hVFH:OGZTVyYL]Ô"oK?aM:BdRT?UIWg ]Ô"M:M:L*]VXL*Rc_8E;MJRLPGL6MVFH:LQAO"IFIcO;e:EGM K§ê QAOGB .ëfDFE"]VF?aO"M 4

7

2

4

OGeVXHJLMJO>R:LIy]\H:O"IXL6MkYiEGMnE"RTPGLDFIFE;DFidIVX?AQAQcQaL*E$PGLI¦oKO"IV OGe:VXHJL M:OTRTL*I?aMmVXH:L}QUE;DFBGLIVIXZ:DFP>?aP>?AM:B]6OGoK@ O"M:L6MV*w!=>?A@ B"DFEG@:HJI]E;MkEGQAIXOYL]6OGMJIVXDFZJ]^VXLRpS?hVFH:OGZTV}=>M:O8pSQaL*RTBGLO;e VFH:LVFO;V\E;Q¦M>Z:omY LDmOGeSM:OTRTLIm?aMCEGRTP8E;M ]^LGwjMC]ÔGMVFDFE"IWV*_ íçxqIXiTIWVFL6osIkIXZJ]\H£E"I EGIVXDFiCEGMJRÿæ H:O"DFR[DFL~Z:?ADXL S=>M:O8pSQALRTB"LrE;YOGZ:VVFH:LmIX?aLrOGeVXH:LdIiTIVXLo O"D?aVFI ="L6iTIX@JEG]6LGw xyH:LDXL*IWVuOGemVFH:Lt@JEG@ LD&?UIjOGDFB"EGM:?aLR©EGIlefO"QaQAO8p,I p}LRTLIF]^DF?AY LIX=?A@BGD\E;@:HJIbEGMJRýEGQaB"OGDF?hVFH:osIèfOGDbVFH:L6o ?AMRTL^V\E;?AQr?AML]^VX?AOGM óTwûL*]VX?AOGM I E;MJ! R £RTL*IX]6DX?AYL VFH:LKDXL@JE;?ADoKL]\HJEGM:?AIXo E;M RuevEGZ:QhVXgVFOGQAL6D\E;MJ]6Lm@JDXO"@ LDVF?aL*I efO"DEýIX=>?a@BGD\E;@:Hw æ OGMVXLM"VF?aO"MEGMJE;QAiTI?UICEGMJRQaOEGR Y E;QUE;MJ]6?aM:BKDFLIXZ:QaVFISE;DFLRTLIF]^DF?AY L*Rn?AM&L*]VX?AOG M ":w¦¢?aMJEGQaQAiG_ p}L]Ô"MJ]^QAZJRTL?AMj3*37' õ(!7:3*3 L6M>P>?ag DFOGMJodLMV&?aMpSH:?A]\HýE;QAQr@:DFOT]^LIFIXLIu]6OGoKorZ:MJ?A]E8VXLCpS?hVFH L*EG]\HO;VFH:L6D.YiILMJRT?AM:B,oKLIFIFE;BGL*IO8PGLDE,]Ô"odomZ:M:?U]6E;VX?AOGM ]\H E;M:M:LQwxyH:LSIiTIVXLo?AI !7T5$4v7Jøv*ø )u+3 ) 9*ö|58 |3 _G?zw L"wa_ VFH:L6DFL,?UI E :TLRsZJ@:@ LD YOGZJMJRu§VF?aoKL6gzO"ZTV\¨¦OGMsVFH:L,VFDFEGMJIg oK?UIXIX?AOGMmR:L6QUE$iO;eEoKLIFIFE;BGL"w DFOT]^L*IXIXLI]6EGM 9G5$7J3ö _G?zw L"wa_ H E;QaV@:DFL6osE;VXZ:DFL6QAiG_8E;M Rr]^D\EGIXH:L*I.E;DFL¦@L6DFosE;M:LMVw L}ZJIXL VFH:LVFL6DFo ,VXOsDFL6@JDXL*ILM"VEK@JDXOT]^L*IXISVXHJE;V?AI,DXZ:MJM:?aMJB O"MuEs@JEGDVF?A]6Z:QAEGD,osEG]\H:?AM:L"w LdEGIFIZJodLVXHJE;VLE"]\HlodL*IWg IFE;B"L,V\E;=GL*IyE8VyodOIWVSZ:MJ?hVyVX?AoKLVXOKY LRTLQa?APGLDXL*RE;M RnEGMi ?AMVXLDXMJEGQ@:DXOT]6LIFI?AM:BsE8V,EdosEG]\H:?AM:LVFEG=GLIyMJOmVF?aoKL"w

#

5$7ö3 3+*øv34 Z:B Gé ?UIsE`DFEGMJRTO"od?A6L*RtYJEGQAEGMJ]^L*RVFDXLL RJE8VFEbIVXDFZJ]VFZ:DFLO"DXBE;M:?A6L*RE"IsE&VFO8p LDKO;e?aMJ]6DXL*EGIX?aMJBGQAi IX@JEGDFIXLKQa?AM:=GL*R`Qa?UIWV\I6/ w .LPGLQ¦élO;eSEjI=>?A@Qa?UIVr?AIrElQa?AM:=GL*R QA?UIWVOGe¦E;QAQ|MJO>R:LI,?AMu?AMJ]^DFLE"I?AM:BsO"DFRTLDY>i=GL6i"w¢:O"DL*EG]\H 0 BGDFLE;VXLDVXH E;MÿéJ_,LE"]\HM:OTRTL&?AM£QAL6PGLQ 021 ê&E;@J@ L*E;D\I ?AM`QaLPGL6Q 0 ?aMJR:L6@L6MJRTLMVXQAiNpS?aVXHIXOGoKL :TLRN@:DXO"YJE;YJ?aQA?hVWi 3 wMEÿRTO"Z:Y:QAigzQA?aMJ=GLRIX=>?a@ýQa?UIV_dLEG]\HM:OTRTLCIVXO"DXL*I E©@:DFLR:L]^L*IXIXOGD`@OG?AM"VFL6DEGMJRE©IXZJ]]^LIFIXOGDb@ O"?aMVFL6DefO"D L*EG]\H`Qa?UIVr?aMpSHJ?A]\Hb?aVmE;@:@LEGDFI_efO"DrE;MtE$P"L6D\E;B"LrO;e 4657 @OG?AMVXLDFIb@L6DCM:OTRTLGw xyH:L£QA?AIVFItE;VtVXHJL£H:?ABGH:LDtQaLPGLQ E"]VNE"9 I 8XL^T@:DFLIFIjQUE;M:L*;I :[VFHJE8VbE;QAQaO8pñVFH:LIXL~Z:LMJ]^LO;e MJO>R:LIVXOlYLKVXD\E$PGL6D\IXLRu~Z:?U]\=>Qai"wKL*E;D\]\H:?AM:BkefO"DEnMJO>R:L pS?aVXHCEu@JEGDVF?A]6Z:QAEGD=GLiN?AM>PGO"QaP"LIrIXLEGDF]\HJ?aM:B DFIVr?AMtVXHJL HJ?aB"H:LIVQaLPGLQ_E;MJR`DFL6@LE8VFLRTQAiNR:DXO"@:@:?AM:BuRTO8pSMElQaLPGLQ pSHJL6M:LPGL6D¦?hV¦YL]6OGoKLI ]^QALEGD/VXHJE;VVXHJLM:OTRTL,?UIMJO;V¦?AMsVXHJL ]6Z:DFDXLM"VSQAL6P"L6Qzw}æ OGMJIX?URTL6DF?aMJBmVFH:LrIXLEGDF]\Hn@JE8VFHj?aMlDFL6PGLDFIXL IXH:O8p,I}VFHJE8VMJOoKOGDFLVXHJEGM 4@:?U]6EGQ/Y:?AMJE;DFijVXDFL6LsO"@ LDFE;VX?AOGMJI l OGMjEsIXL~Z:LMJ]^LpSH:OILLQaLodLMVFI,EGDXLIVXOGDFLRlE;VIL@JE;D\E8VFL QAO>]E8VF?aO"MJIs?AM£EH:?ABGH:QAiR:?AIVXDF?aYJZTVXL*RIiTIVXL6o IXZ:Y WL]^VVXO Z:M:@JDXL*RT?A]^VFEGY:QaL}evEG?aQAZ:DFLIw|[I=>?A@mQA?UIWVE;QAOGMJL ?UIM:O;V/L6MJOGZ:B"H efOGDnOGZ:Dn@:Z:DF@ OIL*I6_SYL]E;ZJIXL&?aVnQUEG]\=TIkDXL*RTZ:MJR:EGMJ]î[E;M R ?UIVFHZ InP>Z:QAM:LDFEGY:QaLuVXOYO;VFH£evEG?aQAZ:DFLIE;MJR£]6OGMVXLMVX?AOGMw ?AMJ]^LNOGM:QAi[EbefL6p M:OTRTL*InEG@:@ L*E;D?AMVFH:L&H:?ABGHJLIVg{QaLPGL6Q QA?AIV_LE"]\HbIXZJ]\HbM:OTRTLE"]VFIrEGIEjIX?aM:B"QaLs@OG?AMVrO;e}evE;?AQAZ:DXL pSH:OILjDFL6oKO8P8E;QS@JEGDVF?hVF?aO"MJIKVFH:LuQA?AIV_,EGMJRCefOGDFoKIkEH:O;V IX@ OGV`VFHJE8VtomZJIVb@JDXOT]^L*IXIbE ]Ô"MJIVFE;MVbefD\EG]VF?aO"MýOGeEGQaQ IXLE;D\]\HdOG@L6D\E8VX?AOGM I6w!=>?a@KQA?AIVFIEGQAIXOO L6D!efLp[BGZJEGDFEGM"VFL6L*I VXH E8Vk?AMJRT?AP>?ARTZ E;QMJO>R:LIEGDXLjM:OGVnIXL6@JEGDFE;VXLRefDFOGoVXH:L?aD efL6QAQAO8p,IL6P"L6MbpS?aVXHtOT]6]EGIX?aO"MJE;Q/D\E;M RTOGo evE;?AQaZ:DFLIwu?AMJ]^L LE"]\HKM:OTRTL,?UI]Ô"M:M:L]^VXL*RKOGMsE$PGLDFEGBGL VXOOGMJQai K§Wê$¨!O;VFH:L6D M:OTRTL*I6_yL6P"L6ME]Ô"MJIVFE;MVs@:DFOGYJEGY:?AQa?aVWiOGeM:OTRTLlevEG?aQAZ:DFLI pS?AQaQ?UIXOGQUE8VXLEdQUE;DFBGLefDFE"]VX?AOGMO;e|VXH:LIXZ:DFP>?aP>?AM:BKM:OTRTLIw Z:D/IO"QaZ:VX?AOGM?UI|VXORTL JMJL}EBGL6MJL6D\E;QA?a*E8VX?AOGMOGe EI=>?A@ QA?AIVVXH E8Vnp}Lu]6EGQaQE +3 * 587 !ö w I?AMÿEI=>?A@Qa?UIV_ LE"]\HtM:OTRTL?aMENIX=>?a@BGD\E;@:Ht?UIKEuoKL6omY LDKO;eomZ:QhVF?a@JQaL QA?aM:="LRbQA?AIVFIwlxyH:LQAL6PGLQ¦éjQA?AIVm]6OGMJIX?AIVFIO;eSE;QAQ¦M:OTRTL*I?aM IXL~Z:L6M ]^LGw HJL6DFLdEI=>?A@&B"DFEG@:Hu?UIRT?AIVX?AM:B"Z:?AIXH:L*RjefDFOGo EÌ=>?A@QA?AIVs?AIdVFHJE8VdVXH:LDXLlosE$ibY LlosE;M>iQA?AIVFIsE;VdQAL6P"L6Q 0 _E;MJRtL6PGLDXi`M:OTRTL@JE;DXVX?U]^?A@JE;VXLIr?aMCOGM:LnO;eSVFH:LIXLnQA?UIWV\I6_ Z:MVX?AQVXHJLNM:OTRTL*IlE;DFLÌX@:QA?aMVXLDXL*R?AM"VFOI?AM:BGQAL^VFOGMJIE8eVFL6D K§fQAOGB .¨KQAL6PGLQAIOGM£E$PGLDFEGBGL"w£ IX=?A@[BGD\E;@:HIXZ:@:@OGDXVFI _ _,E;MJ R OG@L6D\E8VF?aO"MJIE;MJEGQaO"BGOGZ I VXOVFH:L]6OGDFDXL*I@OGMJR:?aM:BO"@ LDFE;VX?AOGMJIefO"D¦I=>?A@KQa?UIWV\I ?AMJRTL6L*Rc_ p}LrIHJO8p©?AM ..L6oKosEkóTwAêVXH E8VEGQaB"OGDF?hVFH:osIyefOGDI=>?A@uQA?AIVFI ]6EGMYL}EG@:@:QA?aL*RrRT?ADXL*]VFQaiVXOIX=?A@B"DFEG@:HJI_$E"I|EI=>?A@rB"DFEG@:H ?UISL~Z:?AP8E;QAL6MVyVXOsEs]Ô"QaQAL]^VX?AOGMO;e|ZJ@nVFO NIX=>?a@lQA?AIVFI}VFHJE8V HJEG@:@ LMVXOsIH E;DFLIXOGoKLO;e|VXH:L?aDQaO8p}L6DyQAL6PGLQAIw }L]6EGZJIXLkVFH:L6DFLjE;DFLnosE;M>iQA?AIVFIsE;VsLEG]\HCQaLPGLQ_¦VXH:L ]\HJEGMJ]^L*I[VXHJE;VüE;M>i?aMJR:?aP>?URTZJE;QNM:OTRTL@JEGDVF?A]6?a@JE;VXL*I?aM IXOGoKLIL*E;D\]\HN?UIIXosE;QAQ_L6QA?aoK?AMJE8VF?aMJBjY OGVXHtIX?aM:B"QaLs@OG?AMVFI O;emevE;?AQaZJDXLE;M RüHJO;VuI@O;V\I6wq¢JZ:DVFH:L6DFoKOGDFLG_LE"]\HüM:OTRTL HJE"I d§fQAOGB .¨MJL6?ABGH>Y O"DFIuOGME$PGLDFEGBGLG_E;MJR pS?aVXHHJ?aB"H @:DFOGYJEGY:?AQa?aVWi M:O M:OTRTLC?UIb?UIO"QAE;VXLRw ML*]VF?aO"M ©p L OGY ILDXP"LyVXHJE;V}IX=?A@B"DFEG@:HJIEGDXL,DFLIX?AQa?AL6MVVFOM:OTRTL,evEG?aQAZ:DFLI E;M RHJE$PGLÈ;M£L6T@JE;MJIX?AOGMD\E8VX?AOOG e §Wê QaO"B .¨pS?aVXH M:OTRTL*Iy?aMVXHJLBGD\E;@:Hw MCE"R:RT?aVX?AOGMtVFON@JDXO8P>?URT?aMJBjevE;Z:QaVgzVXO"QaLDFEGMJ]^L"_/HJE$P>?aMJB E; M §fQAOGB .¨dRTLBGDFL6LkVXObIZ:@J@ O"DV K§fQAOGB .¨rIXLEGDF]\HVF?aoKL

2

'

2

,4

4

7

4

4

4

2

,4

4

21

33

10

01

LEVEL 2 48

75

99

00

00

11

11

21

75

99

10

11

11

13 00

SKIP LIST

13

MEMBERSHIP VECTOR

2

,4

33

48

01

00

13

21

33

48

75

99

00

10

01

00

11

11

LEVEL 1

LEVEL 0

¢?ABGZ:DFLó IX=?A@BGD\E;@:HnpS?hVFH'&QAOGB)(+*-,9dQaLPGL6QUIw !

x|OnDFLE"IO"M&E;YOGZ:VVFH:?AIIVXDFZJ]^VXZ:DFLefO"DXosE;QAQAiG_cp}LmpS?AQaQ MJL6LRIXOGoKLMJO;VFE;VX?AOGMw .L6V/.&Y L}E JMJ?hVFL E;QA@:HJEGY L6V_$QAL^V/.10 YLVFH:LmIXL^VO;eE;QAQ JMJ?hVFLrp}OGD\R:I,]Ô"MJIX?AIVX?AM:BOGe/]\H E;D\EG]VFL6D\I ?A' M ._,E;MJRQAL^+ V .#2ü]ÔGM I?UIWVOGeE;QAQ,?aM JM:?aVXLup}OGD\R:Iw L Z ILkIXZ:YJIF]^DF?A@TVFIrVXONDXL6efL6DVFO&?AMJRT?AP>?ARTZ E;QS]\HJE;D\EG]^VXLDFIOGeE p}OGD\Rc_>IWV\E;DXVX?AM:BdpS?hVFHlIXZ:YJIF]^DF?A@TVy'é :Erp}OGD\$ R !©?UIyL~ZJE;QVFO !435! 4 ! w .L6V 8 !98$Y LyVFH:LyQaLM:B;VFHmOG e !r_GpS?aVX: H 8 !8,; ?a=?.#/2!6765w,6 {e 8 !8A@ 0 _pSDX?aVXB L !DC 0 efO"D,VFH:Lr@:DFL JlOG/e ! OGe|QAL6M:BGVXH 0 w DF?hVFF L ESefO"DyVXH:LLod@:VWip O"DFRw ¤SL6VXZ:DFM:?AM:BVFOÿI=>?A@ BGD\E;@:HJI_VXHJLtY OGVVFOGo QaLPGLQ?AI EGQapyE$iTIsERTO"Z:Y:QAigzQA?aMJ=GLRQA?AI+ V GIH]Ô"MJIX?AIVX?AM:BtOGeEGQaQVXHJL LQaLoKL6MVFI&?aMO"DFRTLDw M B"L6M:LDFEGQ_efO"D&L*EG]\J H ! ?A> M .108_ VFH:LtRTO"Z:Y:QAi"g{QA?aM:="LRüQa?UIK V GMLô]6OGMVFEG?aMJIjEGQa Q efOGDjpSH:?U]\H !ú?AIE @:DFL J OGe § ¨^_j?aM?AMJ]6DXL*EGIX?aM:BOGD\RTL6D*w L IFE$i©VXHJE;VtEÿ@JEGDVF?A]6Z:QUE;DbQa?UIN V G L ?AI`@JEGDVbO;eQaLPGL6Q 0 ?ae 8 !89, 0 w xyH:?UIjB"?aP"LIlE;M ?AM JM:?aVXLevEGoK?aQAiÿOGeKRTO"Z:Y:QAig QA?AM:=GL*RjQa?UIVF+I ?AMNEGM&EG]^VXZJEGQ.?AoK@:QaLoKL6MVFE;VX?AOGM_cO"M:QainVXHJO"IXL G L pS?aVXHÿE;VnQALE"IWVVWp}OtLQaLodLMVFIkEGDXL&DXL@:DXL*ILMVXLRw IX=>?a@mBGD\E;@:Hm?AI@:DFL]6?AIXL6QAiEevE;oK?aQAP i OQG Løv3*õ QAL6PGLQ tQAL6PGLQhg\ê õ>øv3*õ I@[é | övøõ ¨ R:LG_ÿIXLEGDF]\HJìLiG_ QaLPGLQ ¦VXO OQG L7 . 2 "= .#2 /G 3 G 4 G õ>øv3*õ QAL6PGLQ tQAL6PGLQhg\ê 7 6 7 6 6 R:L ?aMTg VX?AOGMb§vQaB"OGDF?hVFH:o ê$¨¦?UIyL^:E"]VXQAiKVXHJLIXEGodLEGIy?AMnVXH:L]6E"IL $ v %$ O;e.EmI=>?A@kQA?AIV pS?aVXHnOGM:QAiKoK?aM:O"D}E"R:E;@:VFE8VF?aO"MJI¦VXOrDFZ:M?AMnE IXL6DXVFIy?aVFIXL6Qae/?aMjIXOGoKLQA?AIVE8VL*EG]\HQaLPGLQcVX?AQaQ.?hV MJR:I,?aVFIXL6Qae R "¨^wS}V RT?UIWVFDX?AY:ZTVFLRIiTIVXLowxyHJLIXLEGDF]\Hk?AISIVFEGDVFLRE8VyVXH:LVFOG@Tg EGQaO"M:L?AMuEsQa?UIVE8VEGM>ikQAL6PGLQ §,QABGOGDF?aVXH:osIósEGMJ oKO"IVQAL6PGLQO;e!VFH:LM:OTRTLrIXL6L=>?aM:BnEK=GL6iE;MJRl?aV@:DFOT]^LLR:I QAL6P"L6Qé:_ pS?aQAQ QA?AM:=KVXOdEM:OTRTLpS?hVFHnEr=GL6is]6QaOIL*IWV VXOr?aVFI E;QAOGMJBNVFH:LuIFE;oKLlQaLPGL6QSpS?aVXHJOGZTVkO8P"L6D\IHJOOGVX?AM:BuVFH:Lj=GLiG_ O8pSMs="L6i"w!}VyLE"]\HsQaLPGLQ 0 _ 0 @üêG_ pS?aQAQJVFDXidVFO JM RsVXHJL ¨ C 0 , § UB ¨ C0 ]Ô"MVX?AMZJ?aM:BE;V¦EQaO8p}L6D/QAL6P"L6QT?aeDFL~Z:?ADFLRc_;ZJM"VF?aQ ?hVDFLE"]\H:LI ]6QaOIL*IWV M:OTRTL ?aMQAL6P"L6Q 0'1 ê,pS?hVFH § O nE;V QAL6P"L6Q 0 w!¥¦E"]\HsL^T?UIWVF?aM:BrM:OTRTL]E;MkRTLQAE$i QAL6PGLQSé:w¥?aVXH:LDdVXH:LlEGR:R:DXL*IXImO;e,VFH:LM:OTRTLIVXO"DX?AM:B&VXH:L EGMJRKQA?aM:=dVFB IXLE;D\]\H[=GLiG_S?aer?hVL^T?UIWV\I6_SO"DVXHJLNEGRJRTDXL*IXIkO;eVXHJLNM:OTRTL R:L^VXLDXoK?AM:?AM:B § ¨ Z:MVX?AQSEuM:LpM:OTRTLlIHJO8p,IrZ:@EGIX=g IVXOGDF?AM:BrVFH:L=GLik]^QAO"IXLIVyVXOKVFH:LIL*E;D\]\Hk="L6i?UIyDXL6VXZ:DFM:L*Rcw ?AM:BdefOGD?hV\I,P8E;QAZ:IL :VXH>ZJI,E;VE;M>ikB"?aP"L6MnVX?AodLrOGM:QAinE JMJ?hVFL @JDXL :mOGecEGM>iroKL6omY LDFIXH:?A@sPGL]^VXO"DHJEGIVXOYL,B"L6M:LDFE;VXLRw E;QUIXOKEdD\E;MJR:OGo P8E;DF?AEGY:QALGw

Ln]6E;MEGQAIXOVXH:?AM:=Ò;e,ElI=>?A@BGD\E;@:HbEGIElD\E;M RTOGo BGD\E;@JH_npSHJL6DFLVXH:LDXLü?AIE;MôLRTB"LÿYL^VWp}L6L6M EGMJR pSH:LM:L6P"L6F D EGMJR EGDXLsE"R EG]6L6MV?aMtIXOGoK L G L wlíL JM:L I/QALêV EGMJRdDX?ABGHV/M:L?aB"HYOGD\I!E8VQAL6P"L6Q 0 E"I!?hV\I/?AodoKL*RT?AE;VXL @:DFLRTL*]^L*IXIXOGDEGMJRsIZ ]6]^L*IXIXOGD*_;DFLIX@ L*]VF?aP"L6QAiG_G?AM G ? @ _OGD ?heSM:OuIXZJ]\HbM:OTRTLIL^T?AIVw LpS?AQAQ¦pSDF?hVFP L efO"F D I QALêV MJL6?ABGH>Y O"D¦E8V QaLPGL6Q 0 EGMJ" R efOGD¦?aVFI¦DX?ABGHV¦MJL6?ABGH>Y O"D_ E;M R?AMkBGLM:L6D\E;Q pS?aQAQVXH:?AM:=sOGe E;MJR EGIy]6OGoK@ OIXEGY:QAL OG@L6D\E8VFOGD\I6_JVXOE;QAQaO8p pSDF?hVF?aM:BnL^T@:DFLIFI?AOGM I,QA?a="B L 5 4 L^V\];w ,M E;QaVXLDXM E8VX?APGLñP>?aLp OGeE IX=?A@þBGD\E;@:Hþ?AIqE 4658õ RTQ 2" T_S¢:DF+L #"é>_SìMZ O;erIX=>?a@£QA?UIWV\IVFHJE8VjIH E;DFL VXHJL6?ADQAO8p}L6DQaLPGL6QUIw.{e p}L VXH:?AM:=OGeEI=>?A@rQA?AIV!efOGDFoKEGQaQAiEGI EkIXL~Z:LMJ]^LmO;eD\E;MJR:OGo P$EGDX?UE;YJQaL*I GA3 G 4 G _pSH:LDXL VXHJLP$EGQaZJLOG/e G ?AIyVFH:LQAL6PGLQ 0 QA?AIV_TVFH:L6Mlp}LHJ67E$65PG6 L

>=

'

D(E!#F+ G

:

"

7

+-,

3

/.( %

2

-1546

.

"!$ $# -

(

-

FM '

L

4O QPRTSRUP F(E! +VJ' - .

N:

=

5

CB

4O QPRTSRTP

,'10')

"!$

$

$ (

'

.

5

4O

N:

PZRTSRUP [(E!#F+K\' -1. %IH =

$0( %

&%$'

$0( %

FM '

L

5

.

CB

F+

?A@

4O

PRTSRUP

'(

%

'-1

'%

YX

(

:

MJ

=

7

B

?I@

7,

8,

]&^Z _

'

$0( %

2

9

%

` abIcedAf

( [!

4%#

4

hg

- (*$&

.'(

(*$0

&%

ji

kJ

l\

2

2

2

4

2

"!$ # -

$0

2

# F(

F+

%WH

?A@

YX

#. %

B

F+

%IH

)(*

' -1.

+

%IH

?I@

D(E!#F+KJ

:

' -1.

=

?A@

CB

4

VXH:L¦evE;Z:QaV.VFOGQAL6D\E;MJ]6L ÓÓ6Õ XÓ @JDXO"@ LDVF?aL*I OGeEdI=>?A@nB"DFEG@:Hw/¢JEGZ:QaV}VFOGQAL6D\E;MJ]6LOGe|DFL6QUE8VFLR 9 RJE8VFEIVXDFZJ]VFZ:DFLI_"IXZJ]\HdE"IE;ZJBGoKL6MVXL*RdPGL6D\IX?aO"MJIO;eQa?AM:=GL*R QA?UIWV\I|EGMJRY:?AMJEGDXiVXDFL6L*I6_8H EGI|Y LL6Mrp}L6QAQag{IVXZJR:?aL*RrE;M RrIXOGoKL xyH:LM:OTRTL*IS]Ô"M:M:L]^VXL*RkVFO +kEGMJR E8V,QAL6P"L6Q 0 1 ê DFLIXZ:QaVFIN]6E;MY LILL6M ?AMô ë :_ I# wòxyHJLosE;?AM HJE$P"L¦VFOYLyoKL6DFBGLRrY>irILMJRT?AM:BVXH:L}efO"QaQAO8pS?aMJBoKLIFIFE;BGL*I ~Z:L*IWVF?aO"M?AIrH:O8p osE;M>i&M:OTRTL*Im]E;MYLkIXL6@JEGDFE;VXLRNefDFOGo VFH:L,@:DF?AoKEGDXim]ÔGoK@OGM:LMV¦Y>irVFH:LSevE;?AQAZ:DXLSOGecO;VXHJL6DM:OTRTL*I6_ , DXO"Y LSQAL6P"L6Q 0 1 êyVXO JM RIosEGQaQALIViEGMEGRTP"L6D\IXEGDXi VFHJE8V[]6E;M O"YJIXL6DFPGL[VXHJL IVXDFZJ]^VXZ:DFL O;e`VXH:L IX=>?a@ BGD\E;@JH ]E;M RTO OGM:QAiQA?aoK?aVXL*R 1kø 58f4*ö - 21 efOGDSM:OTRTL RJE;osE;B"LGw ?hVFHH:?aB"HC@JDXO"YJE;Y:?AQA?hVWi"_ EIX=?A@BGD\E;@:HpS?hVFH Z:@ O"MlDXL*]^L6?AP>?aMJB )- 21 _|_ & M:OTRTLI}HJE"I}EGM §ê QAOGB .¨¦L^T@JEGMJI?AOGMkDFE;VX?AOJ_>?aoK@:QAi>?aMJB 6 4*ö|õ F V J H E8VSE8VyoKO"IV K§ QaO"B .¨ M:OTRTLIy]E;MkYLIL@JE;D\E8VFLRKefDFOGo 3*õ )- 21 _|_ VXO F V : H d L @:DX?AosE;DFiu]Ô"od@OGMJL6MVY> i èvEG?aQAZ:DFLIwrxyH:L*ILdDXL*IZJQhV\I õø3õ G E X D L T R * L X I 6 ] X D A ? Y * L k R A ? u M > < L ^ ] X V A ? G O M / Jw Aê VFod@K, J ¢ G O D \ D ; E J M : R G O q o v e G E a ? A Q : Z F D L I _ X V HJLkI?aVXZ E8VX?AOGMEG@:@ L*E;D\IL6P"L6M , K o " O X D m L : @ X D " O K o A ? X I a ? J M B ' O G : Z D ^ L T @ 6 L F D ?aoKLM"V\E;QDXL*IZJQhV\I6_c@:DFLIXL6MVFLR , A ? N M > < * L ] F V a ? " O M Jw » T ó _ I : H 8 O © p F V J H 8 E V f e G O DEDXL*EGIXOGMJEGY:QainQAEGDXB"LI=>?A@ 4*ö|õ , " B F D G E : @ H : M * L ; E F D a Q i ; E A Q } Q : M T O T R L m I X D L s o ; E ?AMt?aMVXH:L@:DF?aosEGDXi]Ô"odg 3õ .- 21 _;VXoK@_ VXO" @OGMJL6MVZJM"VF?aQEGY O"ZTVVWp OGgVFH:?ADFR:IO;e¦VXH:LKM:OTRTL*IevE;?AQ_EGMJR VFHJE8V ?hV}?AI @ OIXIX?AY:QaL,VXOosE;="LIXLE;D\]\H:L*I/H:?ABGH:QAimDFLIX?AQa?AL6MVVFO evEG?aQAZ:DFLKL6PGLMbpS?hVFH:OGZTVmZJI?AM:BVXHJLDXL@JE;?ADoKL]\HJEGM:?UIo Y>i Z ILO;e!DFLRTZ:M R:E;MVSQa?AM:=TIw 1kø 58f4*ö - 0/ efOGDSM:OTRTL Z:@ O"MlDXL*]^L6?AP>?aMJB )- 0/ _ |_ 1k õ5837:5$7:ø {7:vø.58õ>3 ¡?aP"L6MsEIZJYJIL6VO;eVXHJL v 4öõ J M > O : R L | I O;e EI=>?A@rBGD\E;@JH_8RTL JMJ!L "EGI.VXH:LyIXL^V!O;e EGQaQM:OTRTLI 3*õ )- 0/ _|_ VXO VFHJE8V¦EGDXLyM:OGV¦?A# M £Y:ZTVVFHJE8V¦EGDXL,E"R EG]6L6MV!VX$ O w/¢JZ:DVFH:L6D õø3õ : R L J : M %'&( E"IVFH:LIXL^VO;eyE;QAQ/M:OTRTLIVFHJE8VrEGDXLdM:O;V?AM) L VFodK @ , YJZTVEGDX1L WO"?aMJLRlVFOnEMJO>R:Lr?A M Y>ilE;MuL*RTBGLdE8VQaLPGL6+Q *w ,

æ A Q L G E X D A Q i , "',.- & /&0E;MJ? R 8 "8@CosE8 & 8 /&08hw , y x : H d L ^ L T J @ G E J M X I a ? " O u M F D ; E X V A ? k O G O ¦ e n E X I ^ L V 1 ?UP I 8 "98 8 98 wxyHJL 4*ö|õ , 6 L T J @ ; E J M X I A ? G O d M F D ; E X V A ? O ; O e E G B \ D ; E : @ K H U ? ! I X V J H L K o a ? J M a ? omZ:oýL6T@JE;MJIX?AOGM O 3õ .- 0/ _;VXoK@ _ VX" D\E8VF?aOÒ;eE;M>iIXL^, V efO"DspSH:?A]\H ê 8 8 ;ó:w[xyHJL L6T@JE;MJIX?AOGM£D\E8VF?aORTL^VFL6DFod?AM:L*IkVFH:LbDXL*I?AQA?aLMJ]^LNO;emEI=>?A@ B"DFEG@:H?AMkVFH:L@:DFLIXL6MJ]6LOGe|EGRTP"L6D\IXEGDX?UE;QJevE;?AQaZJDXL*I6_>YL]6EGZJIXL IXL6@ E;D\E8VX?AM:BEIXL^2 V úefDFOGo VFH:L©@:DX?AosE;DFi ]ÔGoK@OGM:LMV Original Links Unchanged Links DFL~Z:?ADFLIEGQaQ}M:OTRTLIm?A3 M " VFOuevE;?AQzw LnpS?AQaQyIXH:O8pVXHJE;V IX=>?a@ÿBGD\E;@:HJIkHJE$PGL §Wê !QaO"B .¨L6>@ E;MJIX?aO"MDFE;VX?AO"InpS?hVFH HJ?aB"Hs@:DXO"YJE;YJ?aQA?hVWi"_;?Aod@JQai>?AM:BVFHJE8V¦O"M:QAi K4§ QAOGB .¨!M:OTRTLI ]E;MdY LIL@JE;D\E8VFLRmY5 i sevEG?aQAZ:DFLI_GL6P"L6Md?heVFH:LSevE;?AQAZ:DXL*I/E;DFL ] ; E F D ^ L f e : Z A Q A Q K i F V ; E F D G B 6 L X V * L c R w

ÓÓ6New

Õ XLinks Ó²SWÁzÁz¯\àWÁ Z:DmIWVFDFE;VXL6B"iuefO"DrIHJO8pS?aM:BuElQAO8p}L6DYOGZ:M RbOGMbVXHJL 6 L T J @ ; E I=>?A@uBGD\E;@:HjpS?AQAQ|YLVFOnIXH:O8p©VXHJE;V ¢?aB"Z:DFL - OG@L6D\E8VF?aO"MsVXOdoKL6DFBGLM:OTRTLI}OGMVXH:L pS?aVXHKMJH:IX?A?ABGOGHKMl@:DFDFE;OGVXY ?AOE;Y:O;?Ae¦Qa?aEk W V G i _"E;QAQJIL6VFI[L?hVFH:L6D¦HJE$PGLyQUE;DFBGL6 3' IFE;oKLQaLPGL6Qzw §v?w LGwA_JosEGMinM:L6?ABGH>YOGD\ISE8V,VFH:LYO;VXVXOGo QAL6PGLQO;eVXHJLrI=>?A@

Ï !Ï !2# %

(

M'

e

4

4O

N:

(

=

@ @

?I@

[B

ki

i

4

4

2

@ @

?I@

4

8 8), 5 4 4 è 4 5 5 4 5 4

.

'( (

%

/

4

'-1

'%

"

J

"!$

#

4

"

; %

.

# -

(

N8 3 8

%

&W.

J

4

'-

!

$

(

Size as fraction of live nodes

BGD\E;@JH ¨cO"DH E$PGL¦QUE;DFBGL!/&(efO"D/IO"odL @JE;DXVX?U]^ZJQAEGD+*d]\H:OILM YJE"IL*RtOGMCVXHJLlIX?A6LO; e rw LlY LBG?AMCY>it]Ô"Z:MVX?AM:BNVXH:L M>Z:orYL6D}O;e.IXL^V\I üO;e.EBG?APGL6MnI?A6LVXHJE;V HJE$P"LIosEGQaQ 3 w

1

0.8

0.6

0.4

¤SL6@:DFLIXL6MVdLEG]\H E"ImE&Y:?hVXgzP"L]^VXOGD pSH:LDXLýê£?aM RT?A]E8VFLIE oKL6omY LDCOGejVXH:L IL6VEGMJRéE M:O"MTgzoKLorYL6D*w`xyH:L M 8 3 98|?AIdE8VKQaL*EGIVrVFH:LkM>Z:omY LDdOGe ?AM"VFL6DFP8E;QUIO;eSL6DFOL*I?AMVXH:?UImY:?hVXgzP"L]^VXOGD*wjxyH:LYOGZ:M R?aM Probability of node failure VXHJLQAL6oKosEr?UI¦VXH:LMkOGY:VFE;?AM:L*RY>iKY O"Z:MJRT?AM:BmVXH:LM>Z:orYL6D ¢ ?ABGZ:DFL !?A6LO;ecVFH:LQAEGDXB"LIV ]Ô"M:M:L]^VXL*R]Ô"od@OGMJL6MV}E"I O;eQaLM:B;VFH ÿY:?hVXgzP"L]^VXOGD\IdpS?hVFH O"M:LIKEGMJRE;VKoKOIWV & m E efD\EG]^VX?AOGMO;e.VFH:LIXZ:DXP>?AP>?aM:BKM:OTRTL*IypS?hVFHbê+:ê*é GóM:OTRTL*I6w ?AM"VFL6DFP8E;QUIyO;e|L6DFO>LIw ! '( . %

54

-1546

0.2

0

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

1.1

4

D

4

(

/O

# 8 & & 8 i 4

&

ó

; & %

"!$

# -

[ó J

6

'(54

G(

§ó ¨ 5

'

%

Gó

i

_

4

4-

#

*O.

+

( "

5

xyH:LS="L6iO"YJILDXP8E;VX?AOGMd?AI!VFHJE8V/efO"D/LE"]\H

4y?AM:O*é 6ê R & >_ LE"]\HI=>?A@QA?AIV4G!¦VFHJE8Vy]ÔGMV\E;?AMJI¦ErodLorYL6D ! '( . %

4

- 46

O;e:YO;VFH E;MJR?hV\I]6OGoK@:QAL6oKL6MV!]ÔGMVFDX?AY:ZTVFLIE8V|QALE"IWVOGM:L RT?UIWVF?aM ]VLQaLodLMV,VXO '&(rw LVFH:L6M&IXH:O8pÿVXHJE;VE8VQALE"IWV EdVXHJ?aD\RO;e!VXH:B L G",E;DFLQa?A=GLQaikVXORTOIXOsY>ikYOGZ:M RT?aMJBKVXH:L @:DFOGYJEGY:?AQa?aVWidVXHJE;V}L?hVFH:L66D üOG1D G 1 E;DFLDFL6@:DFLIXL6MVXL*RK?aM QALIFI}VXHJEGMnVWp}O;gzVXHJ?aD\R:I}O;eVXH:B L G w

%$ @(# ê 1 K§ !) 5 & ¨ *$ #

465O879& #

- (

%

/"g

$0 $0( +

2

"!$ (*$&54 ( OüIXosE;QAQwò¢:OGDNLE"]\H & IXL^V OGeuI?A6L _ *?AIC]\H:O"IXL6M IO VXHJE;VtVXH:L 4 ó YOGZ:MJRlOGe ..L6oKosE Jw»ódL^:]^LLR:I VX?AoKLISVFH:LL6>@ E;MJIX?aO"M D\E8VX?AOJwxyHJL@:DXO"YJE;YJ?aQA?hVF?aL*ISRTL6DF?APGLRkefDFOGo ..L6oKosE Jw»óKE;DFL VXHJL6MNIXZ:oKoKLR&O8PGL6DE;QAQ/IL6VF I OGe E :TL*R&IX?aL ZJIX?aM:B .LoKoKE JwAêG_TEGMJRsVFH:LDXL*IZ:QaVyO;e.VFH:?UIy@:DXOT]6LIFI¦?UIyIZ:oKoKLR O8PGLDSE;QAQ +$QAOGB , &VXOsO"YTVFEG?aMnVXH:L MJE;QYOGZJMJRcw

! '( . %

54

-1546

2

\

4

5

2

:

4

,4

7

1.1

0.9 0.8 0.7

#

'

465O879& *O é 6ê R .

#

( %

#

R: L ©?aM©EtB"?aP"L6MÿIX=>?a@üBGD\E;@: H GEGIkVXH:L @:DFOGYJEGY:?AQa?aVWirVFHJE8VyE;M & 1 /IXLE;D\]\HsH:?aVFI n]6OGMJRT?aVX?AOGMJLRsO"M VXHJLnoKL6omY LDFIXH:?A@tPGL*]VFOGD\IO;eEGQaQ}M:OTRTL*Ir?AMVXHJLn?AMVXL6DFP8E;Q _mpSH:L6DFL & wxyH:?UIÈ;@:@:DFO$T?aosE;VXLIjVXH:L IX?hVFZJE8VF?aO"M©?AME :TLR I=>?A@ BGD\E;@:HüpSH:L6DFLE[@JE;DXVX?U]^Z:QUE;D VFEGDXB"L^ V r?UIKZJIXLRCefOGDsosEGMiCIL*E;D\]\H:LIrVXHJE;VosE$itH:?a V |_ Y:ZTV!VFH:L}IXOGZJDF]6LI|O;e:VFH:LIXLSIL*E;D\]\H:LI|E;DFL ]\H:OILMrD\E;MJRTO"oKQai efDFOGo VFH:LO;VFH:L6DSM:OTRTL*IS?AMkVFH:LBGD\E;@:H.w 5

8J

J

465O879& *O é 6ê R ( * $ g )i R 8 , ó'5 5(

"! ,

#

_

r 9Gøv3*v

%

'

8 O ) >@é D*

.

'%

/ +

4-

; &%

'-1

J

"!$ ^# -

#

e(

G

(

ZQ

.

'

$0( %

%

0.3 0.2 0.1

\

i

LüHJE$P"LüRTL JM:L*RôE MJL6púR:E;VFEýIWVFDXZJ]^VXZ:DFLG_lVFH:L I=>?A@ BGD\E;@JH_,efO"DRT?UIVXDF?aY:Z:VXLR©R:E;VFEIWVFOGDFLIkVXHJE;VlH EGIILPGL6D\E;Q RTL*I?ADFEGY:QAL@:DXO"@ LDVF?aL*I6w÷æ OGMJIVXDFZJ]^VX?AM:BJ_?AMJIXL6DXVX?AM:B M:Lp

'

0 76400

76450

76500

76550

76600

76650

Nodes

¢?ABGZ:DFL # ]VFZJE;QEGMJR&L6T@ L*]VXL*R&QAO"E"Ru?AMNElIX=?A@&B"DFEG@:H pS?aVXH`ê+Jêé ;óM:OTRTL*IypS?hVFHVXH:LVFEGDXB"L^V , #"I Jw.ëjLIFIFE;BGL*I p}L6DFL[RTL6QA?aP"L6DFLRefDXO"o LE"]\HýMJO>R:LCVFO VXH:L[V\E;DFBGL6VbEGMJR VFH:LNE"]VFZJE;QQaOEGRO"M£LE"]\H£M:OTRTL`p}E"IoKLE"IZJDXL*RcwxyHJL L6T@ L*]VXL*RkQAO"E"Rk?UI,]6OGoK@:ZTVFLRZJIX?aM:BsxyH:LOGDFL6o ":waê"w

#

MJO>R:LI?AMVXOdE;MJRsIXLEGDF]\H:?AM:B?AMkErIX=>?a@sB"DFEG@:H]6EGMsY LRTOGMJL ?AMÿQAOGBE;DF?hVFH:oK?A]&VX?AoKLGw IX?aMJBVFH:LbDXL@JE;?ADlodL*]\HJE;MJ?AIXol_ R:?AIXDXZJ@TVX?AOGMJI&VXOüVXHJLR:E;VFEüIWVFDXZJ]^VXZ:DFL[]6E;MY LDXL@JE;?ADFLR ?AMVXH:LüE;YJIXL6MJ]6LO;euEGRJRT?hVF?aO"MJE;QevE;Z:QaVFIw i&O;e,EjDFLIXOGZJDF]6LdMJLE;DdEl@JE;DXVX?U]^ZJQAEGD QAOT]6E;VX?AOGMY>iZJIX?aM:BVXHJL QAOT]6E8VF?aO"MmE"I.QAO8pygzO"DFR:L6D JLQARm?AMVXHJL ="L6iEGMJRl]^QAZJIWVFL6DF?aMJBdOGe|M:OTRTL*ISpS?aVXHjI?AoK?aQUE;DS="L6iTIw xyH:?UIrRJE8VFE&IWVFDXZJ]^VXZ:DFLB"?aP"LIDF?AIXLsVFO&Eu]^QUEGIFIOGeyD\E;M:g R:OGo B"DFEG@:HJIpSH:O"IXLb@:DFOG@L6DXVX?ALIlp}L`H E$PGLbOGM:QAi£YL6B"Z:M VFONL6:E;oK?aMJL jIO"oKLnO"@ LMC@:DFOGYJQaLoKIKDFL6osEG?aMCDXLB"E;D\RT?AM:B VFH:LDFL6QA?UE;Y:?AQa?aVWi©O;esVXHJLIXLBGD\E;@JHJI6w QAIXOJ_dI=>?A@BGD\E;@:H I R:OMJO;VL^T@:QAOG?aVBGL6O"BGD\E;@:HJ?A]E;Q@:DXO$T?AoK?hVWij?AMNQAOT]6E;VX?AOGMÒ;e DFLIXOGZJDF]6LIrEGMJR?aVsp O"Z:QARtY Ll?AM"VFL6DFLIVX?AM:BuVFOÌVXZ RTi@ LDg efO"DXosEGMJ]^LnY LM:L :V\IK?aMCVXH E8VsRT?aDFL]^VX?AOGM_ @ LDXH E;@JImY>iZJIWg ?AM:BmorZ:QaVX?ag{R:?aoKL6M I?AOGMJEGQIX=>?a@kBGD\E;@:HJIw!¢|?AMJEGQaQAiG_>pSH:?AQaLVXHJL VFH:L6O"DXL6VX?U]6EGQ@JDXO"@ LDVF?aL*IE;MJR`DFL6QUE8VX?APGLsIX?aoK@:QA?U]^?aVWiuO;eSI=>?A@ B"DFEG@:HJIroKEG=GLsVFH:L6oEuBGO>OTRt]E;MJRT?UR:E;VXLefO"Dm?AoK@:QAL6oKL6MTg V\E8VF?aO"M_VFH:LjZ:QaVX?AoKE;VXLlVFLIVO;eVXH:L?aDsZJIXLêfZJQaM:L*IXIpS?aQAQ,YL VFH:L6?AD@L6DXefOGDFoKEGMJ]^LK?AMb@:DFE"]VF?A]6LGwxyH:?UI?AIrE;M`?AIFIZJLKVXHJE;V p}LH:OG@LVXOIVXZJR:inIXOO"Mw #

õ zõ58õ 9"õ>3 :

'(

$J

0.5

(

è

0.6

0.4

#

Actual Load Expected Load

1

Load

EGIkE;ML6QAL6oKLM"VIWVFOGDFLRE8VEb@JE;DXVX?U]^Z:QUE;DkM:OTRTLupS?AQaQM:O;V IXZ:DXP>?APGLmVXH:LKQAO"IFIO;e¦VFHJE8VMJO>R:LdO"D?hV\IM:L6?ABGH>YOGD\I?AMNVXH:L BGD\E;@JH_$oKEGM>iIXLEGDF]\H:L*I.RT?ADFL]VFLRE;VE@JE;DXVX?U]^Z:QUE;D|L6QAL6oKL6MV pS?AQaQQaL*EGRVFO,H:?ABGHQAO"E"ROGMVXHJL¦M:OTRTL/VFHJE8V!IWVFOGDFLI.?hV|EGMJRO"M M:OTRTL*I¦QA?a="L6QAirVFOrYLO"MErIXLE;D\]\HK@JE8VFHw/ç,O8p}L6P"L6D*_Gp}L]6EGM IXH:O8p£VFHJE8V,VFH:?UI,L L]^VRTDFOG@JIyO &D\E;@:?URTQAikpS?aVXHuRT?UIWV\E;MJ]6LI L6QAL6oKLM"V\IVXHJE;VEGDXLrevE;DE$p}E$inefDXO"o E@OG@:ZJQAEGDV\E;DFBGL^V?aM VXHJL,Y OGVVFOGodgzQAL6P"L6Q:QA?UIWV@:DFOTRTZJ]6LSQa?aVVFQaLE"R:RT?aVX?AOGMJEGQ:QAO"EGRdO"M E$PGLDFEGBGL"w

LBG?APGLVWp Om]\HJE;D\EG]^VXL6DF?AE8VF?aO"MJI/OGecVXH:?UI}DXL*IZ:QaVw/xyH:L JD\IWVIXH:O8p,IbVFHJE8VVXH:L@:DFOGY E;Y:?AQa?aVWi VFHJE8VE @JE;DXVX?U]^Z:QUE;D IXLE;D\]\H£ZJIXLIjECM:OTRTLbYL^VWp}L6L6MüVXHJLbIXOGZJDF]6LÈGMJRV\E;DFBGL^V RTDFOG@JIO k?aM>P"L6D\ILQaipS?aVXHdVXHJLyR:?AIVFEGMJ]^L}efDFOGoVFH:LSM:OTRTLyVXO VXHJLVFEGDXB"L^V*wxyH:?UI,evE"]V?UIM:O;VM:L]6LIFIXEGDX?AQainDXL*EGIFIZJDX?AM:BKVXO H:L*E$P?AQAi"g{QAO"EGR:LRnM:OTRTLIwygI@:DFLE"RT?AM:B&L L*]VFIkE;DFLnVFH:LjDFLIXZ:QhVOGe EGIFIXZ:oK?aM:BEDFEGMJRTO"oodLorYL6D\IHJ?a@dPGL*]VXO"DefOGDVXH:L,IXOGZJDF]6L O;eVXHJLIL*E;D\]\Hw

$ %&('*),4P+./*DQCK-0J6/*25131R254S4674Pe/ '*rL),~KY+^72,25JV&4J6F?2513DQDA&C CKGD(3;JV CKTV8TVTVCE?A*18;CKJLT GR? % DQ>7?QTU4P2ETEG:EZ]'*\3')IfVrG _Pfac^~Pm*n(|r5oqp=lRaYf_e~K^fi=~fw,)(UR9*,+Q¦*¦I $$ 3qOX+:NFy L3q+:q>72 2,4V L4PMB3wC: P%HGqBR254VJV4 JP CE1 + 89*85/*1RTV8C 4PCEB DQDA2I>G (GCK*CE/DQDAG @EC/JPTU974PCEG ?Q1]" R251 q8CE3TV@6B]"&//*1 (B=25P 8 ]//I(R@E/4V4.RB3CE7B3/25B=131R2 ?O/I4PG/*.3F2I2G Z *(2CK/*TU4VTV1=JVC >2