资源描述：
《Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、FASTAPPROXIMATENEARESTNEIGHBORSWITHAUTOMATICALGORITHMCONFIGURATIONMariusMuja,DavidG.LoweComputerScienceDepartment,UniversityofBritishColumbia,Vancouver,B.C.,Canadamariusm@cs.ubc.ca,lowe@cs.ubc.caKeywords:nearest-neighborssearch,randomizedkd-trees,hierarchicalk-meanstree,clustering
2、.Abstract:Formanycomputervisionproblems,themosttimeconsumingcomponentconsistsofnearestneighbormatch-inginhigh-dimensionalspaces.Therearenoknownexactalgorithmsforsolvingthesehigh-dimensionalproblemsthatarefasterthanlinearsearch.Approximatealgorithmsareknowntoprovidelargespeedupswit
3、honlyminorlossinaccuracy,butmanysuchalgorithmshavebeenpublishedwithonlyminimalguidanceonselectinganalgorithmanditsparametersforanygivenproblem.Inthispaper,wedescribeasystemthatanswersthequestion,“Whatisthefastestapproximatenearest-neighboralgorithmformydata?”Oursystemwilltakeanygi
4、vendatasetanddesireddegreeofprecisionandusethesetoautomaticallydeterminethebestalgorithmandparametervalues.Wealsodescribeanewalgorithmthatappliesprioritysearchonhierarchicalk-meanstrees,whichwehavefoundtoprovidethebestknownperformanceonmanydatasets.Aftertestingarangeofalternatives
5、,wehavefoundthatmultiplerandomizedk-dtreesprovidethebestperformanceforotherdatasets.Wearereleasingpublicdomaincodethatimplementstheseapproaches.Thislibraryprovidesaboutoneorderofmagnitudeimprovementinquerytimeoverthebestpreviouslyavailablesoftwareandprovidesfullyautomatedparameter
6、selection.1INTRODUCTIONformedefficiently.Inthispaper,wewillassumethatXisanEuclideanvectorspace,whichisappropriateformostproblemsincomputervision.Wewillde-Themostcomputationallyexpensivepartofmanyscribepotentialextensionsofourapproachtogeneralcomputervisionalgorithmsconsistsofsearch
7、ingformetricspaces,althoughthiswouldcomeatsomecosttheclosestmatchestohigh-dimensionalvectors.Ex-inefficiency.amplesofsuchproblemsincludefindingthebestmatchesforlocalimagefeaturesinlargedatasetsForhigh-dimensionalspaces,thereareoftenno(Lowe,2004;Philbinetal.,2007),clusteringlocalknow
8、nalgorithmsfornearestneighborsear
