=Paper=
{{Paper
|id=Vol-515/paper-8
|storemode=property
|title=Annotated Search and Element Retrieval
|pdfUrl=https://ceur-ws.org/Vol-515/livingweb2009_paper8.pdf
|volume=Vol-515
|dblpUrl=https://dblp.org/rec/conf/semweb/ZaragozaMBA09
}}
==Annotated Search and Element Retrieval==
https://ceur-ws.org/Vol-515/livingweb2009_paper8.pdf
Annotated Search and Element Retrieval
1 1 1 1
Hugo Zaragoza and Michael Matthews and Roi Blanco and Jordi Atserias
Yahoo! Research, Barcelona (Spain)
Abstract. Despite the great interest in dierent forms of textual an-
notation (named entity extraction, semantic tagging, syntactic and se-
mantic parsing, etc.), there is still no consensus about which search tasks
can be improved with such annotations, and what search algorithms are
required to implement e cient engines to solve these tasks. We de ne
formally two retrieval tasks in annotated collections: annotated retrieval
and element retrieval. We discuss their dierences and describe e cient
indexing structures, and how they can be implemented in Lucene and
MG4J, two open source retrieval engines. Finally, we give a technical
overview of two element retrieval use cases.
1 Introduction
There has been a great deal of work in natural language processing (NLP) over
the past several decades. While there has been hope that this work will translate
into better search, this still has not been clearly realized. Most NLP processing
involves adding annotations to documents that help to clarify the documents
intended meaning. Named-entity recognition (NER) is one of the most studied
NLP techniques and one that has signi cant potential to improve search appli-
cations. The following is just a sample of examples queries: 1) [George Bush,
PERSON] , 2) [George Bush, PERSON] born [DATE] , 3) IBM ceo [PER-
SON] . Like traditional ad-hoc queries in Information Retrieval, these queries
should return a set of document or passages. A dierent type of query aims at
retrieving and ranking the entities themselves (instead of the documents). For
example, in tasks such as person nding, entity ranking, or queries such as: 4)
nd people related to George Bush or 5) nd institutions (or dates, or emotion-
ally charged verbs) related to the query impact of terrorism on public opinion
in Great Britain .
There are many potential search tasks over annotated collections, but they often
require specialized indexes and algorithms. This makes it hard to establish a
research agenda for annotated search. But as more and more examples appear
(publications, applications) some trends emerge and we can hope to establish
common frameworks and technologies. In this paper we propose a division into
two families of annotated search tasks :
Annotated Retrieval: retrieval of documents relevant to an annotated ad-hoc
query.
Element Retrieval: retrieval of elements (e.g. entities, not documents) rele-
vant to an ad-hoc query.
Annotated Retrieval is the standard ad-hoc document retrieval task, with the
added di culty of coping with annotated collections and queries (examples 1-
3 above). Element retrieval is signi cantly dierent from document retrieval,
because what is returned is not a ranked list of documents, but rather, a ranked
list of elements such as entities (examples 4-5 above).
In the remaining of the paper we discuss both tasks, with an emphasis on the
later. We describe e cient indexing mechanisms required by them (Sections 2
and 3) and describe several use cases.
1.1 Related Work
With the incredible growth of the Internet, there has been a great deal of work on
e ciently searching large collections [14,16] including a number of open source
search implementations such as Lucene [19] and MG4J [20,6]. In the bulk of this
work, a document (or passage) is represented by tokens, possibly with some sim-
ple stemming operations, but without any further linguistic annotations. There
has been a parallel eort to move beyond keyword representation to capture the
meaning of documents. The semantic web has long promised delivering content
in machine understand form, typically based in RDF [13]. However, the bulk
of information today is still in the form of free text which has lead to a surge
of research into natural language processing and an increasing number of an-
notation frameworks such as GATE [8] and UIMA [10] which allow for large
documentation annotation projects. The bene t of the resulting annotations to
search applications has been shown in such areas as biotechnology, legal doc-
ument retrieval, etc. Entity ranking has also been gaining interest in dierent
forms: expert search, people search, and other forms of entity ranking have been
addressed by the major evaluation campaigns (such as INEX [1] and TREC
[4]). Some academic and commercial search applications have appeared on dif-
ferent entity search tasks, such as Beagle++ [7] which provides a semantic-based
desktop search utility. However, in our opinion there is still the need of a clear
framework for research in annotation retrieval and entity ranking; Rode [12] pro-
vides an early attempt on entity ranking, very much in the lines of our present
work.
Several open source search engines have tackled the technical problems of im-
plementing annotated search engines, mainly (to our knowledge): PF-Tijah [9]
a native XML search-engine, Solr [22] and LuceneSail [11], which combines the
keyword search capabilities of Lucene with structured data stores, and MG4J
v3.0 and Archive4J [17,20] which implement parallel indexes and can be com-
bined to build e cient element indices.
1.2 Notation
There is no standard notation for retrieval on annotated collections, and dierent
authors have used terms to mean slightly dierent things (terms like entity,
forward index, etc). For this reason we are forced to introduce our own term
de nitions and notations. We will discuss annotations and elements (entities, in
a very general sense); relations are outside the scope of this paper.
( )
A passage 𝑠𝑖 ∈ 𝒮 is a sequence of tokens plus context: 𝑠𝑖 = 𝑤𝑖1 , 𝑤𝑖2 , ..., 𝑤𝑖∣𝑠𝑖 ∣ , 𝛺 .
Passages may be sentences, paragraphs, documents, sliding windows of text, but
they need to be uniquely identi ed textual units (for now we do not allow any
structure on the units). Tokens will typically correspond to words, but language
tokenisation is a di cult business and outside the scope of this paper. We will
assume that there is some tokeniser that has taken raw text and segmented it
into tokens. Passages may contain some context information (𝛺 ) such as the
title of the document, a surrounding window of text, external meta-data, etc.
A token annotation is the tuple 𝑎 = (𝑖, 𝛼, 𝛽, 𝑡) where 𝑖 is the identi er of the
passage annotated, 𝛼 and 𝛽 are the beginning and ending positions of the an-
notation respectively, and 𝑡 is the type of the annotation. An element is a tuple
𝑒 = (𝑠, 𝑡) where 𝑠 is its value (a sequence of tokens) and 𝑡 is its type. Unlike
annotations, elements are not tied to a particular passage. We call ℰ the set of
all elements.
Annotations can be obtained by automatic or manual extraction and can be
encoded in many dierent ways, depending on their intended usage, their sizes,
types, etc. The following sections will discuss this issue.
We also need some notation to express search queries. Given the collection of
passages 𝒮 , a query is de ned as a function that maps 𝒮 to a ranked subset
𝑆𝑞 . We will use the following query operators (which can be combined into
more complex queries): conjunction “𝑎 𝑏” retrieves passages with tokens 𝑎 and
𝑏, disjunction “𝑎∣𝑏” retrieves passages with tokens 𝑎 or 𝑏, eld restriction 𝐴 : 𝑎
retrieves passages with token 𝑎 in eld 𝐴, position restriction “[𝑎, 𝑏] ∼ 𝑛” re-
trieves passages where token 𝑎 is followed by token 𝑏 in a window of at most 𝑛
tokens, and alignment “𝑎 ∧ 𝑏” retrieves passages where token 𝑎 is aligned with
(in the same position as) token 𝑏.
2 Annotated Passage Retrieval
Inverted indices allow fast and e cient retrieval of passages for token queries
allowing some operators (such as disjunctive and conjunctive queries, token pre-
xes, constraints on match distances, etc). It is possible to modify these indices
to allow similar query operators on an annotated collection.
In its basic form, an inverted index contains one postings list for every token
present in the collection. Typically, postings lists may contain information ar-
ranged into dierent levels of granularity, from the presence/absence of tokens
to their frequency or retrieval weight, their position, eld information, typog-
raphy, etc. It is possible to modify inverted indices slightly to perform retrieval
and ranking over annotated collections. One approach is to implement several
parallel indexes on the collection, by allowing several tokens in dierent elds to
share the same position: the main index stores the positions of text tokens, and
each additional index stores the annotations of the dierent types. At a low-level
this implies building a dierent index for each type we want to include in a query
(tokens, entity types, and so on), and implementing a fast alignment operator.
For instance, querying for the element 𝑒1 =[apple, SUBSTANCE] would re-
quire a searching for the text-token apple in the same position as the type-token
SUBSTANCE. The query for the element 𝑒1 could be translated then into ap-
ple:TOKENS ^ SUBSTANCE:TYPES . A passage would satisfy this query if
both apple and SUBSTANCE are found in the same passage at the same po-
sition. Since the alignment operator preserves the semantics of the other query
operators, the result is a very powerful query language over annotated collec-
tions. Alignment can be used in combination with phrasal queries, negation,
positional restrictions, etc. For example, we could query for pizza or pasta in
New York as [(pizza|pasta) [New^CITY, York^CITY]∼1]]∼10 .
Note that in the examples above we did not enforce the limits of the elements:
our queries would incorrectly match longer elements (such as [apple pie, SUB-
STANCE] ) or sequences of short ones (such as [New, CITY] [York, CITY] ).
This can be solved by encoding the limits into the types. In particular, we con-
catenate to the type a character encoding the bracketing (e.g. beginning (B ),
ending (E ), continuing (I ) or a single token (U )). This way we can query for
apple^SUBSTANCE_U and [New^CITY_B, York^CITY_E]∼1 .
There is a special type of annotated query that is common in applications and
that does not require a full-blown parallel index: a type restriction. Here, we
want to restrict our search to passages that contain a particular annotation type
(e.g. Einstein DATE ). We are not concerned with the position of the type
annotation in the text, or even with the actual value of the annotation. This
type of ltering is easily implemented using elds (without positions) where we
simply store the types present in the passage.
Parallel inverted indices can be easily implement in traditional search engines
with positional indices, and for this reason they have been used extensively al-
though rarely discussed in the academic literature. In the open domain, parallel
indices are implemented in MG4J and can be implemented easily in other frame-
works such as Lucene. For example, in Lucene, one can obtain a parallel index
by writing a document reader that does not increment the position (setting Po-
sitionIncrement to 0) when types are encountered. Although Lucene does not
provide speci cally an alignment operator, one can obtain one by forcing a dis-
tance of zero between the token and the type. In MG4J parallel indices can be
obtained naturally by indexing dierent elds and aligning them at query time
with the alignment operator. Another example of a parallel index discussed in
the literature is the colored index used by Attardi's IXE system [3].
3 Element Retrieval
In applications such as element ranking and faceted search we are required to
provide a ranked list of elements (not documents) that are relevant to the query
in some sense. This requires more analysis in the corpus than the standard
retrieval task: after solving the query and obtaining a ranked list of passages (𝑆𝑞 ),
we need to nd which elements appear in those documents (𝐶𝑞 ), a potentially
expensive operation.
The most straightforward method would be, for each returned passage, to load
the full original annotated passage and simply traverse the passage counting
the annotations. The performance would be highly dependent on the e ciency
with which the passage annotations could be loaded given the passage identi er.
If the original documents are stored as individual les in a le system or as
records in a database system, it may be possible to retrieve 10 or even 100
passages, but retrieving even 1000 passages will not be feasible for a real time
search application. It is clear that a more e cient data structure must be used
to perform the counts.
If we ignore the positions of annotations (𝛼 and 𝛽 ) the relationship between
passages and element instances can be represented conceptually as a graph, in
which each passage 𝑠 ∈ 𝒮 and each element 𝑒 ∈ ℰ are nodes, and there is a
directed edge from 𝑠 to 𝑒 if the element 𝑒 is present (contained) in the passage 𝑠.
We call this an element containment graph C, and since it is a bipartite graph it
can be represented as a ∣𝒮∣ × ∣ℰ∣ matrix, where 𝐶𝑖𝑗 is the strength of connection
between passage 𝑠𝑖 and element 𝑒𝑗 (typically 1 if it appears, 0 otherwise).
At query time, we execute the standard query and obtain the set of passages
of interest (𝑆𝑞 , or perhaps only the top-𝑘 scores in this set). Then, for every
passage of interest we query 𝐶 to obtain the elements contained in the passage.
Doing so, we obtain the subgraph 𝐶𝑞 ⊆ 𝐶 which contains information useful for
ranking, such as the frequency of an entity in the result set.
Representing 𝐶 as a graph allows us to use tools from graph theory and linear
algebra to further understand and manipulate elements. For example, we see
that the passage frequency of an element is equal to its degree in the graph,
and this can be extended to the weighted degree, which takes into account the
𝑇
strength of the connection of each of its instances. Furthermore, CC gives us a
passage similarity (equal to the number of element co-occurrences if C is binary),
𝑇
and C C an entity similarity (number of passage co-occurrences if C is binary).
We can further use C to de ne graph centrality algorithms such as HITS or
PageRank, or to de ne several types of random walks [12].
Representing C as a bipartite graph also allows us to use existing graph com-
pression and querying algorithms, such as WebGraph [5]. The actual values of
the entities and passages (e.g. its string values and other meta-data) are typically
stored separately in dictionaries, for example as alphabetically ordered les (or
further compressed as front-encoded lists for example). This makes it possible
to keep in memory element containment graphs of millions of nodes, and query
them many thousands of times per second.
Like any sparse matrix, C can also be represented as an index either in row
(passage) order or column (element) order. A row can be seen as a description
of the elements contained in a passage: 𝑠𝑖 : {𝑒𝑖1 , ..., 𝑒𝑖𝑛 }, whereas a column is a
description of the passages in which an element is present 𝑒𝑗 : {𝑠𝑗1 , ..., 𝑠𝑗𝑚 }. Both
these representations lead to e cient indexes which allow querying for passages
(in the rst case) and for elements (in the second case). If instead of elements we
were considering textual terms, then the column vectors would be similar to an
inverted index. Pushing the analogy, some people refer to row or passage order
indices as forward indices.
There exist e cient algorithms to store forward indices. Archive4J [17] was
speci cally designed for this purpose, and implements a data structure called
an archive, which builds a direct le of a document collection allowing retrieval
of data from a single document, speci cally its length in words and which terms
occur in the document with their respective term frequencies. The tool provides
random access to documents while being able to obtain high compression ratios.
By indexing elements instead of terms, we can obtain a forward index (a row of
C). Solr, a search engine built using the Lucene libraries, has a similar structure
referred to as an UnInvertedIndex. Both structures are useful to rapidly deter-
mine (and possibly count) which elements are present in 𝒮𝑞 , the (possibly very
large) set of passages returned by the query.
The following subsections describe the technical details of two applications that
utilize many of these techniques.
3.1 Correlator
Correlator [18,15] is an entity retrieval demo on the English Wikipedia. It allows
users to search for entities (elements of certain types) related to a free query. The
collection in Correlator consists of 2,276,293 English Wikipedia entries (roughly
one billion words). This collection was pre-processed with a set of linguistic
tools (see [2] for an explanation) to obtain annotations following the Wall Street
1
Journal BBN Entity Types from LDC . This lead to 26,110,586 unique elements
of 105 types.
In order to implement element retrieval in Correlator, we use several of the data
structures discussed above. First, a passage is de ned as a single sentence (an
automatic sentence splitter was used for this, leading to 62,614,788 sentences).
The context of a passage is de ned as the Wikipedia entry title, plus the two
sentences immediately before and after the sentence indexed. This content is
indexed in a separate eld to the sentence (which forms the body of the retrieval
unit). Furthermore, in order to implement ltering by type, we index with each
1
Linguistic Data Consortium: LDC2005T33
sentence a sequence of type tokens which indicate which types are present in the
sentence. This type of index allows us to nd passages (sentences) relevant to a
query, and to lter them by type. To implement entity retrieval, we also construct
the element containment graph using the top 1000 results. This graph contains
one node per sentence, one node per element and one edge per annotation; the
size of the resulting graph, once compressed using WebGraph, is 1.8G bytes.
3.2 Question eXplorer
Question eXplorer (QX) [21] is a browsing interface that demonstrates the power
of combining linguistic parsing and fast forward indices. Every time the user
types a query, besides doing the traditional retrieval, it computes statistics over
all the elements present in the result set (e.g. in the query element containment
graph 𝐶𝑞 ). It uses these statistics to build lists of the most frequent elements of
every type and proposes them to the users for query completion. The types of
elements used are very speci c: noun phrases (NPs), verbs (Vs), noun modi ers
(K), verb modi ers (M) and numbers (Q). In order to extract the most interesting
elements in a passage, we pre-process the passage using a linguistic parser (as
described in [2]) and select the elements closest to the root of the parsing tree.
Furthermore, for noun phrases with more than one token, we created elements for
the phrase and for sub-phrases containing the head (e.g. we created the element
[cheap computer screen,NP], but also [compute screen,NP] and [screen,NP]).
In order to implement this e ciently we need to rank all the elements present
in a result set. This problem is similar to the entity ranking problem, but with
some dierences. First, the number of entities is potentially very large: every
verb and noun-phrase, and many sub-strings of these. Second, the number of
types is very small (only two). Third, we want to count all the elements in
the returned passages (or as many as possible), not just the top-𝑘 . In order to
implement this, we encoded the element containment graph as a fast passage-
element index (using the Archive4J libraries [17]). For a collection of 4,483,032
questions (roughly 48M tokens) we extracted 56,280,105 elements (roughly 390M
bytes of text). The forward and backward indices are implements using MG4J.
The inverted index for searching passages (standard token inverted index) results
in a size of 2,144M bytes. The element forward index (implemented using the
archive4J library) has a size of 656M bytes.
4 Conclusions and Future Work
We have formally de ned two retrieval tasks on annotated collections and de-
scribed how these tasks have been implemented for two applications using open
source tools. In the future, we plan on evaluating the performance of the tech-
niques presented in order to provide guidelines for building annotated search
applications.
References
1. Overview of the inex 2008 entity ranking track. In INEX, 2008.
2. J. Atserias, H. Zaragoza, M. Ciaramita, and G. Attardi. Semantically annotated
snapshot of the english wikipedia. In LREC'08, 2008.
3. G. Attardi. IXE at the TREC 2005 Terabyte Task. In TREC, 2005.
4. P. Bailey, A. P. de Vries, N. Craswell, and I. Soboro. Overview of the trec 2007
enterprise track. In Proceedings of TREC 2007 the 16th Text REtrieval Conference,
2007.
5. P. Boldi and S. Vigna. The WebGraph framework I: Compression techniques. In
WWW 2003, pages 595601. ACM Press, 2003.
6. P. Boldi and S. Vigna. MG4J at TREC 2005. In TREC 2005, Special Publications.
NIST, 2005.
7. I. Brunkhorst, P.A. Chirita, S. Costache, J. Gaugaz, E. Ioannou, T. Iofciu, E. Mi-
nack, W. Nejdl, and R. Paiu. The beagle++ toolbox: Towards an extendable
desktop search architecture. In SemDesk 2006, volume 202, November 2006.
8. H. Cunningham, D. Maynard, K. Bontcheva, and V. Tablan. GATE: A framework
and graphical development environment for robust NLP tools and applications. In
ACL, 2002.
9. R. van Os D. Hiemstra, H. Rode and J. Flokstra. PF/Tijah: text search in an
XML database system. OSIR, pages 1217, 2006.
10. D. Ferrucci and A. Lally. UIMA: an architectural approach to unstructured in-
formation processing in the corporate research environment. Nat. Lang. Eng.,
10(3-4):327348, 2004.
11. E. Minack, L. Sauermann, G. Grimnes, C. Fluit, and J. Broekstra. The sesame
lucene sail: Rdf queries with full-text search. Technical Report 2008-1, NEPOMUK
Consortium, February 2008.
12. H. Rode. From Document to Entity Retrieval: Improving Precision and Perfor-
mance of Focused Text Search. PhD thesis, University of Twente, Enschede, The
Netherlands, June 2008.
13. N. Shadbolt, Berners T. Lee, and W. Hall. The semantic web revisited. Intelligent
Systems, IEEE, 21(3):96101, 2006.
14. I. H. Witten, A. Moat, and T. C. Bell. Managing Gigabytes: Compressing and
Indexing Documents and Images. Morgan Kaufmann Publishers, CA, 1999.
15. H. Zaragoza, H. Rode, P. Mika, J. Atserias, M. Ciaramita, and G. Attardi. Ranking
very many typed entities on wikipedia. In CIKM '07. ACM Press, 2007.
16. J. Zobel and A. Moat. Inverted les for text search engines. ACM Computing
Surveys, 38:156, 2006.
17. Archive4j. http://archive4j.dsi.unimi.it.
18. Correlator. Yahoo! SandBox. http://sandbox.yahoo.com/Correlator.
19. Lucene. Homepage. http://lucene.apache.org/.
20. MG4J: Managing gigabytes for java. Homepage. http://mg4j.dsi.unimi.it/.
21. Query explorer. Yahoo! SandBox (to be published). http://sandbox.yahoo.com/
qx.
22. Solr. Homepage. http://lucene.apache.org.