nach oben

Cognitive Computation

Erschienen in:

01.12.2016

Towards GPU-Based Common-Sense Reasoning: Using Fast Subgraph Matching

verfasst von: Ha-Nguyen Tran, Erik Cambria, Amir Hussain

Erschienen in: Cognitive Computation | Ausgabe 6/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Background/Introduction

Common-sense reasoning is concerned with simulating cognitive human ability to make presumptions about the type and essence of ordinary situations encountered every day. The most popular way to represent common-sense knowledge is in the form of a semantic graph. Such type of knowledge, however, is known to be rather extensive: the more concepts added in the graph, the harder and slower it becomes to apply standard graph mining techniques.

Methods

In this work, we propose a new fast subgraph matching approach to overcome these issues. Subgraph matching is the task of finding all matches of a query graph in a large data graph, which is known to be a non-deterministic polynomial time-complete problem. Many algorithms have been previously proposed to solve this problem using central processing units. Here, we present a new graphics processing unit-friendly method for common-sense subgraph matching, termed GpSense, which is designed for scalable massively parallel architectures, to enable next-generation Big Data sentiment analysis and natural language processing applications.

Results and Conclusions

We show that GpSense outperforms state-of-the-art algorithms and efficiently answers subgraph queries on large common-sense graphs.

Vorheriger Artikel Weight Uncertainty in Boltzmann Machine

Nächster Artikel Probabilistic Belief Embedding for Large-Scale Knowledge Population

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

https://developer.nvidia.com/what-cuda.

Brocheler M, Pugliese A, Subrahmanian VS. COSI: cloud oriented subgraph identification in massive social networks. In: 2010 International conference on advances in social networks analysis and mining (ASONAM). IEEE; 2010, p. 248–55.

Cambria E. Affective computing and sentiment analysis. IEEE Intell Syst. 2016;31(2):102–7.CrossRef

Cambria E, Hussain A. Sentic computing: a common-sense-based framework for concept-level sentiment analysis, vol. 1. Berlin: Springer; 2015.CrossRef

Cambria E, Hussain A, Havasi C, Eckl C. Common sense computing: from the society of mind to digital intuition and beyond. Berlin: Springer; 2009.

Cambria E, Olsher D, Rajagopal D. SenticNet 3: a common and common-sense knowledge base for cognition-driven sentiment analysis. In: AAAI. Quebec City; 2014. p. 1515–21.

Cambria E, Rajagopal D, Kwok K, Sepulveda J. GECKA: game engine for commonsense knowledge acquisition. In: FLAIRS; 2015. p. 282–7.

Cambria E, Wang H, White B. Guest editorial: big social data analysis. Knowl Based Syst. 2014;69:1–2.CrossRef

Cook SA. The complexity of theorem-proving procedures. In: Proceedings of the third annual ACM symposium on theory of computing. ACM; 1971. p. 151–8.

Cordella LP, Foggia P, Sansone C, Vento M. A (sub) graph isomorphism algorithm for matching large graphs. IEEE Trans Pattern Anal Mach Intell. 2004;26(10):1367–72.CrossRefPubMed

10.

Han W-S, Lee J, Lee J-H. Turbo iso: towards ultrafast and robust subgraph isomorphism search in large graph databases. In: Proceedings of the 2013 ACM SIGMOD international conference on management of data. ACM; 2013. p. 337–48.

11.

Harish P, Narayanan P. Accelerating large graph algorithms on the GPU using CUDA. Berlin: Springer; 2007.CrossRef

12.

Harris M, Sengupta S, Owens JD. GPU gems 3: parallel prefix sum (scan) with CUDA. Addison-Wesley Professional; 2007. p. 851–76.

13.

He H, Singh AK. Graphs-at-a-time: query language and access methods for graph databases. In: Proceedings of the 2008 ACM SIGMOD international conference on management of data. ACM; 2008. p. 405–18

14.

Hong S, Kim SK, Oguntebi T, Olukotun K. Accelerating CUDA graph algorithms at maximum warp. In: ACM SIGPLAN notices, vol. 46. ACM; 2011. p. 267–76.

15.

Jenkins J, Arkatkar I, Owens JD, Choudhary A, Samatova F. Lessons learned from exploring the backtracking paradigm on the GPU. Berlin: Springer; 2011.CrossRef

16.

Katz GJ, Kider JT Jr. All-pairs shortest-paths for large graphs on the GPU. In: Proceedings of the 23rd ACM SIGGRAPH/EUROGRAPHICS symposium on graphics hardware. Eurographics Association; 2008. p. 47–55.

