High Performance Data Mining Using the Nearest Neighbor Join
Lists
Only you see this
Abstract
The similarity join has become an important database primitive to support similarity search and data mining. A similarity join combines two sets of complex objects such that the result contains all pairs of similar objects. Well-known are two types of the similarity join, the distance range join where the user defines a distance threshold for the join, and the closest point query or k-distance join which retrieves the k most similar pairs. In this paper, we investigate an important, third similarity join operation called k-nearest neighbor join which combines each point Of one point set with its k nearest neighbors in the other set. It has been shown that many standard algorithms of Knowledge Discovery in Databases (KDD) such as k-means and k-medoid clustering, nearest neighbor classification, data cleansing, postprocessing of sampling-based data mining etc. can be implemented on top of the k-nn join operation to achieve performance improvements without affecting the quality of the result of these algorithms. We propose a new algorithm to compute the k-nearest neighbor join using the multipage index (MuX), a specialized index structure for the similarity join. To reduce both CPU and I/O cost, we develop optimal loading and processing strategies.
BibTeX
@inproceedings{bohm2002high,
author = {Christian Böhm and Florian Krebs},
title = {{High Performance Data Mining Using the Nearest Neighbor Join}},
booktitle = {ICDM},
year = {2002},
url = {https://openreview.net/forum?id=xx2UNO4zF_Yn},
}Loading related content...