Similarity Search in Metric Spaces on Parallel multi-core and multi-GPU Platforms
Universidad Complutense de Madrid
Universidad Complutense de Madrid, 2013
This thesis has proposed a set of algorithms and strategies to solve similarity searches in metric spaces using different parallel platforms. In the first part of the thesis, we have used a multi-core platform, where we found that particular strategies are more suitable depending on the traffic query, obtaining a high speed-up (up to 7.9x with 8 cores) over the sequential algorithm. In the second part, we have used a NVIDIA GPU (Graphic Process Units) graphic card, where we proposed and mapped a set of indexing and exhaustive search strategies to process similarity queries, efficiently exploiting the memory hierarchy of the GPU. We largely outperformed the multi-core version, and we achieved up to 466x of speed-up over the sequential brute force algorithm, solving range queries. In the third part of the thesis we have used a multi-GPU platform, where we extended our previous single-GPU algorithms. We considered two different scenarios: in the simplest one, we assumed that the whole database fits into GPU memory, and in the more realistic scenario we assumed that the database is large enough not to fit in GPU memory.