An alternative line of research which has proven to be more productive in supporting user query formulation has been automatic or interactive query expansion (AQE, IQE) based on relevance feedback (Robertson et al 1997). However, this approach also has limitations. Its success depends on three factors: the user identifying good relevant documents, the relevant documents containing appropriate terms to add to the query and in the case of IQE the effective display of candidate terms for user selection.

The current proposal aims to address some of these issues by introducing a concept-based approach to query expansion. The project will investigate and evaluate the automatic generation and hierarchical organisation of concepts derived from retrieved documents to supporting user query formulation and reformulation. The objective is to provide users with an overview of retrieved documents to assist them in finding relevant documents and to display potential query terms is a meaningful context.

End users of text retrieval systems including searchers on the Web consistently generate brief and often broad two or three term queries and have proven to be very reluctant to explore current tools to expand initial queries (e.g. thesauri, Boolean operators) (Manglano et al 1998). However methods for AQE based on relevance feedback have been shown to be beneficial. In the Text REtrieval Conference (TREC), sponsored by the National Institute of Science and Technology, systems such as Okapi and Inquery have used top ranking documents for query expansion (Robertson et al 1995, Allan et al 1996). In the case of Okapi, AQE has also led to more successful searches in operational tests based on users' real information needs (Hancock-Beaulieu & Walker 1992). In addition the Okapi team has explored different methods for implementing IQE both under controlled conditions in the TREC Interactive Track and in several field studies (Beaulieu & Gatford 1998, Beaulieu 1997).

Overall results to date indicate that query expansion approaches whether automatic or interactive are effective in terms of retrieving more items similar to those first retrieved but there is much room for exploring interactive methods for improving precision. Searchers generally derive some satisfaction in participating in the query expansion process by selecting candidate terms presented by the system. However the task of differentiating between the terms which would be most appropriate to improve search precision and those which would not is very demanding. Under different experimental conditions, users have tended either to reject most of the candidate terms suggested by the system or to accept them all. The difficulty appears to stem from different contributory factors. Firstly, the presentation of individual candidate terms in a ranked list based on selection values determined by the system is not meaningful in itself and does not offer sufficient contextual information for users to modify their queries effectively. Secondly, in spite of attempts to make the dynamic changes in the current ‘working’ query more apparent as individual positive relevance judgements are made, terms occurring in relevant retrieved documents are not explicitly related to those appearing in the working query. In order to enable searchers to explore the document space and assist with query modification other approaches are being considered.

One such area of research is the organisation of documents retrieved in response to a query, aspects of which have been researched in detail.

The classic automated method of organising retrieved documents is based on so-called polythetic clustering. Here, each cluster is defined by a set of words and phrases (referred to here as terms) and a document’s membership is based on its possession of a sufficient fraction of the terms that define the cluster. Documents can be organised hierarchically by re-clustering each initial cluster to form a second level of clusters. These in turn can be clustered in a recursive manner until only individual documents remain. As they are defined, and subsequently described, by many terms, the clusters are hard to understand. Consider for example, the following cluster description, from Hearst (1996) "battery california technology mile state recharge impact official cost hour government". Undoubtedly, one can make a reasonable guess at the topic, but it is hardly an ideal description of a group of documents about ‘‘alternative energy cars".

In an attempt to create more understandable document clusters, an alternative approach was attempted by one of the authors based on automatically extracting and organising (hierarchically) the concepts within a set of retrieved documents. Such an organisation is undoubtedly one goal of IR. Were it to be achieved, documents containing the extracted concepts would be arranged in a form somewhat like existing manually constructed subject hierarchies, such as the Library of Congress categories, or the Dewey Decimal system. The only difference being that the categories would be customised to the topics of the document set itself, thereby, providing an overview of those documents. The categories used in such organisations are known as monothetic clusters (van Rijsbergen 1979): clusters where document membership is based on the presence of a single feature. Monothetic clusters are different in two main ways from the polythetic variety described above.

