Diagonal Ordering: a new approach to high-dimensional KNN processing
Jing Hu, Bin Cui, Heng Tao Shen · Australasian Database Conference · 2004
In this paper, we propose Diagonal Ordering, a new technique for K-Nearest-Neighbor (KNN) search in a high-dimensional space. Our solution is based on data clustering and a particular sort order of the data points, which is obtained by slicing each cluster along the diagonal direction. In this way, we are able to transform the high-dimensional data points into one-dimensional space and index them using a B+-tree structure. KNN search is then performed as a sequence of one-dimensional range searches. Advantages of our approach include: (1) irrelevant data points are eliminated quickly without extensive distance computations; (2) the index structure can effectively adapt to different data distributions; (3) on-line query answering is supported, which is a natural byproduct of the iterative searching algorithm. We conduct extensive experiments to evaluate the Diagonal Ordering technique and demonstrate its effectiveness.