A Fast Similarity Join Algorithm Using Graphics Processing Units

M. D. Lieberman, J. Sankaranarayanan, H. Samet
Data Engineering, 2008. ICDE 2008. IEEE 24th International Conference on In Data Engineering, 2008. ICDE 2008. IEEE 24th International Conference on (2008), pp. 1111-1120


   title={A fast similarity join algorithm using graphics processing units},

   author={Lieberman, M.D. and Sankaranarayanan, J. and Samet, H.},

   booktitle={Data Engineering, 2008. ICDE 2008. IEEE 24th International Conference on},





Download Download (PDF)   View View   Source Source   



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 in A,q in B, such that the distance D(p,q) < 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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: