BC-iDistance: an optimized high-dimensional index for KNN processing

To facilitate high-dimensional KNN queries, based on techniques of approximate vector presentation and one-dimensional transformation, an optimal index is proposed, namely Bit-Code based iDistance ( BC-iDis-tance). To overcome the defect of much information loss for iDistance in one-dimensional transformation, the BC-iDistance adopts a novel representation of compressing a d-dimensional vector into a two-dimensional vector, and employs the concepts of bit code and one-dimensional distance to reflect the location and similarity of the data point relative to the corresponding reference point respectively. By employing the classical B + tree, this representation realizes a two-level pruning process and facilitates the use of a single index structure to further speed up the processing. Experimental evaluations using synthetic data and real data demonstrate that the BC-iDistance outperforms the iDistance and sequential scan for KNN search in high-dimensional spaces.