Introduction

In 2004, the XLDB Group made its debut participation in CLEF, on the monolingual ad hoc Portuguese retrieval task [4]. The main goals were to obtain hands-on experience in joint evaluations of information retrieval (IR) and evaluate tumba!, our web search engine [11], on this task. We learned that we had to come up with new approaches and methods, as the strategy for searching and indexing large web collections has to be different for the kind of document collections used in the CLEF ad hoc task.

This year, we embraced the ad hoc task with the objective of evaluating new methods and algorithms for the task:

• Implementation of new logic operators on query strings, to support expanded queries • Development of new methods for using all the topic information provided and merging the combined result sets.

• Topics translation for submission of English to Portuguese bilingual runs.

This paper is organized as follows: Section 2 describes our system and enumerates the main changes from last year's configuration. In Section 3, we present our evaluation goals and submitted runs. Section 4 presents the results obtained. Section 5 summarises our conclusions.

One of the main lessons learned from last year's CLEF ad hoc task participation was that IR in large web collections is quite different from IR on small text collections. Simple adjustments to a web search engine aren't sufficient if we want to use all the information provided for each topic instead of just a few terms to query the CLEF ad hoc collection. This motivated the development of a set of new software, to handle properly the task.

We developed a new query expansion module that generates alternative queries from the descriptions given. This module, called QuerCol (Queries Collator) is external to the core tumba! search engine, but has an essential role in the production of the runs we submitted to CLEF in 2005.

We also improved tumba! on its capability to properly rank poorly linked and tagged documents. To rank the results for CLEF 2005, we developed a simplified version of the Okapi weighting algorithm [9], added support for the 'OR' operator in query strings, and implemented new result set merging algorithms.

With these new modules, our group is now taking the first steps to adopt the basic set of components required for serious participation on in this kind of IR task -robust stemming, weighting scheme and blind feedback [2].

In the remainder of this Section, we detail the design of QuerCol, the newly developed query expansion module, and the improvements made to the query processing sub-system of tumba!.

Query Expansion

The main conclusion of our CLEF 2004 participation was that, in order to achieve higher recall values, we need to expand the title terms into alternative variants, as collections include many documents relevant to the query topic without all the topic terms [4]. So, this year we created multiple queries for each topic, based on synonyms, morphological and lexical expansion of the title terms, and a selection of other terms from the topic description.

Query strings can now include the 'OR' (disjunction) operator, which wasn't supported by the query server that we had in 2004. This enabled us to make extensive use of synonyms and morphological variations of the title terms. Other systems and former CLEF participants, like David Nateau et al, experimented query expansion modules based on the 'OR' operator [7], and that inspired us to start QuerCol.

QuerCol generates queries from a given topic using the following approach:

1. Eliminate common stop-words and CLEF-related stop-words. The latter include terms like 'document' and 'relevant', which are frequent in topic descriptions. We obtain these by selecting the top 5 most frequent terms from all topics.

2. Obtain title concepts. After stop-word elimination, we assume that all remaining title words are rootterms of Boolean expressions in the disjunctive normal form, each representing a concept, which must be present in all query strings derived from the topic. We used jspell to expand morphologically the title concepts [1,12]. Jspell is a morphological analyser based on derivation: words are created applying a set of rules over a root term. This way, it is easy to check the root term and apply rules to create word derivations for each title concept. From these, we only pick those having a frequency of least 5 in the collection.

3. Obtain expanded concepts. For each topic title, we take the terms as a conjunction query, which is submitted to the tumba! instance indexing the CLEF ad hoc collection. Then, we measure the tf x idf value for each term in the topic's set of words, for each document in the obtained result set. We rank the top 8 terms and discard those with a document frequency lower than 5 in the collection. The selected terms are called expanded concepts.

4.

Compute the similarity between the title concepts and the expanded concepts. For instance, if the title concepts are shark and attack, and the term strike is selected as an expanded concept, we want to relate it to the attack concept, to create a query like shark attack OR shark strike. We used a database of term co-occurrences of Portuguese terms developed by the Porto node of Linguateca, built from two Portuguese corpora, CETEMPublico [10] and WPT 03 [6]. In the example above, we queried the database for the top-20 terms that co-occur after the term shark. If strike is in the result, we can say that the two terms belong to the same concept, and we add strike to the attack concept term list.

If an expanded concept isn't associated to a concept, it is later added to the query string as a disjunction. This means that expanded concepts don't influence the result set lists, but contribute to weighting the documents containing them.

5. Query string generation. In the end, each title concept is defined as a list of terms, selected both from the expanded concepts and from the morphological expansions of the initial title terms. With all the lists of concepts for each topic, we compute all term combinations as a m × n matrix of m concepts ×n term list size for each concept, and finally we merge them with disjunction operators to generate a single query string.

For the English to Portuguese bilingual ad hoc task, we devised the two following approaches:

1. Using the Babelfish web translation tool [14]. The topic strings were extracted and sent one at a time to the translator and the translations replaced the original topic strings.

2. Using Example Based Machine Translation (EBMT) methods in parallel corpora [13]. The translations were made from a translation memory built from multilingual thesauri freely available on the Internet (EuroVoc, Unesco thesaurus and others). The thesauri have not only simple term entries but also multi-word entries that help in the translation of some word sequences. The translation memory was then used to translate word sequences of the topics file. Words without a corresponding entry in the translation memory were individually translated using Babelfish.

Weighting and Ranking

Sidra [5] is the indexing and ranking system used in the tumba! web search engine. Sidra provides support for "all the terms" searches, exact phrase queries and field searches that restrict result sets to a specific subdomain or document format. Sidra was primarily designed to rank web documents, as its original ranking function relied mainly in metadata such as links' anchor text, URL strings and page titles. However, it performs poorly when handling document collections with scarce metadata, such as the CLEF ad hoc collection. Sidra does not perform term stemming. The index terms are all the single works, indexed by a full inverted file.

To improve the performance of Sidra on CLEF, we made two major enhancements:

1. Implement a weighting function based on term frequency, to tackle the absence of meta-data.

2. Develop support for disjunction of terms expressions as queries to handle expanded queries created by QuerCol.

As weighting function, we implemented a simplified Okapi BM25 formula, without relevance information [8]. This way, the weighting effect is very similar to a simple tf*idf weighting function. The initial idea was to develop a baseline for a future implementation of a full BM 25 schema, which is not yet available.

Query strings submitted to Sidra are no longer interpreted as AND expressions of terms. Term expressions with the logic 'OR' operator can only be accepted in the Disjunctive Normal Form. Given that the Sidra query servers handle each conjunction as a simple query, support for the 'OR' operator consisted in devising strategies for merging the result sets of ranked documents obtained in each sub-query. We used two simple approaches:

Weight Merge: The final result set is obtained by sorting the weights of each result on the combined result set. The final weight of a document present in more than one result set is the sum of the weights of the document in each result set.

Round-Robin Merge:

The final result set is generated by sorting the result sets by the weight of the top ranked document in the result set. Then, documents are picked from each result set using a roundrobin rule. Documents already picked to the merged result set are ignored.

Runs

For the ad hoc task, we submitted 5 runs for the Portuguese monolingual ad hoc task (4 regular runs plus one mandatory run) and 4 for the English to Portuguese bilingual ad hoc task. As we were testing implementations of the 'OR' operator on tumba!, we selected the result set merging methods as a parameter to measure which produced better results. Hence, we applied the Weight Merge algorithm to half the runs plus the mandatory run, and Round Robin Merge to the other half (see Table 1 In the monolingual task, we created runs XLDBTumba01 and XLDBTumba05 by manually adding all kinds of synonyms and morphological expansions to the queries that seemed reasonable. We used it as a baseline for evaluation against other submitted runs. For runs XLDBTumba02 and XLDBTumba06, QuerCol automatically generated the queries. We aimed at obtaining result sets of the same level of quality as for manually created runs, as QuerCol used the same query creation approach. XLDBTumba09 is a mandatory run, with query strings automatically generated from the topics' title and description fields only.

On the bilingual task, the goal of our participation was to have a preliminary evaluation of the EBMT systems being developed at the Braga node of Linguateca.

Results

Run label

Retrieved Relevant Ret_rel Avg. 2 show the obtained results. One of our main goals was to compare the two result sets merging strategies, and in the end the Weight merge method outperformed the Round-Robin method. A deeper analysis on the results will provide valuable hints on the result set merging mechanism to implement for disjunctive queries.

Manual query creation (runs 01 and 05) performed better than automatic query creation (runs 02 and 06). Further analysis on the obtained results will also provide good hints for improving QuerCol to narrow The results of the monolingual runs are much better than the bilingual. This is likely a consequence of some poor translations. We concluded that we were using thesauri with less quality than expected. As we have overlaps (alternative translations coming from different thesauri), some of the used translations came from the wrong thesaurus and were the source of the bad translation results. Table 2 shows that the runs using EMBT translation obtained more relevant results with less retrieved documents, which is an encouraging result.

The relative performance of the best of our runs compared to other groups' submissions is close to the median. There are a few queries where our performance is much worse than the median for reasons that we have yet to find. However, given that in 2005 our weighting algorithm was very simple, we believe that an improvement here would likely raise the performance level of our software in future evaluations.

Conclusion

The results obtained this year represent show a major improvement since last year. This comes as a direct consequence of the changes made to our IR system. Some of the developments for this CLEF task will be incorporated in the next version of tumba!

We have also identified further improvements, like extending QuerCol with a Portuguese stemmer. This would create better term expansions and improve the 'clustering' of terms from the same concept. QuerCol's generated queries also revealed some flaws that we need to amend, as there are concepts with more than one term that shouldn't be handled separately (for instance, Bill Clinton). Some morphological expansions of title terms might also produce misleading variations. Finally, we could also incorporate the software developed for our participation in GeoCLEF 2005 to expand geographic names in queries [3].