A KNN-Join Algorithm Based on Δ-Tree for High-Dimensional Data

KNN-Join is an important database primitive, which has been successfully applied to speed up applications such as similarity search, data analysis and data mining.Up to now, the KNN-Join has been studied in the context of disk-based systems where it is assumed that the databases are too large to fit into the main memory.This assumption is increasingly being challenged as RAM gets cheaper and larger.Therefore, it is necessary to study the problem of KNN-Join in the main memory. Δ-tree is a novel multi-level index structure that can speed up the high-dimensional query in the main memory environment. In this paper, a new KNN-Join approach is proposed, which uses Δ-tree as the underlying index structure, exploits coding and decoding, bottom up, depth first search and pruning technique.The problem that it is hard to identify the distance from each point in R to its K nearest neighbors in S is solved and the Join efficiency is improved.The correctness verification and cost analysis of the above mentioned algorithm are presented.Extensive experiments on both real datasets and synthetic clustered datasets are conducted, and the results illustrate that Δ-tree-KNN-Join is an efficient KNN-Join method in main memory.