An Improved Keyword Search on Big Data Graph with Graphics Processors

With the development of database research, keyword search on big data graph have attracted many attentions and becoming a hot topic. However, most of existing works are studied on CPU. An important problem is efficiently generating answers for keyword search. In this paper, we research an method of keyword search under graphical processing unit. An improved algorithm based on interval coding is proposed. It includes two main tasks, which are finding root nodes and getting shortest paths from root to keyword nodes. To find root nodes quickly, we judge the reachability between any two nodes based on interval assigned to every node. To speed up finding root nodes and getting shortest paths from root to keyword nodes, we provide data parallel processing for compute-intensive tasks based on intervals assigned to every node and Floyd-Warshall algorithm. Experiment results show the high performance of the proposed solution both on CPU and graphical processing unit.