Diagonal Ordering: A New Approach to High-Dimensional KNN Processing

Hu, J., Cui, B. and Shen, H.

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 difference data distributions; (3) on-line query answering is supported, which is a natural by product of the iterative searching algorithm. We conduct extensive experiments to evaluate the Diagonal Ordering technique and demonstrate its effectiveness.

Cite as: Hu, J., Cui, B. and Shen, H. (2004). Diagonal Ordering: A New Approach to High-Dimensional KNN Processing. In Proc. Fifteenth Australasian Database Conference (ADC2004), Dunedin, New Zealand. CRPIT, 27. Schewe, K.-D. and Williams, H. E., Eds. ACS. 39-47.

(from crpit.com) (local if available)