_....-e-..... _
`
`DO .. ...,. _
`
`.......... '::'::-_" .
`
`Locally Lil\ing the Cune of Di mensionality (or
`Nearel t Neighbor S-=h
`
`...........,. O" __ . .... ~_ .. _..;.u..._ ... 100
`_olpo_ ... """e- . ___ 01 __
`_.tloo ..... _ ..... '_ ......... __ .. -..-_ ..
`... ; ,,=,."' ..... , .. ....... -
`.. -"""-
`
`of,
`
`_
`
`..... ".....0/
`
`-.. .. _
`
`',
`
`' ....
`
`~"""""
`
`W t_ .... ~"'_....-_"' ... K
`."
`......... 1_ 1,.,1' _____ ...! ................ _0.1
`. . . ....:pt>oo .. _
`....... . _
`__ I<e , ........ _
`Of , ............. .....,..., __ .. okoo _1 .0 .... __ • llt./l
`.~-Wo ~_<Ioo _of .......... ...-,00.1 cI" ' Io.iJ"'~~
`__ .. r......., __ ... ~_ ........... __ ....
`~_ .. _ - , . - . ___ 0.."";._
`Io~_ ' -, ____ 01_
`.'_ . . -
`It, i) .) , " • ...,., ...... .....,..,., _
`....... _
`_
`l ca- . __ .... . _.-.. ___ 1ft.!i"' _
`1\
`__ _ 0..-017
`...... _
`... _ ....... __
`00_"(0._..-... ' __ ... ";..,-.., ..... _
`,",<10 • . . - .. ' 'l;o,.,_ • • __ d ... _
`..... ..-
`_
`.... 01 ...... 10 ... __ ~< L 10' ..... ",," __ ..... ".... u--
`..... - . - ~"""' .... ... - - - ..... , -_ . . ....ty.
`_____ Io'-,. .... ~
`.... L.....-podao .. f .. __ ~
`....... 01 ..... _ __ ' •
`
`of
`
`I. Lr.t..od ...,.I0~
`rll'ldiaJ _ I l l ....;,pin. ill Eudid.o. . . - 01....,.1000- ...... _
`it ~
`, ...... , at ill. ,,,,,,,,,0I-..1< ___ .-kb .......... _'lJr...,... .... ,., ...... ,.,
`leal)' 1M .. Mel paaical. '"""" w. _ d. Voronoi diqJ .... [Aw1/ I [ 1D......t-
`",u. dj
`,~ .. pr<)jfletion..,\orsw:pooiUon r..d>noq_ ....... kd-Il_ [FBS1~ . FS F".
`BFTi, D-aoj and ..... <ap-poin. _i<pooo [Uh191t>, tibJ9h , R I"9~ , Yb tll
`for cm«aI """"' _
`ci;nllin. ... AIlJo ...... dl....,.,ion , .. eoll"tcIl ....
`I ttL Io' __ 'n" ~ ClI ,;,4001 ......... 111. ~ U W ..... ?LO
`, .....
`d . . . . . L" ' __ .ac"" .... _ t : .. _ . . __ __
`o
`.
`"iN' ...,. __ .. [Y .....
`
`,.. .. ---- ....... -..................
`.-_.----'-
`
`NEnVORK- I EX HIBIT 2010
`Googlc Inc. v. NClwork-1 Technologics, Inc.
`IPR20 15,00345
`
`Page I of 14
`
`

`
`All dimens>OJ\ d p ..... brp ... _
`
`trM '<d>niqu ... perform si&-'>ific&ntly be< ...
`
`,
`\han On:",-""," 00&1'" on" if the Ill!II'.bor of ~ PO"'''' " VC"'" ""'poaeD~
`in d. 0., in the cue r.l VO<OD<Ji <lias ... ""., i! ~ in<rtMM ~tiallr
`i~ iJ: ~ ""hln. oo1y if Ile]o ani "",* .. tw.- '" ,lie qn~. Tho!
`The """' ... :ion!o< ohio "", k " Iho~ CW, iII~, or.eit.....:ally
`main COfIUibutiol'l of <lois ~ it the aIpi''''''''= Idea of <If1I"'OU>"" """""f an.:!
`iU a.oaIj'Sd rot Ibe wWorn.Iy dinribut«l ~ypertUb.. In this ""Iq, with • ..uu:al
`<Itli.ni.""" of .~ a-. we shco< 1M; the Uj>«:tod ':IUI mmplooci.,. 01 6ndi."I&
`""&I'O£ .... ~ .. ~\...w. ""pea '" """"""",-' -.00 .he spaco <>:*' '"
`indepo<-~ of d, &.'><1 Ii:>ou in n .
`In .. [urUde!u> i>ypIttube the m·';mll'" du.~ bel""", IlI'O poims r;r<)1I'J
`";,h J4. IlJ .~ dou we """'" _"'" • ~bood ... ~ t..n .. it •
`"""" ..... " ~..:\ion RoI.:!Iisdistann!. A ~ 0 < p < 1 Olo>"_-ola,n., ~y
`t.tw ....... -.;,,..;U Iot.:ou the ~ ~ ..;min lhit..a::cb doma.i.:L For ud:>
`~of RoMp .. cob~", an ~"/ < I.udllhal. .lIoe_<:b ri.l pobm
`on avenge'" n T distaAce eaoputati_. a:>d th4 domma.. "'" work pcrfort:Kd
`No<i<e o.hat"/ it Indeper>do. .... of d.
`1Ii- ~y w,. valueo b R a::d ~......- probabilitico. For "".
`The pracl.ical .<iV'lfn_ d. QUI work ill tJw ..... elI !.Do ...... ."..".,. nbfu>ca,
`""'pit, -..ching 1,000,000 pain .. u~ t&1W"it.".od 1ft [_ 1, ""J'- ";';11 .,.,..
`~ 001" """', aI- R -
`() I, ~"" .~_ '" 30,000 d,;,waoo mm·
`pu~ ..,.j NCteedo ..w. probabiIil! 0.9968
`In thio enmplo .,. ,. () 7!l !ma>
`OW" onaI)'Sis. Arbitrarily hlP....."... ptobabili:;..on bo! ~ at th e_
`of disI.mco rom;>u~
`w • .-..:-~ WI ,tU;s _k ..... rnotlTatod "1-" the au'boo" ' <an< _k of [yiDW I •
`........ the objoctln II 10 buiJd • d ...... truclw. ~ ;>o.,.;deo __ "","" sul>Iiae&I".
`lime radiao.limi,ed __ Dtishbo< ..ro. [ .. ~ .... of q:lCfy) fO< .. ,,_
`w- With unifo<m diiUibutioJls in tudOde.&n ';>0000, tI>o :'MUI~ 0UUCL.ll'0S
`.uppon .arm noi&bbo<:.:,od oJ. only 0(1) """'. in OOn'..- ... .tI ""'"" oJ. thoo po.peI
`<lw ""ale b-,Iy ll'il~ u.. maxlmulD br.,*"",,1It dist1l>CO.
`Eatl, ~ in Ma.._ ""'&bbo< _011 io <un8)"ed" [DuG}:' Thote.a~.
`~te< .. "", "" :he .. &r<:h probIom, much ofl, tI.bo.&tin(; "" .~~: thai certain
`p.-o]«tioul 1.0<'11. • _trie $pAOO 10 :t 110. ... ~ ptOpertJ" ""'" proj6et.0d d'",nca
`an! -10m;"" "" by !lo.w in We original >paC\>.
`'The .wo mo .. itnpoo"",,, ouch projooetionf U\l i) inn .. producl. "",h. W'Ii< """'"
`in EI>ddoan space, ODd ill di.<anDII !tom • ~ ... .0:090 ........ n.... _
`.....
`,~_Iy Om in _k lDdudi.o& (BK73, Fni<TS, M VO, FS82 . SIuo 71j.
`TUin& t!>e Inne< p<odua with • rvxmiu! Mri< " ' - ' in eudidoe:ln Sp;IC<
`!leo...,. iFBS7li, FB F':'7 , BF7\1,
`ttadI 11) the ••• U·!.-,> 1»-_ of Fl"i<odc>am _
`R.onStlj '"""" «'CUm..,. d1Tido. ~ ;" r' b! p«>jocUns NdI clcme .. 0""".
`d"""!.uisboed """'di ...... ~tI, ru.triloutlon ad'P'"''''''' and incemeI:t.>l
`IN.I'cl>eo ..... descrlbfJo:! lD [EW821, (KP SSj, and (Bro lM,lj :~,...t1
`
`, ·'i_ .. od __ _
`'_ .. 4-4U",
`'roo __ '" 11M __ ........ to _
`"'r!.. L ... 0 (_ ....... _
`....................... ~ . . . _
`"'bit, """'" ,.,. c!~.,""" 0( ........ _""
`
`...... _
`
`;,...,
`
`"""" ...... _
`
`Page 2 of 14
`
`

`
`The.arch or ...... buLd !>u ....... Iblly <he oame .... .,......~ .. . kQ. .... built
`!Ii"'" ".D.:io,.n1y "'~,~ da ... •. Md """""lined to ..... tho w... cu' <:O<l<'di.
`n .. "" '" 011 DOdoes 101 & Ii-- """ Iewl Our <ri1<rioD /or pruning bn.ntIMs durU>,s
`_cll. ODd I .. &B&!~ ~ tho I'flmMY ¢)<Iuii:><luono ,. <hlf _
`atId ~
`<JU! IIW"..hod;& from w.uee ~dI
`Men """"'!Y, ,be !\eId" """';>u>UloAal """""'cr ha.o yWdood :nonr inteteotirl&
`~u JUch .. ,...,.,. (V...u! 9, ClaM, CIa37, FMT1I2] and -"or [D UIl1-
`VtfJ' ,-.tJy & twmbor ,. 1"''''''' !>aft _-..d "tiYilo,/; few ~ et!\<:ift>t ~
`<i,tun. wolh WOD.·c_ limo bounds for tho "I'?""%'''''''' ......... Mi~ 1'<_
`[A"l:'I~"' , KIe9T, KORll8, IM9ti. r - u;oioi' prcponioI Q1,andom projec_
`"'- berood .be simple ,...,.....,.. Ju:._ """"mon« fot::. IDt<ltiQno.d above, aDd
`add!<!DnaI !d.aI l" .. 1.abIisb _ " "*"" bowods.. Our...,.k ... y be vI<-ooed .. "".
`ploi~"t U\e t.c1 that ,&a<I<>a> pro~ ollJ'1ib."ly rudo<. data in & hypercube,
`an<! <:J .....;pho<Oood b&Ib <:J ,&dillS p<<>p<>ni<lo.ai to.Jt. both. ha> .. ~.""';­
`ance wi ....... ~ to 4. s... &!so let_tTl for """.,~ """I on ...... do in Y"""'.aI
`
`tiooo; tIw ",ado poI)"!1D1Dla1 "f'&C'. aDd ill. """'" easeI~ .... p,tpr ....... "& b
`f>S\ ~ in "'" ..ant.,... W, """", k that to be uoofuI ;., PlocUce, ..
`nea. __ IOeif.hbot a!pttlm 1lnat roquir<! ""y Muir !k.ou opaco -
`... n "t1'"'
`,equiJ-=-. A. dauooou fPI"', even Iow-de:g:ee poIyn<m!aI SJi'""'" ~ "'!'idlY
`
`--~.aI of ,1>0 papers meotionod""""!DeI":' in"""""" ,More<.ical <:<mOU"",
`-. ;'<1< """,;>1....-. _ Iy M>fk <IeaIin& orit.h ,,.,, special ~ shoulrl be ...... -
`
`t."-<! R.ouionl 01 si::aii..u binary ""JS lor <::>Mid .. od br Ri_ i~ [Riv7~i aDd tl:e
`Loo -."'! Is L'>o &x... d [YunTlli- Ab:> _ {BM &O] t>r ___ <:aMI data.tnoe-
`'u. " for cl>o n>rIf< ~ problem. FI:>aUy, ,...." _lis [BOR99] and [CCGLi9]
`wt.ablish DOCUiviailowot """"do :0' ......... r>O!Ahbo: Mf1:h.
`Io. <he foIlot<\ng -uoc ... ai'" ~ L'>Ii -,do aI&oriL'uns ~.~....t
`for Ot:.f UDiiorm "'.'r>6_ 5IrcI.ioa 3 sl- .. """""", anal" .. ,. ,I>eroo aI&>rit.iunl ..... ,
`indudo uk-.Jiatiooo of tho appIlea.b1e -.do tir:>e complexl,y ~"IIl', ODd !aJunr
`r:fimeDsioooJ "'_iMot Ht&bI:.hod br .....J) ... Finally, _
`p<obobiIi,y Exporimento ue ~ in sea"~ ., .. w. <Orl&r.n iD p" ...... a
`tho
`<liroc\iorIo fD< f...v-~
`
`""'"' ...... """,,.:one:! ill ...,..,.. ~.
`
`~ . Alpi <l .. ".
`
`1.1. Construction, A orwd, ..... if booilt wi, h ~ ..... 01 dot.a pou>U _
`ito
`le& ...... r~!oa:! """""WI, L'or ....... .,,,,,,,,,te .. & );d·'rer! bui\< (JB da". lhal h&s lint
`bce<r l<aroDror"",1 to ... ondom """"din"",.,....., Ccn.UUCtioD time "' .... 11' """"
`to be O!. .. locn) Md ....... ill U ... ,.,
`[..od, ;~"',"'" ...:odor ..... '''PU' & Est of
`c.-.."",inn P"- '''"'u,.i .... r
`poiD~. n.. .oot.'. !lot. .. I..' ..... ,i",'" A""";"t.o!<J with - . Irl, .. ior DOdo " a
`rMdou:iy .. Iected L01i. __ .or ,,<, .. hon!. donot.., I~ (""aD<lO rrom tho roox)
`T!oo """""" oi .. ,do _""~;" , "'" ~ '" tbo depth 01 """ rinus ant (beca.:oe
`the .. iI "" """"'" 0""';"'''' with a IoJI n.;. .... ;., .. , .... nocted '"' .. to be
`
`~ ... _ • • <1.0.- ,. ... " ..... """ .. 0;" coor<liuoo......- ir>o!ucod b:r • .-..
`........... " ....... _mod _""&- II tboa
`"""" • _
`_ _ ".,.... ,ho M-o. ... -.. _
`... "'- , . - . 0( • ~ __ ..kit • poo~ __
`,!to __ ... ,.,,"" _
`
`Page 3 of [4
`
`

`
`,..,honormaI. Fin" ".:><b:n -un ~~, th ... <hoy ..... onhono .. ,nuZOJd iD
`the ... taI ... y (Grazn.Seh.oo;d,)
`C""""'uction of .. ::.><It a:x.oiw of reod~ !u lnp~t bI. eoo.putiog tho "'(cid:173)
`.-Ith the :>Ode', _oeM a" and adq tho " ' (cid:173)
`I"oduct .... erodt _
`to ~ ~/I 0< nl"'>! OU'I'II' II", d<~ OIl II..i ~n. 10 , ..... 101 ,hi! dividm.( ;>om'
`;. d>oooIl mo .. In,ell!&ontly, e., by eompuWroS the .. tdlao .... tile in_ po<><luc<
`,~ Buo ID..,." unI!onn (-1. -+1)" --tint; .. j"', ..... ~ lot .unplid;y. Ldt
`and ~ d>;w"", an . - ,.::,.,.,,<ed ~>eI,. U .. tIOodo>'s il:p~' lio, """""" '"
`"""lie """""",. '''''' that oodio I:«omeo,,!eo! and """'" .boo ",,,,,,,,,,,..mru.. i'.
`~.2 . .su.oh, Tb......ro. ;. ~ by ~ """"Y 9, a ...: ... R ~ (0.1)
`&ivins tb. I""'JPO'tioftal sloe "' ....... &rdo do.c&in. and ~ probM>:lhy 0 < p < I :.:..
`.. relllU!d to '""" .~eoao ra;e." ""pocl-
`'Tht ir...,. prod"", 01. f and e&eh,., ir; Era """,puud Ii.,., r.he ;:niti ... ~
`old Ciaaooce i K
`oJ. ~~(P) ill eompu<ed, .. here. do"""" .. ". ... ",.I ... i ... <btribotioa
`t.m<tior> 100 ,,1IOmII.I &e...;..y with tJ:e >W'.a.xe illdka.tt<l by IlUboorip"
`Seaoh ~ 'ecro. .. ,..ay !tom tho ,_. For a noOo at 1e",,1 , the """'"
`< ,.~, >- ir; ~ IE , iII ...... iM i """ , 100 \Jt dlild .. """""'"Y ~ed Ir
`i, oo.ueda -/ then tho ,;po. dild iu " pbed ~ot.i.,. 1M' ... ;.,., < l, u, >-E ( _t. +l)
`both chOIdnc ... erpjoo-ed WJw:,t a k>f .. """""" ..... 0.1, the d:...ano.;. """"~
`bt\_ W ~_e>< it ~ &lid q
`ThiIIdtcioioD ruleio_ed ....... ~'" ""r~ uni!".,.. {-l ,+l r
`..... """, ~UI .. Wily uaDU:.ed 10 .... arbit.<"" eo. poial, e..t
`\he modi&n 01. """
`~ro~ values.
`Aft<.: each w......:011 canput.ui<>o ~(,. zJ .. po.rt","m .. 1 ,loo ;wnpYtion 01(.,=)" ../4
`io com;><noed U stn&!Ier I.ba.o R. tI:en R".-edna<! and t ,_"","".
`Thill concludeo lho detcrip<ion '" Cut . , ... .,;b aItooithm ....:t ..., ...... brlol!l,
`~ ,fbted iMu.. aD<i ~
`AD. ir::tpo>r""" i<b in kd·" .... .uch ;....,.,." th~ """'pu-.aUon of \he mini .... "m
`cfutatt.,.!::om \he q ..... y to u.. ",bopace a"JI,.,."""dill@,"" a -...de \0 boo upIor:ed
`Ir ,hir, <iAaDce ,,0000 ~ the ,adi ... rA "'_ .. ,. tbe node .. pru."Wd We do
`Il0l, ~ , i:.clL><le i' in "'" ozW)'$i$ 0< ""I'"'W",aI irnpo.mm;.at.ioo boec:au!oe III
`ow ItiP di:Demi(:nal .... w.,.;" r.he ~rA """"" .. ,.iaUy """'r dota ot-.. ,
`,his:w w nnWtiqIr Iiulo .ff«,. l".,,·,;~)·, ,hi> .. bocauoor.ho ..... dI ...... 10
`"'" _IJ <bp _uP "" tho ",inimu.m di><aoco 10 &">" I.o<te>" tho" the...-.:!l
`r...u ...
`Tl-.e ~ <J/.,hlo kd·" ... .,... i& ...... ti~ io .... oIlftnat.:" .... _01 ow
`~i>h= aIxM! 11: .. .qJuly '"'<I""", l ... bilo do.o<et,,\;na 6""'&1> i_
`<>0<100 to
`,~the fo<:IlI> .... b.. dis .. ""'.b-"tiM '" dwt ~'" ~thin a t..!!.bot.n lhe q_y
`is "".,.. uni!o%m. But, """n. '''''' ... ...::and ",oJo. .n....
`rmaUy ..... e:nark that the l-cutdl" o.w-<h taL:n oJ><"." "ugh, boo roplaDod
`";\h an en1.;>ei! probKiEnic ,,"uRin, ocl>oono 11> .... ~ ",uI:.ohilitioo !::"'" out
`tulalySs don to tad! diId dud", ..... ch n.. i>!oh .. bir"' .... cl'n.d \0 the "lOt
`.... tI:en multiplied ""d _do coo,;".",. ,ic_"",d ",,,il ..... , .. ,,1, I.aIlo boeIcoo a
`.~;ho.mold
`
`'1'" _:>me boI!P. c..;a. pain .. M<I quer;.. ... uniCOImly dl!"ibu,ed ...... hiII :!ae
`~be [_1, -+ 1l" Tbe Euclid .. ,,, t!istaDco mouio app&, and 1M oo.ui.:rIam
`
`, .
`
`........ yo ..
`
`Page 4 of {4
`
`

`
`cilnan.,. 1>0\_ ,..., poUIt.O in un. IIpaOO to 2Jd. W. ClmOid", ~;", pcoI;Iem 01
`/ind<.->g u.. _ ... ,,~ 01 • quory 1 ",thiD oome distlOlIU i .hot :. &.........."
`p'oportion ollh. ". .............. \Jl"'poiD.~, i. d .. m./ii with 0 <.il: < I
`A"1 ~o.i' _ _ .. ai- ,iM to a j><ojo<:ti<:x>~. IIU!'¢ng ~ E I" into I defu>ed
`It Oi ."" .. Ii". ,hal di!<ta"", in IhI! =.p d uu. proj...-.lIIOl Me
`by .; :r,_;'
`dominatfId b:r dist..,.,. in Iho dotn.oin. I, .. Ulil roe, u.... kC.-IAN@X]>Ioi' to pnmO
`1><_ d~ b,&Dd>· ... ...s·bo<.:nd -.-th.
`U T Apl-.t< the disIa:>co to Lbo ........ ..,;ghbor ~ so Iu d~
`• -.d!, thoe:I thil lac!. impIlto LUI ...,. ~ of !.he ~ oI,adi"" T,..,,· ed
`at the q • ....,. 1 m"90 tlnde< any". iflto L"" '-"'1!.1 [ ... (, } _ T .... (q} + T]. So!ai·
`\n"ot oeuch may t<>Dlide:>d1 disL"S ... d an1 data J><>intI ua. PfOjo<. oot.liCe of thlo
`!~. Unllke lhor 'd-tree, .:.;,,!, 5_ cM.. ..... nOghIxn ... tb. cell.ai"'y ..... ..-ill
`CJ:llWIder ,andomitM .........,.,.i<:ao that ~ with ..,.",. opecif.ed ~.
`Si.noo 6 seal .. up ~'-'ly wi.h ../d. Ibo lo.....-.,.l &<t>n [tr. (q) - 6 .... (d -Ij _ ,
`and.,.,., !.he kd·u .. cat! ~U, ~ruoo ~ n~.""': pefor.no & """'''"
`oxb_i ... oearch.
`Bu. ill OW" unib0lll1 , ... ">do", '"'WIt!. we will ,bo-r U!a.L """ ~ bo.II abou. q
`P<O!tC:S 10 & di.nril,,"ioa abou. ~(q) ha""" emm.. .... ~ This is """'" it is
`poa;bie Lo ...... inue to ...-,1 .. 11611,.. pn.mr i"-"" .. elli:ctiYdy .....,~ .. d ... 00
`Sioco d i :p_ ~ "D< alf"" ~,,' ot.;i"y '" l'">~ ~~ ... I~ d •• <W"X 01
`di""''''''''i'r in our~.
`w. __ proce«l with .1>0 dee<,lpt;';".">d ido.oli<ed M.&I.. ... 01 our oIpitbm
`with"", fdIowing I>fOP!l«itioll, .. hich .. tahIi!be!L '~"<l e!.",..,..,. bot "'" cfino:n..
`oioA&i _ ' "
`P1IOI'O'lITlON 11 .) WI ~ boo ~,.,.,...,." .nil....,;tor", _kt X aro":, o..u.-
`.......... '" ___ ..... ,"f..ae.. "'" bOlO dirio......"..j .. 1 of ........ ".(X l h4> "' __
`anJ _"'" 1/3 - ~I .f d"....,..;.", - ~ !<>d>. ond X ..............
`........... nJ C.......dn ...,., E It'" ..... ", r ~ •• "'ft ...... _101" '-uJ. ...
`tilt ,.,.,_ .1. />011 omt'" III 9 ol....nu. 1R./ii TIw:> ~ .. ", ."" _
`.......
`. ,
`.". .n.mkn"" .f HI-o ...... tr ) h4> ....... r_(q) ...... ..".,..... (R' -,~ ~I
`
`f'llOOF The V>tianot <li ta<b """'poDmt 01." i:L lid""'" < ~,~ >~ I b:r
`dl'lbItioa ODd ,i"" <:OIt!1'O"l"'U ..,~ i.i.~ Cu"liiLlt< a , ... duoI:L "'""aOl ~ ~ -I , .. W
`H .... &""'1* b"l;l ~ --'>fu"'" thal tl>o _<e of """" ~I II I/ l . So
`u.. ,.,......,. 01 oad> ""'" 01 < ~,'" > to I/ y , ... d Lb. .. oo.lM"";'" innot FQ<Iuct
`to the« 1/3 .. ,eoquited. "'_ tach ...... ~ 01 u ... 'I!! ",!wi me&ll U'O"" """
`< ",:I ;,. bas "..., ... ... 0 -
`lad palt I) lo I!$LahlW>ed
`... (. lls """Lr.td .. r.(9) by 1iD •• d'T 01 ...... ' p<o<!W1 So .... =1 .........
`wi.M", \noo d 8 ...... 1'.,. thal q so O. 'low tho inn., pooo"", <lit..., ,..,<\0<0 """
`__ on is easily seen to ha.-e.-arianoe I/ d. Scalin& 000 01 Lhoom b:r • !.octo< 0I2R./d
`increNes Ibo .... i ... .,. br • {oc"", 01 4R'!l, 10 <h .. it bo-com. (R' "" ""lUlfe:l :..
`pan ii).
`0
`~ III1d eoo.sideo ...... "u"..,·, projo<tioo r .(q} n- tr,
`~ Ih some uni' _
`p,~.,., 1 1 ..... d i~ bype<oube ~" .... tf!..-:t;, thoo projoctiOD 00 tIw dau
`poiDLs .-ithln \.be Com.ab 01 ..arcb .... dinriixlOd about ".(9) with vvw.c. ""
`ve_ ....... 4R'.
`s..e.... Qista..,.. bK_ projt<uC point.O aze don-iu'e:l by <heir ~
`thal I-. (r ) _ ~.(q)1 < 2R.,fd fOf ""~ '" ill '.he """ch docuoil:.
`d.isunce it is 01_
`
`Page 5 of 14
`
`,
`
`

`
`So ""I' dao.a poi~ .. ...w. proj«t!ooA fa.thn t!wr 2R./J. frQm ~.(.) """ be
`O>I!fi<Ienc!y n:Ied 0." duri=& - .. I. 10 this II."; pruniq ~t kd-..... (aDd
`maar ro:buod .", .... urft) a;>Ioit to.,.-oi<l ~"" ~ polo, dUrin! _
`.. ,
`~ .. a:rdo.
`Bu. :lOtio!> .bat thIo pr-Jrl.il:rg c-IlID dii~ ,JlW ... "" ,,;11, d .. m. cbe
`""""""" Ao. remit !tar<i Pl"1D\ns 10 ... )'!<I~r
`P'o .... .loo. -w,ce _
`I~.." .,.,. ,his ~_ ,iNt to the ....... -j""", ......... oluJ b
`......... , oett,bOO,
`Maldo...u.s kd-\, ... it! OIl! -.lng.
`Ser. oboe, .. Ih ..... . CODSolqUft><e of tho ""'Ira! limit t!>oorem the diouib<>-
`tiooA of ?:r"l""ri'''''' 3 1 .. e U)."..~ClItCr -",aJ -
`aDd .... ... mark ~ .. a
`p1ac""..ical ","",Ie this;" a ,000:1 oppro>in,, ;""; c .."" for- ~~ <f.rn~ . So
`h:<n this painl on L~ cu:r .....t)".11 .... ..;U oimply ......... DOnII.aIi'y, i,.. ~ d io
`suJEOomb' iuse 10 Ilw I .. devIatloo ftou> ........ atity is~.
`We::"" .. ,Iv. at ox. of t.. ... "'"""'" obooo __ of this _
`...
`U>u the _
`~_. ptojoclion if;,..;uw, <»r>t<Um ~ cf",(, )...w. .. bnruUy bi,gII &I>d
`easily ""1,,,·l oted proOaOi:ily J> depo!nd"~ .. ",",y on t1is _
`and """ on II
`RecaJ <hat \he t..'"ft n ball<i :ecuxs,""ly bioe<u tht ... 01 dao.a po:'"'' uori.q a
`randomly aeJer::uod .. by ~« i18 p<o~ imo It!! and ~ht. b<ancbs at a
`cu, poial c "'&I" 'no 1DO<fan. Ci_. quo')' ~ we P'''''''''''' of \heM! btandwo ri
`~. (9) 10 &l Ioa,o, 10m. cutOIf dis,""", l fran "" w. r.m to thi< idM. .. ~
`~-P.O .... IT'O~ 3.2. ~ ... "f C"O"'O Nt_ t '" ~ ;':"{P) =~ pnM ......... 0<011
`cdMo ~ ,... .... , ~ (_m"" ... c uutt ...... m .....".,. 2R./J. ~ dot
`ITO"") ~ ~ 1 -" 0: tad! - . , ...... ~.,: %) kw:tu cit. ~
`do.stnhoon ,.""."", "'" dot '"'" ,." .. ~ ....... 01 ... "..,tv..tll ..,,,,,,,,,,,.'
`PlOOF. E<!U&.in& :.he ~ !.a:Ju,e Iale I-p "-;,h \!Ie ...... of Lbo! d;"'tibo!t.,., ·.
`poo:\;.....a;] si- 1 - ...... (1) ., I - 1'10 1 _ . ;';'(p)_
`0
`
`Api.D. :'0'" ,M<. thit cutol!" dio~ l is ~, despM 1he lace. "' .. .:..
`obooI_ aze of our .... eII dofnain .. ~ with .fd ... " _ 00 W~......,,.,..
`"" .. bTN a.u:cJe " .... ~ .... eII ...... pjo,:rit;" and s.>«:se probf.bili<)'
`Ft.p, ""oil fnmo ~I"'" J I, -.1
`P.OPOSrTlON 3.3_ G,,,..,. n diu. _
`"''''''''''9 d" n(Jus "), :t.m ,) OK~ .ureA ..u ftI.II '" ,, -
`!bAt flCdtl U>\m ""r _
`~, :I+,,.(t). onJ """"","",". 11_<1>",,,,,,,,,,,,, E.dod",,, rtu.""", .. a. 0001, """.)
`dot ..-.it onJl .. ~ ..ell ~rt]r "" ~kT IA"" '" rJoo' •
`?0Qf> R~lIil "'*' ~ t:<pe<"\ I!raI ... ....:, DOd< <I :.ht !.rte W. projea;oc of
`01 ""p<e>:imudy 1/3. We Ii:< <r<r' .. t.erll.ioo on ~ oudt ...,.;..nth "", .. _di,.
`
`tho ,-.ain.:n& <!blab..~ .. w'1I ha.., ""'""/mfd:ao. <:kdt 10 ~:o.OO ow'~
`
`uni, ..ao, • &Il<i """""'" W. r:ut pol.n it exa<:\1y ....., .. ...:I >ali>.cco ;, .,...,,1,(cid:173)
`l/J_ Siz>ce .... ba .. ..,a:.ed <ha, "'" quu;'" "'" abo 1Dlif<rnI~ d.io\:;butod. v..;r
`proj.oct:o!> is idonti""L So ~ """ u.sily coJcu:"" Ihe ~ty b !hal • q-,. ,
`li .. rrithiD diota:r>ce t <I:l>o uro_ In t..'IiI~, bo<h 1m a:r>d ,.." lxllr>Cb.s mu5I
`be .. pbed O\b.....;.... r.1lI ;>roMhil:ly I - ~ _-e eM P'~CDe so \hat 0iIiy one
`is expb-ed_
`ibro_d.""" <ail (~d I):' l-. ,(S!I) bomw!lidl it killorrr"s!hat I-~
`is ',"",,!his YaI,... So ~ _ 'l't,,,(1) _ I "Thea the ex~ r>umb<. F of ~
`,_Led io 2 • •• ( I - ~)_ 2.l/.rl)
`
`Page6 ofl4
`
`

`
`sm.:. d ~ OOos ,,) it is pooo;blo 10 """""" Wlit """'on &_ ~ 10 leal ~'"
`..,e ~ ("-s. tho! <:&I>OIUe&l t...;. ), ....,d,om ",.;ton rill be ,..,,11 00, uo:!
`our ,aaodom orthOMr""':iution f>'~ ron ........ ,ly IOU<:-.:I So """"f'I. lor ..,.".,
`.n.ec.. •• 1»dI ... d"'opnt, it iI ,.....,,,0I>l00 10 _""'" clw .....-r pn>joctio<>s uo:!
`;~I<l"," oIont o3lh IOOt-leat~ .
`iLl",. p!oI;.h;l;t;'" ai"
`s;.,.,. .. v. " .... dopo.h ;0 Jols.,n (_11 -.me;><rlect baIanoce) Ute _do ";U
`visit roc,' ~. T'hM is 'l"'o, " .. " or ........ , .. tabIW>i"S I)
`x_ the ","",,,,, ,..;pbor ;, ""'-l __ heo--e ... leal at thoo 'rH. To ..,""'"<!d,
`Jl"UI"O ;. '" 0fI~ oi <he q. .. DOd.o ....... p&<h up 10 thoo root.
`,be _cb mulIt _
`ni. happeno .'ilb proboroIj~'1 p..,' ...ubIo.hint, ii) -
`",1o.eo: .. lacIependenot!ol\oooos
`~"'" the .... b<>!"..,>lily at~ ... .... at pr<>joc_. uo:! tho "H...,ption of. wtifot-o>
`da<ribulion.·
`D
`NDCir:e tb; ;.'>e e<pODcIll or" in propositioo. 33 is ,.;th;n rOo I). AI$o, tho
`~,u&!' d . n(lor.n) i, t>OI "ef"J" mtrict.i .. .....,. "';.., ..... the nwnbo<
`.. n·;·1 in d""" _Iier t.ec.~niquel eaa bt u.><d to> ofiriemly
`at <W& poiDt.o is et; .
`Ioa4e ~ neipbon..
`Tbo ptoJ>.i>ili,y .. t.itr .... oi l'!~ticII 3.3 i, =romely 0Dt>Sermti... T!>e
`octuoJ !.Uur..l"obabili .... ~ much ~~; i) <lUI aooITSio hao .... ;>Ecitly
`.....oed that tlto Q&«J" aI~ p.ojecu ;0 . poin' ox..ctlJ I from tho au. poim..
`l~ Is t.ht _iI c.ue. If ~ ~;o~, ,hen <>Ot.'>inc ;, pruned ODd DO
`.,,..,.. ""'" be mad<; uo:! i! Iht; diJ!1.AD<tO io 1arlO', .be e&ct; .. cutoff.r...a..c.. io
`dK\i¥tly iaaoaaed: """ ~) we haTe -=ed that u .• .......,.t ~lIbor i:! ~
`jus< -.-ilhin <he domaiD at.....-cb. In""':;", <tueri .. will be disuibm.od wi .... <hi>!
`~.
`£..., ..;thou, ~ t.h..., fo<""" "'" eaJ.cuLor-ioou suu, .. t ,hat. ..me;".,.
`.-.-d> io pcosiblo lor """'""atd:J !&r, • .u... of It
`'IabIe 3 ai- """"""'" values lor oeIec.ed valu .. at R &Dd p For """"pie.
`if R _ o.~ and p .
`I _ 10- ' _ 0.9999 tl>m 6e """"",",,' ;, '" 0,i066. Gi_
`n = 10. 000. 000 data poiDt.o our to'Stl!u sute W. to) rm<e tl>ao ,,'-- '" 9.1&2
`"'- poodun opet",ioao will be pethmod, ODd tha, the......-- :>Oighbo< -.r.D be
`~..;u. ~obabili'~ 0.9999'-" '" 0 9!r.l' Cboo!in& P" 1 - 10-' ~
`10 48. 19-1 """" ~Qd:><to ..;t.h tloe ~ty 01"""""," ~-. to O.9999'n AU
`01..- ~ti<:<Jo are ~Iy ~t of~.
`We """"n"" ~'>is uample to ill ..... "'" the .... 01 fores'" ;0 ""PO"" perlor_
`in ..,..... ""'\(~ Lt.«< ... orilJ 5:Y< • tbo<><",ic.aI COJ1I«l_ 01 tbi.o i<l .... COfltiodt.
`\*O~. ~.,.;tbp.I_10-· n..... ... 'M~oI,andont uoi,-.
`;, i .... ""<>det ... Bot.h '""" ......... ebeci lor eod> quer \\" then u;o<cI. a faibr ..
`Ute of .. ( I _ 0 !l9j7)' _ JXJOO:l529 .... .<1 2 9, 152 • 18.32-1 i.",.,- p1oCUoCU .. "
`.""'" t.hit failo.a,. , ... ;, ~y bout< than the 1 _ 0.999977 .
`petIor."..j.'
`mne. ;X<oducuo
`o oo:JJ23,..".w'lIl& hom . !i.o&le " ... "",,,,;1 . I-W-·. and ~ _
`COODruml"iaD io Iioubled n.io .,...,,;>1. illusuiU.eo .;,.
`.... """,pawd. bu, _
`' po!I<e-time deIi&n ,radeo« Ihat an....-beD. ~ our n..... in pt~
`Tbe nMuloJ,~ of thio ideoa Ieado "'. roo"", of iDd<pendom lrCa_
`!tecaII tba< a faLure ..... 01 • ,in&!" If ... goo.o, oJb<it Uo--Iy, .-;u, n By wilt!
`"'~ ___ ""," ... ......-·._.,bab_.,._ ...... ", ~
`. "',...,.,., .. I>oolo .... , .... .no..,
`..... """- ..... '"""
`
`.~
`..... __ . .... _
`
`"' ...... _
`
`Page 7 of 14
`
`

`
`•
`
`H
`10-0 10- < 10-'
`
`\1)-' 10-1• 10-"
`
`,
`. .., O.'l52 0.179 .. ~ o !2li .on C-618
`.00 0.17' 0_26~ O.33i .~, 0413 .=
`Q,1lI 0.(9) ~J41 0.117 ."" .~, .".
`(1.05 .~ .- .. -ong . "" "'"
`.~ •. = 0479 O.~7~ .'" .... .,~
`007 MU • m ... "" .~ .'"
`'00 .... 0..642 0.746 cal3 .~ ~
`".M .~ .. ~ ..,,, O~ll .'" .-
`• W .... ... .'" .~, "- 0969
`.M oeu 1l..S1O 0.597 O_~'11 .... 0 .919
`." . ,., . ., . ~, .~ . "~ ....
`"" "= .. , C.1m' .m .m .'"
`." o 1:l; •. '" ..... .... .... ....
`... .,., .. , 0.965 0.99;; . '" ...
`... . ." . ~, .... .~, "'" . ..
`"" 1l.371 ~.!179 .. -.m '000
`." . -.... . -, .. , .. ' .000
`.w "'" 11.9'71 •. '" •. '" , "" '000
`0.19 ... .... .'" , "" , "" .000
`." 09'21 .~, .'" , .. , "" , ..
`
`.000
`
`TAlIL~ 1 Sco.Idlco;8 au! "","","-;'" L ~ u.., !""Iuire" n'
`" ' - prOdua <>pcr:><i""" """ _~. 'J'boo ...... """1 viii"""
`~ nriouo ~ of R &ad p!rom (lou ""01.,.....
`
`~ !lUb:;""", ........ """'" .. tho ~ of poI~ space 10 ~ 100
`
`~ ..- on~ <:an ""Ol ,~ ro.eso. .. '.0:1"", t&lO to ....., .. " ifICI_ .. hi\e
`t!>t additioDal " ..... To anaIyu "';0 Ie; >; denMe Ihe ,,,,,,'s d<p<b ... d ""-YO .......
`(1 - P')' si- !.he (><'ObIlbiIi.~ 01 WM 100 . fonsI oil! d"ci<lc\ ..... doc> U ..... k
`""" be """""" Ih<.I <f J _ , -(1+ ... /oor &:I)' < :> 0, ,he:> t.It.io probabili\l..ads to
`t<lI'O U ~ ;W w.l!be n}~' smo. % _ q,,, ... "" .. her of I""", •
`n -- ' .. ol ..... in c.er.,.. of n. Seo.tcll Ii"", (<he ,,~ of;",..,. ~~ opo<a<lono)
`alao ;IICI _ by 8 Iac<or of r. Spo.ee incrt.aoes fro"Ilintat \0 DUm)- FUo.a!Iy. to
`:na;:>r.a;n it>dQ<ndfn ... ..-e "' .... in",_ "'" bom bou:><! on d to n~ \oi 'IJ_
`[~iI_en' &om table 3 ~h .. Ibis ideo. _11.1 !Of OWIr """tl.,olR&Od p F<Jr
`""""'pI.,;r R .. 0.1X> .. ">d p _ 1 - 10"-0 ...... <he orilinol ~ 0..;66 ~
`~ 001 .. '" I to! x 10-0
`;" !0110 ,baa the tahI<'. p<~. Bo. ;, dod ...... _.
`t .... !a.-,. val"", of R L'>o exp<IDOf>I. ,. .., clooe to I ~ """
`:or ubitrary R ""d p
`odded ",."pIe;.i,y 3O.akeo Lbo :.otaI .... _~
`Not. tlw. O(noi) opoooo io ",,-u;,ed :0 ...... tho d ..... oIoca:,. Ill""'""'-..... 1>0"
`001.,. 0( .. ) Op&ce io neodod 6:>t ,he lnwiot """ ~ ",IUd. pOint :0 dat .. olect:mo.
`50, in poaaioo • ..., can a&rd O(cI} L-"'" .1Ii:" , .... ..a.inio,liDea< ~ r.. lI<KIioe
`"'" __ tlw. in tu", d'm ... ·ion """ cat:! euily alfO«! """"1 1: ... withoul.......,.
`:'.aIly aJk<:ti:>a space roDSooption. In llI"",y it """'" Ih&1 if d io .... umed to 1'000
`
`Page 8 of 14
`
`

`
`.. an ~ • .r.alI pc>wft of ~ .. ~ ... Xl, then tho _
`
`r"..., OCCU",", IlDear
`
`-R<!t,.,.";,,, \I> out cboico of "". [-I, ..-11" bn>t"rcub<, .... <>boon-o <Iw i) A~ 01.
`
`oor ........,...,.. apply Imrned1o'*'r to [0, I/" aflO< eMlponaati:lg f<Ir tho ,hifUd -..>,
`' III u.. d-<\il""' ..... na! .yper<pbe",_ Th_
`""d II) <Iw our atgWl.OBU OWl! *'l .
`I.blI __ :!!.a, ." dot produtO; of. laadom t>Di1 >e<\M and .. "'4don> d"'bew
`hat n:;""'" Il tI, 0I>d tho maxi"""" ;r,letpOin, d;st&l>Ot iI wns;an., 10 <he
`_
`projKUon of. propon.ioIuJ :>fl&htalloo<! _
`&100 l3I1o wit!! l i d.
`FinalI] ... ,..m ... " ...... II ... al..-r""; .. to f.ortou, """ CUI t..illd a ,,;,w. ....
`in whi<:!t -.:II \o¥o! .. DHrioppod, ; .. i __ ..... ".' .. "" ,tored ;" l>oo;Il tbo
`...,. aDd,.;e., "'~ This eE«lin/y ~oeo (alld ... III !I ........ Ii"", - U tbo
`" "_ of polynomial s;>IoCI (s;'~ . """'"'""" !taco"", 01 0Yftl&p at _~)
`
`4 . Expec;",.mt>
`Th e::n6rn> OUr ar...tr* -e YfOte a.n ,\ ..... 31·C PI"SI"'" 10 build a.nd """,ell u .....
`It ~d, n, R, P II lOlA""""''"' in additlooo to the nun:bet cL ,...:101'0. q_ to
`...... ..".;. I""dorn seed.
`"The data poIn" ... e <iL;buu.! wU!ormIy;" [_1,+1"4 Q-a..,.._ .....
`b)' <bocoirlf,. dati poUI' ~ at rudon::, thoo.. ,,,,,dom WIl. _~,..,d !Ot ....... ,
`tho SUD'- 2 . (I-.)~R~ -10 thaI <be """",- .... joaI i. ....... of.h ....... cl"lomain.
`W. \1M. eo _0001 . Thls __ ,Ita> ............. "'boo """'" within ..... do<:>:om..
`. iI ,~led by IIt.1Inins -,mil random
`An ;"dued set cL pro)oct>ln _
`""",on &ad onhO<lonrom;, them in tho O<IIIda.Id....,. t.:h 1e\-eI in ..... 1. .......
`• '" """rMpOnd"'a- to..!,io _ .. itaprojectot So.Ioo_of~ ... "O(Io« .. ),
`and in pno:tlce is '" 7 10&. .. bee ..... tho .-.Jtiog ,,~ _ "'" 1'<',""'ly \>alaDood.
`For ,inP/id' Y .. ,.0 is ahrays used II I. .. an poi'" duriq t: ... """"I'll"""".
`1111 or"'" to allow- ... to lIimulWlODUsly ""pko-. I.,.ge n ""d 4 without ....-diPS
`.,.,.;JabIo RA . .\I, .... ~ til<! data poinI.o to he seorthed .. iq • ~dom
`~cnr. ...... oeed lhal sulI\ceo 10 """"""'" <bem. A •• ....u. _ C&lI MOiIy .00,.
`n " 1,000,(0) and hlgbet ill aI",OI\ Ilbit .. u,- hlp dimonsion
`f"i&url 1 illustlatal dial ...-dt oomplerity ~ in d>e ~ <Ii i=e<
`p:od ..... 01""'0.1".,. podormod is \"'~ "...J~ <ir:>en,ioD':nvanam - conIi.nt:.in& OW
`~ Sn U>t>l _~ ~ up Ql"Jy w....1y...,lIt dimelllioa ",u, t~ """'~
`of.., """" pn>duct opoaat:oo.
`t'(DIoe <Iw for .impllcit~ "" reg..-d .., _
`prodUOCt _~ on<! A E'di ..... n
`di.iu.nce ","",p"latioo ... bIvin&;eru"txIJ """plerity Aho, tbo tablo ', reoo.tIts ... .
`clll<!e U:e ."",hly 71or,. " iIutft produ",", r..,wfl<! \0 compo,", the quory'. project"'"
`.t ..m ~ of. the " ....
`RoaIl that DIC &M!yoIo of /aiIw.~ ......... qui" _ _ It"ellld_~
`C<Icli= ""'- Actual rail,.,. ""'" for.-y....., in Fi3ure 1 ___ ~..".."
`th.on ....,.. he o.r.al..TS!s For uamplo', ill. tbo 11 r. 0 20 cue, anaIyP predicta 1Iw
`1M -"'" ...m II\Iceeod Wit.!> prQbai>ili:y "" O!5, lind tho .aual .-ah" ;. .. o.lli
`I>_..:.a. <)DO lUOCD '" t:tir'" the moder_ .......... p" 0 Witt ou.- Sludr illIw we
`~Ye ttl<.fU-lP<d that nI .... fa! dos . ... to ""'0 tfSIl.!t in 00 ~ UP'"'i:»er".aJ
`
`., ..... 9_ <be limit..:! nurn:.er of. q_ we ba .. time 10 pE<fu<m
`
`W'<O<IlPIlt ~ in OUr -.;bof..,.;th kd-t. .... ~ (F' BSn, r B FT." ,
`B rn, S-SOj. W, .... iruer .. ted in .,.;y. ....... within. opeo:fted distance cL t.!Ioo
`qu«T To f'tpI"Oducelhit "",tinA, kcl-u-.o --.:b" inill.o.li1e:l II ~ ... ~
`.t the opec:£&.d di<t ...... hu ahoo.dy hem _ cd.
`
`Page 9 of 14
`
`

`
`,
`
`,
`
`I
`_ ... -
`-~------------~
`:;::; -:-
`
`-...
`
`--.~ .
`
`-
`t-
`: , (cid:173)•
`
`~---',. ---~.-. .... ---------l
`-
`
`•
`,.~:;;::;;:::;:::;:::;:::;-;::;-;::;-;::;-;::::! ..
`FI(;uu 1 """""~ ra<!i""......:11 oornpiony ill..,.....,.. willi
`""P'"<'''' di~ - o:<>nfi"""" ow anal)"Sls. W. fI>eUUfe c.be
`.,..,...,.,. of __ ""«ed. EacI:.-\lit ox,"p:>ndo to .. Eocli.dun
`d.' M' """,p."at~ In ,two ~, the IWIIIbo< d. unim"".!,.
`cllltriboted data poi:llo " '" 100, 000, BlId I. ... » "'- OUt anal"";'
`is 0 99 F.acII _1 is 8"" .. ated to .. \0 be "4bUy ..... 'han
`~ 2R."fd!rom oom~ d .. o_ eiemen', SO <Iu< out .>dIu.(cid:173)
`U.r.lted ... &10 aI_ys "'~ . ThI: _ul" oil, OC() stIdI 'U"",",
`.. ~ an '~11¥<1 .0 pl'<><lutt eadI da ... ?OicI. OIl: aw.!"';'
`p<fdict • ..,......,1 "'"""" ol.~J 3, ;2, 19&r. 13.S;3, aAd
`40, 114 .",.,...pondinl lO R val ... of 0.01. O.~, 0 IG. O.ll, and 0.:20
`~ .. I" n.. ~0Dta! ~ """P". ,",1 with ~
`;., ~ an doo:ncn.atod by ,,,-,,,, by " foo:tO< cI
`esU"'ateo, _
`_tJIcimaLOly two,
`
`A ,eoeIIt \;.d.,,,,,, implema:,,,,ion P.lA t9) .. .,.,di1ie<! lot """ oxpeti_ .... It.
`"""' rtIIIti.. ..... IU~ alte!'e<! to ~~wt ,od!cI-Ilm~td stUd is de5efibtd a:.:..e . ....,
`~ cEmribu,,,,,,', .... "'PIO 1"""""" is ~ to:epcrt the a_",~ numb<::- cl ~
`\al!<e """'1>11I .. 1i0<' .. po~ i:I ,_ '" each Q\!OIJ ~ in ow- eulie:- p;per.
`jm ...... que:-ia an ,,,,,,,"a.;M by "&r<'~ "" .. <hu.h&oo _
`, &nd ~ c.be
`. poec:£ed diou.noe away in .. ,an",,,,, di......,.. So _,. QU<O"!' m our erpotime<' ..
`Loco.teo .. .....,.... qhbo< wilb", ,he ,..:ius <ll~ . . u a otIf-dteck 1M ""'1Ik
`provam i/o lunb<r modjliod Lo nrify Ibis -.ditic<> A:teo ........ ~ a
`rlif "", """,POOriJOC is;>oaib" btt"""n ow m<'Ih:>d ond g_u ... -.:th.
`!'rom ow- onaIyUo j ; iI <loot \hat kd-I<e< _oh...;n "'" a3ibi, I. ... $ilIU <Ii.
`tneI1sjrcW in .... iMoo. aDd Ii.&llle 2 ~ tb ~too:t(Wtf , 1U.I'd! dill. ,""",""
`,ap:d/y lioI ,I>< R ~ 0 10 caoeo ,!\at the "", io....,,<iall! in<!feai ... by dimons;or,
`len Br -... ... (fi«uro 1) ow "....J>od __ et£o:ti .... for arl:ovBlilr lli&-~ dinoen(cid:173)
`sion_ ReoaII , """~, 1.h&o kd-tree .. >«it is ._"",otd '" fiDrllbt ......... ' qi>l>ot
`willli~ in:lle domain, wbile ow ....u.o.: -.n:l!ail wil h >0<:>0 (C>ali pro!W:>ili" .
`
`Page IOof 14
`
`

`
`.. --
`
`. ¥ '
`
`-
`-• • - I
`
`• > •
`• >
`;
`
`•
`
`f
`I
`•
`
`FIGU RE 2. P'opor<iorW .1Oci .. kd-uee litorO compla;ily is ~'"
`"""'ant 'O'l,h respect W d_ , .,..; inct_ rapidly fOl R:>
`o.lOllOthat Irrd;..,..,.ion 100","_"" ill -.IJ ""bo,..i,-.. F--.:i
`~ visit ",,"_cis "'. Euo:Ido&n dls....,,,, euoputatioll . 'Tho
`I!tImW ailU'.iIon:>Iy dlmibuted <Wa pain" n. 100.000. &ltd th.
`~ allOO ,andO;Jm q"":-ieI S-Ned .. to 4'" I .... .... 'osN
`'" plt"i"". nc!o <!au point.
`
`J\ primaoy moli.atioB lot thio 1'<'9"'" ..... ow d_ r in [Yi.o!l9] that kd-v_.
`and .. rdNcd &<'IICIoJ"",",Im! call,d a ..... .t_ I"'"'' ,.,._ do oxh>bi\ -,cit """".
`pkrily Il:.M is \Il,...-...", with ' - ' '" tti""",",,,!or .. <Iomainol ...... ,on,,,..,...._
`and .. _iaI "''".lip <M!I ~.i"" .ucl> art ruliled ".,ly fa. di ... p~
`-au ,.m; The ""P<'imo<t' ropoote<i in IiIIUf'O 3 """Ii< .... this. &ad ill""' ...... tho
`fun~ly diffe ... " uympu>;;" ~ (with ~ w d) of kd·"!e-a.
`and"", ou: ...,,,,pr.rur.s~ . T ... a..~cf :i&w~ 1 .... in the pteoeooe
`~/ Ito _ell I&d'~ IILM ,..,... .. lib .fri .. bee ~ at 3 '"""'= a ""arch radiu;) r..tw
`... "':.h '''pee< '" d. Fo< ~~ by dia_ 32 .. do«";" of "";.y
`is _
`radlUi ~ .. ~r al>a:N.i .. ..reb By contn.!t !tm~ 1 , hoffs ~ b
`H. .. 0.1 &Dd Ii .. IOC(I (c:tXT'O>poIld:"& \G .. ,.db. onnJd '" l!i.lJ), OUr -.:h .-;.,;;'"
`o.o:.,~ Ill. of 1M!nJ """ ...
`We oonclu<i< OUt di5cuoricn cf _'-to by deoci~ .. sin&1. eump~ oi
`ou:" :nuhod iD l) """, da.il ,hat. P ....... " "" .. ",d tl> L 000. 000. p up '" O.m.
`and <bo BWDbe! of qlI!!Iios "" to 20,000 !be d:m~n.sOon is 1,000. 11_. anaI)'1iI
`prod""'.....,... P1<>babi1i'r 0.9&)3 &Dd ... obJe< .... O.998S. n... ueo', de?<h .. J9
`and 17,899 Iea_ .. . "'"'oed 00:> __ a&e ~w~. >eIIr'<h
`I'":>.l"odico.ed"'! ... io
`~ 7,020 n.. ... pe.i....,. :equi>"<i l ,80I_oo a400MbJ. Pe>c.ium II POOOllOlCl
`
`~. Conduding Renarko
`w. ~ thO. "",k w... .... ""-" '"" pt"",icN -t ~ n~ "'"lbMo
`", .. ch ... bi&h d:.r..,..,;oa. In oddi,,,,,,, .... harpeoir:, OUZ" a..a!ys;. fu, Lv""""m
`
`Page I I