Skip to main content
Top

2016 | OriginalPaper | Chapter

An Improved Keyword Search on Big Data Graph with Graphics Processors

Authors : Xiu He, Bo Yang

Published in: Computational Intelligence and Intelligent Systems

Publisher: Springer Singapore

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference Bhalotia, G., Hulgeri, A., Nakhe, C., Chakrabarti, S., Sudarshan, S.: Keyword searching and browsing in databases using banks. In: Proceedings of the 18th International Conference Data Engineering (ICDE), pp. 431–440 (2002) Bhalotia, G., Hulgeri, A., Nakhe, C., Chakrabarti, S., Sudarshan, S.: Keyword searching and browsing in databases using banks. In: Proceedings of the 18th International Conference Data Engineering (ICDE), pp. 431–440 (2002)
2.
go back to reference Kacholia, V., Pandit, S., Chakrabarti, S., Desai, R., Karambelkar, H.: Bidirectional expansion for keyword search on graph databases. In: Proceedings of the 31st International Conference Very Large Data Bases (VLDB), pp. 505–516 (2005) Kacholia, V., Pandit, S., Chakrabarti, S., Desai, R., Karambelkar, H.: Bidirectional expansion for keyword search on graph databases. In: Proceedings of the 31st International Conference Very Large Data Bases (VLDB), pp. 505–516 (2005)
3.
go back to reference Kimelfeld, B., Sagiv, Y.: Finding and approximating top-k answers in keyword proximity search. In: Proceedings of the 25th ACMSIGMOD-SIGACT-SIGART Symposium Principles Database Systems (PODS) (2006) Kimelfeld, B., Sagiv, Y.: Finding and approximating top-k answers in keyword proximity search. In: Proceedings of the 25th ACMSIGMOD-SIGACT-SIGART Symposium Principles Database Systems (PODS) (2006)
4.
go back to reference Huang, H., Liu, C.: Query evaluation on probabilistic RDF databases. In: Vossen, G., Long, D.D., Yu, J.X. (eds.) WISE 2009. LNCS, vol. 5802, pp. 307–320. Springer, Heidelberg (2009)CrossRef Huang, H., Liu, C.: Query evaluation on probabilistic RDF databases. In: Vossen, G., Long, D.D., Yu, J.X. (eds.) WISE 2009. LNCS, vol. 5802, pp. 307–320. Springer, Heidelberg (2009)CrossRef
5.
go back to reference Liben-Nowell, D., Kleinberg, J.: The link prediction problem for social networks. In: Proceedings of the 12th International Conference Information Knowledge Management (CIKM), pp. 556–569 (2003) Liben-Nowell, D., Kleinberg, J.: The link prediction problem for social networks. In: Proceedings of the 12th International Conference Information Knowledge Management (CIKM), pp. 556–569 (2003)
6.
go back to reference Adar, E., Re, C.: Managing uncertainty in social networks. IEEE Data Eng. Bull. 30(2), 15–22 (2007) Adar, E., Re, C.: Managing uncertainty in social networks. IEEE Data Eng. Bull. 30(2), 15–22 (2007)
7.
go back to reference Nierman, A., Jagadish, H.V.: ProTDB: probabilistic data in XML. In: Proceedings of the International Conference Very Large Data Bases (VLDB) (2002) Nierman, A., Jagadish, H.V.: ProTDB: probabilistic data in XML. In: Proceedings of the International Conference Very Large Data Bases (VLDB) (2002)
8.
go back to reference Senellart, P., Abiteboul, S.: On the complexity of managing probabilistic XML data. In: Proceedings of the 26th ACM SIGMOD-SIGACTSIGART Symposium Principles Database Systems (PODS) (2007) Senellart, P., Abiteboul, S.: On the complexity of managing probabilistic XML data. In: Proceedings of the 26th ACM SIGMOD-SIGACTSIGART Symposium Principles Database Systems (PODS) (2007)
9.
go back to reference Kimelfeld, B., Kosharovsky, Y., Sagiv, Y.: Query efficiency in probabilistic XML models. In: Proceedings of the ACM SIGMOD International Conference Management of Data (2008) Kimelfeld, B., Kosharovsky, Y., Sagiv, Y.: Query efficiency in probabilistic XML models. In: Proceedings of the ACM SIGMOD International Conference Management of Data (2008)
10.
go back to reference Golenberg, B.K.K., Sagiv, Y.: Keyword proximity search in complex data graphs. In: Proceedings of the ACM SIGMOD International Conference Management of Data (2008) Golenberg, B.K.K., Sagiv, Y.: Keyword proximity search in complex data graphs. In: Proceedings of the ACM SIGMOD International Conference Management of Data (2008)
11.
go back to reference Ke, Y., Cheng, J., Yu, J.X.: Querying large graph databases. In: 15th International Conference on Database Systems for Advanced Applications (2010) Ke, Y., Cheng, J., Yu, J.X.: Querying large graph databases. In: 15th International Conference on Database Systems for Advanced Applications (2010)
12.
go back to reference Dalvi, B.B., Kshirsagar, M., Sudarshan, S.: Keyword search on external memory data graphs. In: VLDB, pp. 1189–1204 (2008) Dalvi, B.B., Kshirsagar, M., Sudarshan, S.: Keyword search on external memory data graphs. In: VLDB, pp. 1189–1204 (2008)
13.
go back to reference Bhalotia, G., Nakhe, C., Hulgeri, A., Chakrabarti, S., Sudarshan, S.: Keyword searching and browsing in databases using BANKS. In: International Conference on Data Engineering (ICDE), pp. 431–440 (2002) Bhalotia, G., Nakhe, C., Hulgeri, A., Chakrabarti, S., Sudarshan, S.: Keyword searching and browsing in databases using BANKS. In: International Conference on Data Engineering (ICDE), pp. 431–440 (2002)
14.
go back to reference Kacholia, V., Pandit, S., Chakrabarti, S., et al.: Bidirectional expansion for keyword search on graph databases. In: Proceedings of 31st International Conference on Very Large Data Bases, pp. 505–516 (2005) Kacholia, V., Pandit, S., Chakrabarti, S., et al.: Bidirectional expansion for keyword search on graph databases. In: Proceedings of 31st International Conference on Very Large Data Bases, pp. 505–516 (2005)
15.
go back to reference Hao, H., Wang, H., Yang, J., Yu, P.S.: BLINKS: Ranked keyword searches on graphs. In: SIGMOD, pp. 305–316 (2007) Hao, H., Wang, H., Yang, J., Yu, P.S.: BLINKS: Ranked keyword searches on graphs. In: SIGMOD, pp. 305–316 (2007)
16.
go back to reference Zhou, G., Feng, H., He, G., Chen, H.: Survey of data management on graphics processor units. J. Front. Comput. Sci. Technol. 4, 289–303 (2010). (in Chinese) Zhou, G., Feng, H., He, G., Chen, H.: Survey of data management on graphics processor units. J. Front. Comput. Sci. Technol. 4, 289–303 (2010). (in Chinese)
17.
go back to reference Wang, H., Wang, W., Lin, X., Li, J.: Labeling scheme and structural joins for graph-structured XML data. In: Zhang, Y., Tanaka, K., Yu, J.X., Wang, S., Li, M. (eds.) APWeb 2005. LNCS, vol. 3399, pp. 277–289. Springer, Heidelberg (2005)CrossRef Wang, H., Wang, W., Lin, X., Li, J.: Labeling scheme and structural joins for graph-structured XML data. In: Zhang, Y., Tanaka, K., Yu, J.X., Wang, S., Li, M. (eds.) APWeb 2005. LNCS, vol. 3399, pp. 277–289. Springer, Heidelberg (2005)CrossRef
19.
go back to reference Angles, R., Gutierrez, C.: Survey of graph database models. ACM Comput. Surv. 40, 1–39 (2008)CrossRef Angles, R., Gutierrez, C.: Survey of graph database models. ACM Comput. Surv. 40, 1–39 (2008)CrossRef
20.
go back to reference Hristidis, V., Papakonstantinou, Y., Balmin, A.: Keyword proximity search on XML graphs. In: Conference on Data Engineering, pp. 367–378. IEEE Press, Bangalore (2003) Hristidis, V., Papakonstantinou, Y., Balmin, A.: Keyword proximity search on XML graphs. In: Conference on Data Engineering, pp. 367–378. IEEE Press, Bangalore (2003)
21.
go back to reference Jagadish, H.V., Agrawal, R., Borgida, A.: 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, pp. 253–262 (1989) Jagadish, H.V., Agrawal, R., Borgida, A.: 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, pp. 253–262 (1989)
Metadata
Title
An Improved Keyword Search on Big Data Graph with Graphics Processors
Authors
Xiu He
Bo Yang
Copyright Year
2016
Publisher
Springer Singapore
DOI
https://doi.org/10.1007/978-981-10-0356-1_41

Premium Partner