First, it is relatively easy to understand the topic covered by a monothetic cluster: the cluster is about the single feature that defines it. Second, if a document is a member of a monothetic cluster, one can guarantee that it will be about that cluster’s topic at least in the opinion of the person or process that did the categorising.

Although there have been many attempts to build hierarchical document organisations using polythetic clustering or existing manually constructed hierarchies as training data, to the best of our knowledge, no one has tried to build automatically from scratch, a monothetic concept hierarchy for a set of documents. The rest of this section contains an overview of a preliminary approach to building such a hierarchy summarised from (Sanderson 1999).

An initial implementation of the monothetic hierarchical clusters has been built. Although it is limited in the scope of documents it can process and utilises only term co-occurrence information, it has proved to be surprisingly good at creating meaningful concept hierarchies. The documents processed by the system are those retrieved by a query. Words and phrases from the query and retrieved documents are extracted and organised into a hierarchy. The organising method is a term association measure called subsumption. It is defined as follows, for two terms, x and y, x is said to subsume y if the following two conditions hold,

(1) P(x|y) = 1, P(y|x) < 1.

In other words x subsumes y if the documents which y occurs in are a subset of the documents which x occurs in. Because x subsumes y and because it is has a higher document frequency (df), x becomes the ancestor of y in a resulting concept hierarchy. In practice, the number of terms that adhere to this strict notion of subsumption is relatively small. Subsequently, the first condition is relaxed as follows

(2) P(x|y) ³ 0.8, P(y|x) < 1.

Concept hierarchies resulting from this elementary process have undergone limited user testing, the results of which have proved to be encouraging. We believe that the hierarchies provide a highly compressed and comprehensible overview of the underlying documents laying out the concepts contained within them (potential expansion terms) in an understandable form.

Once the concept hierarchies are created, the next stage is to visualise the structures in some manner. A hierarchical menu system was chosen since it is a standard feature of operating systems and users could be expected to be familiar with it (Pollitt 1988). Some important information is lost through this visualisation as the menu system displays a strict hierarchy where a child can have only one parent. In the structures being generated, a child often has multiple parents and such children can be important in understanding concept relationships. Nevertheless, the visualisation is judged to be a good compromise and any changes or improvements form the basis for the current proposal.

Figure 1 shows parts of the hierarchy resulting from documents retrieved in response to TREC topic 302: "Poliomyelitis and Post-Polio". It is presented as a series of menus. As can be seen, much of the concept organisation is promising especially with the desired properties of having easy to understand monothetic clusters being organised with general terms on the left leading rightwards to the more specific. The number by each concept is its df. Some of the terms in the hierarchy are names: "Salk", for example, is "Dr. Jonas Salk", inventor of a polio vaccine.

Given that users generate broad and brief queries and then encounter difficulties in refining their initial query on the basis of items retrieved, the overall research aims to provide user support for query formulation and reformulation in searching large scale textual resources including those on the WWW. The specific objectives are:

• to investigate methods for the automatic generation and organisation of concepts derived from retrieved documents
• to explore the presentation of document derived concept structures for incorporation into a user interface
• to evaluate the retrieval effectiveness of document derived concept structures for selecting relevant documents in a retrieved document set
• to evaluate the retrieval effectiveness of incorporating concept structures to assist users in selecting candidate terms for interactive query expansion
• to assess how searchers make use of concept structures to bridge the gap between the query space and the document space in interactive searching

The overall methodological approach is to address the interdependent research issues related to the above objectives in a progressive and integrated fashion and to incorporate an evaluative component at each stage. A major emphasis is to include user participation in all of the elements under investigation and to take full account of user searching behaviour and the interactive searching process as well as retrieval effectiveness testing in the approach to evaluation.

The TREC test collection will form the basis for the different evaluative experiments. In the first instance a range of concept structures will be derived from TREC document collection(s) and queries. Queries used in the TREC Interactive Track will be particularly useful to provide comparative data for experiments where users will be undertaking interactive searching. The test data for the newly established TREC Web Track will also be used and the evaluation methodology currently being developed by participants in the track will be taken into account as appropriate. A number of formative evaluative experiments will be undertaken in the course of the project in order to establish a suitable evaluation facility and environment for conducting retrieval tests. The project will culminate with the design of a set of interactive summative evaluative experiments. The different research questions being addressed are discussed at the four stages of the project as set out below.

