摘要
传统的局部敏感哈希算法建立哈希表时往往需要较大的内存空间以及较长的建立时间.在查询阶段,查询样本K个最近邻数据项的所需时间超过整个运行时间的95%.针对这些问题,运用计算设备架构将局部敏感哈希算法移植至图形处理器,并用多线程并行计算数据项的哈希值来建立哈希表.查询阶段在全局内存中引入基于工作队列的多样本查询,以提高算法的运行效率.实验结果表明,所提出的算法与传统的局部敏感哈希算法相比,能在不降低运算精度的情况下将运算速度提高近12倍.
The traditional locality sensitive hashing （LSH） algorithm often takes a large memory space and long settling time to build a hash table. In the query phase, it takes more than 95% of the overall running time to search K nearest neighbor data items of samples. To solve these problems, this paper uses the compute unified device architecture （CUDA） to transplant LSH algorithm into a GPU, using parallel multi-threads to calculate the values of data items to build the hash table. In the query phase, we introduce multi- sample query based on work queue to global memory to improve efficiency of the algorithm. Experimental results show that computing speed of the proposed LSH algorithm is 12 times faster than the traditional LSH algorithm.
出处
《应用科学学报》
CAS
CSCD
北大核心
2015年第5期550-558,共9页
Journal of Applied Sciences
基金
国家"863"高技术研究发展计划基金(No.2013AA01A603)
上海市教育委员会科研创新项目基金(No.14YZ011)资助
关键词
计算设备架构
图形处理器
局部敏感哈希
K最近邻
compute unified device architecture （CUDA）； graphics processing unit （GPU）；locality sensitive hashing； K-nearest neighbor
