Top-k Queries Processing With Uncertain Data on Graphics Processing Units
College of Software, Nankai University, Tianjin, 300071, China
Fourth International Symposium on Parallel Architectures, Algorithms and Programming (PAAP), 2011
@article{chang2011top,
title={Top-k Queries Processing With Uncertain Data on Graphics Processing Units},
author={Chang, H. and Qin, T. and Liu, X. and Wang, G. and Yin, A.},
year={2011}
}
Considering the complex uncertain database, top-k query processing in uncertain databases is semantically and computationally different from classical top-k processing. Score is not the only factor we should concern. The interplay between score and membership uncertainty makes computation complex. Powerful computing capability of Graphic Processing Unit(GPU) is needed in the processing of this kind of queries if we want to acquire the results as soon as possible. Using GPU with batch mode, we present a CPUGPU cooperative computing framework to processing top-k queries in uncertain database. Two parallel GPU algorithms are designed to solve the problem specifically. Moreover, a "label-confidence" data format conversion is proposed to reduce CPU-GPU communication. We also suggest an errorcorrection method with the heap-based algorithm to improve the accuracy and correction of the results. Experimental results show that the CPU-GPU framework provides a better performance and it is quite efficiency in handling uncertain top-k problem.
January 9, 2012 by hgpu
