TY - JOUR
T1 - Metric space similarity joins
JF - ACM Trans. Database Syst.
Y1 - 2008
A1 - Jacox,Edwin H.
A1 - Samet, Hanan
KW - distance-based indexing
KW - external memory algorithms
KW - nearest neighbor queries
KW - range queries
KW - Ranking
KW - Similarity join
AB - Similarity join algorithms find pairs of objects that lie within a certain distance ε of each other. Algorithms that are adapted from spatial join techniques are designed primarily for data in a vector space and often employ some form of a multidimensional index. For these algorithms, when the data lies in a metric space, the usual solution is to embed the data in vector space and then make use of a multidimensional index. Such an approach has a number of drawbacks when the data is high dimensional as we must eventually find the most discriminating dimensions, which is not trivial. In addition, although the maximum distance between objects increases with dimension, the ability to discriminate between objects in each dimension does not. These drawbacks are overcome via the introduction of a new method called Quickjoin that does not require a multidimensional index and instead adapts techniques used in distance-based indexing for use in a method that is conceptually similar to the Quicksort algorithm. A formal analysis is provided of the Quickjoin method. Experiments show that the Quickjoin method significantly outperforms two existing techniques.
VL - 33
SN - 0362-5915
UR - http://doi.acm.org/10.1145/1366102.1366104
CP - 2
M3 - 10.1145/1366102.1366104
ER -