2015 CostEffectiveConceptualDesignfo

(Termehchy et al., 2015) ⇒ Arash Termehchy, Ali Vakilian, Yodsawalai Chodpathumwan, and Marianne Winslett. (2015). “Cost-Effective Conceptual Design for Information Extraction.” In: ACM Transactions on Database Systems (TODS) Journal, 40(2). doi:10.1145/2716321

Subject Headings: Information Extraction from Text.

Notes

Cited By

Quotes

Abstract

It is well established that extracting and annotating occurrences of entities in a collection of unstructured text documents with their concepts improves the effectiveness of answering queries over the collection. However, it is very resource intensive to create and maintain large annotated collections. Since the available resources of an enterprise are limited and/or its users may have urgent information needs, it may have to select only a subset of relevant concepts for extraction and annotation. Wecall this subset a conceptual design for the annotated collection. In this article, we introduce and formally define the problem of cost-effective conceptual design where, given a collection, a set of relevant concepts, and a fixed budget, one likes to find a conceptual design that most improves the effectiveness of answering queries over the collection. We provide efficient algorithms for special cases of the problem and prove it is generally NP-hard in the number of relevant concepts. We propose three efficient approximations to solve the problem: a greedy algorithm, an approximate popularity maximization (APM for short), and approximate annotation-benefit maximization (AAM for short). We show that, if there are no constraints regrading the overlap of concepts, APM is a fully polynomial time approximation scheme. We also prove that if the relevant concepts are mutually exclusive, the greedy algorithm delivers a constant approximation ratio if the concepts are equally costly, APM has a constant approximation ratio, and AAM is a fully polynomial-time approximation scheme. Our empirical results using a Wikipedia collection and a search engine query log validate the proposed formalization of the problem and show that APM and AAM efficiently compute conceptual designs. They also indicate that, in general, APM delivers the optimal conceptual designs if the relevant concepts are not mutually exclusive. Also, if the relevant concepts are mutually exclusive, the conceptual designs delivered by AAM improve the effectiveness of answering queries over the collection more than the solutions provided by APM.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2015 CostEffectiveConceptualDesignfo	Arash Termehchy Ali Vakilian Yodsawalai Chodpathumwan Marianne Winslett			Cost-Effective Conceptual Design for Information Extraction				10.1145/2716321		2015