A Parallel Query Processing Technique for Keyword Search over Data Graph

Abstract:

As a hot topic in the field of database research, keyword search on data graph has attracted many attentions. However, most of existing works are mainly studied on CPU. An important problem is how to efficiently generate answers for keyword search. In this paper, a parallel approach of keyword search based on interval coding is investigated. The approach includes two main tasks, which are finding root nodes and getting shortest paths from root to keyword nodes. To find root nodes quickly, we adopt a strategy of reachability judging between any two nodes with interval assigned to every node. Meanwhile, aim to speed up finding root nodes and getting shortest paths from root to keyword nodes, we provide data parallel processing for compute-intensive tasks by using graphical processing unit. Experiment results show the high performance of the proposed solution both on CPU and graphical processing unit.

• Periodical: Applied Mechanics and Materials (Volumes 380-384)
• Pages: 2609-2613
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.380-384.2609
• Online since: August 2013
• Authors: Shu Xin Yang, Wei Tang, Bi Bo He
• Keywords: Data Graph, Graphic Processing Unit, Keyword Search, Parallel Processing

References

[1] Yiping Ke, James Cheng, Jeffrey Xu Yu, Querying Large Graph Databases, In the 15th International Conference on Database Systems for Advanced Applications, (2010).

[2] B. B. Dalvi, M. Kshirsagar, and S. Sudarshan, Keyword Search on External Memory Data Graphs, VLDB, 2008, pp.1189-1204.

DOI: 10.14778/1453856.1453982

[3] G. Bhalotia, C. Nakhe, A. Hulgeri, S. Chakrabarti, and S. Sudarshan, Keyword searching and browsing in databases using BANKS, International Conference on Data Engineering(ICDE), 2002, pp.431-440.

DOI: 10.1109/icde.2002.994756

[4] V. Kacholia, S. Pandit, S. Chakrabarti, et al, Bidirectional expansion for keyword search on graph databases, In Proceedings of 31st International Conference on Very Large Data Bases, 2005, pp.505-516.

[5] He Hao, Wang Haixun, Yang Jun, Yu, Philip S. BLINKS: Ranked keyword searches on graphs, SIGMOD, 2007, pp.305-316.

DOI: 10.1145/1247480.1247516

[6] ZHOU Guoliang, FENG Haijun, HE Guoming and CHEN Hong, Survey of Data Management on Graphics Processor Units, Journal of Frontiers of Computer Science and Technology(in Chinese), vol. 4, Apr. 2010, pp.289-303.

[7] Hongzhi Wang, Wei Wang, Xuemin Lin, et al, Labeling scheme and structural joins for graph-structured XML data, Web technologies research and development, 7th Asia-Pacific conference, Springer-Verlag Berlin, Berlin, Germany, 2005, p.277–289.

DOI: 10.1007/978-3-540-31849-1_28

[8] DBLP XML Repository, http: /dblp . uni-trier. de/xml/, Sep. (2010).

[9] ANGLES R, GUTIERREZ C, Survey of graph database models, ACM Computing Surveys, vol. 40, 2008, pp.1-39.

DOI: 10.1145/1322432.1322433

[10] Hristidis V，Papakonstantinou Y，Balmin A, Keyword proximity search on XML graphs, Conference on Data Engineering, Bangalore: IEEE Press, 2003, pp.367-378.

DOI: 10.1109/icde.2003.1260806

[11] H. V. Jagadish Rakesh Agrawal, Alexander Borgida, Efficient management of transitive relationships in large data and knowledge bases, In Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data (SIGMOD 1989), Portland, Oregon, 1989, p.253.

DOI: 10.1145/67544.66950

[12] NVIDIA, The cuda toolkit, http: /www. nvidia. com/object /what _is_ cuda_new. html, Sep. (2010).