The initial efforts, outlined above, created concept hierarchies using co-occurrence information. Results from a user study showed that approximately half of the hierarchy’s concept relationships had been sensibly arranged. Given the relative simplicity of the methods used to create the hierarchy, the results indicated that co-occurrence was a successful first step on the way to producing a concept hierarchy. What is now proposed is an examination of other means to increase the number of meaningful relationships. A range of complementary techniques will be applied, investigated, integrated and tested.

Currently a simple phrase extraction process performs identification of concepts within documents; however, there are a number of other utilities created within the field of Information Extraction (IE) which may improve identification accuracy. A Named Entity Recogniser (NER) is a basic tool used to perform initial text processing in an IE system (Wakao et al 1996). It locates and types common text forms such as proper nouns, dates/times, money expressions, postal addresses, etc. For proper noun recognition, name lists for people, places and companies may be used. It is anticipated that use of such a mark-up tool will better inform the concept selection process by avoiding text types that are unlikely to be good concepts, such as email addresses or phone numbers. In addition new conceptual groupings will be possible based on the NER types such as the names of people or companies related to a particular concept.

One other IE tool that will be examined is a co-reference resolver. This is a tool that finds in a text different references to the same concept. The range of co-references such a system can tackle is large, but for the purposes of this project only Proper name co-references will be resolved (Wakao 1996). For example, determining if, in a document, the name "Dr. Jonas Salk" and the name "Salk" refers to the same person. Successful use of this tool would group multiple references and thus remove duplicates from the concept hierarchy.

Although subsumption identifies relatively accurately a large number of valid concept relationships, it is believed that a range of other existing methods can be employed to increase this number and will provide validation of existing relationships.

The subsumption-based work used so far was found to be successful in providing a set of concepts organised into a hierarchy leading from the most general concepts to the most specific. No attempt was made to locate synonymous relationships. There is a body of work on using forms of statistical co-occurrence to locate such relationships. One such technique is co-variance. Two concepts are said to co-vary when the contexts in which they occur are similar. Grefenstette (1994) has had success in locating synonym relationships using co-variance. This technique will be applied to the concept hierarchy formation process to group sets of synonymous concepts. Another source of information on synonymous relationships is a thesaurus.

Before the work on subsumption, a preliminary investigation was conducted into the feasibility of relating concepts based on evidence from the WordNet thesaurus (Miller 1995) using Resnik’s semantic similarity measure (Resnik 1995). As an initial approach, it was not as successful a means of arranging concepts as subsumption was. Often, the precise classification of the concepts in the thesaurus caused problems. For example, within a set of documents retrieved in response to a query on natural disasters, it might have seemed sensible to relate "volcano" and "earthquake" together as a form of loose synonym. However, WordNet provides no link between these two as it classifies the former concept as a physical object and the latter as a geological phenomenon. Nevertheless, there were a sufficient number of concepts successfully related to warrant a re-examination of WordNet to more thoroughly investigate its ability at providing information on concept relationships. In the illustrated example shown in Figure 1, for example, "polio" and "poliomyelitis" are located in different parts of the concept hierarchy despite being synonyms of each other; use of WordNet would have concatenated these two terms into a single concept. In addition, as WordNet places concepts within a classification hierarchy, it may also provide evidence on the generality and specificity of concepts to further improve the hierarchy formation process.

In addition to the subsumption work described above, in the field of text analysis, there have been other attempts at automatically deriving from text pairs of related concepts and determining which is more general and which more specific. Hearst (1998) found that certain key phrases could be an indicator of such a relation. Three of the phrases she found were

• "such as", e.g. "...popular forms of entertainment such as movies...";
• "and other", e.g. "...Robert De Niro and other actors...";
• "especially", e.g. "...most horror films, especially Psycho and The Exorcist.".

