Despite the great interest in dierent forms of textual annotation (named entity extraction, semantic tagging, syntactic and semantic 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 ecient engines to solve these tasks. We dene formally two retrieval tasks in annotated collections: annotated retrieval and element retrieval. We discuss their dierences and describe ecient 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.
Element Retrieval: retrieval of elements (e.g. entities, not documents) relevant to an ad-hoc query.
Annotated Retrieval is the standard ad-hoc document retrieval task, with the added diculty of coping with annotated collections and queries (examples 13 above). Element retrieval is signicantly 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 ecient indexing mechanisms required by them (Sections 2 and 3) and describe several use cases. 1.1
With the incredible growth of the Internet, there has been a great deal of work on
eciently searching large collections [
Several open source search engines have tackled the technical problems of
implementing annotated search engines, mainly (to our knowledge): PF-Tijah [
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 denitions and notations. We will discuss annotations and elements (entities, in a very general sense); relations are outside the scope of this paper. A passage si 2 S is a sequence of tokens plus context: si = wi1; wi2; :::; wijsij; Passages may be sentences, paragraphs, documents, sliding windows of text, but they need to be uniquely identied textual units (for now we do not allow any structure on the units). Tokens will typically correspond to words, but language tokenisation is a dicult 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 a = (i; ; ; t) where i is the identier of the passage annotated, and are the beginning and ending positions of the annotation respectively, and t is the type of the annotation. An element is a tuple e = (s; t) where s is its value (a sequence of tokens) and t is its type. Unlike annotations, elements are not tied to a particular passage . We call E 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 S, a query is dened as a function that maps S to a ranked subset Sq. We will use the following query operators (which can be combined into more complex queries): conjunction \a b" retrieves passages with tokens a and b, disjunction \ajb" retrieves passages with tokens a or b, eld restriction A : a retrieves passages with token a in eld A, position restriction \[a; b] n" retrieves passages where token a is followed by token b in a window of at most n tokens, and alignment \a ^ b" retrieves passages where token a is aligned with (in the same position as) token b. 2
Inverted indices allow fast and ecient retrieval of passages for token queries allowing some operators (such as disjunctive and conjunctive queries, token prexes, 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 arranged into dierent levels of granularity, from the presence/absence of tokens to their frequency or retrieval weight, their position, eld information, typography, 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 e1 =[apple, SUBSTANCE] would require a searching for the text-token apple in the same position as the type-token SUBSTANCE. The query for the element e1could be translated then into apple:TOKENS ^ SUBSTANCE:TYPES . A passage would satisfy this query if both apple and SUBSTANCE are found in the same passage at the same position. Since the alignment operator preserves the semantics of the other query operators, the result is a very powerful query language over annotated collections. 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, SUBSTANCE] ) 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 concatenate 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
although rarely discussed in the academic literature. In the open domain, parallel
indices are implemented in MG4J and can be implemented easily in other
frameworks 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
PositionIncrement to 0) when types are encountered. Although Lucene does not
provide specically an alignment operator, one can obtain one by forcing a
distance 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 [
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 ( Sq), we need to nd which elements appear in those documents ( Cq), 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 eciency with which the passage annotations could be loaded given the passage identier. 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 ecient 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 s 2 S and each element e 2 E are nodes, and there is a directed edge from s to e if the element e is present (contained) in the passage s. We call this an element containment graph C, and since it is a bipartite graph it can be represented as a jSj jE j matrix, where Cij is the strength of connection between passage si and element ej (typically 1 if it appears, 0 otherwise). At query time, we execute the standard query and obtain the set of passages of interest (Sq, or perhaps only the top- k scores in this set). Then, for every passage of interest we query C to obtain the elements contained in the passage. Doing so, we obtain the subgraph Cq C which contains information useful for ranking, such as the frequency of an entity in the result set.
Representing C 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, CCT gives us a
passage similarity (equal to the number of element co-occurrences if C is binary),
and CT C an entity similarity (number of passage co-occurrences if C is binary).
We can further use C to dene graph centrality algorithms such as HITS or
PageRank, or to dene several types of random walks [
Representing C as a bipartite graph also allows us to use existing graph
compression and querying algorithms, such as WebGraph [
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: si : fei1; :::; eing, whereas a column is a description of the passages in which an element is present ej : fsj1; :::; sjmg. Both these representations lead to ecient 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 ecient algorithms to store forward indices. Archive4J [
The following subsections describe the technical details of two applications that utilize many of these techniques. 3.1
Correlator [
In order to implement element retrieval in Correlator, we use several of the data structures discussed above. First, a passage is dened as a single sentence (an automatic sentence splitter was used for this, leading to 62,614,788 sentences). The context of a passage is dened 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 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 (QX) [
We have formally dened two retrieval tasks on annotated collections and described how these tasks have been implemented for two applications using open source tools. In the future, we plan on evaluating the performance of the techniques presented in order to provide guidelines for building annotated search applications.