17.

Merrill D, Garland M, Grimshaw A. Scalable GPU graph traversal. In: ACM SIGPLAN notices, vol. 47. ACM; 2012. p. 117–28.

18.

Minsky M. Society of mind. New York City: Simon and Schuster; 1988.

19.

Mueller ET. Commonsense reasoning: an event calculus based approach. Burlington: Morgan Kaufmann; 2014.

20.

Poria S, Cambria E, Howard N, Huang G-B, Hussain A. Fusing audio, visual and textual clues for sentiment analysis from multimodal content. Neurocomputing. 2016;174:50–9.CrossRef

21.

Poria S, Gelbukh A, Agarwal B, Cambria E, Howard N. Common sense knowledge based personality recognition from text. Berlin: Springer; 2013.

22.

Poria S, Gelbukh A, Cambria E, Das D, Bandyopadhyay S. Enriching senticnet polarity scores through semi-supervised fuzzy clustering. In: 2012 IEEE 12th international conference on data mining workshops (ICDMW). IEEE; 2012. p. 709–16.

23.

Poria S, Gelbukh A, Cambria E, Yang P, Hussain A, Durrani TS. Merging senticnet and wordnet-affect emotion lists for sentiment analysis. In: 2012 IEEE 11th international conference on signal processing (ICSP), vol. 2. IEEE; 2012. p. 1251–55.

24.

Shang H, Zhang Y, Lin X, Yu JX. Taming verification hardness: an efficient algorithm for testing subgraph isomorphism. Proc VLDB Endow. 2008;1(1):364–75.CrossRef

25.

Sun Z, Wang H, Wang H, Shao B, Li J. Efficient subgraph matching on billion node graphs. Proc VLDB Endow. 2012;5(9):788–99.CrossRef

26.

Tran HN, Kim JJ, He B. Fast subgraph matching on large graphs using graphics processors. In: Renz M, Shahabi C, Zhou X, Cheema AM, editors. Database systems for advanced applications: 20th International Conference, DASFAA 2015, Proceedings, Part I. Springer; 2015. p. 299–315.

27.

Ullmann JR. An algorithm for subgraph isomorphism. J ACM (JACM). 1976;23(1):31–42.CrossRef

28.

Vineet V, Harish P, Patidar S, Narayanan P. Fast minimum spanning tree for large graphs on the GPU. In: Proceedings of the conference on high performance graphics 2009. ACM; 2009. p. 167–71.

29.

Wang Q-F, Cambria E, Liu C-L, Hussain A. Common sense knowledge for handwritten Chinese text recognition. Cognit Comput. 2013;5(2):234–42.CrossRef

30.

Zhang S, Li S, Yang J. GADDI: distance index based subgraph matching in biological networks. In: Proceedings of the 12th international conference on extending database technology: advances in database technology. ACM; 2009. p. 192–203.

31.

Zhao P, Han J. On graph query optimization in large networks. Proc VLDB Endow. 2010;3(1–2):340–51.CrossRef

32.

Dashtipour K, Poria S, Hussain A, Cambria E, Hawalah AYA, Gelbukh A, Zhou Q. Multilingual sentiment analysis: state of the art and independent comparison of techniques. Cogn Comput. 2016. doi:10.1007/s12559-016-9415-7.

Titel: Towards GPU-Based Common-Sense Reasoning: Using Fast Subgraph Matching
verfasst von: Ha-Nguyen Tran
Erik Cambria
Amir Hussain
Publikationsdatum: 01.12.2016
Verlag: Springer US
Erschienen in: Cognitive Computation / Ausgabe 6/2016
Print ISSN: 1866-9956
Elektronische ISSN: 1866-9964
DOI: https://doi.org/10.1007/s12559-016-9418-4

Springer Professional

Abstract

Background/Introduction

Methods

Results and Conclusions

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 6/2016

Bifurcation Analysis of Two-Neuron Networks with Discrete and Distributed Delays

Weight Uncertainty in Boltzmann Machine

Multi-criteria Group Decision-Making Based on Interval Neutrosophic Uncertain Linguistic Variables and Choquet Integral

Group Decision Making with Dual Hesitant Fuzzy Preference Relations

A Computational Approach of the French Flag Model to Connect Growth and Specification in Developmental Biology

An Extended Outranking Approach to Rough Stochastic Multi-criteria Decision-Making Problems