Sentences that contained these phrases were parsed to identify the noun phrases being related. Hearst discovered around ten such phrases that were accurate identifiers of the "type-of" relation. However, manual intervention was required for their discovery and the scope of the noun phrase pairs identified was limited. Hearst suggested using the key phrases to help thesaurus lexicographers search for new relations. Use of this technique could be applied to the formation of the concept hierarchies and an investigation of its utility will be conducted.

Two pieces of work on phrase analysis are also promising avenues of research. Grefenstette (1997) has described a method of phrase classification, where, through the use of simple syntactic analysis, he was able to place noun and verb phrases into one of nine classes. He illustrated his ideas by examining all possible phrases containing the word "research". For example depending on whether "research" was the head or the modifier of a noun phrase, Grefenstette was able to differentiate types of research (e.g. market research, recent research, scientific research, etc) from research things (e.g. research project, research program, research centre, etc). No tested application of this classification scheme was reported.

Woods also used phrase analysis in addition to a large knowledge base to organise terms into a concept hierarchy (1997). By locating the head and modifier of noun and verb phrases, Woods was able to make choices on how to classify phrases. For example in the phrase "car washing", Woods’ system would identify "car" as the modifier and "washing" as the head of the phrase. This would inform the system to classify the phrase "car washing" under "washing" and not "car". The success of the technique relied on a large morphological knowledge base of information to help identify phrase components. Woods used the concept hierarchy to automatically expand non-matching terms of a query.

The issue of how to best integrate the various techniques (outlined above) will be addressed through testing based on users’ satisfaction with the concepts and relationships being generated. The studies will focus on each method separately assessing each one’s individual contribution. Those that are found to be consistently successful at producing concept relationships which users find sensible and useful will be integrated to produce a tool generating a single hierarchy. Some fine-tuning of this tool will be performed again through user testing of its output.

In the preliminary work, presentation of the concept structure was achieved using hierarchical menus. Although simple to manipulate and interpret, this form of visualisation lost some of the information held within the structures, the reason (as described above) being that the hierarchical menus visualise a strict hierarchy, one parent to each child. The actual data, however, has children possessing multiple parents, which can be important. For example, in a hierarchy built from documents on international conflicts, the child term "war" had two parents "India" and "Kashmir". Seeing this shared link helped users’ understanding of the concept organisation. Currently, the hierarchical menu system handles this situation by placing a copy of such a child under each of its parents, the hope being that a user will notice the child term under each parent and mentally make the link between them.

Alternative visualisations will be explored. The structure to be visualised is in fact a Directed Acyclic Graph (DAG): much work has been conducted on DAG visualisation tools and some are freely available such as the daVinci system (Fröhlich 1994). One of these tools will be selected and applied. It remains to be seen how well these tools will display as large a structure as that currently being generated (each hierarchy holds several hundred concepts). If the use of these tools fails to be successful, an alternative will be to work within the existing menu framework and produce a system whereby any child can be expanded in some alternate manner to show a list of its parents.

A formative evaluation at this stage will aim to identify the best approach to meet both the concept representation requirement and the users’ navigational requirements. User testing will consist of finding relevant documents by navigating through the concepts displayed through different tools.

The third stage of the investigation will involve incorporating the display and navigation of the concept structures into a Java user interface environment to support interactive query expansion. The focus here is on designing the search interaction itself to enable the user to explore the retrieved set of documents through the concept structure and, in turn, to use the concept structure as a mechanism to expand the initial query in an iterative and seamless fashion. The formative experiments will focus on human-computer interaction aspects and include user walkthroughs to test different ways of integrating the different displays for navigating the concept structure, browsing through retrieved documents and modifying queries. The interface will thus serve as a front end for handling document sets retrieved from different search engines. The aim is to arrive at an acceptable design based on standard user interface tools to conduct evaluative interactive retrieval experiments with users.

The final stage of the project will be concerned with evaluating the retrieval effectiveness and usability of concept structures in supporting interactive query expansion. A set of laboratory based comparative interactive experiments will be designed to assess the use and performance of the concept tool for different aspects of the retrieval task and within the overall searching process. Three dimensions will be independently evaluated. Firstly, the performance of concept structures derived from documents retrieved by different Web search engines compared to those derived by ranking systems (i.e. Okapi and Inquery). Secondly, the selection of relevant documents from concept structures compared to selection from ranked lists. Thirdly, the selection of terms from concept structures for query expansion as opposed to selection from ranked lists. Subjects will be recruited primarily from masters and doctoral students. The intention is to have different users participate in the different sets of experiments over the duration of the project. In order to gain more insight from users it may also be beneficial to have a core group of subjects (staff or doctoral students) who will contribute to more than one experiment and will build some knowledge and experience of the search environment over time.

The project will be undertaken over a period of three years starting in November 1999. Although different phases have been demarcated, tasks are interdependent and may to some extent be iterative and overlap between phases.

The objective of this first phase is to improve upon the concept hierarchies created by using co-occurrence information. The current method is a simple term association measure called subsumption by which a parent/child concept hierarchy is determined as follows. A parent term x is said to subsume a child term y if the documents in which y occur are a subset of the documents in which x occur. Given that the approach was a successful first step in producing relatively meaningful concept hierarchies, three issues need to be addressed in the initial phase of the project. Firstly, to explore what other techniques could be applied to improve on the efficiency of the concept identification. Secondly to investigate how the current strict hierarchical structure, whereby a child has only one parent, can be extended to include the display of multiple hierarchies, i.e. one child with more than one parent and other types of associative relationships.

The TREC test collection will provide the data for the experimental work. The approach will be to use the existing training set of 50 TREC queries and concept hierarchies derived from retrieved documents as a baseline and add other query sets to conduct the evaluative experiments as appropriate in the course of the project

This task will be concerned with complementing and improving on the phrase extraction process which is used to identify concepts. The focus will be on applying other text processing techniques, i.e. Information Extraction (IE) tools, for proper noun recognition which will serve to identify proper names linked with particular concepts. This Named Entity Recogniser will also be used to exclude certain unwanted text forms such as email addresses and phone numbers. Another IE tool will be used to identify proper name co-references to the same concept and to remove duplicates from concept hierarchies.

The object will be to see how these different tools can be integrated and applied to improve concept identification from the retrieved documents of the training set of queries. An initial assessment will involve a comparative analysis of the concept hierarchies produced by the basic phrase extraction process and those generated by a combination of the different IE tools. The integration of the different algorithms and analysis of the combined results will require a fair amount of programming effort.

The current subsumption method organises the concepts into broad and narrow hierarchies. Other techniques for generating both hierarchical and associative concept relationships need to be explored. These will include the use of co-variance information from term occurrence, concept classification as applied in thesaural tools, and parsing techniques for text analysis. Firstly co-variance will be examined as a method for handling synonymous or associative relationships. Such relationships are an integral part of any knowledge representation or structure as exemplified in thesaurus construction. Secondly, although WordNet was found not to be as useful for the initial identification and organisation of concept structures from retrieved documents as the subsumption approach, it will be examined as a complementary method for mapping related concept structures from initial hierarchies. Thirdly, noun phrases as well as functional phrases will also be explored to further differentiate types or categories of hierarchical relationships.

The approach in this task is to experiment with existing techniques and available tools in order to identify the more promising ones for the automatic organisation of concept relationships. As in Task 1 comparative analyses of the output will be carried out. It is anticipated that several concept hierarchies will be generated for individual queries for validation in Phase 2. The outcome of Phase 1 is to produce an enhanced training set of concept hierarchies which will then be tested and validated by independent human subjects.

How to validate and evaluate the adequacy and performance of the concept structures for searching and retrieval is far from straight forward. There are a number of possible elements which can be considered: the interpretation of the labels, the interpretation of the document clusters attached to the labels, as well as the performance of the concept structures as a searching tool for retrieving relevant documents. At this stage we are primarily concerned with searchers' ability to interpret the derived concepts and the relationships between them and to establish useful assessment criteria.

In our preliminary tests, subjects were simply asked to confirm parent/child relationships for concept hierarchies derived by the subsumption method as opposed to the same concepts derived from a random association. Here we propose to devise an experiment which will seek to ascertain how consistent users are at recognising and interpreting different concept labels and relationships which have been generated for the training set as opposed to those found in an established thesaurus such as WordNet.

Since the generation of the concept structures is intended to provide an overview of the retrieved document set, a second experiment will endeavour to determine to what extent the test subjects consider the different concept labels to be representative of the linked documents. It will also confirm the strength of association between the different documents under the same concept label.

The object of the validation is to confirm the best method for generating meaningful concept structures. It must be noted that although a concept structure generated from a retrieved document set may hold several hundred concepts, for validation purposes only concept hierarchies in the top levels of the overall structure, i.e. the most frequent concepts, will be used. The outcome of this second phase of the project is thus to produce a pool of concept structures for at least 50 queries which will be used for the subsequent phases of the project. It is envisaged that based on the level of consensus amongst the test subjects, it may be possible to differentiate between concept hierarchies which are more highly or more loosely structured. This may serve as a means of determining what level of structure is adequate to support the query expansion process.

The classification and labels for the concept structures will have already been established and validated in Phases 1 and 2 and the existing hierarchical menu tool will be used to carry out the user experiments. Phase 3 will be concerned with improving upon the current visualisation approach and investigating what would be the most appropriate tool for presenting the concept structures as well as supporting user navigation of those structures in a user interface. Although menus are a well established and easily understood graphical convention, as implemented in our preliminary work, it does not accommodate multiple or associative hierarchies. Therefore the existing framework will need to be extended in order to display these more complex structures. An alternative approach based on a Directed Acyclic Graph (DAG) will also be explored. DAG display tools are freely available and one such tool will be selected for the formative evaluation.

Major issues to be addressed is to what extent the visualisation tool can display large concept structures, how much of the concept structures will need to be displayed and how easily can they be navigated. The formative evaluation will aim to identify the best tool for presenting the concept structures and for supporting navigation. User testing will consist of setting up comparative search tasks whereby searchers will need to navigate the concept hierarchies to find relevant documents using the different tools.

The outcome of this task is to select the most appropriate visualisation tool to incorporate into a user interface.

Task 2 - Integrating the concept visualisation tool into a user interface

The main effort of this phase of the project is the design of a Java user interface which will enable the searcher to explore the retrieved set of documents for the different queries through the concept structure displayed by the visualisation tool. In addition, the user will use the structure as a mechanism to expand the initial query in an iterative and seamless fashion. Formative experiments will focus on the human-computer interaction aspects of the searching process and include user walkthroughs to test how the different tasks, i.e. navigating the concept structures, browsing through retrieved documents and selecting concepts to modify queries, can be presented in an integral fashion

In order to carry out the retrieval tests as described in Phase 4, two tests systems will be built. The Java user interface will serve as a common interface or front end to two different search engines, Okapi and InQuery. Since both Okapi and InQuery are modular systems the main effort for constructing a robust test system will be in the design of the interface as described above. The two test systems will be configured as follows. The databases will consist of the top 500 documents retrieved by each of the two search engines for each of the 50 TREC queries in our training set. The concept structures for each of the retrieved document sets for the individual search engines will have been derived offline by the concept tool and incorporated and made accessible through the visualisation tool in the user interface. In addition versions of the Okapi and InQuery systems without the concept structures tool will serve as controls in the evaluative experiments.

The final phase of the project will be concerned with evaluating the retrieval effectiveness and usability of concept structures in supporting interactive query expansion. A set of laboratory based comparative interactive experiments will be designed to assess the use and performance of the concept tool for different aspects of the retrieval task and within the overall searching process. Firstly, the performance of concept structures derived from documents retrieved from the two ranking systems will be compared including highly structured and more loosely structured hierarchies. Secondly, the selection of relevant documents from concept structures will be compared to selection from ranked hit lists. Thirdly, the selection of terms from concept structures for query expansion as opposed to selection from ranked term lists will be compared. The normal precision/recall measures will be used based on the relevance judgements available for the TREC data.

