%!PS-Adobe-2.0 %%Creator: dvipsk 5.58f Copyright 1986, 1994 Radical Eye Software %%Title: paper.dvi %%Pages: 16 %%PageOrder: Ascend %%BoundingBox: 0 0 612 792 %%DocumentPaperSizes: Letter %%EndComments %DVIPSCommandLine: dvips -o paper.ps paper %DVIPSParameters: dpi=600, compressed, comments removed %DVIPSSource: TeX output 1998.03.06:0803 %%BeginProcSet: texc.pro /TeXDict 250 dict def TeXDict begin /N{def}def /B{bind def}N /S{exch}N /X{S N}B /TR{translate}N /isls false N /vsize 11 72 mul N /hsize 8.5 72 mul N /landplus90{false}def /@rigin{isls{[0 landplus90{1 -1}{-1 1} ifelse 0 0 0]concat}if 72 Resolution div 72 VResolution div neg scale isls{landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div hsize mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul TR[matrix currentmatrix{dup dup round sub abs 0.00001 lt{round}if} forall round exch round exch]setmatrix}N /@landscape{/isls true N}B /@manualfeed{statusdict /manualfeed true put}B /@copies{/#copies X}B /FMat[1 0 0 -1 0 0]N /FBB[0 0 0 0]N /nn 0 N /IE 0 N /ctr 0 N /df-tail{ /nn 8 dict N nn begin /FontType 3 N /FontMatrix fntrx N /FontBBox FBB N string /base X array /BitMaps X /BuildChar{CharBuilder}N /Encoding IE N end dup{/foo setfont}2 array copy cvx N load 0 nn put /ctr 0 N[}B /df{ /sf 1 N /fntrx FMat N df-tail}B /dfs{div /sf X /fntrx[sf 0 0 sf neg 0 0] N df-tail}B /E{pop nn dup definefont setfont}B /ch-width{ch-data dup length 5 sub get}B /ch-height{ch-data dup length 4 sub get}B /ch-xoff{ 128 ch-data dup length 3 sub get sub}B /ch-yoff{ch-data dup length 2 sub get 127 sub}B /ch-dx{ch-data dup length 1 sub get}B /ch-image{ch-data dup type /stringtype ne{ctr get /ctr ctr 1 add N}if}B /id 0 N /rw 0 N /rc 0 N /gp 0 N /cp 0 N /G 0 N /sf 0 N /CharBuilder{save 3 1 roll S dup /base get 2 index get S /BitMaps get S get /ch-data X pop /ctr 0 N ch-dx 0 ch-xoff ch-yoff ch-height sub ch-xoff ch-width add ch-yoff setcachedevice ch-width ch-height true[1 0 0 -1 -.1 ch-xoff sub ch-yoff .1 sub]/id ch-image N /rw ch-width 7 add 8 idiv string N /rc 0 N /gp 0 N /cp 0 N{rc 0 ne{rc 1 sub /rc X rw}{G}ifelse}imagemask restore}B /G{{id gp get /gp gp 1 add N dup 18 mod S 18 idiv pl S get exec}loop}B /adv{cp add /cp X}B /chg{rw cp id gp 4 index getinterval putinterval dup gp add /gp X adv}B /nd{/cp 0 N rw exit}B /lsh{rw cp 2 copy get dup 0 eq{pop 1}{ dup 255 eq{pop 254}{dup dup add 255 and S 1 and or}ifelse}ifelse put 1 adv}B /rsh{rw cp 2 copy get dup 0 eq{pop 128}{dup 255 eq{pop 127}{dup 2 idiv S 128 and or}ifelse}ifelse put 1 adv}B /clr{rw cp 2 index string putinterval adv}B /set{rw cp fillstr 0 4 index getinterval putinterval adv}B /fillstr 18 string 0 1 17{2 copy 255 put pop}for N /pl[{adv 1 chg} {adv 1 chg nd}{1 add chg}{1 add chg nd}{adv lsh}{adv lsh nd}{adv rsh}{ adv rsh nd}{1 add adv}{/rc X nd}{1 add set}{1 add clr}{adv 2 chg}{adv 2 chg nd}{pop nd}]dup{bind pop}forall N /D{/cc X dup type /stringtype ne{] }if nn /base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{dup dup length 1 sub dup 2 index S get sf div put}if put /ctr ctr 1 add N}B /I{ cc 1 add D}B /bop{userdict /bop-hook known{bop-hook}if /SI save N @rigin 0 0 moveto /V matrix currentmatrix dup 1 get dup mul exch 0 get dup mul add .99 lt{/QV}{/RV}ifelse load def pop pop}N /eop{SI restore userdict /eop-hook known{eop-hook}if showpage}N /@start{userdict /start-hook known{start-hook}if pop /VResolution X /Resolution X 1000 div /DVImag X /IE 256 array N 0 1 255{IE S 1 string dup 0 3 index put cvn put}for 65781.76 div /vsize X 65781.76 div /hsize X}N /p{show}N /RMat[1 0 0 -1 0 0]N /BDot 260 string N /rulex 0 N /ruley 0 N /v{/ruley X /rulex X V}B /V {}B /RV statusdict begin /product where{pop product dup length 7 ge{0 7 getinterval dup(Display)eq exch 0 4 getinterval(NeXT)eq or}{pop false} ifelse}{false}ifelse end{{gsave TR -.1 .1 TR 1 1 scale rulex ruley false RMat{BDot}imagemask grestore}}{{gsave TR -.1 .1 TR rulex ruley scale 1 1 false RMat{BDot}imagemask grestore}}ifelse B /QV{gsave newpath transform round exch round exch itransform moveto rulex 0 rlineto 0 ruley neg rlineto rulex neg 0 rlineto fill grestore}B /a{moveto}B /delta 0 N /tail {dup /delta X 0 rmoveto}B /M{S p delta add tail}B /b{S p tail}B /c{-4 M} B /d{-3 M}B /e{-2 M}B /f{-1 M}B /g{0 M}B /h{1 M}B /i{2 M}B /j{3 M}B /k{ 4 M}B /w{0 rmoveto}B /l{p -4 w}B /m{p -3 w}B /n{p -2 w}B /o{p -1 w}B /q{ p 1 w}B /r{p 2 w}B /s{p 3 w}B /t{p 4 w}B /x{0 S rmoveto}B /y{3 2 roll p a}B /bos{/SS save N}B /eos{SS restore}B end %%EndProcSet TeXDict begin 40258431 52099146 1000 600 600 (paper.dvi) @start /Fa 1 81 df80 D E /Fb 4 104 df0 D 48 D102 D<12FCB47EEA0FC0EA01E06C7EB01378A2 133EEB0FF01303130FEB3E001378A25BB0485AEA0FC0B45A00FCC7FC14317BA420>I E /Fc 8 62 df<130C1338137013E0EA01C0EA038013005A120EA25AA25AA312781270A3 12F0AB1270A312781238A37EA27EA27E7E1380EA01C0EA00E013701338130C0E317AA418 >40 D<12C012707E7E7E7E7E1380EA01C0A2EA00E0A21370A313781338A3133CAB1338A3 13781370A313E0A2EA01C0A2EA038013005A120E5A5A5A12C00E317CA418>I<1438B2B7 12FEA3C70038C7FCB227277C9F2F>43 D<13E01201120712FF12F91201B3A7487EB512C0 A212217AA01E>49 DI<13FF000313C0380F03 E0381C00F014F8003E13FC147CA2001E13FC120CC712F8A2EB01F0EB03E0EB0FC03801FF 00A2380003E0EB00F01478147C143E143F1230127812FCA2143E48137E0060137C003813 F8381E03F0380FFFC00001130018227DA01E>I<137F3803FFC0380781E0380E00704813 380018131C1238A3123C003F1338381FC078EBE0F0380FF9E03807FF80120114C0000713 F0380F0FF8381C03FC383801FE3870007E141F48130F1407A314060070130E0078130C6C 1338001F13F03807FFC0C6130018227DA01E>56 D61 D E /Fd 1 70 450 300 dfs[23 23 126 150 41 69 D E /Fe 10 122 df97 DI<143C147E14FE1301A3EB00FC14701400AE 137C48B4FC3803C780380703C0000F13E0120E121C13071238A21278EA700F14C0131F00 F0138012E0EA003F1400A25B137EA213FE5B12015BA212035B141E0007131C13E0A2000F 133CEBC038A21478EB807014F014E0EB81C0EA0783EBC7803803FE00EA00F8174378C11E >105 D108 D 110 DII114 D<1470EB01F8A313035CA313075CA3 130F5CA3131F5CA2007FB512E0B6FC15C0D8003FC7FCA25B137EA313FE5BA312015BA312 035BA312075BA3120F5BA2EC0780001F140013805C140E003F131EEB001C143C14385C6C 13F0495A6C485AEB8780D807FEC7FCEA01F81B3F78BD20>116 D<137C48B414072603C7 80EB1F80380703C0000F7F000E153F001C1600130712385E0078157EEA700F5C011F14FE 00F0495B12E0EA003FEC00015E5B137E150301FE5C5BA2150700015D5BA2150F00035D5B A2151F5EA2153F12014BC7FC6D5B00005BEB7C0390383E0F7EEB1FFEEB03F090C712FE5D A214015D121F397F8003F0A24A5A4848485A5D48131F00F049C8FC0070137E007813F838 3801F0381E07C06CB4C9FCEA01FC294078AB2F>121 D E /Ff 51 122 df<1506150E151C157815F0EC01E0EC03C0EC0780EC0F005C143E143C5C14F8495A 5C1303495AA2495A49C7FCA2133EA2137E137C13FC5B12015B1203A25B1207A25B120FA3 485AA448C8FCA4123E127EA5127C12FCA95AA97E127CA6123C123EA2121EA2121F7EA26C 7EA27F120312017F6C7E1370137813387F7F13061F6473CA26>40 D<14C08014708080141E140E140FEC0780A2EC03C0A2EC01E0A215F01400A215F8A21578 157CA5153EB0157EA7157C15FCA5EC01F8A415F01403A315E01407A215C0140FA2158014 1F1500A25C143E147E147C14FC5C13015C495AA2495A5C130F49C7FC131E5B137C5B5B48 5A485A485A48C8FC121E5A5A12E05A1F647FCA26>I44 D<007FB512E0A3B612C0A31B067C9721>I<121EEA3F80EA7F C012FFA41380EA7F00123C0A0A77891B>I<151C153C157CEC01FCEC07F8147FEB7FFF14 F31483EB000715F0A5140F15E0A5141F15C0A5143F1580A5147F1500A55C5CA513015CA5 13035CA513075CA3130FEB3FFCB612FEA31F4277C131>49 DI54 D56 D<15FF020F13C0023F13F091387F 01FC903901FC007ED903F0133E4948133F4948EB1F80495A013FEC0FC049C7FC13FE17E0 484814071203A34848140FA217F0A2120F5BA217E0161FA35B163FA2167F12076DECFFC0 A200035C0001EC03BF6D143F6C6CEB077F017C011E13806D133890381F80F0902607FFC0 13000100EB00FF91C7FC5E15015EA24B5AA24B5AA2001F4A5AD87F805C6D131F4B5A00FF 92C7FC49137E5D4848485A0060495A0070495A6CEB1F80003F01FFC8FC380FFFFC6C13F0 C613802C4479C131>I<1378EA01FCEA03FEA21207A3EA03FC13F8EA00F01300B3A5121E EA3F80EA7FC012FFA41380EA7F00123C0F2B77AA1B>I<170C171C173C173E177EA217FE A21601835EA21606A24C7FA2EE187FA21630A204607F173F16C0A2ED018084ED0300171F 1506A25D844B130FA25D157003608015E04B130714015D140392C77F02061403A2020FB6 FCA24A810218C712034A1401A25CA24A8183495AA249C9FC851306187F5B131CA2013C83 137CEA01FE2607FF80913801FFF0007F01E0027FEBFFC0B5FCA242477DC649>65 D<011FB712E018FCF0FF809026003FF8C76C7E6E48EC1FF0727E4B6E7E1803727E858414 3F5D1A80A4027F17005D606118036102FF150792C8485A614E5AF07FC04EC7FC49ED03FE 4AEC0FF8EFFFE091B7128018F04AC7EA03FC0103ED00FF4A6F7E727E727E727EA2010770 7E5C85A31803130F4A1507A461011F160F4A5E181F4E5AA24E5A013F4C5A4A4A90C7FC4D 5AEF0FFC017FED3FF001FF4AB45AB9128005FCC8FC17C041447CC345>II<011FB712E018FE 49707E9026003FF8C713E06E48EC1FF0F007FC4BEC01FE727EF17F80193FF11FC0023FEE 0FE05DF107F0A21AF81903147F4B16FCA219011AFEA214FF92C9FCA54917035CA5010318 FC4A1607A31AF8A20107170F4A17F0A2191F1AE0A2010FEF3FC05CF17F801A006161011F 4C5A4A4B5A4E5A180F4E5A4E5A013F4CC7FC4A15FEEF03FCEF0FF0017FED3FE0496C9038 03FF80B848C8FC17F094C9FC47447CC34B>I<011FB812FEA39026003FF8C7121F6E4814 01F0007E4B153E191EA2190EA2143F5D1906A4147F5DA2170CA2190002FF5C92C7FCA217 38A217784915704AEB01F0160791B6FCA3903A03FE000FE04A130316011600A301075D5C A5010F92C8FC5CA5131F5CA5133F5CA3137FEBFFF0B612F8A33F447CC340>70 D<011FB500FC017FB512F04C16E0A29026003FFCC8EBF000DA1FF0ED7FC0A24B5EA419FF 143F4B93C7FCA460147F4B5DA4180314FF92C85BA418075B4A5E91B8FCA34AC8120F1303 4A5EA4181F13074A5EA4183F130F4A5EA4187F131F4A5EA418FF133F4A93C8FCA3017F5D 496C4A7FB6D8E003B67EA203C093C7FC4C447CC349>72 D<011FB512FEA39039001FFE00 EC0FF8A25DA5141F5DA5143F5DA5147F5DA514FF92C7FCA55B5CA513035CA513075CA513 0F5CA5131F5CA3133F497E007FB512F0B6FCA227447DC323>I<0207B6FCA3DA000313C0 03001380A21700A45DA25EA41503A25EA41507A25EA4150FA25EA4151FA25EA4153FA25E A4157FA25EA4001F14FFEA7F80486C91C7FCA34A5A13804A5A130000D8495A00E05C0060 495A0070495A6C495A6C49C8FC380F81FC3803FFF038007F80304679C332>I<011FB6FC A39026003FFCC8FCEC1FF0A25DA5143F5DA5147F5DA514FF92C9FCA55B5CA513035CA513 074A1503A31806A2130F4A150E180CA2181C1818011F16385C1878187018F01701013FED 03E04A1407170F173F017FEDFFC001FF140FB9FC1880A238447CC33D>76 D<90261FFFF094B512C06F198062D9003F9439037FC000021F4EC7FC1A06DA19FC5F1A0C A21A18DA18FE1619023817310230601A611AC1157FF101831470026093380303F8A26F6C 1406A2F10C0714E002C004185B6F7E193019601A0F010117C04A6C6C5EF00180A2F00300 6F6C151F0103160602006060606F7E4E133F5B01064C5CA26F6C5BA24D48137F130E010C 4BC790C8FCED00FE17065F62011C5D0118027F5D5FA25FDC3FE0130101385D6201785D94 C7FCD801FC6E1403D807FF021E4A7EB500F80307B512FE161C4A010C5E5A447BC359>I< 90261FFFF84AB512F01BE081D9001F9239001FFC006E6CED07F0021F705ADA19FF6F5A62 02187FA26F6C140314389126303FE092C7FCA26F7EA26F6C5C147091266007FC1406A26F 7EA26F6C140E14E04A6C6D130CA2707EA2706C131C13014A6D6C1318A2707EA2706C1338 130391C76C6C1330A2707EA270EB80705B010692387FC060A2EF3FE0A294381FF0E0130E 010C6F6C5AA2EF07FCA2EF03FF131C01186F5BA283A2187F133872C8FC137884EA01FCD8 07FF82B512F818065C4C447CC349>I<011FB712C018F818FF9028003FF8000113806E48 9038003FE0F00FF04BEC07F8F003FCA2F001FEA2023F16FF4B80A5027F5D5DA319FE1803 14FF92C813FCF007F8A2F00FF0F01FE049EE3FC04AED7F00EF01FEEF07F8EF3FE091B712 804903FCC7FC02FCCAFCA513075CA5130F5CA5131F5CA5133F5CA3137F497EB612E0A25D 40447CC342>80 D83 D<0007BAFCA3270FFE0003EB000301E04AEB007F49173F90C749141F00 1E180FA2001C180712180038020715065E1230A25AA2150F5E5AA3C81600151F5EA5153F 5EA5157F5EA515FF93C9FCA55C5DA514035DA514075DA3140FEC3FFE48B712C05FA24044 75C346>I86 DI97 DII<177FEE3FFFA25E160182A217FEA41601A217FCA41603A217F8A41607A2 DA03F813F0EC3FFF9138FE0787903903F001E790390FC0006F4948137F49C7EA3FE001FE 141F485A49140F0003151F485A000F16C05B121F5B003F153FA2007F16805BA3167F12FF 90C81300A45EA26C5DA46C14017F001F4A5A6D1307000F140F6C6C131D6C6C49B4FC6C6C 01F313F839007E03C390381FFF03D903FCEBF80030467AC436>IIIII< 143C14FEEB01FFA25BA3EB01FE14FCEB00781400ADEB03F8EA01FFA3EA000F130714F0A5 130F14E0A5131F14C0A5133F1480A5137F1400A55B5BA31201487EB512F8A318437DC21C >I107 DI< 902703F801FEEC3FC0D801FF903B0FFFC001FFF848913B3E07F007C0FE923B7003F80E00 7FD8001FD9E001497F902607FBC0D9FC781480DAF70014E002F6010049131F02FE14FD4A ECFF804A4990C7123F130F4A5CA24A5CA3011F0203157F4A4A1500A5013F02075D4A4A5C A5017F020F140191C7495CA549021F1403494B5CA30001033F1407486C4A6C497EB5D8FC 1FB50083B512F0A34C2C7DAB52>I<903903F801FED801FF90380FFF804891383E0FE092 387007F03A000FF9E003902607FB8013F8ECF70002F6130114FE5C4A1303130F5CA25CA2 1607131F4A14F0A4160F133F4A14E0A4161F137F91C713C0A4163F5B491580A30001157F 486CECFFC0B5D8FC3F13FFA3302C7DAB36>II<91393F803F80903A1FFF81FFF049903887C0FC92389E003F010001 B8EB1F80DA7FF0EB0FC04B14E04BEB07F05D92C7EA03F8A24A15FC4A1401A218FEA31301 5CA41703010316FC5CA3EF07F8A20107150F4A15F0EF1FE0A2EF3FC01880010F157FEFFF 006E495A4C5A6EEB07F002EE495AD91FE7EB1F809126C3C0FEC7FC9138C0FFF8ED3FC092 C9FC133FA25CA4137FA291CAFCA45B487F007F13FEA2B55A373F81AB36>II<903903F007E0D801FFEB3FF848EC787CEDE1FC39000FF1C19038 07F383ECE70314EE9138EC01F89138FC00E04A1300130F5CA35CA2131F5CA5133F5CA513 7F91C8FCA55B5BA31201487EB6FCA25C262C7DAB26>I<91383FE030903903FFF8709039 0FC01EF090381E0007017C13034913015B0001EC00E0485AA412076D14C0A26D1400EA03 FEEBFFE014FE6CEBFFC06C14F06D7F6D13FE130F01017FD9000F13801401EC007F001814 3F151F1238150FA4ED1F00127CA2007E143E153C007F5C6D5B39F9C003E039F0F00FC026 E07FFFC7FC38C00FF0242E7DAC26>I<14C0A313015CA21303A21307A249C7FCA25B5B5B 5B485A1203001FB512F0B6FCA2C648C7FC12015BA512035BA512075BA5120F5BA215C0A3 001FEB018013C0A414031500A25C1406000F130E6D5A00075B6C6C5AC6B45AEB3F801C3E 77BC26>I<01FEEC3F80007FEC1FFF00FF5CA2000314000001157F491500A45E1203495C A415011207495CA41503120F495CA41507121F495CA2150FA2151FA249495AA2157F6C6C 13EF913801DFF83B07E0079FFFC03903F01E1F3800FFFCD91FE0EBC0002A2D77AB36>I< B539F001FFFCA3000F90C7EA7FE0D803FCEC3F80EE1E00161C00011518163816306D5C12 005EA24B5A7F6D49C7FC5D15066E5A133F5DA25D14C0011F5B15E05D14E1010F5B02E3C8 FCA214E614F6EB07FCA25CA26D5A5CA25CA26D5A2E2C77AA33>I<3E7FFFF87FFFF01FFF C04AB512E0B5FC0007903C0007FE0007FE006C486D48EB03F86C484A6D5A03015D61616D 80000002034AC7FCA203061406A2030C5C6D806D01185C167E03305CA2DB607F5B148001 3F01C05C82DA8180495AA2DAC3000183C8FC131F02C61486161F02CC148CA202F814D801 0F15F84A6D5AA24A5CA24A5C13074A6D5AA291C790C9FC1606422C78AA46>I<90B539F0 07FFF8484A5AA2D80007D9800313806D0100EBFC006D4814F001005D6E14806E49C7FCED 80066E6C5A021F5B6F5A020F5BEDF0E0913807F1C0EDFB806EB4C8FC5D6E5A6E7E81814B 7EEC01BF9138033FC0EC061F020C7FEC1C0F4A6C7E02707FECE003D901C07F9038038001 D907007F491300011E80017E8113FED807FF4913E0B5D8800713FF5DA2352B7FAA33>I< 90267FFFF8EBFFFEA301030180EB3FF06D48C7EA1FC0EF0F00170E0100150C171C17186E 5C805FA26F5B023F13015F4CC7FC15C0021F1306A25E161CEDE018020F133816305E15F0 02075BA2EDF18015FB020390C8FC15FEA25DA26E5AA25D5D14005DA24A5AA24AC9FC5C14 065CA2001C5B127F5C485BA25C48485A4848CAFCEA600EEA783CEA3FF0EA0FC0373F80AA 33>I E /Fg 5 50 df0 D<12E012F812FEEA3F80EA0FE0EA03F8 EA00FEEB3F80EB0FE0EB03F8EB00FEEC3F80EC0FE0EC03F8EC00FEED3F80ED0FE0ED03F8 ED00FEEE3F80EE0FC0A2EE3F80EEFE00ED03F8ED0FE0ED3F8003FEC7FCEC03F8EC0FE0EC 3F8002FEC8FCEB03F8EB0FE0EB3F8001FEC9FCEA03F8EA0FE0EA3F80007ECAFC12F812E0 CBFCAC007FB71280B812C0A22A397AAB37>21 D<170EA3170F8384170384170184717E18 78187C84180FF007C0BA12F819FC19F8CBEA07C0F00F00183E601878604D5A6017036017 0795C7FC5F170EA33E237CA147>33 D<137813FE1201A3120313FCA3EA07F8A313F0A2EA 0FE0A313C0121F1380A3EA3F00A3123E127E127CA35AA35A0F227EA413>48 DI E /Fh 9 112 df 21 D<140C141C143C1438A21478147014F014E0130114C0A21303148013071400A25B13 0E131E131CA2133C13381378137013F05BA212015B12035BA2120790C7FC5A120EA2121E 121C123C123812781270A212F05AA216317CA420>61 D<90B57E92C7FCEB07C0A2495AA4 49C8FCA4133EA45BA45BED0180A2ED0300485A1506A2150E48485B153C15F800071303B6 FC5D21227CA12A>76 D<131FEBFF8C3801E0DE3803807E3807007C48133C121E123E003C 5B127CA3485BA215401560903801E0C012781303393807E180391C1CF300380FF87F3807 E03C1B177E9522>97 D101 D<1338137CA2137813701300A7EA0780EA1FC0EA38E01230EA60 F0EAC1E0A3EA03C0A3EA0780A2EA0F0013041306EA1E0CA21318121CEA1E70EA0FE0EA07 800F237DA116>105 D<13F8EA0FF0A21200A2485AA4485AA43807801E147FEB81C3EB83 87380F060F495A1318EB700E4848C7FCA213FCEA1E7EEA3C0F80EB0781158039780F0300 A21402EB070600F0138CEB03F8386000F019247CA221>107 D<000F13FC381FC3FF3931 C707803861EC0301F813C0EAC1F0A213E03903C00780A3EC0F00EA0780A2EC1E041506D8 0F00130C143C15181538001EEB1C70EC1FE0000CEB07801F177D9526>110 DI E /Fi 1 70 df69 D E /Fj 36 122 df 45 D<121C127FEAFF80A5EA7F00121C0909798817>I48 DIII<1538A2157815F8A2140114031407A2140F141F14 1B14331473146314C313011483EB030313071306130C131C131813301370136013C01201 EA038013005A120E120C5A123812305A12E0B712F8A3C73803F800AB4A7E0103B512F8A3 25397EB82A>I<0006140CD80780133C9038F003F890B5FC5D5D158092C7FC14FC38067F E090C9FCABEB07F8EB3FFE9038780F803907E007E090388003F0496C7E12066E7EC87EA2 8181A21680A4123E127F487EA490C71300485C12E000605C12700030495A00385C6C1303 001E495A6C6C485A3907E03F800001B5C7FC38007FFCEB1FE0213A7CB72A>II<12301238123E003FB612E0A316C05A168016000070C7120600 60140E5D151800E01438485C5D5DC712014A5A92C7FC5C140E140C141C5CA25CA214F049 5AA21303A25C1307A2130FA3495AA3133FA5137FA96DC8FC131E233B7BB82A>III<1538A3157CA315FEA34A7EA34A6C7EA2 02077FEC063FA2020E7FEC0C1FA2021C7FEC180FA202387FEC3007A202707FEC6003A202 C07F1501A2D901807F81A249C77F167FA20106810107B6FCA24981010CC7121FA2496E7E A3496E7EA3496E7EA213E0707E1201486C81D80FFC02071380B56C90B512FEA3373C7DBB 3E>65 D<913A01FF800180020FEBE003027F13F8903A01FF807E07903A03FC000F0FD90F F0EB039F4948EB01DFD93F80EB00FF49C8127F01FE153F12014848151F4848150FA24848 1507A2485A1703123F5B007F1601A35B00FF93C7FCAD127F6DED0180A3123F7F001F1603 18006C7E5F6C7E17066C6C150E6C6C5D00001618017F15386D6C5CD91FE05C6D6CEB03C0 D903FCEB0F80902701FF803FC7FC9039007FFFFC020F13F002011380313D7BBA3C>67 D69 DII< B5913807FFFE8080C69238007FE06EEC1F80D9DFF0EC0F001706EBCFF8EBC7FCA2EBC3FE EBC1FFA201C07F6E7EA26E7E6E7E81140F6E7E8114036E7E168080ED7FC016E0153FED1F F0ED0FF8A2ED07FCED03FEA2ED01FF6F1386A2EE7FC6EE3FE6A2EE1FF6EE0FFEA2160716 03A216011600A2177E486C153E487ED80FFC151EB500C0140EA2170637397DB83E>78 D82 DI97 DIIII<147E903803FF8090380FC1E0EB1F8790383F0FF0137EA213FCA23901F803C091C7FC ADB512FCA3D801F8C7FCB3AB487E387FFFF8A31C3B7FBA19>I104 D<3903F00FF000FFEB3FFCECF03F9039F1 C01F803A0FF3800FC03803F70013FE496D7EA25BA35BB3A3486C497EB500C1B51280A329 257EA42E>110 DI<3903F01FE000FFEB7FF89038F1E07E9039F3801F 803A07F7000FC0D803FEEB07E049EB03F04914F849130116FC150016FEA3167FAA16FEA3 ED01FCA26DEB03F816F06D13076DEB0FE001F614C09039F7803F009038F1E07E9038F0FF F8EC1FC091C8FCAB487EB512C0A328357EA42E>I<3807E01F00FFEB7FC09038E1E3E090 38E387F0380FE707EA03E613EE9038EC03E09038FC0080491300A45BB3A2487EB512F0A3 1C257EA421>114 DI<1318A51338A31378A313F8120112031207001FB5FCB6FCA2D801F8C7FCB215 C0A93800FC011580EB7C03017E13006D5AEB0FFEEB01F81A347FB220>II119 D121 D E /Fk 22 114 df0 D<12E07E12787E7E7E7F6C7E6C7E7F12016C7E7F137C137E7FA26D7EA26D7E A26D7EA36D7EA2801301A2801300A280A2147EA2147FA4801580A7EC1FC0B3A5EC3F80A7 15005CA4147EA214FEA25CA213015CA213035CA2495AA3495AA2495AA249C7FCA2137E13 7C13FC5B485A12035B485A485A90C8FC121E5A5A5A5A1A777C832E>I8 D<12F012FEEAFFC0EA3FF0EA07FCEA 01FE6C6C7EEB3FC06D7E130F801307801303B3B0801301A26D7E806E7E6E7E6E7EEC07F8 EC01FC9138007F80ED1FE01503151FED7F80913801FC00EC07F8EC1FE04A5A4A5A4AC7FC 5C495AA213035CB3B013075C130F5C131F495AEBFF804848C8FCEA07FCEA3FF0EAFFC048 C9FC12F0237775833A>I<16F01501ED03E0ED07C0ED0F80ED1F005D157E5D5D14014A5A 4A5A4A5AA24A5A143F92C7FC147EA25C13015C13035C13075C130F5C131FA2495AA349C8 FCA213FEA312015BA212035BA21207A25BA2120FA25BA2121FA45BA2123FA55B127FA990 C9FC5AB3AA7E7FA9123F7FA5121FA27FA4120FA27FA21207A27FA21203A27F1201A27F12 00A3137FA26D7EA36D7EA2130F801307801303801301801300147EA28081141F6E7EA26E 7E6E7E6E7E140081157E8181ED0F80ED07C0ED03E0ED01F0150024B26E833B>16 D<12F07E127C7E7E6C7E7F6C7E6C7E12017F6C7E137E7FA26D7E80130F6D7EA26D7E8013 0180130080147E147F8081A26E7EA36E7EA26E7EA3811403A2811401A281A21400A281A2 81A21680A4153FA216C0A5151F16E0A9150F16F0B3AA16E0151FA916C0153FA51680A215 7FA41600A25DA25DA21401A25DA214035DA214075DA34A5AA24A5AA34A5AA292C7FC5C14 7E14FE5C13015C13035C495AA2495A131F5C49C8FCA2137E5B485A5B1203485A485A5B48 C9FC123E5A5A5A24B27C833B>I<171E173E177C17F8EE01F0EE03E0EE07C0160FEE1F80 EE3F00167E167C16FC4B5A4B5A15075E4B5A4B5A153F93C7FC5D15FE5D14015D14034A5A A24A5AA24A5AA24A5AA24AC8FCA214FEA213015C13035C1307A25C130F5C131FA25C133F A3495AA349C9FCA35A5BA312035BA31207A25BA2120FA35BA3121FA35BA3123FA55BA212 7FAB485AB3B06C7EAB123FA27FA5121FA37FA3120FA37FA31207A27FA21203A37F1201A3 7F7EA36D7EA36D7EA3131F80A2130F80130780A21303801301801300A2147FA26E7EA26E 7EA26E7EA26E7EA26E7E140181140081157F8182151F6F7E6F7E8215036F7E6F7E167C16 7E82EE1F80EE0FC01607EE03E0EE01F0EE00F8177C173E171E2FEE6B8349>I<12F07E12 7C7E7E6C7E6C7E7F6C7E6C7E6C7E137C137E7F6D7E80130F6D7E6D7E801301806D7E147E 147F80816E7EA26E7EA26E7EA26E7EA26E7EA26E7EA2818182153F82A2151F82150F82A2 150782A36F7EA36F7EA38281A31780167FA317C0A2163FA217E0A3161FA317F0A3160FA3 17F8A51607A217FCABEE03FEB3B0EE07FCAB17F8A2160FA517F0A3161FA317E0A3163FA3 17C0A2167FA21780A316FF1700A35D5EA34B5AA34B5AA35E150FA25E151F5E153FA25E15 7F93C7FC5D5DA24A5AA24A5AA24A5AA24A5AA24A5AA24A5A92C8FC5C147E14FE495A5C13 035C495A495A131F5C49C9FC137E137C13FC485A485A485A5B485A48CAFC123E5A5A5A2F EE7C8349>I<170F173F17FF1603EE0FFCEE1FF0EE7FE0EEFF804B13004B5A4B5A4B5A4B 5A4B5A4B5A15FF5E5C93C7FC5C5D14075DA3140F5DB3B3B3AE4A5AA3143F5DA24A5AA24A 5AA24990C8FC495AA2495A495A495A495A495A49C9FC485AEA07FCEA0FF0EA3FC0B4CAFC 12FCA2B4FCEA3FC0EA0FF0EA07FCEA01FE6C7EEB7FC06D7E6D7E6D7E6D7E6D7EA26D7E6D 7FA26E7EA26E7EA281141FA36E7EB3B3B3AE811407A38114038180828082157F6F7E6F7E 6F7E6F7E6F7E6F7E6F1380EE7FE0EE1FF0EE0FFCEE03FF1600173F170F30EE73834B>26 D[51 298 114 131 80 40 D[<12F812FE6C7E13E07FEA3FF8EA1FFEEA07FF6C7F6C7F6C7FEB3FF06D7E806D 7E6D7E7F6D7F817F81147F81143F81141FA281140FA3811407B3B3B3B3AD8180A46E7FA3 6E7FA36F7EA26F7E151F82150F826F7E6F7E816F7F707E707E707E707E707E707E933801 FF809338007FC0EF3FE0170FA2173FEF7FC0933801FF80933803FE004C5A4C5A4C5A4C5A 4C5A4C5A4B90C7FC5D4B5A4B5A5E151F5E153F4B5AA24B5AA34A5BA34A90C8FCA45C5DB3 B3B3B3AD140F5DA3141F5DA2143F5D147F5D14FF5D5B5D4990C9FC5B495A495A5C495AEB FFE0485B485B4890CAFCEA1FFEEA3FF8B45A5B138048CBFC12F8>51 298 114 131 80 I80 D88 DI<12F8B3B3B3B3B3B3B3B3B3ABB612 F0A51CB26A8335>106 DIIII<12F012FE6C7E13E0EA3FF8EA0FFCEA03FFC67F6D7E6D7E6D7E6D7E6D7E6D 7EA26D7E7FA281147FB3B3AF81143FA281141F81140F8114076E7E6E7E6E7E6F7E6F7EED 1FF0ED07F8ED01FE923800FF80163FA216FF923801FE00ED07F8ED1FF0ED3FC04B5A4BC7 FC4A5A4A5A4A5A140F5D141F5D143F5DA2147F5DB3B3AF14FF92C8FCA25B495AA2495A49 5A495A495A495A495A000390C9FCEA0FFCEA3FF8EAFFE0138048CAFC12F029B2748342> I<1D601DF01C01A2F403E0A2F407C0A2F40F80A2F41F00A21C3EA264A21C781CF8A2515A A2515AA2515AA2515AA251C7FCA21B3EA263A263A2505AA2505AA2505AA2505AA250C8FC A21A1E1A3EA262A262A24F5AA24F5AA24F5AA24F5AA201024DC9FC130749173EEB3F8001 7F5F13FF486D5E1207260E3FE04B5A121C26781FF04B5A12E000404D5AC66C7E616D6C15 0FA26D6C4BCAFCA2183E6D7E606D7F606E7E4D5AA26E6C495AA26E6C495AA26E6C495AA2 6E6C49CBFCA2173E6E7E5F6E7E5F6E1380EE81F0A292387FC1E016C3ED3FE3EEE7C0ED1F F7EEFF80A26F90CCFCA26F5AA26F5AA25E15015E6F5A5C78768364>I<1D601DF0A21C01 A21DE01C03A21DC01C07A21D801C0FA21D0064A21C1E1C3EA21C3C1C7CA21C781CF8A264 A21B01A2641B03A2641B07A2641B0FA299C7FC63A21B1E1B3EA21B3C1B7CA21B781BF8A2 63A21A01A2631A03A2631A07A2631A0FA298C8FC62A21A1E1A3EA21A3C1A7CA21A781AF8 A262A21901A2621903A2621907A262190FA297C9FC01025F130749171E193E5B496C163C 017F177C13FF486D16784818F8137F000660486C7E001C17011238486C6C5E00E0170312 40C66C6C5E1807A2616D6C150FA296CAFC6D6C5DA2181E183E6D7E183C187C6D7F187818 F8A26E6C5CA217016E7E601703A26E6C5C1707A26E6C5C170FA26E6C91CBFC5FA2171E6E 6C133EA2173C6E6C137CA2177817F86E13805FA2ED7FC1A25F16C3ED3FE35F16E7ED1FF7 5F16FFA26F90CCFCA36F5AA36F5AA35E1501A25E15005E5CB3768364>I E /Fl 18 113 df<007FB912E0BA12F0A26C18E03C04789A4D>0 D<121FEA3F80EA7FC0EAFFE0A5EA7FC0EA3F80EA1F000B0B789E1C>I<037FB612E00207 B712F0143F91B812E0010301C0C9FCD907FCCAFCEB0FE0EB3F8049CBFC13FC485A485A48 5A5B485A121F90CCFC123EA2123C127CA2127812F8A25AA87EA21278127CA2123C123EA2 7E7F120F6C7E7F6C7E6C7E6C7E137E6D7EEB1FE0EB07FC6DB47E010090B712E0023F16F0 1407020016E092CAFCB0001FB912E04818F0A26C18E03C4E78BE4D>18 D<19E0F003F0180FF03FE0F0FF80943803FE00EF0FF8EF3FE0EFFF80DC03FEC7FCEE0FF8 EE3FE0EEFF80DB03FEC8FCED1FF8ED7FE0913801FF80DA07FEC9FCEC1FF0EC7FC04948CA FCEB07FCEB1FF0EB7FC04848CBFCEA07FCEA1FF0EA7FC048CCFCA2EA7FC0EA1FF0EA07FC EA01FF38007FC0EB1FF0EB07FCEB01FF9038007FC0EC1FF0EC07FC913801FF809138007F E0ED1FF8ED07FE923800FF80EE3FE0EE0FF8EE03FE933800FF80EF3FE0EF0FF8EF03FE94 3800FF80F03FE0F00FF01803F000E01900B0007FB912E0BA12F0A26C18E03C4E78BE4D> 20 D<127012FCB4FCEA7FC0EA1FF0EA07FCEA01FF38007FC0EB1FF0EB07FCEB01FF9038 007FC0EC1FF0EC07FC913801FF809138007FE0ED1FF8ED07FE923800FF80EE3FE0EE0FF8 EE03FE933800FF80EF3FE0EF0FF8EF03FE943800FF80F03FE0F00FF0A2F03FE0F0FF8094 3803FE00EF0FF8EF3FE0EFFF80DC03FEC7FCEE0FF8EE3FE0EEFF80DB03FEC8FCED1FF8ED 7FE0913801FF80DA07FEC9FCEC1FF0EC7FC04948CAFCEB07FCEB1FF0EB7FC04848CBFCEA 07FCEA1FF0EA7FC048CCFC12FC1270CDFCB0007FB912E0BA12F0A26C18E03C4E78BE4D> I24 D33 D<14034A7EB3B3B3A50060161800FC16FCB4150301C0140FD81FF0EC 3FE0D803F8EC7F00D800FC14FC017FEB83F890391F8787E090390FC78FC001075C902603 E79FC7FC903801F7BE903800FFFC6E5AA26E5A6E5AA26E5AA26E5AA46EC8FCA32E587EC4 32>35 D49 D<92B6FC02071580143F91B7120001030180C8FCD907FCC9FCEB 1FE0EB3F80017ECAFC5B485A485A485A5B485A121F90CBFC123EA2123C127CA2127812F8 A25AA2B9FC1880A2180000F0CBFCA27EA21278127CA2123C123EA27E7F120F6C7E7F6C7E 6C7E6C7E137E6D7EEB1FE0EB07FC6DB47E010090B6FC023F1580140702001500313A78B5 42>I<0060170C00F0171EB3B3A66C173EA20078173C007C177C007E17FC003E17F86CEE 01F06D15036C6CED07E06C6CED0FC0D803F8ED3F80D801FEEDFF0026007FC0EB07FCD93F FCEB7FF8010FB612E001031580D9007F01FCC7FC020713C0373D7BBA42>91 D<126012F0B3B3B3B3B3A5B512FE14FFA26C13FE18646FCA2C>98 D<1406140FB3B3B3B3B3A5007FB5FCB6FCA26C13FE18647ECA2C>I102 D<12FEEAFFE0EA07F8EA00FE EB7F806D7E6D7E130F6D7EA26D7EB3AD6D7EA26D7E806E7E6E7EEC0FE0EC03FC913800FF E0A2913803FC00EC0FE0EC3FC04A5A4AC7FC5C495AA2495AB3AD495AA2495A131F495A49 5A01FEC8FCEA07F8EAFFE048C9FC236479CA32>I<126012F0B3B3B3B3B3A81260046474 CA1C>106 D<0070130700F01480B3B3B3B3B3A800701400196474CA32>I<1B0C1B1E1B3E A21B7CA21BF8A2F201F0A2F203E0A2F207C0A2F20F80A2F21F00A21A3EA262A262A24F5A A2621903A24F5AA24F5AA24FC7FCA2193EA261A261A24E5AA24E5AA24E5AA24E5AA2010C 4CC8FC133C017C163EEA01FE00035F487E001E5F00387FD8707F4B5A00E07FD8003F4B5A 80011F4B5AA26E4A5A130F6E4AC9FC13076E143E13036E5C13016E5C7F6F5B027F1301A2 6F485A143F6F485A141F6F485A140F6F48CAFC1407EDFC3E14035E15FE02015B15FF6E5B A26F5AA26F5AA26F5AA26FCBFC150E4F647A8353>112 D E /Fm 22 117 df<13FC13FFEB1FC0130F6D7EA36D7EA2130180A26D7EA3147EA280A36E7EA214 0F81A24A7E143F147FECF3F0EB01E3EB03C190380781F8130F49C67E133E5B49137E485A 48487F1207485A4848EB1F8048C7FC127E48EC0FC048EC07E000701403232F7DAD29>21 D<123C127EB4FCA21380A2127F123D1201A312031300A25A1206120E5A5A5A126009157A 8714>59 D<15C0140114031580A214071500A25C140EA2141E141CA2143C143814781470 A214F05CA213015CA213035C130791C7FCA25B130EA2131E131CA2133C1338A213781370 13F05BA212015BA212035BA2120790C8FC5A120EA2121E121CA2123C1238A212781270A2 12F05AA21A437CB123>61 D<124012F012FC127FEA1FC0EA07F0EA01FCEA007FEB1FC0EB 07F0EB01FCEB007FEC1FC0EC07F0EC01FCEC007FED1FC0ED07F0ED01FCED007FEE1FC016 07161FEE7F00ED01FCED07F0ED1FC0037FC7FCEC01FCEC07F0EC1FC0027FC8FCEB01FCEB 07F0EB1FC0017FC9FCEA01FCEA07F0EA1FC0007FCAFC12FC12F012402A2B7AA537>I<01 3FB6FC17C0903A00FE0007F0EE01F84AEB00FC177E1301177F5CA21303177E4A14FEA201 07EC01FC17F84AEB03F0EE07E0010FEC1FC0EE7F009138C003FC91B55A4914FE9139C000 3F804AEB0FC017E0013F140717F091C7FC16035BA2017E1407A201FE15E0160F4915C016 1F0001ED3F80EE7F004914FEED03F80003EC0FF0B712C003FCC7FC302D7CAC35>66 D<013FB7FCA2D900FEC7127F171F4A140FA20101150717065CA21303A25C163001071470 17004A136016E0130F15019138C007C091B5FC5BECC0074A6C5AA2133FA2020090C7FCA2 5B92C8FC137EA213FEA25BA21201A25BA21203B512F0A2302D7DAC2D>70 D<90383FFFFEA2010090C8FC5C5CA21301A25CA21303A25CA21307A25CA2130FA25CA213 1FA25CA2133FA291C7EA0180A24914031700017E5C160601FE140EA2495C163C12015E49 EB01F84B5A0003141FB7FC5E292D7DAC30>76 DII<913807F00691383FFE0E9138F80F9E903903E001FE 903807800049C7127C131E49143CA2491438A313F81630A26D1400A27FEB7F8014F86DB4 7E15F06D13FC01077F01007F141F02011380EC003F151F150FA215071218A3150F003815 00A2151EA2007C5C007E5C007F5C397B8003E039F1F00F8026E07FFEC7FC38C00FF0272F 7CAD2B>83 D97 D99 D<151FEC03FFA2EC003FA2153EA2157EA2157CA2 15FCA215F8A21401EB07E190381FF9F0EB7C1DEBF80FEA01F03903E007E0EA07C0120FEA 1F8015C0EA3F00140F5A007E1480A2141F12FE481400A2EC3F021506143E5AEC7E0E007C EBFE0C14FC0101131C393E07BE18391F0E1E38390FFC0FF03903F003C0202F7DAD24>I< EB03F8EB0FFE90383E0780EBF803D801F013C03803E001EA07C0000F1303D81F80138014 07393F000F00141E387F01FCEBFFF091C7FC007EC8FC12FE5AA4127C156015E0EC01C06C EB0380EC0F006C131C380F81F83803FFE0C648C7FC1B1F7D9D21>I<1307EB0F80EB1FC0 A2EB0F80EB070090C7FCA9EA01E0EA07F8EA0E3CEA1C3E123812301270EA607EEAE07C12 C013FC485A120012015B12035BA21207EBC04014C0120F13801381381F01801303EB0700 EA0F06131EEA07F8EA01F0122E7EAC18>105 D<15E0EC01F01403A3EC01C091C7FCA914 7CEB03FE9038078F80EB0E07131C013813C01330EB700F0160138013E013C0EB801F1300 1500A25CA2143EA2147EA2147CA214FCA25CA21301A25CA21303A25CA2130700385BEAFC 0F5C49C7FCEAF83EEAF0F8EA7FF0EA1F801C3B81AC1D>I<131FEA03FFA2EA003FA2133E A2137EA2137CA213FCA25BA2120115F89038F003FCEC0F0E0003EB1C1EEC387EEBE07014 E03807E1C09038E3803849C7FC13CEEA0FDC13F8A2EBFF80381F9FE0EB83F0EB01F81300 481404150C123EA2007E141C1518007CEBF038ECF83000FC1470EC78E048EB3FC00070EB 0F801F2F7DAD25>I<27078007F0137E3C1FE01FFC03FF803C18F0781F0783E03B3878E0 0F1E01263079C001B87F26707F8013B00060010013F001FE14E000E015C0485A49148000 81021F130300015F491400A200034A13076049133E170F0007027EEC8080188149017C13 1F1801000F02FCEB3F03053E130049495C180E001F0101EC1E0C183C010049EB0FF0000E 6D48EB03E0391F7E9D3E>109 D<3907C007E0391FE03FF83918F8783E393879E01E3930 7B801F38707F00126013FEEAE0FC12C05B00815C0001143E5BA20003147E157C5B15FC00 07ECF8081618EBC00115F0000F1538913803E0300180147016E0001F010113C015E390C7 EAFF00000E143E251F7E9D2B>II<903807E03090381FF87090387C1CF0EBF80D3801F00F3903E007E0EA07C0000F 1303381F800715C0EA3F00A248130F007E1480A300FE131F481400A35C143E5A147E007C 13FE5C1301EA3E07EA1F0E380FFCF8EA03F0C7FC13015CA313035CA21307A2EBFFFEA21C 2B7D9D20>113 D<130E131FA25BA2133EA2137EA2137CA213FCA2B512F8A23801F800A2 5BA21203A25BA21207A25BA2120FA25BA2001F1310143013001470146014E0381E01C0EB 0380381F0700EA0F0EEA07FCEA01F0152B7EA919>116 D E /Fn 13 112 df<13031307130E131C1338137013F0EA01E013C01203EA0780A2EA0F00A2121E A35AA45AA512F8A25AAB7EA21278A57EA47EA37EA2EA0780A2EA03C0120113E0EA00F013 701338131C130E1307130310437AB11B>40 D<12C07E12707E7E7E120FEA0780120313C0 EA01E0A2EA00F0A21378A3133CA4131EA5131FA2130FAB131FA2131EA5133CA41378A313 F0A2EA01E0A2EA03C013801207EA0F00120E5A5A5A5A5A10437CB11B>I43 D48 D<130C133C137CEA03FC12FFEAFC7C1200B3B113FE387FFFFEA2172C7AAB23>II<007FB712F8B812FCA2CBFCADB812FCA26C16F82E137C9937>61 D<15F8141FA214011400ACEB0FE0EB7FF83801F81E3803E0073807C003380F8001EA1F00 481300123E127EA25AA9127C127EA2003E13017EEB8003000F13073903E00EFC3A01F03C FFC038007FF090391FC0F800222F7EAD27>100 DII<013F13F89038FFC3FE3903E1FF1E3807807C000F14 0C391F003E00A2003E7FA76C133EA26C6C5A00071378380FE1F0380CFFC0D81C3FC7FC90 C8FCA3121E121F380FFFF814FF6C14C04814F0391E0007F848130048147C12F848143CA4 6C147C007C14F86CEB01F06CEB03E03907E01F803901FFFE0038003FF01F2D7E9D23>I< EA07C012FFA2120F1207B3B3A3EA0FE0EAFFFEA20F2E7EAD14>108 D111 D E /Fo 33 117 df11 D15 D21 D<121EEA7F80A2EAFFC0A4EA7F80A2EA1E000A 0A78891B>58 D<121EEA7F8012FF13C0A213E0A3127FEA1E601200A413E013C0A3120113 80120313005A1206120E5A5A5A12600B1D78891B>I I<1618163C167CA2167816F8A216F01501A216E01503A216C01507A21680150FA2ED1F00 A2151E153EA2153C157CA2157815F8A25D1401A24A5AA25D1407A25D140FA292C7FC5CA2 141E143EA2143C147CA25CA25C1301A25C1303A25C1307A25C130FA291C8FC5BA2133EA2 133C137CA2137813F8A25B1201A25B1203A2485AA25B120FA290C9FC5AA2121E123EA212 3C127CA2127812F8A25A126026647BCA31>I<127012FCB4FCEA7FC0EA1FF0EA07FCEA01 FF38007FC0EB1FF0EB07FE903801FF809038007FE0EC1FF8EC03FE913800FF80ED3FE0ED 0FF8ED03FF030013C0EE3FF0EE0FFCEE01FF9338007FC0EF1FF0EF07FCEF01FF9438007F C0F01FE0A2F07FC0943801FF00EF07FCEF1FF0EF7FC04C48C7FCEE0FFCEE3FF0EEFFC003 0390C8FCED0FF8ED3FE0EDFF80DA03FEC9FCEC1FF8EC7FE0903801FF80D907FECAFCEB1F F0EB7FC04848CBFCEA07FCEA1FF0EA7FC048CCFC12FC12703B3878B44C>I<1830187018 F0A217011703A24D7EA2170F171FA21737A2176717E717C793380187FCA2EE0307EE0703 1606160CA216181638163004607FA216C0030113011680ED0300A21506150E150C5D845D 03707F15605DA24A5A4AB7FCA25C0206C87F5C021C157F14185CA25C14E05C495A8549C9 FC49163F1306130E5B133C137C01FE4C7ED807FFED01FF007F01F0027FEBFFC0B5FC5C42 477DC649>65 D<91B87E19F019FC02009039C00003FF6F480100138003FFED3FC01AE093 C8121FF10FF0A24A17F84B1507A314035D190FA2020717F04B151F1AE0193F020F17C04B ED7F80F1FF004E5A021F4B5A4B4A5AF01FF0F03FC0023F4AB4C7FC4BEB1FFC92B612F018 FEDA7FC0C7EA7F804BEC1FC0F00FF0727E02FF6F7E92C8FC727EA249835CA313035CA301 075F4A1503A24E5A130F4A4B5A4E5AA2011F4C5A4A4B5A4D485A013F4B48C7FCEF0FFC4A EC3FF801FF913801FFE0B9128005FCC8FC17C045447CC34A>I<91B912F8A3020001C0C7 123F6F48EC07F003FF1503190193C9FCA21A705C5DA3020317605DA314075D18C0170102 0F4B13005DA21703021F92C8FC4B5BA25F023F141E4B13FE92B5FCA24A5CED8000173CA2 02FF141892C7FCA217384915305CA21770010315604A91C9FCA313075CA3130F5CA3131F 5CA2133FA313FFB612F8A345447CC33F>70 D<91B6D8E003B61280A3020001E0C70003EB 8000DB7F806E48C7FC03FF1503A293C85BA219075C4B5EA2190F14034B5EA2191F14074B 5EA2193F140F4B5EA2197F141F4B5EA219FF143F92B8C8FCA3DA7FC0C712014B5DA21803 14FF92C85BA218075B4A5EA2180F13034A5EA2181F13074A5EA2183F130F4A5EA2187F13 1F4A5EA2013F16FFA24A93C9FCD9FFE002037FB6D8E003B67EA351447CC351>72 D<027FB512F8A217F09139007FF000ED3FC0157FA25EA315FF93C7FCA35C5DA314035DA3 14075DA3140F5DA3141F5DA3143F5DA3147F5DA314FF92C8FCA35B5CA313035CA313075C A3130F5CA2131FA25CEB7FF0007FB512F0B6FCA22D447DC32B>I<91B612F8A3020001E0 C8FC6F5A4B5AA293C9FCA35C5DA314035DA314075DA3140F5DA3141F5DA3143F5DA3147F 5DA314FF92CAFCA35B4A16C0A21801010317804A15031900A201075E4A1506180E181E01 0F161C4A153C18381878011F16F84A4A5A1703013F150F4D5A4A14FF01FF02075BB9FCA2 603A447CC342>76 D<91B500C0933803FFFE63630200F1FE00DB6FE0EE1BF803EF171F1B 3703CFEF67F0A21BCF0201EF018F038F60DB87F0ED030F1B1F020317060307040C5BA2F2 183F020717300206616F6C15601B7F020E17C0020CDC018090C7FCA24F485A021C160602 18606F6C5C1A0102381618023004305BA2F16003027016C00260606F6CEB01801A0702E0 ED03004A03065CA24E130F01015E4A60047F5B1A1F01035E91C74A5CA24D48133F494BC7 FC010661EE3F861A7F010E158C010C039892C8FCA205B05C011C15E001186001386E5A19 0101785D01FC92C75BD803FFEF07FEB500F8011E0107B512FE161C160C5F447BC35E>I< 91B500C0020FB5128082A2DA007F9239007FE00070ED1F8074C7FCDBEFF8150E15CF03C7 160C70151C1401DB83FE1518A2DB81FF1538140303001630831A704A6D7E02061760163F 7114E0140E020C6D6C5CA2706C1301141C021801075D83190302386D7E023094C8FC1601 715B147002606DEB8006A294387FC00E14E04A023F130C18E0191C0101ED1FF04A161817 0FF0F838130391C83807FC30A2943803FE705B01060301136018FF19E0010E81010C5F18 7FA2131C0118705A1338181F137801FC70C9FCEA03FFB512F884180651447CC34E>II<9339FF8001800307EBF003033F13FC9239FF007E07DA01F8EB0F0FDA07E0 9038079F004A486DB4FC4AC77E023E804A5D187E5C495A183C495AA213074A1538A3130F 183080A295C7FC806D7E8014FF6D13E015FC6DEBFFC06D14FC6E13FF6E14C0020F800203 14F8EC003F03077F9238007FFE160F1603707E8283A283A21206A4000E163EA2120C177E 001E167CA25F5F003F15014C5A6D4A5A4C5A486C4AC8FC6D143ED87CF85CD8787E495A3A F01FC00FE0D8E007B51280010149C9FC39C0003FF039487BC53C>83 D<023FB500E0011FB5FCA39126007FFEC7000313E0DB3FF8913801FE006F486E5A1AF06F 6C4A5A626F6C4A5A0706C7FC190E6F6C5C616F6C5C6171485A6F5D4EC8FC93387FC00660 706C5A6060706C5A17F193380FFB8005FFC9FC5F705AA2707EA3707E5E04067F5E93381C 7FC0163816704C6C7EED01C04B486C7E160015064B6D7E5D4B6D7E5D5D4A486D7E14034A C76C7E140E5C4A6E7F143002E06F7E495A0103707E495A131F496C4B7E2603FFE04A487E 007F01FC021FEBFFF0B5FCA250447EC351>88 D97 DIIIII<141E143F5C5C A3147E143891C7FCAE133EEBFF803801C3C0380781E0380601F0120E121CEA1803123812 30A2EA700700605BA2EAE00F00C05BEA001F5CA2133F91C7FCA25B137E13FE5BA212015B EC03800003140013F01207495A1406140E140CEBC01C141814385C00035BEBE1C0C6B45A 013EC7FC19437DC121>105 D<14FE137FA3EB01FC13001301A25CA21303A25CA21307A2 5CA2130FA25CA2131FA25C163F013FECFFC0923803C0E09138000703ED1E0F491338ED70 1F017E13E0EC01C001FE018013C00203EB07004948C8FC140E00015B5C495A5C3803FBC0 01FFC9FC8014F83807F1FE9038F03F809038E00FE06E7E000F130381EBC001A2001FED01 C017801380A2003F15031700010013F05E481506160E007E150C161C00FE01005BED7870 48EC3FE00038EC0F802B467BC433>107 D<01F8D903FCEC7F80D803FED91FFF903803FF E0D8071F903B7C0FC00F81F83E0E0F80E007E01C00FC001C9026C3C0030178137C271807 C700D9F0E0137E02CE902601F1C0133E003801DCDAFB80133F003001D892C7FCD90FF814 FF0070495C0060495CA200E04949485CD8C01F187E4A5C1200040715FE013F6091C75BA2 040F14014960017E5D1903041F5D13FE494B130762043F160E0001060F130C4992C713C0 191F4CED801C00031A1849027E1638F2003004FE167000071A60494A16E0F201C0030192 380F0380000FF18700494AEC03FED80380D90070EC00F84F2D7DAB55>109 D<01F8EB03FCD803FEEB1FFFD8071F90387C0FC03B0E0F80E007E03A0C07C3C003001CD9 C7007F001801CE1301003801DC80003013D8EB0FF800705B00605BA200E0491303D8C01F 5D5C12001607013F5D91C7FCA2160F495D137E161F5F13FE49143F94C7FC187000014B13 6049147E16FE4C13E0000317C049150104F81380170300071700495D170EEE781C000FED 7C3849EC1FF0D80380EC07C0342D7DAB3A>I112 D<91380FC00391383FF0079138 F83C0F903903E00E1E90390FC0063E90381F800790393F00037E4914FC01FE1301485AA2 484814F812075B000F140316F0485AA2003F14074914E0A3007F140F4914C0A3151F90C7 13805AA2153F6C1500A2127E5D007F14FE6C1301A214036C6C485A000F131E3807C03838 03E0F13901FFC1F838003F01130014035DA314075DA3140F5DA2141FA2143F011FB51280 A21600283F7DAB2B>I115 D<141C147EA314FE5CA313015CA313035CA313075CA2007FB512FCB6FC15F839000FC000 A2131F5CA3133F91C7FCA35B137EA313FE5BA312015BA312035BA21570000714605B15E0 15C0000F130101C013801403EC070000071306140E5C6C6C5A000113F03800FFC0013FC7 FC1E3F7EBD23>I E /Fp 33 122 df<121FEA3F80EA7FC0EAFFE0A5EA7FC0EA3F80EA1F 000B0B768A20>46 D<141C143C147CEB01FC1307137FB5FC13FB1383EA0003B3B3AF497E 90381FFF80007FB612E0A3234177C037>49 D<49B47E011F13F0017F13FE9038FC03FF3A 01E0007FC0D80380EB1FE00006C76C7E486E7E4881486E7E15014881126CB4806D15807F A46C5AA26CC8FCC91300A25D5EA24B5AA24B5A5E4B5A151F5E4B5A4BC7FC157E5DEC01F0 4A5A4A5A4A5A4AC8FC143E147814705C4948EB0180495A49C7FC010EEC03005B5B5B01C0 5C485A48C8120E48B612FE5A5A5A5AB75AA329417AC037>II<16E01501A215031507A2150F15 1FA2153F157F15EF15CFEC018F1403150F1406140E141C141814301470146014C0130114 80EB03005B130E130C5B133813305B13E0485A5B48C7FC5A12065A121C5A123012705AB8 12F8A3C8381FE000AC4B7E4B7E027FB512F8A32D427CC137>I<481518D803E014F801FF EB0FF091B55A5E5E93C7FC15FC15F06D13C0D90FFEC8FC90CAFCADEC7FC0903803FFF890 380F807E90383C001F01706D7E01C06D7E49806F7E6CC77FC86C7EA282150082A31780A4 123E127F487E7FA217005B90C75A007E5D12605E6C14035E6C4A5A6C5D000E4A5A6C6C49 5AD801E0017FC7FC3900FC03FE90387FFFF8011F13E0D903FEC8FC29427AC037>I<4AB4 FC021F13C091387E00F0D901F81338D903E0130C495A011FC71216013E147E017E14FF49 5B5B1201485A00076E5A49147C000F92C7FCA2485AA2123FA3485AA2EC1FE0ECFFFC9038 81E03F3AFF83000FC00186EB03E0018C6D7E01988001B06D7E8201E0147FA2491580163F 17C0A25B17E0A2127FA5123F7FA217C0121FA2000FED7F807F0007160016FE6C6C5C6C6C 130100005D017C495A013FEB0FC090391FC03F806DB5C7FC010313FC9038007FE02B427B C037>I<121FEA3F80EA7FC0EAFFE0A5EA7FC0EA3F80EA1F00C7FCB3A3121FEA3F80EA7F C0EAFFE0A5EA7FC0EA3F80EA1F000B2B76AA20>58 D<1638A2167CA316FEA34B7EA24B7F A303067F167FA2030C7F163F031C7FED181FA203307F160FA203607F160703E07FEDC003 A2DA01807F82A2DA030080824A810206147FA24A81173FA24A81171F0238810230140F02 3FB6FC4A81A20260C712074A8117030101824A80A249C88083A20106707EA2010E83010C 163FA24983181F133C017C8301FE832607FF80ED7FFEB500F8021FB512FEA347467CC551 >65 D<922603FF80130C033F13F04AB500FC131C020FD9003F133CDA3FF0903807C07CDA 7F80EB01E0D901FEC8EA70FC49481539D907F0150D4948150749481503495A49C9120149 1600485A4848177CA24848173C120F191C485AA2123F49170CA2127FA219005B12FFAC12 7F7FA2190C123FA27F121FA26C6C1718A212076C6C1730A26C6C17606C7E6D17C06D6C15 016D6C16806D6CED03006D6C1506D903FC151C6D6C5D9026007F8014F0DA3FF0EB07C0DA 0FFFEB3F800201D9FFFEC7FCDA003F13F8030313803E4679C44E>67 D75 DI80 D82 D<003FBAFCA3903BF0000FFE000301 806D48EB007F003EC7161F48F00F8000781807A200701803A300601801A548F000C0A5C8 1700B3B3A44B7E92383FFF8049B712F0A342437BC24E>84 D<1570A215F8A34A7EA24A7E A3EC06FF81A24A6C7EA202187F151FA24A6C7EA202707FEC6007A24A6C7EA2010180EC80 01A249C77EA24980010680A2010FB67EA249810118C7121FA24981160F01708101601407 A2498116031201486C6E7E00071503D81FF04AB4FCD8FFFE027F13F8A335347CB33D>97 DI<913A01FF800180021F13F0027F EBFC03903A01FF803E07903A07F800078FD91FE0EB03DF4948EB00FF49C8127F01FE153F 4848151F4848150F1207491507120F48481503A2485A1701127FA25B94C7FC12FFA9127F A26DED0180A2123FA26C7EEF03006C7E12076D150612036C6C5D6C6C5D017F1538D93FC0 5C6D6C495AD907F8EB0780902701FF803FC7FC9039007FFFFC021F13F00201138031357B B33B>IIII<4AB41303021F13E091B5EAF80701039038007C0F D907F8EB0F1FD91FE0EB03BFD93F806DB4FC49C8FC01FE81484881484881485A000F825B 001F82A2485A83127FA25B94C7FC12FFA9007F4AB512FCA27FDB00011380003F6F130083 6C7EA2120F7F6C7E12036C7E6C7E137F6D6C5CD91FE0EB019FD907F8EB071F903A03FF80 3E0F01009038FFFC07021FEBF00302010180C7FC36357BB340>III109 DI II114 D<90390FF00180EB7FFE48 B512833903F00FC73907C000FF48C7127F001E141F48140F127C00781407150312F8A215 01A27EA26C91C7FC127F13C0EA3FF8EBFF806C13FC6CEBFFC06C14F00001806C80013F7F 01037FD9001F1380020113C0EC003FED1FE0150716F01503124000C01401A46C15E0A26C 140316C06C14076C1580B4EC0F0001C0133ED8F1FC13FC00E0B55AD8C01F13E0010390C7 FC24357BB32E>I<007FB812C0A3903A8007FC003F277C0003F813070078160300701601 A20060160000E017E0A2481760A6C71600B3AA4A7E4A7E010FB512FEA333327CB13B>I< B5D8E007B5903801FFF8A3D80FFEC7D83FF89038007FE0D803FCDA1FE0EC1F8049020F16 006D180E000170140C16076C6C6083A2017F60EE0DFCA26D6C5FEE18FE80011F60EE307F 6E1601010F027001805BEE603F6D6C4CC7FC04E013C0EEC01F6D6C1606923901800FE0A2 D901FC5E9239030007F0A2D900FE5E0306EB03F802FF1638027FEDFC304B1301038C1570 DA3F9CECFE6003981300DA1FD85D03F814FF4B147F020F5E4B143FA2020793C8FC4B80A2 0203151E4B140E0201150C4D347DB253>119 D121 D E /Fq 16 118 df<121FEA3F80EA7FC0EAFFE0A5EA7FC0EA3F80EA1F000B0B6C8A33> 46 D64 D97 D99 DII103 DI<14E0EB03F8A2497EA36D5AA2EB00E091C8FCAA383FFFF8487FA47EEA0001B3AD00 7FB612C0B712E016F0A216E06C15C0243E78BD33>I<383FFFFC487FB5FCA27E7EC7FCB3 B3AD003FB612F84815FCB712FEA26C15FC6C15F8273D7ABC33>108 D<02FC137E3B7FC3FF01FF80D8FFEF01877F90B500CF7F15DF92B57E6C010F13872607FE 07130301FC01FE7F9039F803FC01A201F013F8A401E013F0B3A53C7FFE0FFF07FF80B548 018F13C0A46C486C01071380322C80AB33>I<4AB4FC263FFC0713C0267FFE1F13F000FF 017F7F91B5FC6CB67E6CEC07FEC6EBF801ECF0004A7F4A7F5CA291C7FCA35BB3A43B3FFF F80FFFFC486D4813FEB56C4813FFA26C496C13FE6C496C13FC302C7FAB33>I114 D<90381FFE0F90B5EA8F80000314FF120F5A5AEBF007387F800190C7FC00FE147F 5A153FA37E007FEC1F0001C090C7FCEA3FF8EBFFC06C13FF6C14E0000314F8C680011F13 FF01001480020713C0EC007FED1FE0007C140F00FEEC07F01503A27EA27F15076D14E06D 130F6DEB3FC09038FE01FF90B61280160000FD5C00FC14F8D8F83F13E0D8780790C7FC24 2E79AC33>III E /Fr 81 128 df<9239FF8003F8020F9038F01FFE913A3F 807C3E07913BFC000E780F80D901F090381FF01F494890393FE03FC04948137F494814C0 011FEE1F8091C7FC4991393F800600013E021F90C7FC137EAFB912F0A3D8007EC7D81F80 C7FCB3B18301FF4A7E007FD9FE1FB512E0A33A467EC539>11 D<4AB4FC020F13C091383F 00F002FC1338D901F0130C4948131E4948133E4948137F011F5C49C7FCA2013E147E017E 143C93C7FCAD167FB8FCA3D8007EC7FC8282B3B001FFEC7F80007FD9FC1FB5FCA330467E C536>I14 D<121E123FEA7F80EAFFC0 A8EA7F80ABEA3F00AB121EAB120CA6C7FCAA121E123FEA7F80EAFFC0A4EA7F80EA3F0012 1E0A4678C51B>33 D<001EEB03C0003FEB07E0397F800FF039FFC01FF8A301E013FC007F 130F393F6007EC001EEB03CC0000EB000CA5491318A448481330A248C71260A2000614C0 48EB0180A248EB0300481306002013041E1D7DC431>I<121E123FEA7F80EAFFC0A313E0 127FEA3F60121E1200A513C0A4EA0180A2EA0300A212065AA25A5A12200B1D78C41B>39 D<1406140E14181430147014E0EB01C0EB0380EB0700A2130E5B133C133813785BA2485A A2485AA212075BA2120F90C7FCA25A121EA2123EA3123C127CA6127812F8B21278127CA6 123C123EA3121EA2121F7EA27F1207A27F1203A26C7EA26C7EA213781338133C131C7F7F A2EB0380EB01C0EB00E0147014301418140E1406176477CA26>I<7E7E12607E12387E7E 7E6C7EA26C7E6C7E7F137013787FA27FA27FA214801307A214C01303A214E01301A214F0 A3130014F8A61478147CB2147814F8A614F01301A314E0A2130314C0A213071480A2130F 1400A2131EA25BA25B137013F05B485A485AA248C7FC120E5A5A12305A5A5A16647ACA26 >I<16C04B7EB3AB007FBAFCBB1280A26C1900C8D801E0C9FCB3AB6F5A41407BB84C>43 D<121E123FEA7F80EAFFC0A313E0127FEA3F60121E1200A513C0A4EA0180A2EA0300A212 065AA25A5A12200B1D78891B>II<121E123FEA7F80EAFFC0A4EA 7F80EA3F00121E0A0A78891B>I<14FF010713E090381F81F890387E007E01F8131F4848 EB0F80000315C04913074848EB03E0000F15F0A24848EB01F8A3003F15FCA348C812FEA6 4815FFB3A26C15FEA56D1301003F15FCA3001F15F8A26D1303000F15F0A26C6CEB07E000 0315C06D130F6C6CEB1F806C6CEB3F00017E137E90381F81F8903807FFE0010090C7FC28 427CC031>48 D<143014F013011307131F13FFB5FC13E713071200B3B3AF497E497E007F B6FCA3204178C031>II<49B4FC010F13F0013F13FC9038 FE01FE3901E0007FD80380EB3F8048C7EA1FC0000EEC0FE0D80F8014F0EA1FE016F86D13 07A36C5AA2D80380130FC813F0A3ED1FE016C0A2ED3F801600157E5DEC03F0EC1FC0D90F FFC7FC15F090380001FCEC007EED1F8016C0ED0FE0ED07F016F8150316FC16FE1501A216 FFA3121E123F487E487EA216FEA24913036CC713FC127E0070EC07F8003015F06C140F00 0E15E06CEC1FC0D803E0EB7F803A01FC01FE0039007FFFFC011F13E0010190C7FC28427C C031>I<1507A25D5DA25D5DA25DA25C5C811406140E140C141814381430146014E014C0 1301EB038014005B13065B131C13185B137013605B12015B48C7FC5A1206120E120C5A12 3812305A12E0B812C0A3C86CC7FCAC4B7E4A7F91B61280A32A427DC131>I<000215C0D8 07C0130701FCEB7F8090B612005D5D15F05D158026063FFCC7FC90C9FCAE14FF010713E0 90381F01F0903878007C01E07FD807807F90C71380ED0FC01202C8EA07E016F0A3ED03F8 A316FCA4121C123E127F487EA216F890C7FC4814074815F01260A26CEC0FE016C06C141F 001C15806CEC3F006C147E3903C001FC3901F807F039007FFFE06D1380D907FCC7FC2642 7BC031>II<121CA2EA1F8090B712C0A34816801700A25E00 38C8120C00305D127000605D5EA25E484A5A4BC7FCA2C812065DA25D5D5DA25D14015D14 03A24AC8FCA25C140E141EA2143E143CA2147CA214FCA313015CA31303A61307AA6D5A6D 5A2A447BC231>I<14FF010713E0011F13F890383F00FE0178131F01E0EB0F804848EB03 C04848EB01E048C7FCED00F0120E1678121EA4121FA26D14F07FD80FF0EB01E07FD807FE EB03C06DEB07806C9038C00F006CEBE01E6CEBF83890387FFEF090383FFFC0130F6D7F01 0113F801077F90381E3FFFD9781F1380D9F00713C02601C00313E04848C613F048C7EA7F F8000E141F001EEC0FFC48EC03FE150148EC007E163FA248151FA2160FA4160E1278161E 161C6C15186C1538001F15706C6C14E06C6CEB03C0D803F0EB0F80C6B4EB7F0090383FFF FC010F13F00101138028427CC031>I<14FF010713E0011F13F890387F80FC9038FC003E 48487F4848EB0F804848EB07C0484814E01503484814F0123FED01F848C7FCA216FC5AA2 ED00FEA516FFA37E5DA27E7F001F5CA26C7E000714066C6C5B12016C6C5B017C13709038 3F01E090390FFF80FE903801FE0090C8FCA2ED01FCA416F8150316F0A2D80780EB07E048 7E486CEB0FC01680151F160049133E6C485B390C0001F80007495A3903E01FC06CB55A6C 6C48C7FCEB1FF028427CC031>I<121E123FEA7F80EAFFC0A4EA7F80EA3F00121EC7FCB3 A5121E123FEA7F80EAFFC0A4EA7F80EA3F00121E0A2B78AA1B>I<121E123FEA7F80EAFF C0A4EA7F80EA3F00121EC7FCB3A5121E123FEA7F8012FF13C0A3127F123F121E1200A5EA 0180A4EA0300A21206A25AA25A1238123012200A3E78AA1B>I<007FBAFCBB1280A3CEFC B0BB1280A36C190041187BA44C>61 D<16C04B7EA34B7EA34B7EA34B7EA3ED19FEA2ED39 FF1530A203707FED607FA203C07F163FA2DA01807F161FA24A486C7EA302066D7EA2020E 80020C1303A2021C8002181301A24A8082A24A81177FA291B77EA3D90180C7EA1FE0A201 038291C8120FA2498201061507A2010E82010C1503A249821701A2498283137801F88348 7ED80FFF030313E0B500E0027FEBFFC0A342467DC549>65 DIIIIIIII<010FB512FEA3D9000313806E130080B3B3AB123F48 7EA2487EA25D14011380D87F005B006C495A12306C495A6C495A0007EB1F802603E07FC7 FC3800FFFCEB1FE027457BC332>IIIIIII82 D<49B41303010F13E0013FEBF8079038FE00FCD801F0EB1F0F 4848EB079F4848EB01DF48486DB4FC48C87E001E81123E007E81127C8212FC82A46C81A3 7E6C6C91C7FCA2EA3FE07FEA1FFEEBFFE06C13FE6CEBFFE06C14FC6C14FF6C15C0013F80 010F80010180D9001F7F02017F9138001FFF150303001380167FEE3FC0161FA2EE0FE012 4012C01607A47EA217C07E160F6C1680A26CED1F006C151E6C153ED8FBC05CD8F9F05CD8 F07CEB03F03AE03FC00FE0010FB51280D8C00349C7FC9038003FF02B467BC436>I<003F B912E0A3903BF0003FF0007F01806D48130F003EC7150348EF01F00078170019701270A2 19301260A5481818A5C81600B3B3A54B7EEDFFFC0103B7FCA33D447CC346>IIII89 D<001FB81280A30280C7130001FCC7485A01F0140301C05D49140790C8485A001E5E161F 485E4C5A0038157F5F4CC7FC5D00305D15035E4B5A150FC85B4B5A153F5E4B5A15FF93C8 FC5C5D4A5A14075D4A5A141F5D4A5A147F5D14FF92C9FC4948EC018013035C495A130F4A 140349481500133F5C137F5C49C85A5A5B48485D1207495D000F5E48485D4915FE003F15 0349140F484814FFB8FCA331447BC33C>II<6D13100001143048C71260000614C0A248EB018048EB0300A2481306A248 5BA4485BA500CFEB19E039DF801BF039FFC01FF801E013FC007F130FA3393FC007F8391F 8003F0390F0001E01E1D71C431>II97 DII<16FE157FA315011500167EB3EC7F80903803FFF090380FC07890383F000C01 7C13064913034848EB01FE00031400485A4848147EA2121F485AA2127FA290C8FCA25AA9 7EA37F123FA2121F7F000F15FE6C7E000314016C6CEB037E6C6C147F017C010E13806D01 1C13FE90380FC0F0903803FFE09026007F0013002F467DC436>III I II<14F0EB01F8EB03FCEB07FEA4EB03FCEB01F8EB00F01400AD14 FE137FA313011300147EB3B3AB003C137C127EB413FC14F8A238FE01F0007E13E0383803 C0381E0780380FFF00EA01FC175783C21E>III<2701FC01FEEC7F8000FF903B07FFC001FF F0913B0E03F00380FC913B3800F80E003E0003495C000101C0D97C307F0000037E81D9FD 805C01FFC7D83EC0130F043F81495DA34992C7FCB3A9486C4A6C497EB5D8FC3FB5000FB5 12C0A34A2C7DAB51>I<3901FC01FE00FF903807FF8091381E07E091383801F000030160 7F0001EBC0002600FD807F167C01FFC7FC167E5BA35BB3A9486C14FFB5D8FC7F13FEA32F 2C7DAB36>II<3901FC01FC00FF90380FFF 8091383E07E091387001F800039038C0007C2601FD807F6CB4C7123FEE1F8049EC0FC049 15E0EE07F0A217F8160317FCA3160117FEA917FC1603A317F8160717F0EE0FE07FEE1FC0 6D1580EE3F00D9FD80137ED9FCC05B91386001F891383C0FE091381FFF80DA03FCC7FC91 C9FCAE487EB512FCA32F3F7DAB36>I<91387F8006903903FFE00E90380FE07890383F00 1C017EEB061E5B4848EB033E4848EB01BE12074848EB00FEA2485A003F157E5B127FA390 C8FC5AA97E7FA3123F7F121F16FE6C7E000714016C7E6C6CEB037E00001406017C130C01 3F131890380FC0F0903803FFE09038007F0091C7FCAE16FF037F13FEA32F3F7DAB33>I< 3901F807E000FFEB1FF8EC383CEC607E0003EBC0FF12013800F980EBFB00157E153C01FE 1300A45BB3A77F487EB6FCA3202C7DAB26>I<90383FE0303801FFF83907C01E70390F00 07F0001C1301481300A2481470A212F01530A37E7E007E1400EA7F80EA3FF0EBFF806C13 F86C13FE0003EBFF806C14C0D8003F13E0010313F09038001FF81403EC00FC0040147C00 C0147E153E7E151EA37E151C7E153C6C14386C147000FB14E039F18001C039E0F00F8039 C07FFE00EB0FF01F2E7DAC26>I<1306A5130EA4131EA3133E137EA213FE12011207001F B512F0B6FCA2D8007EC7FCB3A4150CAA133E013F1318A27F90380F803001071360903803 E0C0903801FF809038003F001E3E7EBC26>IIII<3B 7FFFF007FFFCA30001D9800113C06C90C7EAFE006D147C6D14706D6C5B6D6C5BECE00101 07495AD903F090C7FCECF806903801FC0E01005BEC7E18EC7F30EC3F706E5A6E5A811407 814A7EEC0DFC1418EC387E4A7E02607FECC01F01016D7ED903807F4A6C7E01061303496D 7E011C80013C1300017C147ED801FC14FFD80FFE4913C0B5D8800713FFA3302B7FAA33> II<003FB612E0A29039E0000FC090C7EA1F80003C143F00381500157E 003014FE00705C4A5A14030060495A5D4A5A141F5DC748C7FC5C14FE5C495A13035C495A 130F494813605C49C7FC5B017E14C05B1201485A5B48481301120F491303485A003FEC0F 8090C7121F007E14FFB7FCA2232B7DAA2B>III<001EEB0780003FEB0FC0397F801FE039FFC03FF0A4397F801FE0393F000FC0001E EB07801C0A76C231>127 D E /Fs 47 123 df45 DI< EC3FF849B5FC010F14E0013F14F890397FF01FFC9039FFC007FE4890380001FF48486D13 80000716C049147F000F16E049143F001F16F0A2003F16F8A249141F007F16FCA600FF16 FEB3A3007F16FCA56C6CEC3FF8A3001F16F0A2000F16E06D147F000716C06D14FF6C6C49 13806C6D4813006C6D485A90397FF01FFC6DB55A010F14E0010314809026003FF8C7FC2F 427CC038>48 DIII<163FA25E5E5D 5DA25D5D5D5DA25D92B5FCEC01F7EC03E7140715C7EC0F87EC1F07143E147E147C14F8EB 01F0EB03E0130714C0EB0F80EB1F00133E5BA25B485A485A485A120F5B48C7FC123E5A12 FCB91280A5C8000F90C7FCAC027FB61280A531417DC038>I<0007150301E0143F01FFEB 07FF91B6FC5E5E5E5E5E16804BC7FC5D15E092C8FC01C0C9FCAAEC3FF001C1B5FC01C714 C001DF14F09039FFE03FFC9138000FFE01FC6D7E01F06D13804915C0497F6C4815E0C8FC 6F13F0A317F8A4EA0F80EA3FE0487E12FF7FA317F05B5D6C4815E05B007EC74813C0123E 003F4A1380D81FC0491300D80FF0495AD807FEEBFFFC6CB612F0C65D013F1480010F01FC C7FC010113C02D427BC038>I<4AB47E021F13F0027F13FC49B6FC01079038807F809039 0FFC001FD93FF014C04948137F4948EBFFE048495A5A1400485A120FA248486D13C0EE7F 80EE1E00003F92C7FCA25B127FA2EC07FC91381FFF8000FF017F13E091B512F89039F9F0 1FFC9039FBC007FE9039FF8003FF17804A6C13C05B6F13E0A24915F0A317F85BA4127FA5 123FA217F07F121FA2000F4A13E0A26C6C15C06D4913806C018014006C6D485A6C9038E0 1FFC6DB55A011F5C010714C0010191C7FC9038003FF02D427BC038>I<121E121F13FC90 B712FEA45A17FC17F817F017E017C0A2481680007EC8EA3F00007C157E5E00785D15014B 5A00F84A5A484A5A5E151FC848C7FC157E5DA24A5A14035D14074A5AA2141F5D143FA214 7F5D14FFA25BA35B92C8FCA35BA55BAA6D5A6D5A6D5A2F447AC238>IIII65 D I68 DI73 D78 D80 D82 DI<003FBA12E0A59026FE000FEB8003D87FE09338003FF049171F90C71607A2007E1803 007C1801A300781800A400F819F8481978A5C81700B3B3A20107B8FCA545437CC24E>I< 903801FFE0011F13FE017F6D7E48B612E03A03FE007FF84848EB1FFC6D6D7E486C6D7EA2 6F7FA36F7F6C5A6C5AEA00F090C7FCA40203B5FC91B6FC1307013F13F19038FFFC010003 13E0000F1380381FFE00485A5B127F5B12FF5BA35DA26D5B6C6C5B4B13F0D83FFE013EEB FFC03A1FFF80FC7F0007EBFFF86CECE01FC66CEB8007D90FFCC9FC322F7DAD36>97 DIIIIIII<137C48 B4FC4813804813C0A24813E0A56C13C0A26C13806C1300EA007C90C7FCAAEB7FC0EA7FFF A512037EB3AFB6FCA518467CC520>I107 DI<90277F8007FEEC0FFCB590263FFFC090387FFF8092B5D8F001B512E002816E48 80913D87F01FFC0FE03FF8913D8FC00FFE1F801FFC0003D99F009026FF3E007F6C019E6D 013C130F02BC5D02F86D496D7EA24A5D4A5DA34A5DB3A7B60081B60003B512FEA5572D7C AC5E>I<90397F8007FEB590383FFF8092B512E0028114F8913987F03FFC91388F801F00 0390399F000FFE6C139E14BC02F86D7E5CA25CA35CB3A7B60083B512FEA5372D7CAC3E> II<90397FC00FF8B590B57E 02C314E002CF14F89139DFC03FFC9139FF001FFE000301FCEB07FF6C496D13804A15C04A 6D13E05C7013F0A2EF7FF8A4EF3FFCACEF7FF8A318F017FFA24C13E06E15C06E5B6E4913 806E4913006E495A9139DFC07FFC02CFB512F002C314C002C091C7FCED1FF092C9FCADB6 7EA536407DAC3E>I<90387F807FB53881FFE0028313F0028F13F8ED8FFC91389F1FFE00 0313BE6C13BC14F8A214F0ED0FFC9138E007F8ED01E092C7FCA35CB3A5B612E0A5272D7D AC2E>114 D<90391FFC038090B51287000314FF120F381FF003383FC00049133F48C712 1F127E00FE140FA215077EA27F01E090C7FC13FE387FFFF014FF6C14C015F06C14FC6C80 0003806C15806C7E010F14C0EB003F020313E0140000F0143FA26C141F150FA27EA26C15 C06C141FA26DEB3F8001E0EB7F009038F803FE90B55A00FC5CD8F03F13E026E007FEC7FC 232F7CAD2C>IIIIIII<001FB71280A49026FC001F130001E0495A5B49 495A90C7485A48495B123E4A5B4A5B003C495BA24A90C7FC4A5A4A5AC7FC4A5A495B495B A2495B499038800780491300A2495A4948130F49481400A2485B48495B485BA248495B48 90C75A48485C15034848EB1FFEB7FCA4292C7DAB32>I E end %%EndProlog %%BeginSetup %%Feature: *Resolution 600dpi TeXDict begin %%PaperSize: Letter %%BeginPaperSize: Letter letter %%EndPaperSize %%EndSetup %%Page: 1 1 1 0 bop 83 83 a Fs(The)38 b(heigh)m(t)e(and)j(size)d(of)i(random)g (hash)g(trees)f(and)i(random)e(p)s(ebbled)h(hash)h(trees)1625 349 y Fr(Luc)33 b(Devro)m(y)m(e)1298 482 y(Sc)m(ho)s(ol)g(of)f (Computer)i(Science)1513 614 y(McGill)f(Univ)m(ersit)m(y)1291 747 y(Mon)m(treal,)h(Canada)e(H3A)h(2K6)1483 880 y Fq(luc@cs.mcgill.ca) 0 1511 y Fp(Abstra)n(ct.)54 b Fr(The)38 b(random)f(hash)h(tree)g(and)f (the)g(N-tree)h(w)m(ere)g(in)m(tro)s(duced)h(b)m(y)f(Ehrlic)m(h)g(in)g (1981.)0 1644 y(In)i(the)h(random)f(hash)h(tree,)i Fo(n)d Fr(data)g(p)s(oin)m(ts)h(are)f(hashed)h(to)f(v)-5 b(alues)41 b Fo(X)2776 1659 y Fn(1)2815 1644 y Fo(;)17 b(:)g(:)g(:)f(;)h(X)3115 1659 y Fm(n)3162 1644 y Fr(,)42 b(i.i.d.)f(random)0 1777 y(v)-5 b(ariables)31 b(taking)g(v)-5 b(alues)31 b(that)g(are)f (uniformly)i(distributed)g(on)e([0)p Fo(;)17 b Fr(1].)42 b(Place)32 b(the)f Fo(X)3204 1792 y Fm(i)3232 1777 y Fr('s)g(in)g Fo(n)f Fr(equal-)0 1910 y(sized)47 b(buc)m(k)m(ets)h(as)e (in)g(hashing)g(with)h(c)m(haining.)84 b(F)-8 b(or)44 b(eac)m(h)j(buc)m(k)m(et)h(with)e(at)f(least)i(t)m(w)m(o)f(p)s(oin)m (ts,)0 2042 y(rep)s(eat)24 b(the)h(same)g(pro)s(cess,)i(k)m(eeping)f (the)f(branc)m(h)g(factor)f(alw)m(a)m(ys)h(equal)g(to)f(the)h(n)m(um)m (b)s(er)g(of)f(buc)m(k)m(eted)0 2175 y(p)s(oin)m(ts.)42 b(If)26 b Fo(H)501 2190 y Fm(n)573 2175 y Fr(is)g(the)h(heigh)m(t)f(of) f(tree)i(obtained)f(in)g(this)g(manner,)i(w)m(e)f(sho)m(w)g(that)f Fo(H)3123 2190 y Fm(n)3169 2175 y Fo(=)17 b Fr(log)3361 2199 y Fn(2)3417 2175 y Fo(n)28 b Fl(!)f Fr(1)f(in)0 2308 y(probabilit)m(y)-8 b(.)43 b(In)29 b(the)f(random)g(p)s(ebbled)i (hash)f(tree,)g(w)m(e)h(remo)m(v)m(e)g(one)e(p)s(oin)m(t)h(randomly)f (and)h(place)g(it)0 2441 y(in)f(the)g(presen)m(t)i(no)s(de)e(\(as)f (with)i(the)f(digital)g(searc)m(h)h(tree)f(mo)s(di\014cation)g(of)f(a)h (trie\))g(and)g(p)s(erform)f(the)0 2574 y(buc)m(k)m(eting)35 b(step)e(as)g(ab)s(o)m(v)m(e)g(on)g(the)g(remaining)g(p)s(oin)m(ts)g (\(if)g(an)m(y\).)44 b(With)33 b(this)g(simple)h(mo)s(di\014cation,) 1727 2725 y Fo(H)1808 2740 y Fm(n)p 1607 2769 369 4 v 1607 2789 a Fk(q)p 1707 2789 269 4 v 1744 2857 a Fn(2)12 b(log)h Fm(n)p 1717 2878 249 4 v 1717 2935 a Fn(log)f(log)h Fm(n)2013 2792 y Fl(!)27 b Fr(1)0 3092 y(in)44 b(probabilit)m(y)-8 b(.)77 b(W)-8 b(e)44 b(also)g(sho)m(w)h(that)e(the)h(exp)s(ected)i(n)m (um)m(b)s(er)f(of)e(no)s(des)h(in)g(the)g(random)g(hash)0 3225 y(tree)39 b(and)g(random)g(p)s(ebbled)g(hash)h(tree)f(is)g (asymptotic)h(to)e(2)p Fo(:)p Fr(3020238)17 b Fo(:)g(:)g(:)d(n)39 b Fr(and)g(1)p Fo(:)p Fr(4183342)17 b Fo(:)g(:)g(:)d(n)0 3358 y Fr(resp)s(ectiv)m(ely)-8 b(.)0 3673 y Fp(Keyw)n(ords)28 b(and)h(phrases.)22 b Fr(Data)h(structures,)k(probabilistic)e (analysis,)i(hashing)d(with)h(c)m(haining,)0 3806 y(hash)33 b(tables,)h(N-trees,)f(random)g(hash)g(trees,)g(exp)s(ected)i (complexit)m(y)-8 b(.)0 3988 y Fp(CR)38 b(Ca)-7 b(tegories:)37 b Fr(3.74,)32 b(5.25,)g(5.5.)p 0 4998 3786 4 v 28 5081 a Fj(Re)r(s)r(e)q(arc)n(h)26 b(of)h(t)m(h)n(e)g(a)m(u)o(t)m(h)n(or)f(w) n(as)h(sp)r(onsore)r(d)g(b)n(y)g(NSER)n(C)g(Gran)m(t)h(A3456)e(an)n(d)h (b)n(y)g(F)n(CAR)h(Gran)m(t)g(90-ER-0291.)p eop %%Page: 2 2 2 1 bop 0 83 a Fs(1.)38 b(In)m(tro)s(duction.)299 431 y Fr(In)24 b(this)h(pap)s(er,)h(w)m(e)f(analyze)g(the)f(heigh)m(t)h(of) e(the)i(random)f(hash)h(tree)f(\(Ehrlic)m(h,)j(1981\))c(de\014ned)0 563 y(as)39 b(follo)m(ws.)64 b(W)-8 b(e)39 b(are)g(giv)m(en)h Fo(X)1189 578 y Fn(1)1229 563 y Fo(;)17 b(:)g(:)g(:)f(;)h(X)1529 578 y Fm(n)1575 563 y Fr(,)41 b Fo(n)e Fr(indep)s(enden)m(t)i(uniform)f ([0)p Fo(;)17 b Fr(1])38 b(random)h(n)m(um)m(b)s(ers.)65 b(If)0 696 y Fo(n)36 b(>)g Fr(1,)j(w)m(e)g(partition)e([0)p Fo(;)17 b Fr(1])37 b(in)m(to)h Fo(n)f Fr(equal)i(in)m(terv)-5 b(als)39 b(of)e(length)h(1)p Fo(=n)f Fr(eac)m(h,)j(and)d(place)i(all)e (p)s(oin)m(ts)0 829 y(in)h(the)h(in)m(terv)-5 b(als.)61 b(Let)39 b Fo(N)997 844 y Fn(1)1036 829 y Fo(;)17 b(:)g(:)g(:)f(;)h(N) 1333 844 y Fm(n)1418 829 y Fr(b)s(e)38 b(the)h(cardinalities)g(of)f (the)g(in)m(terv)-5 b(als)40 b(\(th)m(us,)3256 754 y Fk(P)3361 858 y Fm(i)3406 829 y Fo(N)3484 844 y Fm(i)3550 829 y Fr(=)d Fo(n)p Fr(\).)0 962 y(Rep)s(eat)h(the)h(partition)f(pro)s (cess)h(for)e(ev)m(ery)j(in)m(terv)-5 b(al)39 b(con)m(taining)g(at)e (least)i(t)m(w)m(o)g(p)s(oin)m(ts,)h(and)e(k)m(eep)0 1095 y(going)j(un)m(til)g(no)g(further)h(divisions)h(are)e(p)s (ossible.)70 b(The)42 b(ro)s(ot)e(no)s(de)h(represen)m(ts)j([0)p Fo(;)17 b Fr(1],)43 b(and)e(eac)m(h)0 1228 y(no)s(de)29 b(represen)m(ts)i(a)e(giv)m(en)h(in)m(terv)-5 b(al.)43 b(All)29 b(in)m(ternal)g(no)s(des)h(ha)m(v)m(e)g(at)e(least)i(t)m(w)m (o)f(of)f(the)i Fo(X)3282 1243 y Fm(i)3310 1228 y Fr('s,)g(while)g(all) 0 1360 y(leaf)f(no)s(des)h(ha)m(v)m(e)h(one)e(or)g(zero)h(of)e(the)i Fo(X)1518 1375 y Fm(i)1546 1360 y Fr('s.)43 b(If)29 b(this)h(structure) h(is)f(to)e(b)s(e)i(used)g(for)f(storing)g(the)h(data,)0 1493 y(then)42 b(t)m(w)m(o)g(imp)s(ortan)m(t)f(quan)m(tities)i(are)f (the)g(n)m(um)m(b)s(er)g(of)f(no)s(des)h(in)g(the)f(tree,)k Fo(S)3060 1508 y Fm(n)3148 1493 y Fr(and)c(the)h(heigh)m(t)0 1626 y(of)35 b(the)h(tree,)h Fo(H)592 1641 y Fm(n)639 1626 y Fr(.)52 b(The)36 b(former)g(quan)m(tit)m(y)h(ob)m(viously)g (measures)h(the)e(storage,)g(while)h(the)f(latter)f(is)0 1759 y(the)42 b(w)m(orst-case)g(searc)m(h)h(time.)71 b(In)41 b(addition,)j Fo(S)1860 1774 y Fm(n)1948 1759 y Fr(is)e(also)g(prop)s(ortional)e(to)h(the)h(time)g(needed)h(to)0 1892 y(construct)31 b(the)g(hash)f(tree.)44 b(The)31 b(mo)s(del)f(is)h(appropriate)f(for)g(situations)h(in)f(whic)m(h)i(a)e (hash)g(function)0 2025 y(can)e(b)s(e)f(constructed)i(that)e(deliv)m (ers)j(a)d(uniform)h([0)p Fo(;)17 b Fr(1])26 b(random)i(v)-5 b(ariate.)42 b(This)28 b(ma)m(y)g(b)s(e)g(a)f(debatable)0 2157 y(h)m(yp)s(othesis.)299 2357 y(The)36 b(distributiv)m(e)i (partitioning)d(metho)s(d)h(in)m(v)m(en)m(ted)i(b)m(y)e(Dob)s(osiewicz) h(\(1978\))d(led)i(Ehrlic)m(h)0 2490 y(\(1981\))24 b(to)h(de\014ne)h (the)g(N-tree.)41 b(In)26 b(N-trees,)h(the)f Fo(X)1896 2505 y Fm(i)1924 2490 y Fr('s)g(are)f(unrestricted)i(on)e(the)h(real)f (line,)i(and)f(giv)m(en)0 2622 y(that)33 b(a)g(no)s(de)g(has)h Fo(k)e Fl(\025)d Fr(2)k(of)f(the)i Fo(X)1337 2637 y Fm(i)1365 2622 y Fr('s,)g(it)f(spa)m(wns)i Fo(k)h Fr(equal)e(c)m(hild)h(in)m (terv)-5 b(als)34 b(of)f([min)3199 2637 y Fm(i)3243 2622 y Fo(X)3324 2637 y Fm(i)3352 2622 y Fo(;)17 b Fr(max)3578 2637 y Fm(i)3622 2622 y Fo(X)3703 2637 y Fm(i)3732 2622 y Fr(].)0 2755 y(Note)28 b(that)g(there)g(are)g(alw)m(a)m(ys)i(at)d (least)i(t)m(w)m(o)f(nonempt)m(y)i(subin)m(terv)-5 b(als)30 b(\(the)e(\014rst)g(and)g(the)g(last)g(one\),)0 2888 y(so)44 b(that)g(the)g(size)h(of)e(the)i(N-tree)f(is)g(limited)h(to)f Fo(n)p Fr(\()p Fo(n)30 b Fr(+)f(1\))p Fo(=)p Fr(2.)77 b(A)44 b(basic)h(study)g(of)e(N-trees)i(and)0 3021 y(random)29 b(hash)h(trees)h(w)m(as)f(p)s(erformed)g(b)m(y)g(T)-8 b(amminen)31 b(\(1983\).)41 b(The)30 b(results)h(of)e(T)-8 b(amminen)31 b(will)f(b)s(e)0 3154 y(summarized)41 b(in)d(the)h(next)h (section.)63 b(Ho)m(w)m(ev)m(er,)42 b(T)-8 b(amminen)40 b(did)f(not)g(study)h Fo(H)3078 3169 y Fm(n)3124 3154 y Fr(.)62 b(Hashing)39 b(with)0 3287 y(sev)m(eral)h(lev)m(els)g(of)e (buc)m(k)m(ets)j(has)d(b)s(een)h(kno)m(wn)h(since)g(F)-8 b(agin,)39 b(Niev)m(ergelt,)i(Pipp)s(enger)f(and)e(Strong)0 3419 y(\(1979\))44 b(as)h(extendible)i(hashing.)81 b(Its)46 b(analysis)g(w)m(as)g(subsequen)m(tly)i(re\014ned)e(in)f(sev)m(eral)i (pap)s(ers,)0 3552 y(including)e(pap)s(ers)f(b)m(y)h(T)-8 b(amminen)45 b(\(1981\))e(and)h(Fla)5 b(jolet)44 b(\(1983\).)76 b(Ho)m(w)m(ev)m(er,)49 b(these)c(structures)0 3685 y(di\013er)33 b(fundamen)m(tally)h(from)f(the)g(trees)g(studied)h(here.)299 3884 y(The)42 b(random)f(hash)g(tree)h(and)f(its)g(mo)s(di\014cations)h (studied)g(here)g(are)f(v)-5 b(aguely)42 b(related)f(to)0 4017 y(random)g(tries)g(\(see)g(Pittel,)i(1985,)f(for)e(the)h(main)f (prop)s(erties\).)68 b(W)-8 b(e)41 b(will)g(sho)m(w)h(that)e(the)h (heigh)m(t)0 4150 y Fo(H)81 4165 y Fm(n)176 4150 y Fr(of)48 b(the)h(random)f(hash)h(tree)g(is)g(with)f(high)h(probabilit)m(y)g (close)h(to)d(log)2923 4174 y Fn(2)2980 4150 y Fo(n)p Fr(,)52 b(whic)m(h)e(is)f(rather)0 4283 y(disapp)s(oin)m(ting.)61 b(The)39 b(reason)f(for)f(this)i(phenomenon)h(is)e(the)g(same)h(reason) g(wh)m(y)g(random)f(binary)0 4416 y(tries)i(ha)m(v)m(e)g(heigh)m(t)g (close)g(to)f(2)17 b(log)1314 4439 y Fn(2)1370 4416 y Fo(n)p Fr(.)64 b(This)40 b(prompted)g(us)g(to)e(consider)j(a)e(mo)s (di\014cation)g(similar)0 4548 y(to)g(the)i(mo)s(di\014cation)f(of)f(a) h(trie)g(in)m(to)g(the)g(digital)g(searc)m(h)h(tree)f(of)g(Co\013man)g (and)g(Ev)m(e)h(\(1970\):)57 b(if)0 4681 y Fo(n)44 b Fr(p)s(oin)m(ts)g(b)s(elong)f(to)g(an)g(in)m(terv)-5 b(al)45 b(asso)s(ciated)f(with)g(a)f(no)s(de,)j(remo)m(v)m(e)g(one)d(p) s(oin)m(t)h(uniformly)g(at)0 4814 y(random)30 b(and)g(place)h(it)e(in)i (the)f(no)s(de)g(\(\\p)s(ebble")g(the)h(no)s(de\).)42 b(If)30 b Fo(n)e(>)g Fr(1,)i(the)g(in)m(terv)-5 b(al)31 b(is)f(partitioned)0 4947 y(equally)38 b(in)m(to)g Fo(n)25 b Fl(\000)h Fr(1)36 b(c)m(hild)j(subin)m(terv)-5 b(als)39 b(and)e(the)g Fo(n)26 b Fl(\000)f Fr(1)37 b(remaining)h(p)s(oin)m(ts)f (are)g(placed)h(in)f(their)0 5080 y(subin)m(terv)-5 b(als.)69 b(This)42 b(pro)s(cess)g(is)f(rep)s(eated)g(un)m(til)g(all)f(leaf)h(no) s(des)g(ha)m(v)m(e)h(cardinalit)m(y)f(zero)g(or)f(one.)1872 5280 y Fj(2)p eop %%Page: 3 3 3 2 bop 0 83 a Fr(The)38 b(tree)h(th)m(us)f(obtained)g(is)g(called)h (the)e(random)h(p)s(ebbled)h(hash)f(tree.)59 b(W)-8 b(e)38 b(will)g(sho)m(w)h(that)e(this)0 216 y(minor)42 b(mo)s(di\014cation)g (causes)h(a)e(ma)5 b(jor)41 b(impro)m(v)m(emen)m(t)k(in)c Fo(H)2350 231 y Fm(n)2397 216 y Fr(,)j(whic)m(h)f(is)f(with)g(high)g (probabilit)m(y)0 349 y(close)34 b(to)353 264 y Fk(p)p 452 264 676 4 v 452 349 a Fr(2)17 b(log)g Fo(n=)g Fr(log)h(log)f Fo(n)p Fr(.)299 548 y(Assuming)46 b(that)e(eac)m(h)i(buc)m(k)m(eting)h (op)s(eration)d(is)h(a)m(v)-5 b(ailable)45 b(at)g(unit)g(cost,)j(the)d (exp)s(ected)0 681 y(time)37 b(for)f(unsuccessful)k(and)d(for)f (successful)j(searc)m(h)f(\(assuming)f(all)g(p)s(oin)m(ts)g(are)g (equally)h(lik)m(ely)g(to)0 814 y(b)s(e)31 b(prob)s(ed)g(for\))e(is)i Fo(O)s Fr(\(1\))f(for)g(b)s(oth)g(random)h(hash)g(tree)g(and)f(random)h (p)s(ebbled)h(hash)f(tree,)h(but)e(the)0 946 y(exp)s(ected)36 b(w)m(orst-case)f(searc)m(h)g(time)g(for)e(the)h(latter)g(tree)h(is)f (m)m(uc)m(h)h(b)s(etter)g(than)f(for)f(classical)i(hash)0 1079 y(structures)29 b(in)e(view)i(of)d(the)i(b)s(eha)m(vior)g(of)f Fo(H)1627 1094 y Fm(n)1673 1079 y Fr(.)42 b(F)-8 b(or)26 b(example,)k(for)d(standard)g(hashing)h(with)g(c)m(haining)0 1212 y(under)35 b(the)f(ab)s(o)m(v)m(e)h(mo)s(del,)g Fo(M)1138 1227 y Fm(n)1216 1212 y Fl(\030)c Fr(log)17 b Fo(n=)g Fr(log)g(log)h Fo(n)34 b Fr(in)h(probabilit)m(y)g(\(Gonnet,)f (1981;)g(see)h(Devro)m(y)m(e,)0 1345 y(1985,)g(for)f(distributions)i (with)g(a)f(b)s(ounded)g(densit)m(y\),)j(where)e Fo(M)2473 1360 y Fm(n)2555 1345 y Fr(is)f(the)h(w)m(orst-case)g(searc)m(h)g(time) 0 1478 y(\(or,)c(equiv)-5 b(alen)m(tly)d(,)35 b(the)e(maximal)h(size)f (of)f(an)m(y)i(c)m(hain\).)299 1677 y(The)24 b(random)f(p)s(ebbled)i (hash)e(tree)h(is)g(also)f(sup)s(erior)h(to)f(random)g(binary)h(searc)m (h)g(trees,)j(where)0 1810 y(the)38 b(heigh)m(t)g(is)g(in)f(probabilit) m(y)i(of)e(the)g(order)h(of)f(log)17 b Fo(n)38 b Fr(\(under)g(a)f (simpler)i(computational)e(mo)s(del,)0 1943 y(ho)m(w)m(ev)m(er\).)54 b(It)36 b(also)f(compares)i(fa)m(v)m(orably)f(with)g(fusion)g(trees)g (\(F)-8 b(redman)36 b(and)f(Willard,)i(1990\))d(for)0 2076 y(standard)42 b(dictionary)g(op)s(erations.)70 b(Unfortunately)-8 b(,)44 b(hash)e(trees)g(are)g(not)f(appropriate)g(without)0 2208 y(mo)s(di\014cations)33 b(for)f(fully)i(dynamic)g(situations.)44 b(A)33 b(brief)f(section)i(is)f(dev)m(oted)h(to)f(this)g(issue.)299 2408 y(There)d(are)e(hash)i(structures)g(with)g(b)s(etter)f(exp)s (ected)h(w)m(orst-case)g(searc)m(h)g(and)f(insert)h(times.)0 2540 y(Azar,)40 b(Bro)s(der,)g(Karlin)e(and)g(Upfal)g(\(1994\))f(ha)m (v)m(e)j(sho)m(wn)f(that)f(the)h(w)m(orst)g(c)m(hain)g(length)g(in)f(m) m(ul-)0 2673 y(tihashing)47 b(with)h Fo(d)j(>)h Fr(1)46 b(hash)h(functions)h(and)f(insertion)h(in)m(to)f(the)g(shortest)h(c)m (hain)f(leads)h(to)e(a)0 2806 y(maxim)m(um)d(o)s(ccupancy)h(of)d(ab)s (out)g(log)1485 2830 y Fm(d)1542 2806 y Fr(log)18 b Fo(n)42 b Fr(with)g(high)g(probabilit)m(y)-8 b(.)72 b(This)43 b(leads)f(to)g(exp)s(ected)0 2939 y(w)m(orst-case)32 b(searc)m(h)h(times)f(ab)s(out)f Fo(d)17 b Fr(log)1493 2963 y Fm(d)1550 2939 y Fr(log)h Fo(n)p Fr(,)32 b(whic)m(h)g(are)f(m)m (uc)m(h)i(b)s(etter)f(than)f(with)h(random)f(p)s(eb-)0 3072 y(bled)42 b(hash)g(trees.)72 b(Ho)m(w)m(ev)m(er,)46 b(m)m(ultihashing)d(is)f(not)f(an)h(option)f(when)i(the)f(table)g(is)g (to)f(b)s(e)h(used)0 3205 y(for)37 b(sorting)h(and)f(order-preserving)i (hash)f(functions)h(are)f(called)g(for.)58 b(Also,)39 b(the)f(p)s(erformance)g(of)0 3337 y(m)m(ultihashing)j(is)e(easily)i (matc)m(hed)f(b)m(y)h(the)e(BBST)h(structure)h(\(buc)m(k)m(eting)g (follo)m(w)m(ed)f(b)m(y)g(a)f(binary)0 3470 y(searc)m(h)34 b(tree\))f(discussed)i(b)s(elo)m(w.)299 3670 y(F)-8 b(or)29 b(a)g(surv)m(ey)j(of)d(kno)m(wn)i(results)g(on)e(hashing)h(and)g (tries,)h(w)m(e)g(refer)f(to)f(Gonnet)g(and)h(Baeza-)0 3802 y(Y)-8 b(ates)39 b(\(1991\))f(and)h(Vitter)h(and)f(Fla)5 b(jolet)38 b(\(1990\).)62 b(Throughout)39 b(the)g(pap)s(er,)i Fo(B)5 b Fr(\()p Fo(n;)17 b(p)p Fr(\))39 b(denotes)h(a)0 3935 y(binomial)33 b(\()p Fo(n;)17 b(p)p Fr(\))32 b(random)h(v)-5 b(ariable.)1872 5280 y Fj(3)p eop %%Page: 4 4 4 3 bop 0 83 a Fs(2.)38 b(Surv)m(ey)g(of)f(kno)m(wn)h(results)f(on)g (N-trees)h(and)g(random)g(hash)g(trees.)299 344 y Fr(Assume)e(that)e (the)g Fo(X)1125 359 y Fm(i)1154 344 y Fr('s)g(are)g(uniformly)h (distributed)h(on)e([0)p Fo(;)17 b Fr(1].)48 b(Then)35 b(T)-8 b(amminen)36 b(\(1983\))0 477 y(sho)m(ws)e(the)f(follo)m(wing)g (for)f(N-trees:)150 676 y(A.)49 b(sup)446 699 y Fm(n)519 637 y Fi(E)p Fm(S)615 645 y Fh(n)p 519 653 139 4 v 567 710 a Fm(n)696 676 y Fl(\024)28 b Fr(2.)154 875 y(B.)49 b(1)p Fo(:)p Fr(64)27 b Fl(\024)h Fr(lim)17 b(inf)875 890 y Fm(n)949 836 y Fi(E)p Fm(S)1045 844 y Fh(n)p 949 852 V 997 909 a Fm(n)1125 875 y Fl(\024)28 b Fr(lim)17 b(sup)1529 899 y Fm(n)1603 836 y Fi(E)p Fm(S)1699 844 y Fh(n)p 1603 852 V 1651 909 a Fm(n)1779 875 y Fl(\024)28 b Fr(1)p Fo(:)p Fr(70.)153 1074 y(C.)49 b(Let)f Fo(A)562 1089 y Fm(i)638 1074 y Fr(b)s(e)g(the)g(depth)h(of)e Fo(X)1468 1089 y Fm(i)1544 1074 y Fr(in)i(the)f(N-tree)g(so)g(that)g (\(1)p Fo(=n)p Fr(\))2784 1000 y Fk(P)2888 1026 y Fm(n)2888 1103 y(i)p Fn(=1)3023 1074 y Fo(A)3096 1089 y Fm(i)3172 1074 y Fr(is)g(the)h(a)m(v)m(erage)299 1207 y(successful)35 b(searc)m(h)f(time.)44 b(Then)1648 1457 y Fs(E)1739 1287 y Fk(\()1833 1390 y Fr(1)p 1828 1434 59 4 v 1828 1525 a Fo(n)1964 1333 y Fm(n)1913 1362 y Fk(X)1928 1572 y Fm(i)p Fn(=1)2074 1457 y Fo(A)2147 1472 y Fm(i)2175 1287 y Fk(\))2283 1457 y Fl(\024)28 b Fr(2)299 1727 y(for)k(all)g Fo(n)p Fr(.)149 1926 y(D.)48 b(1)p Fo(:)p Fr(71)27 b Fl(\024)h Fr(lim)17 b(inf)875 1941 y Fm(n)939 1926 y Fs(E)1030 1846 y Fk(\010)1101 1887 y Fn(1)p 1097 1903 43 4 v 1097 1961 a Fm(n)1166 1852 y Fk(P)1272 1878 y Fm(n)1272 1955 y(i)p Fn(=1)1407 1926 y Fo(A)1480 1941 y Fm(i)1508 1846 y Fk(\011)1594 1926 y Fl(\024)28 b Fr(lim)17 b(sup)1998 1950 y Fm(n)2061 1926 y Fs(E)2152 1846 y Fk(\010)2223 1887 y Fn(1)p 2220 1903 V 2220 1961 a Fm(n)2289 1852 y Fk(P)2394 1878 y Fm(n)2394 1955 y(i)p Fn(=1)2529 1926 y Fo(A)2602 1941 y Fm(i)2630 1846 y Fk(\011)2716 1926 y Fl(\024)28 b Fr(1)p Fo(:)p Fr(80.)299 2126 y(If)42 b(the)g Fo(X)664 2141 y Fm(i)692 2126 y Fr('s)g(ha)m(v)m(e)h(a)e (densit)m(y)j Fo(f)52 b Fr(b)s(ounded)43 b(b)m(y)f Fl(k)p Fo(f)11 b Fl(k)2280 2141 y Fg(1)2354 2126 y Fr(,)44 b(then)f(for)e(the) h(random)g(hash)g(tree,)0 2258 y(T)-8 b(amminen)34 b(\(1983\))e (obtained)h(the)g(follo)m(wing)f(results:)150 2458 y(A.)49 b(sup)446 2481 y Fm(n)519 2418 y Fi(E)p Fm(S)615 2426 y Fh(n)p 519 2435 139 4 v 567 2492 a Fm(n)696 2458 y Fl(\024)28 b Fr(3)p Fl(k)p Fo(f)11 b Fl(k)1009 2473 y Fg(1)1083 2458 y Fr(.)154 2657 y(B.)49 b(lim)17 b(sup)598 2680 y Fm(n)671 2618 y Fi(E)p Fm(S)767 2626 y Fh(n)p 671 2634 V 719 2691 a Fm(n)848 2657 y Fl(\024)28 b Fr(4.)153 2856 y(C.)49 b(Let)39 b Fo(A)553 2871 y Fm(i)620 2856 y Fr(b)s(e)g(the)g(depth)g(of)g Fo(X)1414 2871 y Fm(i)1481 2856 y Fr(in)g(the)g(random)g(hash)g(tree)g(so)g(that)g(\(1)p Fo(=n)p Fr(\))3167 2781 y Fk(P)3271 2808 y Fm(n)3271 2885 y(i)p Fn(=1)3406 2856 y Fo(A)3479 2871 y Fm(i)3546 2856 y Fr(is)g(the)299 2989 y(a)m(v)m(erage)33 b(successful)j(searc)m (h)e(time.)44 b(Then)1460 3258 y(lim)17 b(sup)1588 3337 y Fm(n)1776 3258 y Fs(E)1867 3088 y Fk(\()1961 3191 y Fr(1)p 1956 3235 59 4 v 1956 3327 a Fo(n)2092 3134 y Fm(n)2041 3164 y Fk(X)2056 3374 y Fm(i)p Fn(=1)2202 3258 y Fo(A)2275 3273 y Fm(i)2303 3088 y Fk(\))2411 3258 y Fl(\024)28 b Fr(4)k Fo(:)299 3595 y Fr(Note)39 b(in)h(particular)f (that)g(the)h(asymptotic)h(b)s(ounds)f(in)f(parts)h(B)f(and)h(C)f(do)g (not)h(dep)s(end)0 3728 y(up)s(on)45 b(the)g(densit)m(y)-8 b(.)81 b(T)-8 b(amminen)46 b(\(1983\))e(also)g(o\013ers)h(heuristic)i (argumen)m(ts)e(for)f(densities)j(with)0 3860 y(un)m(b)s(ounded)30 b(supp)s(ort)f(and)f(so-called)h(h)m(ybrid)h(trees,)h(where)e(the)g (\014rst)g(lev)m(el)h(is)f(split)h(as)e(in)h(an)g(N-tree)0 3993 y(and)k(all)f(other)h(splits)h(are)e(as)h(in)g(a)f(random)h(hash)g (tree.)1872 5280 y Fj(4)p eop %%Page: 5 5 5 4 bop 0 83 a Fs(3.)38 b(The)f(heigh)m(t)g(of)h(the)f(random)h(hash)g (tree.)299 348 y Fr(In)e(this)h(section,)h(w)m(e)f(assume)h(that)d Fo(X)1758 363 y Fn(1)1798 348 y Fo(;)17 b(:)g(:)g(:)f(;)h(X)2098 363 y Fm(n)2180 348 y Fr(are)36 b(i.i.d.)h(and)f(ha)m(v)m(e)h(common)g (densit)m(y)h Fo(f)0 481 y Fr(on)32 b([0)p Fo(;)17 b Fr(1].)43 b(Let)33 b Fo(H)657 496 y Fm(n)736 481 y Fr(b)s(e)g(the)g (heigh)m(t)h(of)e(the)h(random)f(hash)i(tree.)44 b(W)-8 b(e)33 b(sho)m(w)g(the)g(follo)m(wing.)0 879 y Fp(Theorem)38 b(1.)55 b Ff(F)-8 b(or)32 b(an)m(y)h(increasing)f(sequence)j Fo(a)1898 894 y Fm(n)1977 879 y Ff(\(ho)m(w)m(ev)m(er)g(fast\),)e (there)g(exists)g(a)g(densit)m(y)g Fo(f)43 b Ff(for)0 1012 y(whic)m(h)33 b Fs(P)p Fl(f)p Fo(H)487 1027 y Fm(n)561 1012 y Fl(\025)28 b Fo(a)717 1027 y Fm(n)764 1012 y Fl(g)g(!)f Fr(1)32 b Ff(as)h Fo(n)28 b Fl(!)f(1)p Ff(.)0 1543 y Fp(Pr)n(oof.)56 b Fr(Let)43 b Fo(F)56 b Fr(b)s(e)43 b(the)h (distribution)g(function)f(for)g Fo(f)11 b Fr(,)45 b(supp)s(orted)f(on) f([0)p Fo(;)17 b Fr(1].)74 b(Let)43 b Fo(N)3425 1558 y Fn(1)3507 1543 y Fr(b)s(e)g(the)0 1675 y(n)m(um)m(b)s(er)34 b(of)e(p)s(oin)m(ts)h(in)g([0)p Fo(;)17 b Fr(1)p Fo(=n)p Fr(],)32 b Fo(N)1313 1690 y Fn(2)1385 1675 y Fr(the)h(n)m(um)m(b)s(er)h (of)e(p)s(oin)m(ts)h(in)g([0)p Fo(;)17 b Fr(1)p Fo(=n)2702 1639 y Fn(2)2741 1675 y Fr(])33 b(and)f(so)h(forth.)43 b(Clearly)-8 b(,)1391 1883 y([)p Fo(N)1496 1898 y Fm(a)1533 1906 y Fh(n)1608 1883 y Fl(\025)28 b Fr(2])g Fl(\022)g Fr([)p Fo(H)2030 1898 y Fm(n)2105 1883 y Fl(\025)g Fo(a)2261 1898 y Fm(n)2308 1883 y Fr(])33 b Fo(:)0 2090 y Fr(But,)g(putting)g Fo(p)27 b Fr(=)h(1)22 b Fl(\000)g Fo(F)14 b Fr(\(1)p Fo(=n)1189 2054 y Fm(a)1226 2062 y Fh(n)1273 2090 y Fr(\),)32 b(w)m(e)i(see)g(that)721 2297 y Fs(P)p Fl(f)p Fo(N)926 2312 y Fm(a)963 2320 y Fh(n)1037 2297 y Fo(<)27 b Fr(2)p Fl(g)h Fr(=)f Fo(p)1419 2256 y Fm(n)1488 2297 y Fr(+)22 b Fo(np)1693 2256 y Fm(n)p Fg(\000)p Fn(1)1858 2297 y Fl(\024)28 b Fr(\()p Fo(n)23 b Fr(+)f(1\))p Fo(e)2312 2256 y Fg(\000)p Fn(\()p Fm(n)p Fg(\000)p Fn(1\))p Fm(F)10 b Fn(\(1)p Fm(=n)2749 2233 y Fh(a)2783 2241 y(n)2830 2256 y Fn(\))2889 2297 y Fl(!)28 b Fr(0)0 2504 y(if)41 b Fo(nF)14 b Fr(\(1)p Fo(=n)427 2468 y Fm(a)464 2476 y Fh(n)511 2504 y Fr(\))p Fo(=)j Fr(log)g Fo(n)43 b Fl(!)g(1)p Fr(.)70 b(It)41 b(su\016ces)j(to)d(pic)m(k)i Fo(F)55 b Fr(suc)m(h)43 b(that)f Fo(F)14 b Fr(\(1)p Fo(=n)2835 2468 y Fm(a)2872 2476 y Fh(n)2918 2504 y Fr(\))43 b(=)g(1)p Fo(=)3216 2433 y Fl(p)p 3298 2433 59 4 v 3298 2504 a Fo(n)f Fr(for)f(all)g Fo(n)p Fr(.)0 2637 y(Then)36 b(let)f Fo(f)45 b Fr(b)s(e)35 b(a)f(histogram)h(with)g(breakp)s(oin)m(ts)h(at)f (1)p Fo(=n)2202 2601 y Fm(a)2239 2609 y Fh(n)2286 2637 y Fr(.)49 b(Conclude)36 b(that)f Fs(P)p Fl(f)p Fo(H)3214 2652 y Fm(n)3291 2637 y Fl(\025)d Fo(a)3451 2652 y Fm(n)3498 2637 y Fl(g)f(!)g Fr(0.)p 0 2716 65 4 v 0 2774 4 59 v 61 2774 V 0 2777 65 4 v 0 3168 a Fp(Theorem)38 b(2.)55 b Ff(When)33 b Fo(f)44 b Ff(is)32 b(the)h(uniform)d(distribution)h(on)i Fr([0)p Fo(;)17 b Fr(1])p Ff(,)32 b(w)m(e)h(ha)m(v)m(e)1404 3344 y Fo(H)1485 3359 y Fm(n)p 1348 3388 241 4 v 1348 3479 a Fr(log)1474 3503 y Fn(2)1530 3479 y Fo(n)1626 3411 y Fl(!)27 b Fr(1)32 b Fe(in)j(pr)-5 b(ob)g(ability)32 b Fo(:)1872 5280 y Fj(5)p eop %%Page: 6 6 6 5 bop 0 83 a Fp(Pr)n(oof.)56 b Fr(F)-8 b(or)31 b(a)h(lo)m(w)m(er)i(b) s(ound,)f(it)f(su\016ces)j(to)d(consider)i(a)e(subtree)i(of)e(the)h (random)f(p)s(ebbled)i(hash)0 216 y(tree.)75 b(T)-8 b(o)43 b(do)g(so,)j(w)m(e)e(consider)g(only)g(those)f(no)s(des)h(at)f(depth)g (one)h(that)e(con)m(tain)i(precisely)h(t)m(w)m(o)0 349 y(p)s(oin)m(ts.)f(Let)33 b Fo(L)g Fr(b)s(e)g(the)g(n)m(um)m(b)s(er)h (of)e(these)h(no)s(des.)45 b(Observ)m(e)34 b(that)0 589 y Fs(E)p Fl(f)p Fo(L)p Fl(g)27 b Fr(=)h(\()p Fo(n)16 b Fl(\000)g Fr(1\))p Fs(P)p Fl(f)p Fo(B)5 b Fr(\()p Fo(n)16 b Fl(\000)g Fr(1)p Fo(;)h Fr(1)p Fo(=)p Fr(\()p Fo(n)f Fl(\000)g Fr(1\)\))29 b(=)f(2)p Fl(g)f Fr(=)h(\()p Fo(n)16 b Fl(\000)g Fr(1\))2250 449 y Fk(\022)2324 522 y Fo(n)22 b Fl(\000)h Fr(1)2414 658 y(2)2553 449 y Fk(\023)2784 522 y Fr(1)p 2636 567 345 4 v 2636 658 a(\()p Fo(n)f Fl(\000)h Fr(1\))2941 629 y Fn(2)3007 449 y Fk(\022)3090 522 y Fo(n)f Fl(\000)h Fr(2)p 3090 567 229 4 v 3090 658 a Fo(n)f Fl(\000)h Fr(1)3329 449 y Fk(\023)3402 471 y Fm(n)p Fg(\000)p Fn(2)3567 589 y Fl(\030)3700 522 y Fo(n)p 3682 567 94 4 v 3682 658 a Fr(2)p Fo(e)0 814 y Fr(as)32 b Fo(n)c Fl(!)g(1)p Fr(.)42 b(F)-8 b(urthermore,)33 b(if)f(one)h(of)e (the)i(data)f(p)s(oin)m(ts)g(is)h(c)m(hanged,)h Fo(L)e Fr(c)m(hanges)i(b)m(y)f(at)e(most)i(t)m(w)m(o.)0 946 y(Th)m(us,)h(b)m(y)g(McDiarmid's)f(v)m(ersion)i(of)d(Azuma's)h (inequalit)m(y)i(\(McDiarmid,)e(1990\),)1021 1159 y Fs(P)p Fl(f)p Fo(L)28 b(<)f Fs(E)p Fl(f)p Fo(L)p Fl(g)p Fo(=)p Fr(2)p Fl(g)g(\024)h Fo(e)1910 1118 y Fg(\000)1975 1085 y Fd(E)2016 1064 y Fc(2)2049 1085 y Fb(f)p Fh(L)p Fb(g)p 1975 1103 181 3 v 2031 1144 a Fc(8)p Fh(n)2197 1159 y Fr(=)g Fo(e)2346 1102 y Fg(\000)2532 1075 y Fh(n)p 2411 1087 281 3 v 2411 1136 a Fc(32)p Fh(e)2500 1122 y Fc(2)2535 1136 y(+)p Fh(o)p Fc(\(1\))2738 1159 y Fo(:)0 1344 y Fr(Eac)m(h)33 b(of)e(the)i(subtrees)h(ro)s(oted)d(at)h(these)h(no)s (des)g(is)f(indep)s(enden)m(t)i(of)e(the)g(other)g(ones.)44 b(Both)32 b(p)s(oin)m(ts)0 1477 y(in)c(one)f(of)g(these)i(no)s(des)f (are)f(placed)h(in)g(the)g(same)g(subtree)h(with)f(probabilit)m(y)g(1)p Fo(=)p Fr(2.)41 b(Th)m(us,)30 b(a)d(subtree)0 1610 y(has)33 b(heigh)m(t)g(at)g(least)g Fo(k)25 b Fl(\000)e Fr(1)32 b(with)h(probabilit)m(y)h(1)p Fo(=)p Fr(2)1942 1573 y Fm(k)r Fg(\000)p Fn(1)2074 1610 y Fr(.)43 b(Therefore,)1031 1794 y Fs(P)p Fl(f)p Fo(H)1239 1809 y Fm(n)1312 1794 y Fl(\024)29 b Fo(k)s Fl(g)e(\024)h Fs(E)1745 1714 y Fk(\010)1803 1794 y Fr(\(1)21 b Fl(\000)i Fr(1)p Fo(=)p Fr(2)2158 1753 y Fm(k)r Fg(\000)p Fn(1)2290 1794 y Fr(\))2328 1753 y Fm(L)2380 1714 y Fk(\011)1549 1977 y Fl(\024)28 b Fs(E)1745 1866 y Fk(n)1811 1977 y Fo(e)1856 1930 y Fg(\000)1973 1903 y Fh(L)p 1921 1915 147 3 v 1921 1966 a Fc(2)1951 1952 y Fh(k)q Fb(\000)p Fc(1)2082 1866 y Fk(o)1549 2192 y Fl(\024)g Fo(e)1699 2145 y Fg(\000)1764 2112 y Fd(E)p Fb(f)p Fh(L)p Fb(g)p 1764 2130 146 3 v 1803 2182 a Fc(2)1833 2168 y Fh(k)1946 2192 y Fr(+)22 b Fs(P)p Fl(f)p Fo(L)28 b(<)f Fs(E)p Fl(f)p Fo(L)p Fl(g)p Fo(=)p Fr(2)p Fl(g)1549 2359 y(\024)h Fo(e)1699 2299 y Fg(\000)1911 2272 y Fh(n)p 1764 2284 332 3 v 1764 2335 a Fc(\(2)p Fh(e)p Fc(+)p Fh(o)p Fc(\(1\)\)2)2057 2321 y Fh(k)2132 2359 y Fr(+)22 b Fo(e)2275 2302 y Fg(\000)2461 2275 y Fh(n)p 2340 2287 281 3 v 2340 2335 a Fc(32)p Fh(e)2429 2321 y Fc(2)2465 2335 y(+)p Fh(o)p Fc(\(1\))1549 2516 y Fl(!)27 b Fr(0)33 b Fo(;)0 2701 y Fr(as)g Fo(n)28 b Fl(!)f(1)32 b Fr(if)h Fo(k)d Fr(=)e Fl(b)p Fr(\(1)22 b Fl(\000)h Fo(\017)p Fr(\))17 b(log)1213 2725 y Fn(2)1269 2701 y Fo(n)p Fl(c)33 b Fr(for)f Fo(\017)c Fl(2)g Fr(\(0)p Fo(;)17 b Fr(1\).)299 2901 y(F)-8 b(or)28 b(the)h(upp)s(er)h(b)s(ound,) f(let)h Fo(N)1450 2916 y Fn(1)1489 2901 y Fo(;)17 b(:)g(:)g(:)f(;)h(N) 1786 2916 y Fm(n)1861 2901 y Fr(b)s(e)30 b(the)f(cardinalities)h(of)e (the)i(c)m(hildren)g(of)e(the)i(ro)s(ot)0 3033 y(\(so)36 b(that)375 2959 y Fk(P)481 3062 y Fm(i)525 3033 y Fo(N)603 3048 y Fm(i)665 3033 y Fr(=)d Fo(n)j Fr(unless)h Fo(n)c Fr(=)g(1\).)53 b(If)36 b Fo(X)1708 3048 y Fm(i)1772 3033 y Fr(and)f Fo(X)2045 3048 y Fm(j)2118 3033 y Fr(\014nd)h(themselv)m(es) j(in)d(the)g(same)h(c)m(hild)g(no)s(de)0 3166 y(of)31 b(the)h(ro)s(ot,)f(then)h(they)h(will)f(sta)m(y)h(together)e(at)h (depth)g(2)f(with)h(probabilit)m(y)h(1)p Fo(=)p Fr(2,)e(at)g(depth)i(3) e(with)0 3299 y(probabilit)m(y)j(1)p Fo(=)p Fr(2)646 3263 y Fn(2)685 3299 y Fr(,)f(and)g(at)g(depth)h Fo(k)i Fr(with)e(probabilit)m(y)g(1)p Fo(=)p Fr(2)2288 3263 y Fm(k)r Fg(\000)p Fn(1)2420 3299 y Fr(.)45 b(Let)33 b Fo(A)2740 3314 y Fm(m;k)2898 3299 y Fr(b)s(e)g(the)h(ev)m(en)m(t)g (that)f(for)0 3432 y(the)h Fo(m)p Fr(-th)f(c)m(hild)h(of)f(the)h(ro)s (ot,)f(one)g(of)g(the)h(pairs)f(of)g(p)s(oin)m(ts)h(in)g(the)f(no)s(de) h(sta)m(ys)g(together)g(to)f(depth)0 3565 y Fo(k)s Fr(.)44 b(Clearly)-8 b(,)1283 3750 y Fs(P)p Fl(f)p Fo(H)1491 3765 y Fm(n)1565 3750 y Fo(>)28 b(k)s Fl(g)f(\024)h Fs(P)p Fl(f[)2098 3708 y Fm(n)2098 3774 y(m)p Fn(=1)2255 3750 y Fo(A)2328 3765 y Fm(m;k)2453 3750 y Fl(g)1800 3907 y(\024)g Fo(n)p Fs(P)p Fl(f)p Fo(A)2163 3922 y Fn(1)p Fm(;k)2261 3907 y Fl(g)1800 4143 y(\024)g Fo(n)p Fs(E)2054 3972 y Fk(\()2144 3988 y(\000)2190 4025 y Fm(N)2246 4034 y Fc(1)2217 4103 y Fn(2)2280 3988 y Fk(\001)p 2144 4120 182 4 v 2144 4211 a Fr(2)2193 4182 y Fm(k)r Fg(\000)p Fn(1)2336 3972 y Fk(\))1800 4432 y Fr(=)1914 4365 y Fo(n)22 b Fl(\000)h Fr(1)p 1914 4409 229 4 v 1982 4500 a(2)2031 4472 y Fm(k)0 4636 y Fr(as)33 b Fo(N)198 4651 y Fn(1)270 4636 y Fr(is)g(binomial)g(\()p Fo(n;)17 b Fr(1)p Fo(=n)p Fr(\).)43 b(Therefore,)34 b(for)e Fo(\017)c(>)f Fr(0,)1160 4820 y(lim)1136 4880 y Fm(n)p Fg(!1)1337 4820 y Fs(P)p Fl(f)p Fo(H)1545 4835 y Fm(n)1618 4820 y Fo(>)h Fr(\(1)22 b(+)g Fo(\017)p Fr(\))17 b(log)2149 4844 y Fn(2)2205 4820 y Fo(n)p Fl(g)28 b Fr(=)f(0)32 b Fo(:)p 2585 4767 65 4 v 2585 4825 4 59 v 2646 4825 V 2585 4828 65 4 v 1872 5280 a Fj(6)p eop %%Page: 7 7 7 6 bop 0 83 a Fs(4.)38 b(The)f(heigh)m(t)g(of)h(the)f(random)h(p)s (ebbled)f(hash)i(tree.)299 332 y Fr(In)d(this)h(section,)h(w)m(e)f (assume)h(that)d Fo(X)1758 347 y Fn(1)1798 332 y Fo(;)17 b(:)g(:)g(:)f(;)h(X)2098 347 y Fm(n)2180 332 y Fr(are)36 b(i.i.d.)h(and)f(ha)m(v)m(e)h(common)g(densit)m(y)h Fo(f)0 465 y Fr(on)f([0)p Fo(;)17 b Fr(1].)58 b(Let)38 b Fo(H)682 480 y Fm(n)766 465 y Fr(b)s(e)g(the)g(heigh)m(t)h(of)e(the)h(random)f (p)s(ebbled)i(hash)f(tree.)60 b(Clearly)-8 b(,)39 b Fo(H)3326 480 y Fm(n)3409 465 y Fl(\024)e Fo(n)26 b Fl(\000)g Fr(1.)0 598 y(In)37 b(a)g(random)f(p)s(ebbled)i(hash)g(tree)f(w)m(e)h(in)m (terc)m(hangeably)h(sp)s(eak)e(of)g(no)s(des,)h(in)m(terv)-5 b(als)38 b(\(eac)m(h)g(no)s(de)0 731 y(represen)m(ts)32 b(an)e(in)m(terv)-5 b(al\),)31 b(and)e(cardinalit)m(y)i(\(the)f(n)m(um) m(b)s(er)h(of)e Fo(X)2419 746 y Fm(i)2447 731 y Fr('s)i(that)e(fall)g (in)h(a)g(no)s(de's)g(in)m(terv)-5 b(al\).)0 864 y(W)d(e)33 b(sho)m(w)h(the)f(follo)m(wing.)0 1229 y Fp(Theorem)43 b(3.)55 b Ff(Consider)37 b(a)g(random)f(p)s(ebbled)i(hash)g(tree.)57 b(F)-8 b(or)37 b(an)m(y)g(monotonically)d(decreasing)0 1362 y(sequence)j Fo(a)457 1377 y Fm(n)534 1362 y Fl(#)30 b Fr(0)k Ff(\(ho)m(w)m(ev)m(er)i(slo)m(w\),)f(there)f(exists)h(a)f (densit)m(y)h Fo(f)45 b Ff(for)33 b(whic)m(h)i Fs(P)p Fl(f)p Fo(H)3066 1377 y Fm(n)3142 1362 y Fl(\025)c Fo(na)3359 1377 y Fm(n)3406 1362 y Fl(g)f(!)g Fr(1)k Ff(as)0 1495 y Fo(n)28 b Fl(!)f(1)p Ff(.)299 1794 y Fr(Theorem)45 b(3)e(sho)m(ws)i(that)f(no)f(go)s(o)s(d)g(univ)m(ersal)i(results)g(are) f(p)s(ossible)h(for)e Fo(H)3261 1809 y Fm(n)3351 1794 y Fr(unless)i(the)0 1927 y(densit)m(y)33 b(of)e(the)h Fo(X)693 1942 y Fm(i)721 1927 y Fr('s)g(is)f(suitably)i(restricted.)44 b(As)32 b(w)m(e)h(ma)m(y)f(often)f(assume)i(that)e(the)g(hash)h (function)0 2060 y(is)49 b(v)m(ery)h(go)s(o)s(d,)i(w)m(e)e(will)f (assume)h(that)f(the)g Fo(X)1836 2075 y Fm(i)1864 2060 y Fr('s)g(are)g(uniformly)g(distributed)i(on)d([0)p Fo(;)17 b Fr(1].)91 b(It)49 b(is)0 2193 y(w)m(orth)m(while)35 b(to)d(note)h(that)f(Theorem)i(3)e(remains)i(v)-5 b(alid)33 b(for)f(the)h(N-tree)f(as)h(w)m(ell.)0 2558 y Fp(Pr)n(oof.)56 b Fr(W)-8 b(e)33 b(tak)m(e)h(a)f(densit)m(y)i Fo(f)44 b Fr(that)32 b(decreases)k(monotonically)e(on)f([0)p Fo(;)17 b Fr(1])32 b(and)h(has)h(distribution)0 2691 y(function)e Fo(F)14 b Fr(.)43 b(Remo)m(v)m(e)33 b(one)g(data)e(p)s (oin)m(t.)43 b(Let)32 b Fo(N)1838 2706 y Fn(1)1910 2691 y Fr(b)s(e)f(the)i(n)m(um)m(b)s(er)g(of)e(p)s(oin)m(ts)i(in)f([0)p Fo(;)17 b Fr(1)p Fo(=n)p Fr(].)42 b(Remo)m(v)m(e)0 2824 y(one)d(p)s(oin)m(t)h(again,)g(and)f(let)g Fo(N)1163 2839 y Fn(2)1242 2824 y Fr(b)s(e)g(the)h(n)m(um)m(b)s(er)g(of)f(p)s (oin)m(ts)h(in)f([0)p Fo(;)17 b Fr(1)p Fo(=n)2731 2788 y Fn(2)2770 2824 y Fr(])39 b(and)g(so)g(forth.)63 b(Assume)0 2957 y(without)30 b(loss)f(of)g(generalit)m(y)h(that)f Fo(na)1412 2972 y Fm(n)1488 2957 y Fr(is)h(in)m(teger-v)-5 b(alued)30 b(and)f(strictly)h(increasing)g(to)f Fl(1)p Fr(.)42 b(Clearly)-8 b(,)1341 3140 y([)p Fo(N)1446 3155 y Fm(na)1526 3163 y Fh(n)1600 3140 y Fl(\025)29 b Fr(2])e Fl(\022)h Fr([)p Fo(H)2022 3155 y Fm(n)2097 3140 y Fl(\025)g Fo(na)2311 3155 y Fm(n)2358 3140 y Fr(])33 b Fo(:)0 3323 y Fr(But)j Fo(N)275 3338 y Fm(k)353 3323 y Fr(is)g(binomial)f(\()p Fo(N)973 3338 y Fm(k)r Fg(\000)p Fn(1)1130 3323 y Fl(\000)25 b Fr(1)p Fo(;)17 b(F)d Fr(\(1)p Fo(=n)1596 3286 y Fm(k)1637 3323 y Fr(\))p Fo(=F)g Fr(\(1)p Fo(=n)1995 3286 y Fm(k)r Fg(\000)p Fn(1)2127 3323 y Fr(\)\),)36 b(whic)m(h)h(is)f(sto)s(c)m (hastically)h(greater)f(than)0 3455 y(a)49 b(binomial)g(\()p Fo(N)631 3470 y Fm(k)r Fg(\000)p Fn(1)764 3455 y Fo(;)17 b(F)d Fr(\(1)p Fo(=n)1079 3419 y Fm(k)1121 3455 y Fr(\))p Fo(=F)g Fr(\(1)p Fo(=n)1479 3419 y Fm(k)r Fg(\000)p Fn(1)1611 3455 y Fr(\)\))49 b(random)g(v)-5 b(ariable)50 b(min)m(us)g(one.)94 b(Therefore,)54 b Fo(N)3628 3470 y Fm(k)3720 3455 y Fr(is)0 3588 y(sto)s(c)m(hastically)31 b(greater)e(than)h(a)f(binomial)h(\()p Fo(n;)17 b(F)d Fr(\(1)p Fo(=n)2041 3552 y Fm(k)2083 3588 y Fr(\)\))29 b(random)g(v)-5 b(ariable)30 b(min)m(us)h Fo(k)s Fr(.)42 b(Th)m(us,)32 b(for)d Fo(n)0 3721 y Fr(large)j(enough,)i (setting)f Fo(p)27 b Fr(=)h Fo(F)14 b Fr(\(1)p Fo(=n)1373 3685 y Fm(na)1453 3693 y Fh(n)1499 3721 y Fr(\))28 b(=)1669 3636 y Fk(p)p 1768 3636 375 4 v 1768 3721 a Fo(a)1819 3736 y Fm(n)1888 3721 y Fr(+)22 b(1)p Fo(=n)p Fr(,)33 b(w)m(e)g(ha)m(v)m(e,)i(b)m(y)e(Cheb)m(yshev's)k(inequalit)m(y)-8 b(,)1076 3904 y Fs(P)p Fl(f)p Fo(N)1281 3919 y Fm(na)1361 3927 y Fh(n)1435 3904 y Fo(<)27 b Fr(2)p Fl(g)h(\024)g Fs(P)p Fl(f)p Fo(B)5 b Fr(\()p Fo(n;)17 b(p)p Fr(\))27 b Fl(\024)h Fo(na)2444 3919 y Fm(n)2513 3904 y Fr(+)22 b(1)p Fl(g)1665 4062 y Fr(=)27 b Fs(P)p Fl(f)p Fo(B)5 b Fr(\()p Fo(n;)17 b(p)p Fr(\))27 b Fl(\024)h Fo(np)2440 4021 y Fn(2)2480 4062 y Fl(g)1665 4262 y(\024)1837 4195 y Fo(np)p Fr(\(1)22 b Fl(\000)h Fo(p)p Fr(\))p 1780 4239 518 4 v 1780 4330 a(\()p Fo(np)p Fr(\(1)f Fl(\000)g Fo(p)p Fr(\)\))2258 4302 y Fn(2)1665 4520 y Fl(\030)2021 4453 y Fr(1)p 1780 4497 532 4 v 1780 4602 a Fo(n)1838 4517 y Fk(p)p 1938 4517 375 4 v 85 x Fo(a)1989 4617 y Fm(n)2058 4602 y Fr(+)g(1)p Fo(=n)1665 4730 y Fl(!)27 b Fr(0)32 b Fo(:)0 4913 y Fr(No)m(w,)d(tak)m(e)f(for)e Fo(f)38 b Fr(a)27 b(histogram)g(whose)i(distribution)f(function)g(satis\014es)h Fo(F)14 b Fr(\(1)p Fo(=n)3017 4877 y Fm(na)3097 4885 y Fh(n)3143 4913 y Fr(\))28 b(=)3312 4828 y Fk(p)p 3412 4828 V 85 x Fo(a)3463 4928 y Fm(n)3532 4913 y Fr(+)22 b(1)p Fo(=n)0 5046 y Fr(for)32 b(all)h Fo(n)f Fr(large)h(enough.)p 988 4992 65 4 v 988 5050 4 59 v 1049 5050 V 988 5053 65 4 v 1872 5280 a Fj(7)p eop %%Page: 8 8 8 7 bop 0 83 a Fp(Theorem)38 b(4.)55 b Ff(When)33 b Fo(f)44 b Ff(is)32 b(the)h(uniform)d(distribution)h(on)i Fr([0)p Fo(;)17 b Fr(1])p Ff(,)32 b(w)m(e)h(ha)m(v)m(e)1404 259 y Fo(H)1485 274 y Fm(n)p 1284 303 369 4 v 1284 323 a Fk(q)p 1383 323 269 4 v 1421 391 a Fn(2)12 b(log)h Fm(n)p 1393 412 249 4 v 1393 469 a Fn(log)g(log)g Fm(n)1690 326 y Fl(!)27 b Fr(1)32 b Fe(in)j(pr)-5 b(ob)g(ability)32 b Fo(:)0 915 y Fs(5.)38 b(Pro)s(of)f(of)g(Theorem)g(4.)0 1380 y Fp(Lemma)h(1.)55 b Ff(F)-8 b(or)32 b Fo(t)c(>)f Fr(0)33 b Ff(and)f Fo(t)c Fl(\025)g Fo(c)p Ff(,)1118 1587 y Fs(P)p Fl(f)p Fo(B)5 b Fr(\()p Fo(n;)17 b(c=n)p Fr(\))27 b Fl(\025)i Fo(t)p Fl(g)e(\024)h Fo(e)2046 1546 y Fm(t)p Fg(\000)p Fm(c)p Fg(\000)p Fm(t)13 b Fn(log)g Fm(t)p Fn(+)p Fm(t)f Fn(log)h Fm(c)2640 1587 y Fo(:)0 2059 y Fp(Pr)n(oof.)56 b Fr(W)-8 b(e)33 b(write)g Fo(B)g Fr(=)27 b Fo(B)5 b Fr(\()p Fo(n;)17 b(c=n)p Fr(\).)44 b(By)33 b(Cherno\013)7 b('s)33 b(b)s(ounding)g(metho)s(d,)g(for)f Fo(\025)c(>)g Fr(0,)1131 2267 y Fs(P)p Fl(f)p Fo(B)k Fl(\025)c Fo(t)p Fl(g)g(\024)g Fs(E)1778 2186 y Fk(\010)1835 2267 y Fo(e)1880 2225 y Fm(\025B)s Fg(\000)p Fm(\025t)2104 2186 y Fk(\011)1582 2452 y Fr(=)1685 2341 y Fk(\020)1745 2452 y Fr(1)22 b(+)1914 2371 y Fk(\000)1960 2452 y Fo(e)2005 2410 y Fm(\025)2072 2452 y Fl(\000)h Fr(1)2221 2371 y Fk(\001)2301 2384 y Fo(c)p 2293 2429 59 4 v 2293 2520 a(n)2361 2341 y Fk(\021)2421 2363 y Fm(n)2484 2452 y Fo(e)2529 2410 y Fg(\000)p Fm(\025t)1582 2663 y Fl(\024)28 b Fo(e)1732 2619 y Fm(c)1763 2627 y Fr(\()1801 2619 y Fm(e)1834 2596 y Fh(\025)1874 2619 y Fg(\000)p Fn(1)1964 2627 y Fr(\))2002 2619 y Fg(\000)p Fm(\025t)2161 2663 y Fo(:)0 2871 y Fr(The)34 b(upp)s(er)f(b)s(ound)f(is)h(minimized)i (when)f Fo(e)1650 2834 y Fm(\025)1723 2871 y Fr(=)27 b Fo(t=c)p Fr(.)44 b(This)34 b(yields)g(the)f(desired)h(inequalit)m(y) -8 b(.)p 3501 2817 65 4 v 3501 2875 4 59 v 3563 2875 V 3501 2878 65 4 v 0 3269 a Fp(Lemma)38 b(2.)55 b Ff(If)33 b Fo(B)k Ff(is)32 b(a)h(binomial)c Fr(\()p Fo(n;)17 b(c=n)p Fr(\))32 b Ff(random)g(v)-5 b(ariable)31 b(and)h Fo(t)c(>)g Fr(0)p Ff(,)k(then,)h(for)f Fo(t)c Fl(\025)g Fo(c)p Ff(,)1246 3476 y Fs(E)17 b Fl(f)o Fo(B)5 b(I)1508 3491 y Fm(B)s Fg(\025)p Fm(t)1649 3476 y Fl(g)28 b(\024)g Fo(ce)1919 3435 y Fm(t)p Fg(\000)p Fm(c)p Fg(\000)p Fm(t)12 b Fn(log)h Fm(t)p Fn(+)p Fm(t)g Fn(log)f Fm(c)2513 3476 y Fo(:)1872 5280 y Fj(8)p eop %%Page: 9 9 9 8 bop 0 83 a Fp(Pr)n(oof.)56 b Fr(By)33 b(simple)h(b)s(ounding,)f(w)m (e)g(ha)m(v)m(e)h(for)e Fo(\025)c(>)f Fr(0,)1276 268 y Fs(E)17 b Fl(f)o Fo(B)5 b(I)1538 283 y Fm(B)s Fg(\025)p Fm(t)1679 268 y Fl(g)27 b(\024)h Fs(E)1952 187 y Fk(\010)2010 268 y Fo(B)5 b(e)2134 227 y Fm(\025B)s Fg(\000)p Fm(\025t)2357 187 y Fk(\011)1756 451 y Fr(=)28 b Fo(n)p Fs(E)2009 340 y Fk(n)2093 383 y Fo(c)p 2085 428 59 4 v 2085 519 a(n)2153 451 y(e)2198 409 y Fm(\025B)2295 386 y Fb(0)2318 409 y Fg(\000)p Fm(\025t)2444 340 y Fk(o)1756 667 y Fr(=)g Fo(c)p Fs(E)1993 556 y Fk(n)2058 667 y Fo(e)2103 626 y Fm(\025B)2200 602 y Fb(0)2224 626 y Fg(\000)p Fm(\025t)2349 556 y Fk(o)0 866 y Fr(where)36 b Fo(B)363 830 y Fg(0)421 866 y Fr(is)f(binomial)g(\()p Fo(n)24 b Fl(\000)g Fr(1)p Fo(;)17 b(c=n)p Fr(\).)49 b(Here)35 b(w)m(e)h(made)f(use)h(of)e(the)h (linearit)m(y)h(of)e(exp)s(ectation.)51 b(By)0 999 y(the)33 b(Cherno\013)g(b)s(ound)g(used)h(in)f(Lemma)g(1,)f(w)m(e)i(ha)m(v)m(e) 942 1210 y Fs(E)17 b Fl(f)o Fo(B)5 b(I)1204 1225 y Fm(B)s Fg(\025)p Fm(t)1345 1210 y Fl(g)27 b(\024)i Fo(c)1587 1100 y Fk(\020)1646 1210 y Fr(1)22 b(+)1815 1129 y Fk(\000)1860 1210 y Fo(e)1905 1169 y Fm(\025)1973 1210 y Fl(\000)h Fr(1)2122 1129 y Fk(\001)2202 1143 y Fo(c)p 2194 1187 V 2194 1278 a(n)2262 1100 y Fk(\021)2321 1122 y Fm(n)p Fg(\000)p Fn(1)2475 1210 y Fo(e)2520 1169 y Fg(\000)p Fm(\025t)1422 1473 y Fl(\024)29 b Fo(c)1587 1332 y Fk(\022)1659 1473 y Fr(1)22 b(+)1828 1392 y Fk(\000)1874 1473 y Fo(e)1919 1432 y Fm(\025)1987 1473 y Fl(\000)g Fr(1)2135 1392 y Fk(\001)2301 1405 y Fo(c)p 2207 1450 229 4 v 2207 1541 a(n)h Fl(\000)f Fr(1)2446 1332 y Fk(\023)2519 1354 y Fm(n)p Fg(\000)p Fn(1)2673 1473 y Fo(e)2718 1432 y Fg(\000)p Fm(\025t)1422 1711 y Fl(\024)29 b Fo(ce)1615 1667 y Fm(c)1646 1675 y Fr(\()1683 1667 y Fm(e)1716 1643 y Fh(\025)1757 1667 y Fg(\000)p Fn(1)1847 1675 y Fr(\))1885 1667 y Fg(\000)p Fm(\025t)2043 1711 y Fo(:)0 1896 y Fr(The)34 b(upp)s(er)f(b)s(ound)f (is)h(minimized)i(when)f Fo(e)1650 1860 y Fm(\025)1723 1896 y Fr(=)27 b Fo(t=c)p Fr(.)p 2023 1842 65 4 v 2023 1900 4 59 v 2084 1900 V 2023 1903 65 4 v 299 2095 a(W)-8 b(e)27 b(are)g(no)m(w)h(ready)f(to)g(pro)m(v)m(e)h(Theorem)g(4.)41 b(F)-8 b(or)27 b(the)g(upp)s(er)g(b)s(ound,)i(tak)m(e)e Fo(\017)h(>)g Fr(0)f(and)g(de\014ne)0 2242 y Fo(k)43 b Fr(=)210 2132 y Fk(l)262 2242 y Fr(\(1)22 b(+)g Fo(\017)p Fr(\))546 2131 y Fk(q)p 646 2131 269 4 v 684 2198 a Fn(2)12 b(log)h Fm(n)p 656 2219 249 4 v 656 2276 a Fn(log)g(log)g Fm(n)915 2132 y Fk(m)967 2242 y Fr(.)65 b(The)41 b(tree)f(is)g(pruned)h (b)m(y)f(omitting)g(the)g(ro)s(ot)f(no)s(de)h(if)f(its)i(cardinalit)m (y)0 2384 y(is)f(less)h(than)f Fo(k)s Fr(,)i(all)e(no)s(des)g(at)f (depth)i(1)e(with)i(cardinalit)m(y)g(less)g(than)f Fo(k)30 b Fl(\000)d Fr(1,)42 b(and)e(in)g(general)g(all)0 2517 y(no)s(des)g(at)g(depth)h Fo(d)e Fr(of)g(cardinalit)m(y)i(less)g(than)f Fo(k)30 b Fl(\000)e Fo(d)p Fr(.)65 b(W)-8 b(e)40 b(call)g(this)h(tree)f (the)g(pruned)h(tree.)66 b(T)-8 b(o)0 2650 y(compute)37 b Fs(P)p Fl(f)p Fo(H)607 2665 y Fm(n)686 2650 y Fl(\025)c Fo(k)s Fl(g)p Fr(,)k(the)f(pruned)g(tree)g(and)g(the)g(random)g(p)s (ebbled)h(hash)f(tree)g(are)g(equiv)-5 b(alen)m(t)0 2783 y(as)35 b(all)g(deleted)i(no)s(des)f(are)f(ro)s(ots)f(of)h(subtrees)i (that)e(cannot)g(reac)m(h)h(past)g(depth)g Fo(k)s Fr(.)51 b(The)36 b(exp)s(ected)0 2916 y(n)m(um)m(b)s(er)e(of)e(no)s(des)h(in)g (the)g(pruned)h(tree)f(at)f(depth)h(one)g(is)0 3160 y(\()p Fo(n)9 b Fl(\000)g Fr(1\))p Fs(P)p Fl(f)p Fo(B)c Fr(\()p Fo(n)k Fl(\000)g Fr(1)p Fo(;)17 b Fr(1)p Fo(=)p Fr(\()p Fo(n)9 b Fl(\000)g Fr(1\)\))29 b Fl(\025)f Fo(k)13 b Fl(\000)c Fr(1)p Fl(g)27 b(\024)h Fr(\()p Fo(n)9 b Fl(\000)g Fr(1\))p Fo(e)2020 3119 y Fm(k)r Fg(\000)p Fn(1)p Fg(\000)p Fn(1)p Fg(\000)p Fn(\()p Fm(k)r Fg(\000)p Fn(1\))k(log)q(\()p Fm(k)r Fg(\000)p Fn(1\))2797 3160 y Fr(=)2910 3092 y Fo(n)23 b Fl(\000)f Fr(1)p 2910 3137 229 4 v 3002 3228 a Fo(e)3192 3019 y Fk(\022)3365 3092 y Fo(e)p 3275 3137 225 4 v 3275 3228 a(k)j Fl(\000)e Fr(1)3510 3019 y Fk(\023)3583 3042 y Fm(k)r Fg(\000)p Fn(1)3759 3160 y Fo(:)0 3384 y Fr(where)41 b(w)m(e)g(used)f(Lemma)h(1.)64 b(Let)40 b(the)g Fo(L)g Fr(no)s(des)h(at)e(depth)h(one)g(ha)m(v)m(e)h (cardinalities)g Fo(N)3370 3399 y Fn(1)3410 3384 y Fo(;)17 b(:)g(:)g(:)f(;)h(N)3707 3399 y Fm(L)3759 3384 y Fr(.)0 3517 y(Giv)m(en)33 b Fo(N)360 3532 y Fn(1)400 3517 y Fr(,)g(the)g(\014rst)g(no)s(de)f(spa)m(wns)j(an)d(exp)s(ected)j(n)m(um) m(b)s(er)f(of)e(no)s(des)h(at)f(depth)i(t)m(w)m(o)f(equal)g(to)0 3761 y(\()p Fo(N)116 3776 y Fn(1)155 3761 y Fl(\000)p Fr(1\))p Fs(P)p Fl(f)p Fo(B)5 b Fr(\()p Fo(N)641 3776 y Fn(1)681 3761 y Fl(\000)p Fr(1)p Fo(;)17 b Fr(1)p Fo(=)p Fr(\()p Fo(N)1065 3776 y Fn(1)1104 3761 y Fl(\000)p Fr(1\)\))27 b Fl(\025)i Fo(k)s Fl(\000)p Fr(2)p Fl(g)e(\024)i Fr(\()p Fo(N)1918 3776 y Fn(1)1957 3761 y Fl(\000)p Fr(1\))p Fo(e)2166 3720 y Fm(k)r Fg(\000)p Fn(2)p Fg(\000)p Fn(1)p Fg(\000)p Fn(\()p Fm(k)r Fg(\000)p Fn(2\))13 b(log)q(\()p Fm(k)r Fg(\000)p Fn(2\))2942 3761 y Fr(=)3056 3693 y Fo(N)3134 3708 y Fn(1)3195 3693 y Fl(\000)23 b Fr(1)p 3056 3738 289 4 v 3177 3829 a Fo(e)3392 3620 y Fk(\022)3565 3693 y Fo(e)p 3475 3738 225 4 v 3475 3829 a(k)j Fl(\000)c Fr(2)3710 3620 y Fk(\023)3783 3643 y Fm(k)r Fg(\000)p Fn(2)3954 3761 y Fo(:)0 3985 y Fr(Giv)m(en)43 b(all)f(the)g (cardinalities,)j(w)m(e)e(th)m(us)g(ha)m(v)m(e)g(an)f(exp)s(ected)i(n)m (um)m(b)s(er)f(of)f(no)s(des)g(at)g(depth)g(2)g(not)0 4118 y(exceeding)1280 4169 y Fk(P)1385 4196 y Fm(L)1385 4273 y(i)p Fn(=1)1504 4244 y Fr(\()p Fo(N)1620 4259 y Fm(i)1670 4244 y Fl(\000)23 b Fr(1\))p 1280 4289 577 4 v 1546 4380 a Fo(e)1915 4171 y Fk(\022)2088 4245 y Fo(e)p 1999 4289 225 4 v 1999 4380 a(k)i Fl(\000)e Fr(2)2233 4171 y Fk(\023)2307 4194 y Fm(k)r Fg(\000)p Fn(2)2489 4312 y Fo(:)0 4518 y Fr(But)617 4709 y Fs(E)708 4538 y Fk(\()836 4584 y Fm(L)788 4614 y Fk(X)803 4824 y Fm(i)p Fn(=1)948 4709 y Fo(N)1026 4724 y Fm(i)1055 4538 y Fk(\))1162 4709 y Fr(=)28 b Fs(E)1357 4538 y Fk(\()1442 4584 y Fm(n)p Fg(\000)p Fn(1)1436 4614 y Fk(X)1451 4824 y Fm(i)p Fn(=1)1597 4709 y Fo(M)1691 4724 y Fm(i)1720 4709 y Fo(I)1763 4724 y Fm(M)1831 4734 y Fh(i)1857 4724 y Fg(\025)p Fm(k)r Fg(\000)p Fn(1)2044 4538 y Fk(\))2152 4709 y Fl(\024)g Fo(ne)2360 4668 y Fm(k)r Fg(\000)p Fn(1)p Fg(\000)p Fn(1)p Fg(\000)p Fn(\()p Fm(k)r Fg(\000)p Fn(1\))13 b(log)q(\()p Fm(k)r Fg(\000)p Fn(1\))3141 4709 y Fo(;)0 4947 y Fr(where)31 b Fo(M)373 4962 y Fn(1)413 4947 y Fo(;)17 b(:)g(:)g(:)f(;)h(M)726 4962 y Fm(n)p Fg(\000)p Fn(1)892 4947 y Fr(are)30 b(the)g (cardinalities)h(of)f(the)g Fo(n)16 b Fl(\000)g Fr(1)30 b(in)m(terv)-5 b(als)31 b(in)f(the)g(\014rst)h(partition.)42 b(Here)0 5080 y(w)m(e)f(used)g(Lemma)g(2)e(with)i Fo(c)f Fr(=)g(1.)65 b(Therefore,)43 b(the)e(exp)s(ected)g(n)m(um)m(b)s(er)h (of)d(no)s(des)i(at)e(depth)i(t)m(w)m(o)1872 5280 y Fj(9)p eop %%Page: 10 10 10 9 bop 0 83 a Fr(do)s(es)33 b(not)f(exceed)1236 194 y Fo(n)p 1223 238 85 4 v 1223 330 a(e)1268 301 y Fn(2)1367 121 y Fk(\022)1540 194 y Fo(e)p 1450 238 225 4 v 1450 330 a(k)25 b Fl(\000)e Fr(1)1685 121 y Fk(\023)1758 143 y Fm(k)r Fg(\000)p Fn(1)1972 121 y Fk(\022)2145 194 y Fo(e)p 2056 238 V 2056 330 a(k)i Fl(\000)e Fr(2)2290 121 y Fk(\023)2364 143 y Fm(k)r Fg(\000)p Fn(2)2546 261 y Fo(:)0 472 y Fr(By)33 b(induction,)h(the)f(exp)s(ected)h(n)m(um)m(b)s (er)g(of)e(no)s(des)h(at)g(depth)g Fo(k)25 b Fl(\000)e Fr(1)32 b(do)s(es)h(not)g(exceed)638 668 y Fo(n)p 578 713 179 4 v 578 804 a(e)623 775 y Fm(k)r Fg(\000)p Fn(1)815 611 y Fm(k)r Fg(\000)p Fn(1)816 641 y Fk(Y)823 851 y Fm(i)p Fn(=1)961 625 y Fk(\020)1030 668 y Fo(e)p 1030 713 46 4 v 1036 804 a(i)1085 625 y Fk(\021)1145 648 y Fm(i)1233 736 y Fr(=)28 b Fo(ne)1440 695 y Fn(\()p Fm(k)r Fg(\000)p Fn(1\)\()p Fm(k)r Fg(\000)p Fn(2\))p Fm(=)p Fn(2)p Fg(\000)1931 645 y Fa(P)2003 665 y Fh(k)q Fb(\000)p Fc(1)2003 715 y Fh(i)p Fc(=1)2131 695 y Fm(i)12 b Fn(log)h Fm(i)2326 736 y Fr(=)27 b Fo(ne)2532 695 y Fg(\000)p Fn(\(1)p Fm(=)p Fn(2+)p Fm(o)p Fn(\(1\)\))p Fm(k)2963 671 y Fc(2)3012 695 y Fn(log)13 b Fm(k)3190 736 y Fo(:)0 994 y Fr(Th)m(us,)1115 1132 y Fs(P)p Fl(f)p Fo(H)1323 1147 y Fm(n)1397 1132 y Fl(\025)28 b Fo(k)s Fl(g)f(\024)i Fo(ne)1842 1091 y Fg(\000)p Fn(\(1)p Fm(=)p Fn(2+)p Fm(o)p Fn(\(1\)\))p Fm(k)2273 1068 y Fc(2)2322 1091 y Fn(log)13 b Fm(k)2495 1132 y Fl(!)27 b Fr(0)0 1304 y(for)32 b(the)h(giv)m(en)h(c) m(hoice)g(of)e Fo(k)s Fr(.)299 1503 y(F)-8 b(or)44 b(a)h(matc)m(hing)h (lo)m(w)m(er)g(b)s(ound,)j(w)m(e)d(argue)f(b)m(y)h(em)m(b)s(edding)h (and)e(prune)h(the)f(tree)h(ev)m(en)0 1650 y(further.)h(F)-8 b(or)33 b Fo(\017)d Fl(2)h Fr(\(0)p Fo(;)17 b Fr(1\),)33 b(de\014ne)i Fo(k)e Fr(=)1461 1540 y Fk(j)1514 1650 y Fr(\(1)22 b Fl(\000)g Fo(\017)p Fr(\))1799 1539 y Fk(q)p 1899 1539 269 4 v 1937 1607 a Fn(2)12 b(log)h Fm(n)p 1909 1628 249 4 v 1909 1685 a Fn(log)g(log)g Fm(n)2168 1540 y Fk(k)2220 1650 y Fr(.)47 b(Of)34 b(all)f(no)s(des)i(at)e(depth)i (one,)f(w)m(e)h(k)m(eep)0 1793 y(only)e(those)h(of)e(exact)i (cardinalit)m(y)g Fo(k)s Fr(.)44 b(These)34 b(no)s(des)g(spa)m(wn)g(c)m (hildren)g(at)f(depth)g(t)m(w)m(o,)h(of)e(whic)m(h)j(w)m(e)0 1926 y(k)m(eep)f(only)e(the)g(\014rst)h(c)m(hild)g(and)f(only)g(if)g (it)g(is)h(of)e(cardinalit)m(y)i(precisely)h Fo(k)24 b Fl(\000)e Fr(1.)43 b(Con)m(tin)m(uing)33 b(in)f(this)0 2058 y(manner,)f(the)f(pro)s(cess)g(either)h(b)s(ecomes)g(extinct,)g (or)e(it)h(surviv)m(es)i(up)d(to)h(depth)g Fo(k)i Fr(with)e(at)f(least) h(one)0 2191 y(no)s(de)k(of)f(cardinalit)m(y)h(1.)46 b(In)34 b(the)g(latter)f(case,)i Fo(H)1833 2206 y Fm(n)1909 2191 y Fl(\025)29 b Fo(k)s Fr(.)47 b(A)33 b(no)s(de)h(at)f(depth)h(one) g(has)g(progen)m(y)g(that)0 2324 y(surviv)m(es)h(to)e(depth)g Fo(k)j Fr(with)d(probabilit)m(y)1740 2471 y(1)p 1168 2516 1193 4 v 1168 2607 a(\()p Fo(k)25 b Fl(\000)d Fr(1\))1468 2578 y Fm(k)r Fg(\000)p Fn(1)1601 2607 y Fr(\()p Fo(k)j Fl(\000)e Fr(2\))1902 2578 y Fm(k)r Fg(\000)p Fn(2)2051 2607 y Fl(\001)17 b(\001)g(\001)e Fr(2)2233 2578 y Fn(2)2272 2607 y Fr(1)2321 2578 y Fn(1)2398 2483 y(d)o(ef)2408 2539 y Fr(=)38 b Fo(q)e(:)0 2787 y Fr(Clearly)-8 b(,)36 b Fo(q)g Fr(=)31 b Fo(e)591 2751 y Fg(\000)p Fn(\(1)p Fm(=)p Fn(2+)p Fm(o)p Fn(\(1\)\))p Fm(k)1022 2728 y Fc(2)1071 2751 y Fn(log)13 b Fm(k)1216 2787 y Fr(.)50 b(Giv)m(en)36 b(that)f(there)g(are)g Fo(L)g Fr(no)s(des)g(at)g(depth)g(one)g(in)g (the)h(p)s(ebbled)0 2920 y(hash)d(tree,)g(w)m(e)h(ha)m(v)m(e)1332 3059 y Fs(P)p Fl(f)p Fo(H)1540 3074 y Fm(n)1614 3059 y Fo(<)28 b(k)s Fl(j)p Fo(L)p Fl(g)f(\024)h Fr(\(1)22 b Fl(\000)h Fo(q)t Fr(\))2342 3017 y Fm(L)2426 3059 y Fo(:)0 3230 y Fr(No)m(w,)32 b Fo(L)g Fr(is)f(binomial)h(\()p Fo(n)19 b Fl(\000)h Fr(1)p Fo(;)d(p)p Fr(\),)31 b(where)i Fo(p)27 b Fr(=)h Fs(P)p Fl(f)p Fo(B)k Fr(=)c Fo(k)s Fl(g)j Fr(and)g Fo(B)36 b Fr(is)c(binomial)f(\()p Fo(n)20 b Fl(\000)g Fr(1)p Fo(;)d Fr(1)p Fo(=)p Fr(\()p Fo(n)h Fl(\000)i Fr(1\)\).)0 3363 y(It)33 b(is)g(easy)g(to)g(v)m(erify)h(that) e(for)g Fo(n)c Fl(\025)g Fr(3,)195 3610 y Fo(p)g Fr(=)375 3470 y Fk(\022)448 3543 y Fo(n)23 b Fl(\000)f Fr(1)536 3679 y Fo(k)677 3470 y Fk(\023)910 3543 y Fr(1)p 761 3588 348 4 v 761 3679 a(\()p Fo(n)g Fl(\000)g Fr(1\))1065 3650 y Fm(k)1134 3470 y Fk(\022)1208 3610 y Fr(1)g Fl(\000)1516 3543 y Fr(1)p 1388 3588 305 4 v 1388 3679 a(\()p Fo(n)h Fl(\000)f Fr(1\))1703 3470 y Fk(\023)1776 3492 y Fm(n)p Fg(\000)p Fn(1)p Fg(\000)p Fm(k)2034 3610 y Fl(\025)2166 3543 y Fr(1)p 2150 3588 82 4 v 2150 3679 a Fo(k)s Fr(!)2257 3470 y Fk(\022)2341 3543 y Fo(n)g Fl(\000)h Fr(1)f Fl(\000)g Fo(k)p 2341 3588 405 4 v 2429 3679 a(n)g Fl(\000)h Fr(1)2755 3470 y Fk(\023)2829 3492 y Fm(k)2888 3470 y Fk(\022)2961 3610 y Fr(1)f Fl(\000)3232 3543 y Fr(1)p 3142 3588 229 4 v 3142 3679 a Fo(n)g Fl(\000)h Fr(1)3380 3470 y Fk(\023)3454 3492 y Fm(n)p Fg(\000)p Fn(1)272 3903 y Fl(\025)444 3835 y Fr(1)p 387 3880 163 4 v 387 3971 a(4)32 b Fo(k)s Fr(!)576 3762 y Fk(\022)649 3903 y Fr(1)22 b Fl(\000)917 3835 y Fo(k)p 830 3880 229 4 v 830 3971 a(n)g Fl(\000)h Fr(1)1068 3762 y Fk(\023)1142 3784 y Fm(k)1212 3903 y Fl(\025)1327 3835 y Fr(1)f Fl(\000)h Fo(k)1552 3799 y Fn(2)1591 3835 y Fo(=)p Fr(\()p Fo(n)f Fl(\000)h Fr(1\))p 1327 3880 618 4 v 1555 3971 a(4)32 b Fo(k)s Fr(!)1982 3847 y Fn(d)o(ef)1992 3903 y Fr(=)38 b Fo(q)2153 3861 y Fg(0)2209 3903 y Fo(:)0 4136 y Fr(Hence)c Fo(L)f Fr(is)g(sto)s(c)m(hastically)h(greater)f(than) f Fo(B)1729 4099 y Fg(0)1753 4136 y Fr(,)g(a)h(binomial)g(\()p Fo(n)22 b Fl(\000)h Fr(1)p Fo(;)17 b(q)2653 4099 y Fg(0)2675 4136 y Fr(\))33 b(random)f(v)-5 b(ariable.)44 b(Th)m(us,)439 4339 y Fs(P)p Fl(f)p Fo(H)647 4354 y Fm(n)721 4339 y Fo(<)27 b(k)s Fl(g)h(\024)g Fs(E)1152 4258 y Fk(\010)1209 4339 y Fr(\(1)22 b Fl(\000)h Fo(q)t Fr(\))1503 4298 y Fm(L)1555 4258 y Fk(\011)1640 4339 y Fl(\024)29 b Fs(E)1837 4228 y Fk(n)1902 4339 y Fr(\(1)22 b Fl(\000)h Fo(q)t Fr(\))2196 4298 y Fm(B)2252 4274 y Fb(0)2278 4228 y Fk(o)956 4531 y Fr(=)k(\()p Fo(q)1144 4490 y Fg(0)1167 4531 y Fr(\(1)22 b Fl(\000)h Fo(q)t Fr(\))f(+)g(1)g Fl(\000)g Fo(q)1798 4490 y Fg(0)1821 4531 y Fr(\))1859 4480 y Fm(n)p Fg(\000)p Fn(1)2024 4531 y Fr(=)28 b(\(1)22 b Fl(\000)g Fo(q)t(q)2430 4490 y Fg(0)2453 4531 y Fr(\))2491 4480 y Fm(n)p Fg(\000)p Fn(1)2656 4531 y Fl(\024)28 b Fo(e)2806 4490 y Fg(\000)p Fn(\()p Fm(n)p Fg(\000)p Fn(1\))p Fm(q)r(q)3116 4467 y Fb(0)3171 4531 y Fl(!)f Fr(0)0 4720 y(when)34 b Fo(nq)t(q)407 4683 y Fg(0)458 4720 y Fl(!)27 b(1)p Fr(.)43 b(This)34 b(is)f(easily)h(v)m(eri\014ed)g(for)e(our)g(c)m (hoice)i(of)e Fo(k)s Fr(.)p 2534 4666 65 4 v 2534 4724 4 59 v 2595 4724 V 2534 4727 65 4 v 1851 5280 a Fj(10)p eop %%Page: 11 11 11 10 bop 0 83 a Fs(6.)38 b(The)f(size)g(of)h(random)f(hash)i(trees.) 299 334 y Fr(The)e(second)h(parameter)f(of)e(primary)i(in)m(terest)h (is)f Fo(S)2297 349 y Fm(n)2344 334 y Fr(.)55 b(W)-8 b(e)36 b(will)h(only)g(lo)s(ok)f(at)g Fo(s)3387 349 y Fm(n)3468 334 y Fr(=)e Fs(E)p Fo(S)3712 349 y Fm(n)3759 334 y Fr(.)0 466 y(By)f(linearit)m(y)h(of)e(exp)s(ectation,)i(w)m(e)f (ha)m(v)m(e)769 691 y Fo(s)815 706 y Fm(n)890 691 y Fr(=)993 550 y Fk(\032)1084 617 y Fr(1)g Fo(;)1360 b Fr(0)27 b Fl(\024)i Fo(n)e Fl(\024)i Fr(1)1084 750 y(1)22 b(+)g Fo(n)1328 675 y Fk(P)1433 701 y Fm(n)1433 779 y(i)p Fn(=0)1568 750 y Fs(P)p Fl(f)p Fo(B)5 b Fr(\()p Fo(n;)17 b Fr(1)p Fo(=n)p Fr(\))27 b(=)h Fo(i)p Fl(g)p Fo(s)2368 765 y Fm(i)2428 750 y Fo(;)98 b(n)28 b Fl(\025)g Fr(2.)0 915 y(Note)36 b(that)g(w)m(e)i(pro)m(vide)f(storage)f(for)g(empt)m(y)h (bins)h(as)e(w)m(ell.)56 b(The)37 b(recurrence)h(giv)m(en)f(ab)s(o)m(v) m(e)g(yields)0 1048 y Fo(s)46 1063 y Fn(0)113 1048 y Fr(=)28 b Fo(s)263 1063 y Fn(1)330 1048 y Fr(=)f(1,)33 b Fo(s)588 1063 y Fn(2)655 1048 y Fr(=)27 b(1)22 b(+)g(2\(3)p Fo(=)p Fr(4)f(+)h Fo(s)1326 1063 y Fn(2)1366 1048 y Fo(=)p Fr(4\),)32 b(so)h(that)f Fo(s)1938 1063 y Fn(2)2005 1048 y Fr(=)c(5.)43 b(W)-8 b(e)33 b(ha)m(v)m(e)0 1416 y Fp(Theorem)38 b(5.)55 b Ff(F)-8 b(or)32 b(the)h(random)e(hash)i(tree,)1339 1632 y Fr(lim)1314 1691 y Fm(n)p Fg(!1)1525 1564 y Fs(E)p Fo(S)1659 1579 y Fm(n)p 1525 1609 181 4 v 1586 1700 a Fo(n)1743 1632 y Fr(=)28 b(2)p Fo(:)p Fr(3020238)17 b Fo(:)g(:)g(:)46 b(:)0 1831 y Ff(The)34 b(limiting)28 b(constan)m(t)33 b(is)1703 1957 y Fr(1)p 1703 2001 49 4 v 1705 2092 a Fo(e)1815 1900 y Fg(1)1778 1929 y Fk(X)1793 2139 y Fm(i)p Fn(=0)1949 1957 y Fo(s)1995 1972 y Fm(i)p 1949 2001 75 4 v 1956 2092 a Fo(i)p Fr(!)2066 2024 y Fo(;)0 2262 y Ff(where)h Fo(s)328 2277 y Fn(0)367 2262 y Fo(;)17 b(s)457 2277 y Fn(1)496 2262 y Fo(;)g(:)g(:)g(:)32 b Ff(is)g(giv)m(en)h(b)m(y)g(the)g(recurrence)i(ab)s(o)m(v)m(e.)0 2733 y Fp(Pr)n(oof.)56 b Fr(The)33 b(v)-5 b(alues)34 b Fo(s)936 2748 y Fm(n)1015 2733 y Fr(can)f(b)s(e)g(sho)m(wn)h(to)e(b)s (e)h(appro)m(ximable)g(b)m(y)h(the)f(v)-5 b(alues)33 b Fo(t)3110 2748 y Fm(n)3158 2733 y Fr(,)f(where)1582 2976 y Fo(t)1617 2991 y Fm(n)1692 2976 y Fr(=)1805 2909 y Fo(n)p 1805 2953 59 4 v 1812 3045 a(e)1927 2852 y Fg(1)1890 2882 y Fk(X)1905 3092 y Fm(i)p Fn(=0)2060 2909 y Fo(s)2106 2924 y Fm(i)p 2060 2953 75 4 v 2067 3045 a Fo(i)p Fr(!)2177 2976 y Fo(:)0 3231 y Fr(Indeed,)i(note)f(that)614 3407 y Fo(s)660 3422 y Fm(n)729 3407 y Fl(\000)23 b Fo(t)864 3422 y Fm(n)p 614 3451 297 4 v 734 3542 a Fo(n)949 3474 y Fr(=)1067 3407 y(1)p 1062 3451 59 4 v 1062 3542 a Fo(n)1153 3474 y Fr(+)1301 3350 y Fm(n)1251 3379 y Fk(X)1265 3589 y Fm(i)p Fn(=0)1411 3334 y Fk(\022)1484 3474 y Fs(P)p Fl(f)p Fo(B)5 b Fr(\()p Fo(n;)17 b Fr(1)p Fo(=n)p Fr(\))27 b(=)h Fo(i)p Fl(g)22 b(\000)2414 3407 y Fr(1)p 2370 3451 139 4 v 2370 3542 a Fo(e)32 b(i)p Fr(!)2518 3334 y Fk(\023)2608 3474 y Fo(s)2654 3489 y Fm(i)2704 3474 y Fl(\000)2803 3379 y Fk(X)2815 3589 y Fm(i>n)3006 3407 y Fo(s)3052 3422 y Fm(i)p 2974 3451 V 2974 3542 a Fo(e)h(i)p Fr(!)3154 3474 y Fo(:)0 3733 y Fr(But)g(for)f(0)27 b Fl(\024)h Fo(i)g Fl(\024)g Fo(n)p Fr(,)358 3960 y Fs(P)p Fl(f)p Fo(B)5 b Fr(\()p Fo(n;)17 b Fr(1)p Fo(=n)p Fr(\))27 b(=)h Fo(i)p Fl(g)22 b(\000)1288 3893 y Fr(1)p 1244 3938 V 1244 4029 a Fo(e)32 b(i)p Fr(!)1419 3960 y(=)1523 3820 y Fk(\022)1596 3893 y Fo(n)1609 4029 y(i)1654 3820 y Fk(\023)1738 3893 y Fr(\()p Fo(n)22 b Fl(\000)h Fr(1\))2043 3857 y Fm(n)p Fg(\000)p Fm(i)p 1738 3938 431 4 v 1900 4029 a Fo(n)1958 4000 y Fm(n)2200 3960 y Fl(\000)2355 3893 y Fr(1)p 2310 3938 139 4 v 2310 4029 a Fo(e)33 b(i)p Fr(!)2486 3960 y Fl(\024)2601 3893 y Fo(n)2659 3857 y Fm(i)p 2601 3938 87 4 v 2614 4029 a Fo(i)p Fr(!)2707 3893 y(\()p Fo(n)22 b Fl(\000)h Fr(1\))3012 3857 y Fm(n)p Fg(\000)p Fm(i)p 2707 3938 431 4 v 2870 4029 a Fo(n)2928 4000 y Fm(n)3170 3960 y Fl(\000)3324 3893 y Fr(1)p 3279 3938 139 4 v 3279 4029 a Fo(e)33 b(i)p Fr(!)1419 4253 y(=)1539 4185 y(1)p 1533 4230 61 4 v 1533 4321 a Fo(i)p Fr(!)1613 4185 y(\()p Fo(n)22 b Fl(\000)h Fr(1\))1918 4149 y Fm(n)p Fg(\000)p Fm(i)p 1613 4230 431 4 v 1736 4321 a Fo(n)1794 4292 y Fm(n)p Fg(\000)p Fm(i)2076 4253 y Fl(\000)2230 4185 y Fr(1)p 2185 4230 139 4 v 2185 4321 a Fo(e)33 b(i)p Fr(!)2361 4253 y Fl(\024)2476 4185 y Fo(e)2539 4121 y Fh(i)p 2531 4133 39 3 v 2531 4175 a(n)2580 4148 y Fg(\000)p Fn(1)p 2476 4230 198 4 v 2545 4321 a Fo(i)p Fr(!)2706 4253 y Fl(\000)2860 4185 y Fr(1)p 2816 4230 139 4 v 2816 4321 a Fo(e)f(i)p Fr(!)2991 4253 y Fl(\024)3165 4185 y Fo(i)p 3107 4230 152 4 v 3107 4321 a(n)g(i)p Fr(!)0 4451 y(and)h(for)f(0)27 b Fl(\024)h Fo(i)g Fl(\024)g Fo(n)p Fr(,)-67 4706 y Fs(P)p Fl(f)p Fo(B)5 b Fr(\()p Fo(n;)17 b Fr(1)p Fo(=n)p Fr(\))26 b(=)i Fo(i)p Fl(g)22 b(\000)862 4639 y Fr(1)p 818 4683 139 4 v 818 4775 a Fo(e)32 b(i)p Fr(!)994 4706 y Fl(\025)1109 4639 y Fr(\()p Fo(n)22 b Fl(\000)h Fo(i)f Fr(+)g(1\))1567 4603 y Fm(i)p 1109 4683 487 4 v 1322 4775 a Fo(i)p Fr(!)1615 4639 y(\()p Fo(n)g Fl(\000)h Fr(1\))1920 4603 y Fm(n)p Fg(\000)p Fm(i)p 1615 4683 431 4 v 1777 4775 a Fo(n)1835 4746 y Fm(n)2077 4706 y Fl(\000)2232 4639 y Fr(1)p 2187 4683 139 4 v 2187 4775 a Fo(e)33 b(i)p Fr(!)2363 4706 y Fl(\025)2468 4566 y Fk(\022)2541 4706 y Fr(1)22 b Fl(\000)2734 4639 y Fo(i)h Fl(\000)f Fr(2)p 2722 4683 229 4 v 2722 4775 a Fo(n)g Fl(\000)h Fr(1)2960 4566 y Fk(\023)3034 4588 y Fm(i)3089 4639 y Fo(e)3134 4590 y Fg(\000)3273 4562 y Fc(1)p 3199 4574 180 3 v 3199 4616 a(1)p Fb(\000)p Fc(1)p Fh(=n)p 3089 4683 304 4 v 3210 4775 a Fo(i)p Fr(!)3424 4706 y Fl(\000)3578 4639 y Fr(1)p 3533 4683 139 4 v 3533 4775 a Fo(e)33 b(i)p Fr(!)994 5031 y Fl(\025)1109 4963 y Fo(e)1154 4914 y Fg(\000)1283 4887 y Fh(i)1305 4866 y Fc(2)p 1219 4899 186 3 v 1219 4940 a Fh(n)p Fb(\000)p Fh(i)p Fc(+1)1414 4914 y Fg(\000)1553 4887 y Fc(1)p 1479 4899 180 3 v 1479 4940 a(1)p Fb(\000)p Fc(1)p Fh(=n)p 1109 5008 564 4 v 1360 5099 a Fo(i)p Fr(!)1704 5031 y Fl(\000)1859 4963 y Fr(1)p 1814 5008 139 4 v 1814 5099 a Fo(e)g(i)p Fr(!)1990 5031 y Fl(\025)2149 4963 y Fr(1)p 2105 5008 V 2105 5099 a Fo(e)f(i)p Fr(!)2269 4920 y Fk(\020)2329 5031 y Fo(e)2374 4987 y Fg(\000)2503 4960 y Fh(i)2525 4939 y Fc(2)p 2439 4972 186 3 v 2439 5013 a Fh(n)p Fb(\000)p Fh(i)p Fc(+1)2634 4987 y Fg(\000)2742 4960 y Fc(1)p 2699 4972 117 3 v 2699 5013 a Fh(n)p Fb(\000)p Fc(1)2852 5031 y Fl(\000)23 b Fr(1)3001 4920 y Fk(\021)1851 5280 y Fj(11)p eop %%Page: 12 12 12 11 bop 994 146 a Fl(\025)28 b(\000)1231 79 y Fr(1)p 1186 123 139 4 v 1186 215 a Fo(e)33 b(i)p Fr(!)1351 6 y Fk(\022)1589 79 y Fo(i)1622 43 y Fn(2)p 1434 123 383 4 v 1434 215 a Fo(n)22 b Fl(\000)h Fo(i)g Fr(+)f(1)1848 146 y(+)2046 79 y(1)p 1956 123 229 4 v 1956 215 a Fo(n)h Fl(\000)f Fr(1)2195 6 y Fk(\023)2296 146 y Fl(\025)28 b(\000)2533 79 y Fr(1)p 2488 123 139 4 v 2488 215 a Fo(e)33 b(i)p Fr(!)2653 6 y Fk(\022)2778 79 y Fo(i)2811 43 y Fn(2)p 2737 123 156 4 v 2737 215 a Fo(n=)p Fr(2)2925 146 y(+)22 b Fo(i)3056 105 y Fn(2)3095 146 y Fo(I)3138 162 y Fm(i)p Fg(\025)p Fm(n=)p Fn(2)3357 146 y Fr(+)3555 79 y(1)p 3465 123 229 4 v 3465 215 a Fo(n)g Fl(\000)h Fr(1)3704 6 y Fk(\023)3826 146 y Fo(:)0 369 y Fr(Th)m(us,)34 b(w)m(e)g(ha)m(v)m(e)g(\()p Fo(s)727 384 y Fm(n)796 369 y Fl(\000)22 b Fo(t)930 384 y Fm(n)978 369 y Fr(\))p Fo(=n)27 b Fl(!)g Fr(0)33 b(if)1621 486 y Fg(1)1584 516 y Fk(X)1599 726 y Fm(i)p Fn(=0)1755 543 y Fo(i)1788 507 y Fn(2)1827 543 y Fo(s)1873 558 y Fm(i)p 1755 587 147 4 v 1798 679 a Fo(i)p Fr(!)1939 610 y Fo(<)28 b Fl(1)k Fo(:)0 864 y Fr(But)40 b(that)g(follo)m(ws)h(from)f(the)h(simple)h (fact)e(that)g Fo(s)1939 879 y Fm(i)2008 864 y Fr(=)g Fo(O)s Fr(\()p Fo(i)p Fr(\),)i(something)f(that)f(is)h(easy)g(to)f(v)m (erify)-8 b(.)0 996 y(Numerical)34 b(computations)f(sho)m(w)h(that)1306 1165 y(1)p 1306 1209 49 4 v 1308 1301 a Fo(e)1418 1108 y Fg(1)1382 1138 y Fk(X)1397 1348 y Fm(i)p Fn(=0)1552 1165 y Fo(s)1598 1180 y Fm(i)p 1552 1209 75 4 v 1559 1301 a Fo(i)p Fr(!)1664 1232 y(=)27 b(2)p Fo(:)p Fr(3020238)17 b Fo(:)g(:)g(:)47 b(:)p 2425 1178 65 4 v 2425 1236 4 59 v 2486 1236 V 2425 1239 65 4 v 299 1546 a Fr(F)-8 b(or)32 b(the)h(random)f(p)s(ebbled)i(hash)f(tree,)g(the)g(recurrences) i(are)e(sligh)m(tly)h(di\013eren)m(t.)45 b(Indeed,)428 1764 y Fo(s)474 1779 y Fm(n)548 1764 y Fr(=)652 1623 y Fk(\032)743 1690 y Fr(1)p Fo(;)2075 b Fr(0)27 b Fl(\024)i Fo(n)f Fl(\024)g Fr(1)743 1823 y(1)22 b(+)g(\()p Fo(n)h Fl(\000)f Fr(1\))1234 1748 y Fk(P)1339 1774 y Fm(n)p Fg(\000)p Fn(1)1339 1852 y Fm(i)p Fn(=0)1492 1823 y Fs(P)p Fl(f)p Fo(B)5 b Fr(\()p Fo(n)22 b Fl(\000)h Fr(1)p Fo(;)17 b Fr(1)p Fo(=)p Fr(\()p Fo(n)k Fl(\000)i Fr(1\)\))k(=)h Fo(i)p Fl(g)p Fo(s)2709 1838 y Fm(i)2769 1823 y Fo(;)98 b(n)28 b(>)f Fr(1)p Fo(:)0 1981 y Fr(The)34 b(analysis)f(is)h(en)m (tirely)g(similar)f(as)g(for)f(Theorem)i(5,)e(and)h(w)m(e)g(th)m(us)h (obtain)0 2327 y Fp(Theorem)k(6.)55 b Ff(F)-8 b(or)32 b(the)h(random)e(p)s(ebbled)i(hash)g(tree,)1339 2535 y Fr(lim)1314 2595 y Fm(n)p Fg(!1)1525 2468 y Fs(E)p Fo(S)1659 2483 y Fm(n)p 1525 2512 181 4 v 1586 2604 a Fo(n)1743 2535 y Fr(=)28 b(1)p Fo(:)p Fr(4183342)17 b Fo(:)g(:)g(:)46 b(:)0 2728 y Ff(The)34 b(limiting)28 b(constan)m(t)33 b(is)1703 2851 y Fr(1)p 1703 2895 49 4 v 1705 2987 a Fo(e)1815 2794 y Fg(1)1778 2824 y Fk(X)1793 3034 y Fm(i)p Fn(=0)1949 2851 y Fo(s)1995 2866 y Fm(i)p 1949 2895 75 4 v 1956 2987 a Fo(i)p Fr(!)2066 2918 y Fo(;)0 3154 y Ff(where)h Fo(s)328 3169 y Fn(0)367 3154 y Fo(;)17 b(s)457 3169 y Fn(1)496 3154 y Fo(;)g(:)g(:)g(:)32 b Ff(is)g(giv)m(en)h(b)m(y)g(the)g(recurrence)i(ab)s(o)m(v)m(e.)299 3434 y Fr(In)27 b(particular,)h(note)g(that)e(random)h(p)s(ebbled)h (hash)g(trees)g(are)f(smaller)h(on)e(the)i(a)m(v)m(erage)g(than)0 3567 y(random)33 b(N-trees.)0 3887 y Fs(7.)38 b(BBST:)f(buc)m(k)m (eting)f(follo)m(w)m(ed)g(b)m(y)i(binary)g(searc)m(h)g(trees.)299 4126 y Fr(Assume)c(that)e(w)m(e)h(buc)m(k)m(et)h Fo(n)e Fr(p)s(oin)m(ts)h(in)m(to)f Fo(n)h Fr(equi-spaced)h(buc)m(k)m(ets,)h (and)d(that)g(within)h(eac)m(h)0 4259 y(buc)m(k)m(et,)e(w)m(e)e(main)m (tain)g(a)e(balanced)i(binary)g(searc)m(h)g(tree.)42 b(Then,)31 b(in)d(view)h(of)f(the)g(results)h(of)f(Gonnet)0 4392 y(\(1981\))36 b(and)h(Devro)m(y)m(e)i(\(1985\),)e(the)h(exp)s (ected)h(w)m(orst-case)f(searc)m(h)h(and)e(insert)h(times)g(and)f (indeed)0 4525 y(the)k(exp)s(ected)h(v)-5 b(alue)40 b(of)g(the)g(heigh) m(t)h(of)f(this)h(h)m(ybrid)g(structure)h(is)e(asymptotic)i(to)d(log) 3372 4548 y Fn(2)3428 4525 y Fr(log)18 b Fo(n)40 b Fr(for)0 4658 y(all)47 b(b)s(ounded)h(densities)h Fo(f)58 b Fr(on)47 b([0)p Fo(;)17 b Fr(1].)87 b(In)48 b(fact,)j(the)c(heigh)m(t)h Fo(H)2488 4673 y Fm(n)2582 4658 y Fr(satis\014es)h Fo(H)3037 4673 y Fm(n)3084 4658 y Fo(=)17 b Fr(log)3275 4681 y Fn(2)3331 4658 y Fr(log)h Fo(n)53 b Fl(!)f Fr(1)0 4790 y(in)45 b(probabilit)m(y)-8 b(.)81 b(The)46 b(exp)s(ected)h(a)m(v)m (erage)e(searc)m(h)i(time)e(\(if)g(eac)m(h)g(elemen)m(t)i(is)e(equally) h(lik)m(ely)h(to)0 4923 y(b)s(e)37 b(prob)s(ed)g(for\))f(and)h(the)g (exp)s(ected)i(unsuccessful)h(searc)m(h)e(time)g(\(for)e(a)g(random)h (elemen)m(t)i(dra)m(wn)0 5056 y(indep)s(enden)m(tly)c(from)e(the)g (same)g(densit)m(y)i Fo(f)11 b Fr(\))32 b(are)g(b)s(oth)h Fo(O)s Fr(\(1\).)1851 5280 y Fj(12)p eop %%Page: 13 13 13 12 bop 0 83 a Fs(8.)38 b(Extension:)49 b Fo(m)38 b Fs(p)s(ebbles.)299 336 y Fr(W)-8 b(e)34 b(ma)m(y)h(extend)g(the)g (analysis)g(to)f Fo(m)g Fr(p)s(ebbles,)i(lea)m(ving)f Fo(m)f Fr(randomly)h(selected)h(p)s(oin)m(ts)f(in)0 468 y(ev)m(ery)k(no)s(de)e(b)s(efore)g(buc)m(k)m(eting.)58 b(If)37 b(there)g(are)g Fo(m)26 b Fr(+)f Fo(k)39 b Fr(p)s(oin)m(ts,)g (then)f(there)f(are)g Fo(k)j Fr(\(with)d(p)s(ossibly)0 601 y Fo(k)31 b Fr(=)c(1\))f(c)m(hild)i(no)s(des,)g(eac)m(h)f(corresp)s (onding)h(to)e(a)g(subin)m(terv)-5 b(al)27 b(1)p Fo(=k)s Fr(-th)f(of)g(the)h(length)f(of)g(the)h(in)m(terv)-5 b(al)0 734 y(of)44 b(the)h(split)h(no)s(de.)80 b(This)45 b(leads)h(to)e(random)h Fo(m)p Fr(-p)s(ebbled)h(hash)f(trees.)81 b(A)44 b(quic)m(k)j(analysis)f(not)0 867 y(w)m(orth)29 b(rep)s(eating)g(here)g(sho)m(ws)h(that)e(in)g(this)h(case,)i Fo(H)1999 882 y Fm(n)2073 867 y Fl(\030)2178 782 y Fk(p)p 2278 782 886 4 v 85 x Fr(\(2)p Fo(=m)p Fr(\))17 b(log)g Fo(n=)g Fr(log)g(log)h Fo(n)28 b Fr(in)h(probabilit)m(y)-8 b(.)0 1000 y(Ho)m(w)m(ev)m(er,)34 b(the)f(w)m(orst-case)g(searc)m(h)g (time)f(is)h(roughly)f(\()p Fo(m)21 b Fr(+)f(1\))p Fo(H)2432 1015 y Fm(n)2511 1000 y Fr(when)33 b(comparisons)g(and)f(buc)m(k)m(et)0 1133 y(op)s(erations)j(all)f(tak)m(e)i(one)f(time)g(unit.)50 b(Therefore,)36 b(it)f(seems)i(w)m(asteful)f(to)e(tak)m(e)h Fo(m)d(>)f Fr(1,)k(and)g(th)m(us,)0 1265 y(the)25 b(most)h(imp)s(ortan) m(t)f(mem)m(b)s(er)h(of)e(the)i(family)f(is)g(the)h(p)s(ebbled)g(hash)f (tree)h(studied)g(ab)s(o)m(v)m(e.)42 b(A)25 b(rather)0 1398 y(ob)m(vious)38 b(but)f(unaesthetic)i(mo)s(di\014cation)e(ho)m(w)m (ev)m(er)i(will)e(impro)m(v)m(e)i(matters)e(exp)s(onen)m(tially)-8 b(.)58 b(If)37 b(w)m(e)0 1531 y(set)28 b Fo(m)g Fr(=)g Fo(c)17 b Fr(log)g Fo(n=)g Fr(log)g(log)h Fo(n)27 b Fr(for)g(some)h (constan)m(t)g Fo(c)p Fr(,)h(and)e(pic)m(k)i(the)f Fo(m)f Fr(p)s(ebbles)i(as)f(follo)m(ws)g(for)f(a)g(no)s(de)0 1664 y(represen)m(ting)38 b(in)m(terv)-5 b(al)36 b([)p Fo(a;)17 b(b)p Fr(]:)49 b(\014nd)36 b(the)g Fo(m)p Fr(-th)g(order)f (statistic)i Fo(M)46 b Fr(in)36 b(time)g(linear)g(in)f(the)h(n)m(um)m (b)s(er)0 1797 y(of)k(p)s(oin)m(ts.)68 b(The)41 b Fo(m)g Fr(p)s(oin)m(ts)g(on)f([)p Fo(a;)17 b(M)10 b Fr(])42 b(are)e(placed)h(in)g(a)f(balanced)i(binary)f(searc)m(h)g(tree)g(in)g (time)0 1930 y Fo(m)17 b Fr(log)h Fo(m)28 b Fr(=)f Fo(O)s Fr(\(log)17 b(log)g Fo(n)p Fr(\).)43 b(The)29 b(remaining)g(p)s(oin)m (ts)g(on)f(\()p Fo(M)5 b(;)17 b(b)p Fr(])29 b(are)f(buc)m(k)m(eted)j (as)d(in)h(a)f(random)g(hash)0 2062 y(tree,)41 b(and)e(the)g(pro)s (cess)g(is)h(rep)s(eated.)62 b(This)40 b(tree)f(has)g(exp)s(ected)i (heigh)m(t)e Fo(O)s Fr(\(1\))f(so)g(that)h(exp)s(ected)0 2195 y(w)m(orst-case)34 b(searc)m(h)h(times)f(are)f Fo(O)s Fr(\(log)17 b(log)h Fo(n)p Fr(\).)45 b(As)34 b(this)f(metho)s(d)h(is)g (eclipsed)h(b)m(y)f(the)f(simple)i(BBST)0 2328 y(structure)f(of)e(the)h (previous)h(section,)g(w)m(e)f(will)h(not)e(analyze)i(it)e(in)h(this)g (pap)s(er.)0 2687 y Fs(9.)38 b(Dynamic)e(data)i(structures.)299 2940 y Fr(The)g(data)e(structures)i(describ)s(ed)h(ab)s(o)m(v)m(e)f (are)e(of)h(course)g(useful)h(in)f(an)m(y)h(static)f(setting,)i(in)0 3072 y(whic)m(h)45 b(case)g(w)m(e)g(ha)m(v)m(e)g(exp)s(ected)h(prepro)s (cessing)g(time)e Fo(O)s Fr(\()p Fo(n)p Fr(\))f(and)h(exp)s(ected)i(w)m (orst-case)f(searc)m(h)0 3205 y(times)35 b(as)f(giv)m(en)h(b)m(y)g(the) f(exp)s(ected)i(v)-5 b(alues)35 b(of)f Fo(H)1839 3220 y Fm(n)1919 3205 y Fr(in)g(the)h(analyses.)49 b(Consider)35 b(no)m(w)g(the)f(standard)0 3338 y(dictionary)c(op)s(erations)f Fq(insert)i Fr(and)e Fq(search)p Fr(.)44 b(W)-8 b(e)30 b(ma)m(y)g(in)m(tro)s(duce)g(the)f(load)g(factor)g Fo(\013)q Fr(,)h(the)f(n)m(um-)0 3471 y(b)s(er)f(of)f(elemen)m(ts)j(stored)e (divided)h(b)m(y)g(the)f(branc)m(h)h(factor)e(of)g(the)h(ro)s(ot.)41 b(The)29 b(ob)5 b(jectiv)m(e)29 b(is)g(to)e(k)m(eep)i Fo(\013)0 3604 y Fr(at)f(all)f(times)i(in)f(a)g(\014xed)h(range,)g(suc) m(h)g(as)f([1)p Fo(=)p Fr(2)p Fo(;)17 b Fr(2].)41 b(As)28 b(so)s(on)g(as)g Fo(\013)h Fr(reac)m(hes)g(a)f(b)s(oundary)-8 b(,)29 b(a)e(complete)0 3737 y(rehash)35 b(is)f(p)s(erformed)g(to)g (mak)m(e)g Fo(\013)d Fr(=)e(1.)47 b(In)34 b(an)g(amortized)g(sense,)i (these)f(rehash)g(op)s(erations)f(tak)m(e)0 3869 y Fo(O)s Fr(\(1\))26 b(exp)s(ected)k(time.)42 b(Exp)s(ected)30 b(w)m(orst-case)e(searc)m(h)h(times)g(remain)f(asymptotically)h(the)f (same)h(as)0 4002 y(for)h(the)i(static)f(case.)44 b(Ho)m(w)m(ev)m(er,) 34 b(for)c(a)h(fully)g(dynamic)i(data)d(structure)i(with)g(in)m(tersp)s (ersed)h Fq(delete)0 4135 y Fr(and)g Fq(insert)h Fr(op)s(erations,)f (additional)f(analysis)i(is)f(required.)0 4494 y Fs(10.)38 b(Ac)m(kno)m(wledgmen)m(t.)299 4747 y Fr(I)33 b(w)m(ould)g(lik)m(e)h (to)e(thank)h(all)g(referees)h(for)e(their)h(suggestions.)1851 5280 y Fj(13)p eop %%Page: 14 14 14 13 bop 0 83 a Fs(11.)38 b(Dedication.)299 332 y Fr(This)d(pap)s(er)e (is)h(dedicated)h(to)f(the)g(memory)g(of)f(Markku)i(T)-8 b(amminen)35 b(who)f(died)g(tragically)0 465 y(in)f(New)g(Y)-8 b(ork)33 b(shortly)g(after)g(he)g(\014nished)h(his)f(analysis)h(of)e (N-trees)i(and)e(random)h(hash)g(trees.)1851 5280 y Fj(14)p eop %%Page: 15 15 15 14 bop 0 83 a Fs(12.)38 b(References.)0 339 y Fr(Y.)d(Azar,)h(A.)f (Z.)g(Bro)s(der,)h(A.)f(R.)g(Karlin,)h(and)f(E.)h(Upfal,)f(\\Balanced)h (allo)s(cations)f(\(extended)i(ab-)0 472 y(stract\),")57 b(in:)g Ff(Pro)s(ceedings)g(of)g(the)g(26th)f(A)m(CM)i(Symp)s(osium)d (on)i(the)g(Theory)h(of)e(Comput-)0 605 y(ing)p Fr(,)32 b(pp.)h(593{602,)e(1994.)0 794 y(E.)57 b(G.)f(Co\013man)h(and)g(J.)g (Ev)m(e,)h(\\File)f(structures)h(using)g(hashing)f(functions,")h Ff(Comm)m(unica-)0 927 y(tions)32 b(of)g(the)h(A)m(CM)p Fr(,)h(v)m(ol.)f(13,)f(pp.)h(427{436,)e(1970.)0 1116 y(L.)52 b(Devro)m(y)m(e,)h(\\The)g(exp)s(ected)h(length)e(of)f(the)i (longest)f(prob)s(e)g(sequence)j(when)e(the)f(distribu-)0 1249 y(tion)33 b(is)g(not)f(uniform,")h Ff(Journal)e(of)h(Algorithms)p Fr(,)f(v)m(ol.)i(6,)f(pp.)h(1{9,)f(1985.)0 1437 y(L.)h(Devro)m(y)m(e,)h Ff(Lecture)f(Notes)g(on)g(Buc)m(k)m(et)h(Algorithms)p Fr(,)d(Birkh\177)-49 b(auser)34 b(V)-8 b(erlag,)32 b(Boston,)h(1986.)0 1626 y(W.)57 b(Dob)s(osiewicz,)h(\\Sorting)e(b)m(y)h(distributiv)m(e)i (partitioning,")e Ff(Information)d(Pro)s(cessing)j(Let-)0 1759 y(ters)p Fr(,)33 b(v)m(ol.)h(7,)e(pp.)h(1{6,)f(1978.)0 1948 y(G.)37 b(Ehrlic)m(h,)i(\\Searc)m(hing)f(and)f(sorting)g(real)h(n) m(um)m(b)s(ers,")h Ff(Journal)d(of)h(Algorithms)p Fr(,)e(v)m(ol.)j(2,)f (pp.)g(1{)0 2081 y(14,)32 b(1981.)0 2270 y(R.)f(F)-8 b(agin,)31 b(J.)g(Niev)m(ergelt,)i(N.)f(Pipp)s(enger,)g(and)g(H.)f(R.)g (Strong,)g(\\Extendible)j(hashing|a)d(fast)g(ac-)0 2403 y(cess)g(metho)s(d)f(for)f(dynamic)i(\014les,")g Ff(A)m(CM)g(T)-8 b(ransactions)30 b(on)f(Database)h(Systems)p Fr(,)h(v)m(ol.)f(4,)g(pp.) g(315{)0 2535 y(344,)i(1979.)0 2724 y(P)-8 b(.)32 b(Fla)5 b(jolet,)31 b(\\On)h(the)g(p)s(erformance)g(ev)-5 b(aluation)32 b(of)f(extendible)j(hashing)e(and)g(trie)g(searc)m(h,")h Ff(Acta)0 2857 y(Informatica)p Fr(,)e(v)m(ol.)i(20,)f(pp.)h(345{369,)e (1983.)0 3046 y(M.)50 b(L.)f(F)-8 b(redman)49 b(and)g(D.)g(E.)h (Willard,)f(\\Blasting)h(through)f(the)g(information)g(theoretic)h (bar-)0 3179 y(rier)28 b(with)h(fusion)g(trees,")g(in:)f Ff(Pro)s(ceedings)h(of)f(the)g(Tw)m(en)m(t)m(y)j(Second)e(Ann)m(ual)f (Symp)s(osium)f(on)h(The-)0 3312 y(ory)33 b(of)f(Computing)p Fr(,)f(pp.)i(1{7,)f(A)m(CM)i(Press,)g(1990.)0 3501 y(G.)49 b(H.)g(Gonnet,)g(\\Exp)s(ected)i(length)f(of)e(the)i(longest)f(prob)s (e)h(sequence)h(in)f(hash)f(co)s(de)h(searc)m(h-)0 3634 y(ing,")32 b Ff(Journal)g(of)g(the)h(A)m(CM)p Fr(,)h(v)m(ol.)f(28,)f (pp.)h(289{304,)e(1981.)0 3822 y(G.)58 b(H.)g(Gonnet)g(and)g(R.)g (Baeza-Y)-8 b(ates,)59 b Ff(Handb)s(o)s(ok)f(of)f(Algorithms)f(and)i (Data)f(Structures)p Fr(,)0 3955 y(Addison-W)-8 b(esley)g(,)35 b(W)-8 b(orkingham,)33 b(1991.)0 4144 y(C.)59 b(McDiarmid,)h(\\On)e (the)h(metho)s(d)h(of)e(b)s(ounded)h(di\013erences,")i(in:)e Ff(Surv)m(eys)i(in)d(Com)m(bina-)0 4277 y(torics)53 b(1989)p Fr(,)h(v)m(ol.)g(141,)f(pp.)i(148{188,)d(London)i(Mathematical)h(So)s (ciet)m(y)g(Lecture)g(Notes)g(Se-)0 4410 y(ries,)33 b(Cam)m(bridge)h (Univ)m(ersit)m(y)i(Press,)e(Cam)m(bridge,)g(1989.)0 4599 y(B.)61 b(Pittel,)h(\\Asymptotical)h(gro)m(wth)e(of)g(a)g(class)h (of)f(random)g(trees,")h Ff(Annals)f(of)g(Probabil-)0 4732 y(it)m(y)p Fr(,)32 b(v)m(ol.)i(13,)e(pp.)h(414{427,)e(1985.)0 4920 y(M.)40 b(T)-8 b(amminen,)41 b(\\Analysis)g(of)e(N-trees,")h Ff(Information)d(Pro)s(cessing)j(Letters)p Fr(,)h(v)m(ol.)f(16,)f(pp.)h (131{)0 5053 y(137,)32 b(1983.)1851 5280 y Fj(15)p eop %%Page: 16 16 16 15 bop 0 94 a Fr(M.)36 b(T)-8 b(amminen,)38 b(\\Tw)m(o)e(lev)m(els)i (are)e(as)g(go)s(o)s(d)e(as)i(an)m(y)-8 b(,")37 b Ff(Journal)e(of)g (Algorithms)p Fr(,)e(v)m(ol.)k(6,)e(pp.)i(138{)0 227 y(144,)32 b(1985.)0 426 y(J.)60 b(S.)g(Vitter)g(and)f(P)-8 b(.)60 b(Fla)5 b(jolet,)60 b(\\Av)m(erage-case)h(analysis)f(of)g (algorithms)f(and)h(data)f(struc-)0 559 y(tures,")32 b(in:)f Ff(Handb)s(o)s(ok)g(of)g(Theoretical)f(Computer)h(Science,)h(V) -8 b(olume)30 b(A:)h(Algorithms)e(and)i(Com-)0 692 y(plexit)m(y)p Fr(,)i(ed.)65 b(J.)33 b(v)-5 b(an)33 b(Leeu)m(w)m(en,)i(pp.)e(431{524,) e(MIT)i(Press,)h(Amsterdam,)g(1990.)1851 5280 y Fj(16)p eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF