Variousindexstructureshaverecentlybeenproposedtofacilitatehigh-dimensionalKNNqueries,amongwhichthetechniquesofapproximatevectorpresentationandone-dimensional(1D)transformationcanbreakthecurseofdimensionality.Basedonthetwotechniquesabove,anovelhigh-dimensionalindexisproposed,calledBit-codeandDistancebasedindex(BD).BDisbasedonaspecialpartitioningstrategywhichisoptimizedforhigh-dimensionaldata.Bythedefinitionsofbitcodeandtransformationfunction,ahigh-dimensionalvectorcanbefirstapproximatelyrepresentedandthentransformedintoa1Dvector,thekeymanagedbyaB+-tree.AnewKNNsearchalgorithmisalsoproposedthatexploitsthebitcodeanddistancetoprunethesearchspacemoreeffectively.ResultsofextensiveexperimentsusingbothsyntheticandrealdatademonstratedthatBDout-performstheexistingindexstructuresforKNNsearchinhigh-dimensionalspaces.
