GPU Based Hash Segmentation Index for Fast T-overlap Query

• 作者: Jiaman Ding Jinguo You Lianyin Jia Mengjuan Li Yongbin Zhang
• 来源期刊: 国际计算机前沿大会会议论文集
• 学科: 社会科学
• 关键词: T-overlap QUERY HASH SEGMENTATION SEGMENT at a time SHARED memory GHSII GSPS-TLLO
• 年，卷（期）: 2017,（1）
• 页码范围: 10-12
• 页数: 3页
• 分类号: C5

摘要

T-overlap query is the basis of set similarity query and has been applied in many important fields.Most existing approaches employ a pruning-and-verification framework,thus in low efficiency.Modern GPU has much higher parallelism as well as memory bandwidth than CPU and can be used to accelerate T-overlap query.In this paper,we use hash segmentation to divide inverted lists into segments,then design an efficient inverted index called GHSII on GPU using hash segmentation.Based on GHSII,a new segmentation parallel T-overlap algorithm,GSPS,is proposed.GSPS uses segment at a time to scan segments and uses shared memory to decrease the number of accesses to device memory.Furthermore,an optimized algorithm called GSPS-TLLO using a heuristic query order is proposed to solve the problem of load imbalance.Experiments are carried out on two real datasets and the results show that GSPS-TLLO outperforms the state-of-the-art GPU parallel T-overlap algorithms.