document: Collective annotation of Wikipedia entities in web text To take the first step beyond keyword-based search toward entity-based search , suitable token spans ( `` spots '' ) on documents must be identified as references to real-world entities from an entity catalog . Several systems have been proposed to link spots on Web pages to entities in Wikipedia . They are largely based on local compatibility between the text around the spot and textual metadata associated with the entity . Two recent systems exploit inter-label dependencies , but in limited ways . We propose a general collective disambiguation approach . Our premise is that coherent documents refer to entities from one or a few related topics or domains . We give formulations for the trade-off between local spot-to-entity compatibility and measures of global coherence between entities . Optimizing the overall entity assignment is NP-hard . We investigate practical solutions based on local hill-climbing , rounding integer linear programs , and pre-clustering entities followed by local optimization within clusters . In experiments involving over a hundred manually-annotated Web pages and tens of thousands of spots , our approaches significantly outperform recently-proposed algorithms .
doc_bio_tags: O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O