Entity Annotation based on Inverse Index Operations

Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing (EMNLP 2006), pages 492–500, Sydney, July 2006. c⃝2006 Association for Computational Linguistics Entity Annotation based on Inverse Index Operations Ganesh Ramakrishnan, Sreeram Balakrishnan, Sachindra Joshi IBM India Research Labs IIT Delhi, Hauz Khas, New Delhi, India {ganramkr, sreevb, jsachind}@in.ibm.com Abstract Entity annotation involves attaching a la- bel such as ‘name’ or ‘organization’ to a sequence of tokens in a document. All the current rule-based and machine learning- based approaches for this task operate at the document level. We present a new and generic approach to entity annotation which uses the inverse index typically cre- ated for rapid key-word based searching of a document collection. We define a set of operations on the inverse index that al- lows us to create annotations defined by cascading regular expressions. The entity annotations for an entire document cor- pus can be created purely of the index with no need to access the original docu- ments. Experiments on two publicly avail- able data sets show very significant perfor- mance improvements over the document- based annotators. 1 Introduction Entity Annotation associates a well-defined label such as ‘person name’, ‘organization’, ‘place’, etc., with a sequence of tokens in unstructured text. The dominant paradigm for annotating a document collection is to annotate each document separately. The computational complexity of an- notating the collection in this paradigm, depends linearly on the number of documents and the cost of annotating each document. More precisely, it depends on the total number of tokens in the doc- ument collection. It is not uncommon to have mil- lions of documents in a collection. Using this par- adigm, it can take hours or days to annotate such big collections even with highly parallel server farms. Another drawback of this paradigm is that the entire document collection needs to be re- processed whenever new annotations are required. In this paper, we propose an alternative para- digm for entity annotation. We build an index for the tokens in the document collection first. Us- ing a set of operators on the index, we can gener- ate new index entries for sequences of tokens that match any given regular expression. Since a large class of annotators (e.g., GATE (Cunningham et al., 2002)) can be built using cascading regular ex- pressions, this approach allows us to support anno- tation of the document collection purely from the index. We show both theoretically and experimentally that this approach can lead to substantial reduc- tions in computational complexity, since the order of computation is dependent on the size of the in- dexes and not the number of tokens in the doc- ument collection. In most cases, the index sizes used for computing the annotations will be a small fraction of the total number of tokens. In (Cho and Rajagopalan, 2002) the authors de- velop a method for speeding up the evaluation of a regular expression ‘R’ on a large text corpus by use of an optimally constructed multi-gram index to …

Content truncated to 500 words