Top-k Queries Processing With Uncertain Data on Graphics Processing Units

Haozhe Chang, Tingting Qin, Xiaoguang Liu, Gang Wang, Airu Yin
College of Software, Nankai University, Tianjin, 300071, China
Fourth International Symposium on Parallel Architectures, Algorithms and Programming (PAAP), 2011


   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.},



Download Download (PDF)   View View   Source Source   



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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: