TY - CONF
T1 - A Fast Similarity Join Algorithm Using Graphics Processing Units
T2 - Data Engineering, 2008. ICDE 2008. IEEE 24th International Conference on
Y1 - 2008
A1 - Lieberman,M.D.
A1 - Sankaranarayanan,J.
A1 - Samet, Hanan
KW - algorithm;graphics
KW - algorithms;quadtrees;set
KW - arrays
KW - curves;parallel
KW - join
KW - problem;space-filling
KW - PROCESSING
KW - searching;fast
KW - similarity
KW - theory;sorting;
KW - units;sort-and-search
AB - A similarity join operation A BOWTIE_{epsiv} B takes two sets of points A, B and a value epsiv isin Ropf, and outputs pairs of points p isin A,q isin B, such that the distance D(p, q) les epsiv. Similarity joins find use in a variety of fields, such as clustering, text mining, and multimedia databases. A novel similarity join algorithm called LSS is presented that executes on a graphics processing unit (GPU), exploiting its parallelism and high data throughput. As GPUs only allow simple data operations such as the sorting and searching of arrays, LSS uses these two operations to cast a similarity join operation as a GPU sort-and-search problem. It first creates, on the fly, a set of space-filling curves on one of its input datasets, using a parallel GPU sort routine. Next, LSS processes each point p of the other dataset in parallel. For each p, it searches an interval of one of the space-filling curves guaranteed to contain all the pairs in which p participates. Using extensive theoretical and experimental analysis, LSS is shown to offer a good balance between time and work efficiency. Experimental results demonstrate that LSS is suitable for similarity joins in large high-dimensional datasets, and that it performs well when compared against two existing prominent similarity join methods.
JA - Data Engineering, 2008. ICDE 2008. IEEE 24th International Conference on
M3 - 10.1109/ICDE.2008.4497520
ER -