Proposed timetable

Year 1 - Phase 1 - Nov 1999 - Jul 2000

Year 2 - Phase 2 - Aug 2000 - Jan 2001

Phase 3 - Feb 2001 - Jan 2002

Year 3 - Phase 4 - Feb 2002 - Oct 2002

The project will contribute to information retrieval research in a number of ways:

• Firstly the automatic generation of concepts from retrieved documents would greatly assist users to search the Web more effectively. By being implemented locally and operating independently of the WWW the approach would be much more manageable than the current practice of manually assigning subject categories or applying automatic techniques to whole collections.

• Secondly the novel underlying technique would build on a substantial body of research on monothetic clustering approaches to retrieval.

• Thirdly the use of concept structures for gaining a more meaningful overview of sets of retrieved documents and assisting users in query expansion would provide an alternative or complementary approach to query expansion based on relevance feedback.

• Fourthly by involving users in the evaluative experiments, the project will contribute to the development of the evaluation methodology for interactive systems and build on activities promoted by the TREC interactive and Web retrieval tracks.

It is anticipated that each phase of the project will lead to publishable results and submissions to refereed conferences and journals will be made both in the course of the project as well as on its completion. Obvious candidates include the annual ACM SIGIR, Digital Libraries and CHI conferences. The proposers have a strong publications record and would target both the IR and HCI research communities. Dissemination in the course of the project will also be promoted by the proposers’ participation in the TREC Interactive and Web retrieval tracks.

In addition the outcome of the project will include the test software itself and interface which will serve as an evaluative tool and front end to Web search engines as well the existing experimental search engines, Okapi and Inquery, used by others in the research community.

The proposers are members of the Computational Information Systems Research Group within the Department of Information Studies. The Department has consistently gained the highest rating (5*) in all of the Research Assessment Exercises. Professor Beaulieu was formerly co-director of the Centre for Interactive Systems Research at City University, also a 5* centre of excellence. She was involved in the interface development and evaluation of the Okapi advanced retrieval system and conducted a number of experiments on approaches to query expansion in operational and laboratory settings. Over the past eight years she has participated in the TREC interactive track focusing on the relationships between search interaction, interface and retrieval issues. Dr. Mark Sanderson carried out all the initial work on concept hierarchies while working as a Post Doc at the highly rated Center for Intelligent Information Retrieval at the University of Massachusetts. He has published a number of papers on summarisation and IR interfaces while completing his Ph.D. at the 5* rated Computing Science department at the University of Glasgow.

The project will employ one research assistant for three years with Java programming skills. Some basic technical support will also be required.

A Sun Ultra 10 workstation (£5725) will be made available to the project by the Department of Information Studies, but additional accessories, i.e. 24" screen, memory and extra disc are being requested.

It is envisaged that papers will be submitted to major international conferences in the course of the project. Resources are thus being requested for travel and subsistence to support attendance to one of the ACM conferences a year (SIGIR, Digital Libraries, and CHI) for one member of the project team.

Allan, J, Ballesteros, L., Callan, J.P., Croft, W.B. and Lu, Z. (1996) Recent Experiments with INQUERY. In: D. K. Harman (ed.). The fourth Text REtrieval Conference (TREC-4). Washington: NIST, 49-72.

Beaulieu, M. (1997) Experiments on interfaces to support query expansion. Journal of Documentation, 53(1), 8-19.

Beaulieu, M. and Gatford, M. J. (1998) Interactive Okapi at TREC-6. In: E. M. Voorhees and D. K. Harman (eds.). The Sixth Text Retrieval Conference (TREC-6). NIST, 143-167.

