SystemT: An Algebraic Approach to Declarative Information Extraction

Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 128–137, Uppsala, Sweden, 11-16 July 2010. c⃝2010 Association for Computational Linguistics SystemT: An Algebraic Approach to Declarative Information Extraction Laura Chiticariu Rajasekar Krishnamurthy Yunyao Li Sriram Raghavan Frederick R. Reiss Shivakumar Vaithyanathan IBM Research – Almaden San Jose, CA, USA {chiti,sekar,yunyaoli,rsriram,frreiss,vaithyan}@us.ibm.com Abstract As information extraction (IE) becomes more central to enterprise applications, rule-based IE engines have become in- creasingly important. In this paper, we describe SystemT, a rule-based IE sys- tem whose basic design removes the ex- pressivity and performance limitations of current systems based on cascading gram- mars. SystemT uses a declarative rule language, AQL, and an optimizer that generates high-performance algebraic ex- ecution plans for AQL rules. We com- pare SystemT’s approach against cascad- ing grammars, both theoretically and with a thorough experimental evaluation. Our results show that SystemT can deliver re- sult quality comparable to the state-of-the- art and an order of magnitude higher an- notation throughput. 1 Introduction In recent years, enterprises have seen the emer- gence of important text analytics applications like compliance and data redaction. This increase, combined with the inclusion of text into traditional applications like Business Intelligence, has dra- matically increased the use of information extrac- tion (IE) within the enterprise. While the tradi- tional requirement of extraction quality remains critical, enterprise applications also demand ef- ficiency, transparency, customizability and main- tainability. In recent years, these systemic require- ments have led to renewed interest in rule-based IE systems (Doan et al., 2008; SAP, 2010; IBM, 2010; SAS, 2010). Until recently, rule-based IE systems (Cunning- ham et al., 2000; Boguraev, 2003; Drozdzynski et al., 2004) were predominantly based on the cascading grammar formalism exemplified by the Common Pattern Specification Language (CPSL) specification (Appelt and Onyshkevych, 1998). In CPSL, the input text is viewed as a sequence of an- notations, and extraction rules are written as pat- tern/action rules over the lexical features of these annotations. In a single phase of the grammar, a set of rules are evaluated in a left-to-right fash- ion over the input annotations. Multiple grammar phases are cascaded together, with the evaluation proceeding in a bottom-up fashion. As demonstrated by prior work (Grishman and Sundheim, 1996), grammar-based IE systems can be effective in many scenarios. However, these systems suffer from two severe drawbacks. First, the expressivity of CPSL falls short when used for complex IE tasks over increasingly pervasive informal text (emails, blogs, discussion forums etc.). To address this limitation, grammar-based IE systems resort to significant amounts of user- defined code in the rules, combined with pre- and post-processing stages beyond the scope of CPSL (Cunningham et al., 2010). Second, the rigid evaluation order imposed in these systems has significant performance implications. Three decades ago, the database community faced similar expressivity and efficiency chal- lenges in accessing structured information. The community addressed these problems by introduc- ing a relational algebra formalism and an associ- ated declarative query language SQL. The ground- breaking work on System R …

Content truncated to 500 words