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

被引:13
作者
Ha-Nguyen Tran [1 ]
Cambria, Erik [1 ]
Hussain, Amir [2 ,3 ]
机构
[1] Nanyang Technol Univ, Sch Comp Sci & Engn, Singapore, Singapore
[2] Univ Stirling, Div Comp Sci & Maths, Fac Nat Sci, Stirling, Scotland
[3] Anhui Univ, Hefei, Anhui, Peoples R China
基金
英国工程与自然科学研究理事会; 中国国家自然科学基金; 新加坡国家研究基金会;
关键词
Common-sense reasoning; Subgraph matching; GPU computing; CUDA; SENTIMENT ANALYSIS; ALGORITHM;
D O I
10.1007/s12559-016-9418-4
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
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. 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. We show that GpSense outperforms state-of-the-art algorithms and efficiently answers subgraph queries on large common-sense graphs.
引用
收藏
页码:1074 / 1086
页数:13
相关论文
共 32 条
  • [1] [Anonymous], 2015, P AAAI FLAIRS
  • [2] [Anonymous], 2014, Commonsense Reasoning: An Event Calculus Based Approach
  • [3] [Anonymous], 2007, GPU gems
  • [4] [Anonymous], 2015, Sentic computing: a common-sense-based framework for concept-level sentiment analysis
  • [5] COSI: Cloud Oriented Subgraph Identification in Massive Social Networks
    Brocheler, Matthias
    Pugliese, Andrea
    Subrahmanian, V. S.
    [J]. 2010 INTERNATIONAL CONFERENCE ON ADVANCES IN SOCIAL NETWORKS ANALYSIS AND MINING (ASONAM 2010), 2010, : 248 - 255
  • [6] Cambria E, 2009, COMMON SENSE COMPUTI
  • [7] Affective Computing and Sentiment Analysis
    Cambria, Erik
    [J]. IEEE INTELLIGENT SYSTEMS, 2016, 31 (02) : 102 - 107
  • [8] Cambria E, 2014, AAAI CONF ARTIF INTE, P1515
  • [9] Guest Editorial: Big Social Data Analysis
    Cambria, Erik
    Wang, Haixun
    White, Bebo
    [J]. KNOWLEDGE-BASED SYSTEMS, 2014, 69 : 1 - 2
  • [10] Cook S. A., 1971, Proceedings of the 3rd annual ACM symposium on theory of computing, P151