Evans D.A. and Lefferts R.G. (1994) Design and evaluation of the CLARIT – TREC 2 system. In: D.K. Harman (ed.) The Second TREC retrieval Conference (TREC-2), NIST, 137-150.

Fröhlich M. and Werner M. (1994) The Graph Visualization System daVinci - A User Interface for Applications; Technical Report No. 5/94; Department of Computer Science; Universität Bremen.

Greffenstette G. (1994): Explorations in automatic thesaurus discovery, Kluwer Academic Publishers

Grefenstette G. (1997) SQLET: Short Query Linguistic Expansion Techniques, Palliating One-Word Queries by Providing Intermediate Structure to Text, Proceedings of RIAO, 500-509.

Hancock-Beaulieu, M. and Walker, S. (1992) An evaluation of automatic query expansion in an online library catalogue. Journal of Documentation, 48(4), 406-421.

Hearst M.A. and Pedersen J.O. (1996) Re-examining the Cluster Hypothesis: Scatter/Gather on Retrieval Results. In the proceedings of the 19^th ACM SIGIR.

Hearst M.A. (1998) Automated Discovery of WordNet Relations. WordNet: an electronic lexical database, Christiane Fellbaum (Ed.), MIT Press.

Jansen, B. J., Spink, A., Bateman, J., & Saracevic, T. (1998). Searchers, the subjects they search, and sufficiency: A study of a large sample of EXCITE searches. Proceedings of WebNet’ 98, Orlando, Florida, November, 1998.

Jones, S. Gatford, M., Hancock-Beaulieu, M., Robertson, S.E., Walker, and Secker, J. (1995) Interactive thesaurus navigation: intelligence rules OK?? Journal of the American Society of Information Science, 46 (1), 52-59.

Kristensen, J. (1993) Expanding end-users’ query statements for free text searching with a search-aid thesaurus. Information Processing & Management 29(6), 733-744

Manglano, V, Beaulieu, M. and Robertson, S. (1998) Evaluation of interfaces for IRS: modelling end-user searching behaviour. 20^th Colloquium on Information Retrieval, Grenoble. www.ewic.org.uk

Miller G.A. (1995): WordNet: A lexical database for english, in the Communications of the ACM, 38(11): 39-41.

Pollitt, A. S., Ellis, G. P. and Smith, M.P. (1994) Improving search quality using thesauri for query specification and the presentation of search results. Knowledge Organisation and quality Management. Proceedings of the Third International ISKO Conference, Copenhagen, Denmark, 1994. Advances in Knowledge Organisation, 4, 382-389

Pollitt, A.S (1988) A common query interface using MenUSE – A Menu-Based User Search Engine. Proceedings of the 12^th International Online Information Meeting, 445-457.

Resnik P. (1995), Using Information Content to Evaluate Semantic Similarity in a Taxonomy, Proceedings of the 14^th International Joint Conference on Artificial Intelligence (IJCAI).

van Rijsbergen C.J. (1979) Information retrieval (2nd edition). London: Butterworths: 1979.

Robertson, S.E., Walker, S., and Hancock-Beaulieu, M. (1995) Large test collection experiments on an operational, interactive system: Okapi at TREC. Information Processing and Management, 31 (3), 345-360.

Robertson, S.E., Walker, S. and Beaulieu, M. (1997) Laboratory experiments with Okapi: participation in TREC. To appear in Journal of Documentation, 53(1), 20-34.

Sanderson M.A and Croft W.B. (1999) Deriving concept hierarchies from text. To appear in the proceeding of the 22^nd ACM SIGIR, Berkeley.

Wakao T., Gaizauskas R., Wilks Y. (1996) Evaluation of an Algorithm for the Recognition and Classification of Proper Names. In Proceedings of the 16^th Internation Conference on Computational Linguistics (COLING96), Copenhagen, 1996, 418-423.

Woods W.A. (1997): Conceptual Indexing: A Better Way to Organize Knowledge, a Sun Labs Technical Report: TR-97-61. Editor, Technical Reports, 901 San Antonio Road, Palo Alto, California 94303, USA.