Case 1:14-cv-02396-PGG-MHD Document 148-17 Filed 05/30/19 Page 1 of 13
`Case 1:14-cv-02396—PGG-MHD Document 148-17 Filed 05/30/19 Page 1 of 13
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`EXHIBIT 6
`
`EXHIBIT 6
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 148-17 Filed 05/30/19 Page 2 of 13
`
`Ex dediddeVaage iF ef eae
`eighb Sea h
`ee.Yiai 
` y201998
`eviedA g 11999
`Aba 
`1
`  d i 
`We ideheadi  i iedeaeeighb 
`Theex ded iddevaage if eiaew
` be ia ei a e.Thaigivea
`daa  eha  w  ae biea
` idaaeadaadi  fiee(cid:28) d ea
`i eea heia ei a ef eaeeighb 
`daa  eada iaedea hag ih 
`wihia(cid:12)xedadi (cid:28) fabiay eie.W 
`aidy aehedaae ieae ay ey
` aeef  a edeed hedaaeb i 
`. f i a i adaa  eha
`a(cid:11)e edbyhediib i  f eie.
`videw  aeea hi eb d.
` aayiedi v f eef  a eii
`Vaage ieev ee[32℄adkd ee
`eeig haa ewih if  ad
`[151643℄ gaizea idaae ha
`daae|adexei e (cid:12) heeedi
` bieai eeaeeighb ea he aybee
`i .A he ib i  fheaayiiaew
`f  ed aexe edbaif  e(cid:12)xeddiib
`ee ive he e fdi ei aiyihe 
`i .ef  a edeed hedaaead he
`ex f  eh dadkd eeawe.  ide
`a eddiib i  f eie.
`aizedeighedaaei gaizedi af e
` f1(cid:26)eeea h fdeh g.ee(cid:26)
`Theex ded iddevaage if ev
`f eiaeweaeddaa  eha  
` aybeviewedadeedig (cid:28)hedia ef 
`w  ae bieai eea hef eaeeigh
`i ad hedaae.Theadi  fiee(cid:28)
`b wihia(cid:12)xedadi (cid:28) fabiay eie.
`iai  he gaizai  eadhee
`W  aeef  a edeed hedaaeb 
` iaieaa edaa  ee iaized
`i a(cid:11)e edbyhediib i  f eie.
`awe eiewihihidia e.Sea hehe
`Thedaaei gaizedi af e f1(cid:26)
`e ie1(cid:26) gi e  gi egive
`1(cid:26) e .
`eeea h fdeh g.ee(cid:26) aybeviewed
`adeedig (cid:28)hedia e ea ead he
`   i ihaheeewdaa  e
`daae.Theadi  fiee(cid:28)iai  he
`exhibi ef behavi  yf  aadi ea he
` gaizai  eadhee iadaa  e
`wheedeieheivaiai iea hi e ve
`e iaized awe eiewihihidia e.
`i akd eeef  hbee.
`Ea hee e fhedaae iexa y e
` eyw d:
`eaeeighb ea hVaage i
`ee haheeief ee aiieaa e.
`eev eekd eeC  ai age eyei
`Sea hef waige  eafahiea hee.
`a e. Thea h iwihECReea h i e4 dee
`Theei ba ka kigwheheea hii ied
` eighb wihidia e(cid:28).A giwayevey
`de eWayi e .E ai:yeea h.j.e .
`eighb wihi(cid:28)ie eaiye eed.The
`
`1
`
`

`

` ey e(cid:11)e i g idehede eh ghea h
`ee.Theeae igi(cid:12) aa iay  ai a
`b deaea hi e.S   eaighef 
`ehe ei yaddhedeh fea heei
`hef e aiveahe axi  be fdi
`a eeva ai ea hea hwie ie.Ea hee
` aybeea hedideedey.Sea hehee
` ie gi egive e e f ea hee
`ihef e.
`Wea di deigvaiai haadea e
`f ed i iea hi e|ad aef e
`wihigeee  edi iay.
`Thegeeaideabehidv f eieaiy de
` d.B hv eeadkd eee iveydivide
`hedaae.Aea h dehee aiigdaaee
`e ehaveaa iaedva eadhe deha
`a e dig(cid:12)xedheh dhai ghy e
`aihediib i  fva e.Ee ebe w
`hiheh daeaiged ayheef hidad
`h eab ve heigh.F kd eeheeva e
`aeh e fidivid a diaewihiea hdaa
`ve  .F v eeheyaehedia e fa ei
`a eee e  e(cid:12)xedvaage i.
`Ee eea heheh dead ba ka k
`igd igea h.Wheb idigav f e h
`ee eaedeeedf heeeadaddediead
` ab ke. eheeei eeheb ke
`i gaizedi aeeihea ewaye ig
`ia he aeb ke fee e.Thi 
`i e ihef eib i.Thie(cid:11)e iveyei
`iaeba ka kig.Be a eee eea he
`heh daee iveydeeedadhiheh d
`ieeahe idde fhediib i  fva ewe
`efe daa  eaaex ded iddeva
`age if e.B hv eeadkd ee aybe
`egadedaiviaia e fv f ewih ex
` ded idde.
`Weeeaideaizedaayihaa w 
`edi v f eef  a eii eeig h
`aa ewih if  ad daae.Exe
`i eaee edha (cid:12) heeedi i .
`e ib i  fhiaayiiaieeigew
`ee ive he aed e fdi ei aiy
`haihaeaeeighb ea hi eaeidif
`(cid:12) ywihdi ei . E ideaa egivea
`
` if  ad daaedawf hehye be
`we bevehahew  aediÆ y fv f e
`ea hf ay(cid:12)xed(cid:28) gh beay  i ay 
`awihee  di ei |ad exei
` e (cid:12) hi.Uig1weexe  adif
`(cid:12) yif(cid:28)ia wed i eaewihd1=2dde e
`di ei adhi i (cid:12) edbyexei e.
` aayia  ggehakd eeh dex
`hibihea edi ei ivaia ef (cid:12)xedea h
`adiiadexei e (cid:12) hi.F aw 
` ae eykd eeea hviieeiayhee
`iedaaeb  aveageef  faew k
`hahev f e.
`Thev f ede ibedihie i aed
`hedeve  e f[33℄b d  he evea
`ea havei ediaea i ava e.
`We  de i d i wihabiefdi 
`i  fheeaeeighb ea h be adi
`ea e.See[32℄f addii adi i .
`eaeeighb ea hiai  aakf 
`  aa ei deiyei ai aee gi
`i if  ai eieva e y baedea ig
`adve   aizai .See[11℄f a vey.
`The i  fa ahe ai a ei a e[20℄
` videa ef aba i f eae.Exa
`e f ei a ei deE ideaa ehe
`ik wkia ead ay he.Ex i
`ighe ei a eiageie aiy ei iae
` id igeaeeighb ea hhaa ghi
` y. w kbe g hiie.Thiaeex
`edibyii d ig  ehagivew 
` aei eb df i iedadi ea heii
`vidigaayif he iiii d iga eh d
`f adiga ef i eadivde(cid:12)ig daa
`  eadag ih ie  faba 
`je  whi h biea a heha edia e
`f adiig ihedee ewihh e hakd
`eeha eheva e fadiig ihed diae.
` eayw kB khadad ee[7℄de ibe
` eh df eaeeighb eievabyeva aig
`dia ef diig ihedee e.Theidaa
`  eae i wayee e dig ie
`gava ed ei .
`F k agai[1819℄ex i eige hi e
`[27℄  d eahiea hi ade  ii  fE
` ideaSa e.D igaba hadb dea h
`
`Case 1:14-cv-02396-PGG-MHD Document 148-17 Filed 05/30/19 Page 3 of 13
`
`2
`
`

`

`heiageie aiyi ed  e aeie
` eifhe eyifae gh ide fi.Whie
`ex iga ehe bevehaheiagei
`e aiy aybe ed ei iae edia e
` ai .Akey i iedihawhehe ey
`iweiide fa eheexei eed be
`ea hed.
`C e i  fgahae ideedi[14℄aa
`aba  ei a ewiha ei a igdi ee
`va e y.Thiw kieaed he  i 
` f[7℄. hei  dige akhea h  eay
`ai iaegeeaizai  i eig h
`aR.Theideahavaage ieahe e f
`hea eaebeehah eeahe eewa
`de ibedi[28℄ad haei[32℄.
` ee eaede ibigvaage  ia
` a heae[302925℄ad[32℄wh de ibevai
`a fwhaweefe aavaage  iee.
`A ee[10℄f veye ew k ea hi ei
`a e.Thewe k wkd ee fFied aadBeey
`[151643℄e iveydividea ieiRdby
` je igea hee e  adiig ihed di
`ae.
`  ve ediib i adaai ad
`i e eaea heaede ibedi[13℄[21℄ad
`[6℄ee ivey.
`  fa ew kkd ee e
` d ive   je i wihhe a i a
`bai. ee eyheV   idiga [2℄ha vided
`a ef  i w di ei aE ideaeig
`{adhe vea(cid:12)edad  k fC  ai a
`Ge eyhayieded ayieeige  h
`ah e f[319817℄adeaie[12℄. aea
`ha[12℄ aybehe(cid:12)w kf ig w  ae
`b d.Veye ey eibeg[22℄givew ag ih 
`f aa xi aef  fheeaeeighb  b
`e .Thea ee ie e fhe(cid:12)ae
`hibiiveb hee dwhi ha away(cid:12)d
`a xi aeeaeeighb ee   be f e
`a i aiee.Thee ew ke edi[1℄
`a ideaa xi aef  fhe be .
`Theiaayigiveex eiadeede e db 
`hehe ii vei  fheia a hheyde ibe
` aybe fa i aiee.
`
`F  eeeeayw kdeaigwihw e
` ia aeh dbe ei ed.Reieva fi ia
`biaykeyi ideedbyRivei[26℄adhe
`1eigihef  f[34℄.
`See[5℄f w  aedaa  ef heage
`ea h be .Thi be ieaed b di
`i f eaeeighb ea hi eaeighb 
` abeeabyeveifaige diaeidia.
`B he1eaeeighb  be aybeviewed
`aaia e fageea h.Theiaea de
` ibeaai aa a h adiga ef 
`i eviaa veaig ve. di i  fhi
` i ie i 5a akehigeeaa a h.
`2 Vaage iF e
`Webegibyf  aizigheideaad  i 
`ke hedihei d i .
`De(cid:12)ii 1C ide
`a deed
`eX =
`fx1;:::;xgadava e 2[0;1℄.ew=b 
`ada=bw=2 .Thehe i fX i
` fef iddeadigh bede(cid:12)edby:
`=fxiji(cid:20)ag
`=fxiji>a;i(cid:20)awg
`R=fxiji>awg
`Thaiabaa ed3 wayaii  fXwiha e
`a  i  fa xi aey .
`Ag ih 1Givea e i  f iada
`1 1 je i f  i (cid:25)G:!Rde(cid:12)edf ay
` e yG(cid:18)de(cid:12)e(cid:25)GG behe deede
` fdii eava e e dig hei age f
`G de(cid:25)G. wf  2[0;1℄:
`1. idehe i;;R f(cid:25)Gadde(cid:12)e
`heiG;G;GR fG e dig he
`ei age f;;Ree ivey.
`2.GiveG(cid:18)  abiayeebyf 
`igG;G;GRdi adigGadhed ig
`hea ee iveyf GadGR iige
`ee ee aif  igheee eave.
`
`Case 1:14-cv-02396-PGG-MHD Document 148-17 Filed 05/30/19 Page 4 of 13
`
`3
`
`

`

`3.Saigwihb idaeeT1ade ibedab ve
`adde ei e behiby1.e0=
`heee e
`adde(cid:12)e1=01i.e.
`di adedb idigT1.
`4.F k>1adk16=;de(cid:12)eTkaheee
`b iaab vef k1de eheee  e
`behibykadde(cid:12)ek=k1k.
`De(cid:12)ii 2Weefe hee  fag ih 1
`aheideaizedex ded iddevaage if e
`id edby(cid:25)wih ea  i  .Whei
`a ei a eadhe je i f  i (cid:25)aify
`j(cid:25)x(cid:25)yj(cid:20)dx;y;8x;y2hif ei f e
`f eaeeighb ea hadwef hede(cid:12)e(cid:28)
`be ehaf fhe ii dia ee fa iddee
`di adedd ig  i .
`Wee akhaea hee fhef e aybe
`viewedaaa g  heCa ef eaaa
`yi.Thaihe be f[0;1℄  edbye
` vighe eahid fheieva|ad
` eedige iveyf b hheefadighhid.
` f ehe e d ade  ii  f
`hea ei a i  fCa e.
`Tw i  aexa e fa iabefa iy f
`(cid:25)f  i aevaage i je i f geea
` ei a ead ive   je i f E
` ideaa e.
`Avaage i je  (cid:25)ide(cid:12)edf ay
`2by(cid:25)x=d;x.Thei iiee
`  i  e d aba heeab .
` ieaiyvei(cid:12)edhaj(cid:25)x(cid:25)yj(cid:20)dx;ya
`e ied.Theage fhi je  ihe ega
`iveea.eig =0giveie avaage i
`ee[32℄.
`The ive   je  (cid:25)ide(cid:12)edf ay
`6=0a(cid:25)x=<;x>=kk.Thiieaiy
`ee aifyhee iedie aiyawead
`iagei i ied  egaiveva e.ee
`hei i e d hyeae.Ch ig
`a a i a ive  adeig =0b id
`af  fkd ee[151643℄.
` ii  a
` eha<;x> aybe  ed eaidy
`f  a i a ive  |i ai ewih
`ee  di ei .A wee akhawhe
`eve h g ave  ae ed je i dia e
`
`aeiaeeaddiiveadhahifa  abe
`ex iedakd eed whedeigig i 
`e iaizedf a e.Wed   ideeihe
` fhee i izai ihiae.
`  ii 1C ideaideaizedVaage i
`F ewih ea  i  ad e dig
`va e(cid:28).De(cid:12)e(cid:26)=1=1 g21 .The:
`1.Theeae1(cid:26)eeihef ehavig
` axi deh g.
`2.Aea hf eaeeighb wihidia e
`(cid:28) fa eye ie1(cid:26) gi ead
`ieaa e|ideede fhe ey.
`3.The
`ea h
`e ie g
`i e
`give
`1(cid:26)ideede e .
`4.A igea h je  (cid:25)G abe  ed
`i ai eadhai aa beeva
` aedi ai eadha >0he
`2(cid:26)i eie ied  hef e.
` f:Aea heihe  i he ea
`  i  f ee eie ved haheef
`adigh beaeea h fize1 =2.The
`(cid:12)ee dehihe[1= g22=1 ℄ g2=
` g.S he be fee eefiheee
`i1=1 g21 =(cid:26).
`The be fee eefafehe(cid:12)eeha
`bee  edihe(cid:26).Afehee d
`(cid:26)(cid:26)(cid:26)aeefad .Ceay
`(cid:10)1(cid:26)eeaee ied ed ehe  ai 
` ay(cid:12)xedize.
` ehe  ai habeeed ed 1=2 fi
` igiaizehe be fee ee vedaea h
`eeib iwihavede ied =2(cid:26)=1=2(cid:26)(cid:26).
`Si e1=2(cid:26)>1=2 feweha(cid:26)=2aee ved.
`S he be fee ied ea h=2i
` eha1(cid:26).The bee ied ea h=4
`ihe1=21(cid:26)1(cid:26)|ad f  igage e
`i eie.S he bee ied ea hay(cid:12)xed
`evei1(cid:26).The be feeihef ei
`he1(cid:26)|adhe aa ei eayiea.
`Aea hf eaeeighb wihidia e(cid:28)
`ihe adebyf wigaige  eafahi
`
`Case 1:14-cv-02396-PGG-MHD Document 148-17 Filed 05/30/19 Page 5 of 13
`
`4
`
`

`

`ea heeeabihighee iedi eb d.Ea h
`ee abe ideedideedeyadhee 
` eged aiveaaigeeaeeighb .Thi
`eabiheheaedaae exiy.
`Fiaywe ide gaizai ai e.The(cid:12)
`eve fhe(cid:12)eee iew k  d e
` je i va e fea h iihea eadhe
`i e e(cid:11)e heiieai e deai
`i .Theexeve idea a f1 
`e dad eadig  veai ef
`whi hheaed gaizai i eb df w.2
`F exa eif =1=2heeaeeei
`hef eadea hi ei g.ga
`izai e ie3=2i eb aaway y
`a ei  ed.A !1weexe (cid:28)
`i eaeb he be feea a head
`ea he eeve e exa iigevey i.
`A !0weexe (cid:28) de eaewhieea hi e
`a a hehe gaih i idea.The aa e
`eheiaeeie aebeweeexha ive
`age (cid:28)ea had gaih i  a (cid:28)ea h.
` deve  eab veiveygeeaadde
` ibeideaizedf e.We wexaiiwha
`eeheyaeideaizedadbegi di i  f
`  eeeig.
`Ag ih 1e vea(cid:12)xed ea  i  f
`he iaea hee dei eed.Thii
`i(cid:12)eaayib be a e(cid:28)ide(cid:12)edahe ii
` dia ee fa h ea (cid:28) ighwid
`   a be faya i ava e.A he
` je i f  i wi igeeabe1 1ad
`hideai be ideediayi e eai .
`The e  bje iveiaaifa  yade (cid:11)bewee
`he (cid:13)i igg a f ii izigea hi ead
` axi izig(cid:28).
`ea a hi ii izeea hi egivea
` web d (cid:28).
`  awihheideaized
` aeheei akeee avaiabe ea
`  i | e fdia ee2(cid:28). i eihi ae
`hahe  i e i  aye iaebe
`f eea higaige de.Si ehe h i e f
`je   aya(cid:11)e hi  i i aybewie
`iveaddii ai ed ig  i  eva
`ae ie je  .Thi e d heidea
` fee igavaage if av ee a 
`
`di ei f akd ee.Whe(cid:12)xeddia ee 
`ae adea e i aed ig ef f 
`e  i ieeded.hewieaiyba f
` i aeha2(cid:28)idia eewievebe
`aiged ayee.
` ia i  a  ehawhie f i
` w  aeef  a eadheei ba ka k
`ige ied ea hf eighb wihidia e
`(cid:28)haba ka kig abeef  edaf v ee
` kd eei de aify eiebey d(cid:28).
`A hedi(cid:11)ee ebewee ideaized 
`i ada i ai e eai ihaiheide
`aized ae iae ed yaeeeave.
` hev ee aehe je  if  edbye
`e igaee ev f ba eGad  igi
`dia e he eyad evey heee e f
`G.avig  edidia e he eyhee
`i eed exa ievagaiadweheef eview
`ia edaheiei ee deawhi hiwa
` ed.S hedi(cid:11)ee eihaheeGfvgi
`iaea heve fhee i .Whe ig i
`ve   je i iia  ibe eaee e
`x fhedaabae.ee ii e eay ex
`a iexagaii edx;ieaiy  edgive
`<x;>.
`3 ef  a eia e
`Theik wki   ide edadde(cid:12)ed
`bykXk=ijxij1=f (cid:21)1.A ei e
` f eva aighe  fhedi(cid:11)ee e f
`w ve  .TheE idea ei i2he iy
`b k ei i1adby vei 1givehe
` axi ab eva e veidivid a diae.
`Webegiwihaay  i ae ehaa w
` deadheexe edef  a e fex ded
` iddevaage if eihighdi ei ai
`a e fheea egivediib i  hahe
` if  e.
`  ii 2eXx1;:::;xdbeave   f
`i.i.d.ad vaiabe.C ideYkXkade
`(cid:27)2de ehevaia e fYab i ea.The
`(cid:27)=d1=1=2egadigi(cid:12)xedadeigd!
`1.
`
`Case 1:14-cv-02396-PGG-MHD Document 148-17 Filed 05/30/19 Page 6 of 13
`
`5
`
`

`

` f:C ideY=di=1kxik.Be a ehexi
`aei.i.d.b hhe eaadvaia e fY ae
`ieaywihd.S eaive he agi de f
`he ea fYiadaddeviai hika
`d1=2whe ehediib i  fYva eii
` eaigy  eaedab i ea.Takighe
`h  aiveaYhahee(cid:11)e  f aiga f
`heeva ed wwadbyafa   fa xi aey
`d1==d=d1=1 hevaia e hagebyafa
`  fd2=2.B hevaia e fY aewih
`d hevaia e fY aewihd2=1adi
`adaddeviai wihd1=1=2.2
`T keeiae ei ehe  ii i
` deai.i.d.a i b eie eay. 
`deede eie iedb he eaadvaia e f
`ea hvaiabexieed behea e. i eey
`e eayhahe eaadvaia e fY ae
`a xi aeyieaywihd.
`The  ii iheeevabe a e fw b
`evai ab  if  ydiib edhighdi e
`i aa e.Fiyha h iga iv
`aad hediib i  fkxvk vexi
`hea eexhibihee iediea aigbehav
`i .Se dyha akig d ig  i 
`whehehei a hyeaaiahighdi e
`i aa eeave ba ehaf he  e
` fhi  ii ibehaveike if  yad
` e.Thea ei ef  ive   je i .
`F E ideaa e=2weheexe (cid:27)
`beay  i ay awihdi ei .The
`hediib i  fva ehe  i ag ih
`ieeedwihaea hebe ehea ef 
` Æ ieyhighdi ei .F 1wehaveha(cid:27)
` ae wadwihd1=2adf 1i aed w
`wadwihd1=2.Thee ihaweexe hef
` wigbehavi whe igex ded iddevaage
` if e ea h if  ydiib ed i
`e:1.Thew  aei e ea hf heeae
`eighb wihidia e(cid:28) fa ey dehe
`E idea ei i awihee  di
` ei .
`2.Uig1heakbe eeaiewihi eaig
`di ei   e a ae(cid:28) wadwihd1=2
`
`ad aiai ai e.
`3.F ;>2heakbe ehadewihi
` eaigdi ei .
` eeigyihei i
`ig1 ae a a hieeiayw h
`eb ageea he hi eaybe a e
`aea hf eighb wihi(cid:28)ij aage
` ey fhif  ayig eveydi ei .
`Fiaywee akhahe ae f ive  
`je i iE ideaa edie yead he(cid:12)
` bevai ab vewih he  ii .
`Wehavei e eed ideaaaAS C
`ga .Fig e1ad2de ibeexei ewhi h
` (cid:12) hebehavi ab vef 1ad2. ii
` a eieaehaea highef eiv ve
` de ii  ba ka kig haea hi ei
`eeiay a.S :
`1. exei ee(cid:13)e hei ee ied e
`f  heea hf aygive ey.
`2.Be a e fhea e fheea haeighb 
`wihi(cid:28)wie eaiybee eedd ig
`i.heexei e (cid:12) edheexe edbehav
`i whe>2.Vaage i je i i edb 
` ive   je i givei iae .Avaage
` iiee edaad f he e be
` fhedaae.Thei e eai f  e(cid:12)xed(cid:28)
` ad f e  i wheae aiig
` iaefaied beaiged aeeafeaage
` be fae .Thee iaehe eda
`ai ei.Thei e eai a  e i
`aiei  de j aeave.Fiayii
`igag ih igeeai.e.d e a e1 1
` je i f  i .
`The if  ad aei f e fie
`a i aiee.Whiewegive geeaw 
` aeb diii  a  ehaef  ig
`a(cid:12)xed(cid:28)  i wiawaygeeaeaf e
`ada e dig ey ideedew  ae
`b d ea hi ef haai a ie.
`We aeef  a ei eigwihkd
`eeea h[151643℄adaedf [23℄ade
` ibedi[33℄f adi i iedea h.
`
`Case 1:14-cv-02396-PGG-MHD Document 148-17 Filed 05/30/19 Page 7 of 13
`
`6
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 148-17 Filed 05/30/19 Page 8 of 13
`Case 1:14-cv-02396-PGG-MHD Document 148-17 Filed 05/30/19 Page 8 of 13
`
`
`
`
`
` Nodes
`
`Visited(WorstCue) 8
`
`2
`
`4
`
`8
`
`16
`
`32
`D'
`
`64
`.
`
`128
`
`256
`
`512
`
`1024
`
`Figure 1: The worst—case number of nodes visited by
`an excluded middle vantage point forest search un—
`der the L2 metric (p : 2), the uniform distribution
`(10,000 points), and fixed T radius, does not in the
`limit depend on dimension. The curves depicted from
`bottom to top correspond to central exclusion widths
`from 0.05 to 1.00 in increments of 0.05. Correspond-
`ing T values are half as large.
`
`
`
`
`
`
`
`
`
`
`NodesVisited(WorstCase) 8
`
`
`2
`
`4
`
`8
`
`16
`
`32
`D"
`
`64
`.
`
`128
`
`256
`
`512
`
`1024
`
`Figure 2: For the L1 metric (p : l) and the setting
`of figure 1, dimension invariance is observed if central
`exclusion widths are scaled by x/FI. For example, the
`bottom curve corresponds to T = 0.025 for d = 2 and
`T : «512/2 x 0.025 : 0.4 for d : 512. So for L
`the search radius may increase with dimension while
`holding worst-case performance constant.
`
`Nodes
`
`Vidted
`
`2
`
`4
`
`8
`
`16
`
`64
`32
`Dimension
`
`128
`
`256
`
`512
`
`1024
`
`Figure 3: The average number of nodes visited by kd-
`tree search under the L3 metric (p : 2), the uniform
`distribution (10,000 points), and fixed T radius, does
`not in the limit depend on dimension. The curves
`depicted from bottom to top correspond to central
`exclusion widths from 0.05 to 2.00 in increments of
`
`0.05. Corresponding T values are half as large.
`
`Figure 3 shows the result of our experiment. The
`same dimensional invariance is evident, but now with
`respect to expected search time. As for our worst-
`case structures, this follows from our earlier observa-
`tions about projection distributions in high dimen-
`sional spaces. The figure shows that expected search
`complexity is somewhat lower than the worst case re-
`sults of figure 1 where saturation is evident exclusion
`width 1 is approached. For kd-trees, saturation is
`delayed until roughly width 2.
`
`The expected kd—tree search times are much lower
`than the worst case values of figure 1. In fact, given
`random queries, the probability is vanishingly small
`that kd—tree search will cost as much as our worst
`case search.
`
`In the uniform case a query at the center of the
`hypercube is costly for the kd-tree, and we have con-
`firmed that essentially the entire dataset is searched
`in this case. we observe that one might build a pair
`of kd-trees whose cut points are offset to eliminate
`these hot spots and perhaps even provide worst case
`performance bounds in the radius-limited case.
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 148-17 Filed 05/30/19 Page 9 of 13
`Case 1:14-cv-02396-PGG-MHD Document 148-17 Filed 05/30/19 Page 9 of 13
`
`4 Excluded middle trees vs.
`
`Forests
`
`By slightly modifying the forest construction algo-
`rithm one can build a single 3-way tree.
`Instead of
`adding the central elements to a bucket for later use
`in building the next tree, we instead leave them in
`place forming a third central branch. To search such
`a tree one must follow two of the three branches: ei-
`
`ther the left and middle, or the middle and right. We
`remark that this tree structure was our first idea for
`
`enhancing vantage point trees to provide worst-case
`search time bounds.
`
`Like the forest, this tree requires linear space, but a
`simple example and analysis illustrates that its search
`performance is usually much worse.
`Consider the 3-way tree built by an equal 3-way
`division,
`i.e. where the central exclusion propor-
`tion is 1/3. Then the tree’s depth is log3 N. The
`path taken by any single search consists of a bi-
`nary tree embedded within this trinary tree.
`So
`Nl0g32 2 NO'63 nodes will be visited. But we have
`
`seen that a forest with exclusion proportion 1/2 re-
`sults in ()(N0'510gN) node visits, which is superior
`despite the fact that the tree was built using a smaller
`exclusion proportion (1 / 3 vs. 1/2).
`Table 4 compares the performance of idealized
`trees and forests for various database sizes and cen-
`
`tral exclusion proportions. Figure 4 compares the
`performance of actual trees and forests in a uniform
`distribution Euclidean space setting. The results are
`consistent with our analysis and the computations of
`table 4. We briefly remark that for small 7', trees and
`forests with a higher branching factor make sense.
`Here the projected point. set is partitioned into bands
`with alternating ones corresponding to the excluded
`middle of our 3—way construction.
`
`5 Trading Space for Time
`
`Until now we have considered linear space structures.
`In this section we describe a general technique for
`trading space for time. For analysis we will return to
`the idealized setting in which construction removes
`fixed proportions ~
`~ not fixed diameter central sub-
`
`
`
`Proportion
`0.100
`0.300
`0.500
`0.700
`0.900
`
`103
`0.52
`0.87
`1.21
`1.40
`1.50
`
`Number of Elements
`105
`104
`106
`107
`0.23
`0.37
`0.08
`0.42
`0.18
`0.58
`0.44
`0.83
`0.96
`1.31
`0.88
`1.18
`1.51
`1.65
`1.64
`
`108
`0 .05
`0.11
`0 .36
`0 .77
`1 .51
`
`Table 1: The relative search time ratio of an ideal—
`
`ized excluded middle vantage point forest, to that of
`a tree. The forest is better in almost all cases. No—
`
`tice that its relative advantage can be quite large.
`The tree is preferred only in the case of large central
`exclusion widths, and then by only a small factor.
`
`§ 10
`
`
`
`NodesVldtod(WorstCase) g§
`
`NlllbelotPoills
`
`Figure 4: A comparison of excluded-middle vantage
`trees (dashed line) and forests (solid line) for the L2
`metric, d = 64, the uniform distribution, and central
`exclusion widths of 0.01,0.l0,0.25, and 0.50 corre-
`sponding to the curve pairs from bottom to top. For
`small widths the forest performs better and the ad-
`vantage increases with database size (see the differ-
`ence in curve slopes). This advantage reduces with
`increasing exclusion width, and by 0.50 the tree is the
`winner.
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 148-17 Filed 05/30/19 Page 10 of 13
`Case 1:14-cv-02396-PGG-MHD Document 148-17 Filed 05/30/19 Page 10 of 13
`
`tit
`a)<—I—;—I—>
`L
`M
`R
`m
`
`b) <—%l’fr—Ifl—>
`L
`Rx
`M
`Lx
`R
`\_/\—A_l
`‘-.
`m
`__.-'
`
`Figure 5: a) An idealized illustration of the division
`according to definition 1 of the projection of a. point
`set onto the real line. Subset A! results from remov-
`
`ing the central proportion of m elements. Assuming
`a symmetrical distribution set M has diameter 27'.
`Subset L consists of everything below Ill in projected
`value, and R of everything above it. b) An idealized
`illustration of the tradeoff of space for time. Here an
`additional proportion ml of central elements encloses
`M and corresponds to two subsets R1 and LI. Ele-
`ments of R1 are stored in R and also in L. Likewise
`elements of L, are stored in both L and R. The re-
`sult is that the effective search radius within which
`the worst case time bound holds is extended from 7'
`t0 7' + 7'1.
`
`sets as in the implementation and experiments. This
`will allow us to make calculations intended to illumi-
`
`nate the engineering tradeoffs one faces in practice.
`
`The 3—way split performed by algorithm 1 is il-
`lustrated in figure 5(a). The central proportion m
`is imagined to correspond to some fixed radius 7' as
`shown. We motivate the construction in terms of 7'
`
`but will analyze it in terms of m.
`
`When the projection of a query lies just to the
`right of the dotted centerline, a search for a nearest
`neighbor within T will explore M and R. Increasing
`T by some value T1 forces the search to explore L as
`well.
`
`To avoid exploring all three we store the points in
`interval RI in two places (see figure 5(b)). First, they
`
`are stored as always in L. Second, they are stored
`with those of R. As a result of this overlap only AI
`and R must be explored as before. Points in interval
`L, are similarly stored twice.
`Continuing this modified division throughout for-
`est construction yields a data structure that:
`
`1. Includes the same number of trees as before,
`since the size of the excluded central proportion
`is unchanged.
`
`2. Contains trees that are deeper, but still asymp-
`totically of logarithmic depth. Tree depth is
`logm N.
`
`is the same worst—case asymptotic
`3. The result
`search times, but over the larger idealized radius
`7+1}.
`
`the cost
`4. Provides this search-time benefit at
`I
`. _2_
`”“2 ('l—vu-l-rnr)
`
`of space. The deeper tree has N
`nodes. Space for the entire forest is then:
`1
`1
`
`+—o
`- 1—m+mz
`logo
`
`1
`
`()(N
`
`_ 'l—lugg l—m )
`
`For example, let m = 1/2 and ml. 2 1/4. Then
`space is z ()(NLZOM).
`the same space trade—
`From another viewpoint
`off may be used to reduce search time for a fixed
`T. For example, an ordinary m = 0.5 forest pro—
`vides ()(NO'5 log N) searches. Letting m = 0.25 and
`m1. = 0.25 reduces the time to z ()(N0.293310gN)
`but space is increased from ()(N) to z ()(Nl'2933).
`Finally consider the interesting extreme case where
`m = 0. Here the forest consists of a single bi—
`nary tree. Search time is then ()(log N) with space
`+
`
`()(N “S2 1‘— ).
`
`6 Some Topics for Future Work
`
`Excluded middle forests might be applied to problems
`other than nearest neighbor search. They might, for
`example, improve the effectiveness of decision trees,
`an important tool for machine learning [24]. The
`motivation here is that values near to the decision
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 148-17 Filed 05/30/19 Page 11 of 13
`
`heh d aybe ediÆ  aifybaed 
`eai hi fhii ee hi e heidea f
`heee edde ii vaiabe.
`hiae.Wee akhahea eidea fdi e
`We wdi evea ibiiieeaed ea
`i aaii igaie ayik wki ei 
`eeighb ea h.F ea h(cid:12)xed(cid:28) i e e
`b  fawe a baiaadvaage yihe
`ai geeaeaf ewih ea iaedw 
`B ea ae.
` ae eyi eb d.S ae(cid:28)va eige
`Ade ibedeaie  eh dg wweake
`eae i aeb d. w  ehaa
`wihg wigbe igeeiay eef 1.
`f eib iwih(cid:28)=1adheye ihee
`Thiiieeigi e ddeywih=1he
`eedwiha ey.ex  ehaeayihe
` be be eaia e fageea h.We
`ea haeighb ie eedhaiwewihi
`e aehaideaf ageea h ighi e
`he(cid:28)adi ayadia e0:3(cid:28).Deie g d
`f  be f ebef eea he1|if yaaa
`f  ehee aiigea hwiake ei e.
` xi ae i  heeaeeighb  be .
`Fiaywe bevehaiRd ighedaave
`R  eaveahieveye aiigee beex
`a ied.eideai b id ief e.ef (cid:28)=1
` he evee ieda e.Theee/f e
`web id a