Efficient index-based KNN join processing for high-dimensional data

Yu Cui

doi:10.1016/j.infsof.2006.05.006

Efficient index-based KNN join processing for high-dimensional data

2007-04-01

66

PRE

AI

DOI：10.1016/j.infsof.2006.05.006

Original

Original request for help

Save

Abstract

En 中文

In many advanced database applications (e.g., multimedia databases), data objects are transformed into high-dimensional points and manipulated in high-dimensional space. One of the most important but costly operations is the similarity join that combines similar points from multiple datasets. In this paper, we examine the problem of processing K-nearest neighbor similarity join (KNN join). KNN join between two datasets, R and S, returns for each point in R its K most similar points in S. We propose a new index-based KNN join approach using the iDistance as the underlying index structure. We first present its basic algorithm and then propose two different enhancements. In the first enhancement, we optimize the original KNN join algorithm by using approximation bounding cubes. In the second enhancement, we exploit the reduced dimensions of data space. We conducted an extensive experimental study using both synthetic and real datasets, and the results verify the performance advantage of our schemes over existing KNN join algorithms. (c) 2006 Elsevier B.V. All rights reserved.

Keywords:

high-dimensional data

KNN

similarity join

Efficient index-based KNN join processing for high-dimensional data

Abstract

AI Summary

Journal

Organization