An Introductory tutorial on k-d Trees

《An Introductory tutorial on k-d Trees》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Anintoductorytutorialonkd-treesAndrewW.MooreCarnegieMellonUniversityawm@cs.cmu.eduExtractfromAndrewMoore'sPhDThesis:EcientMemory-basedLearningforRobotControlPhD.ThesisTechnicalReportNo.209,ComputerLaboratory,UniversityofCambridge.1991.Chapter6Kd-treesforCheapLearningThischaptergivesaspeci

2、cationofthenearestneighbouralgorithm.Italsogivesbothaninformalandformalintroductiontothekd-treedatastructure.Thenthereisanexplicit,detailedaccountofhowthenearestneighboursearchalgorithmisimplementedeciently,whichisfollowedbyanempiricalinvestigationintotheal-gorithm'sperformance.Finally,th

3、ereisdiscussionofsomeotheralgorithmsrelatedtothenearestneighboursearch.6.1NearestNeighbourSpecicationkkrdGiventwomulti-dimensionalspacesDomain=

4、estneighbourofdisany.exemplar000(dr)2EsuchthatNone-nearer(Edd).Noticethattheremightbemorethanonesuit-ableexemplar.Thisambiguitycapturestherequirementthatanynearestneighbourisadequate.None-nearerisdenedthus:00000000None-nearer(Edd),8(dr)2Ejd;djjd;dj(6.1)InEquation6.1thedistancemetric

5、isEuclidean,thoughanyotherL-normcouldhavebeenused.pvui=kduX0t02jd;dj=(d;d)(6.2)iii=1wheredistheithcomponentofvectord.iInthefollowingsectionsIdescribesomealgorithmstorealizethisabstractspecicationwiththeadditionalinformalrequirementthatthecomputationtimeshouldberelativelyshort.6-1Algorithm:

6、NearestNeighbourbyScanning.DataStructures:domain-vectorAvectorofk oatingpointnumbers.drange-vectorAvectorofk oatingpointnumbers.rexemplarApair:(domain-vectorrange-vector)Input:exlist,oftypelistofexemplardom,oftypedomain-vectorOutput:nearest,oftypeexemplarPreconditions:exlistisnotempty00Pos

7、tconditions:ifnearestrepresentstheexemplar(dr),andexlistrepresentstheexemplarsetE,anddomrepresentsthevectord,000then(dr)2EandNone-nearer(Edd).Code:1.nearest-dist:=innity2.nearest:=undened3.forex:=eachexemplarinexlist3.1dist:=distancebetweendomandth