Department of Information Studies
University of Tampere
P.O.Box 607
FIN-33101 TAMPERE, Finland
Return to Kal's home page.
Return to Kal's publication list.
Paluu Kallen kotisivulle.
Paluu Kallen julkaisuluetteloon.
QE can be performed, on one hand, prior to the initial search or the relevance feedback search and, on the other hand, on the basis of statistical or linquistic information (Ekmekcioglu & al., 1992). The source of expansion may be document titles, a thesaurus, or a classification (Hancock-Beaulieu, 1992). Thesaurus-based QE may be performed through a weighted spreading activation method (Paice, 1991) or through ordinary thesaural relationships (e.g., equivalence, association and hierarchical relationships; Kristensen, 1993).
Ekmekcioglu (& al., 1992) found that statistical or linguistic QE did not provide significant difference in retrieval effectiveness when compared to unexpanded queries (ranked output, over 26 000 title-and-abstract documents). Kristensen (1993) reported a doubling in recall with a 11 % decline in precision (63 to 51 %) for thesaural QE (Boolean retrieval, 227 000 newspaper articles). Jones & al. (1995) found that query expansion through a thesaurus in a ranked output system reordered the result but did not improve it (ranked output, large INSPEC database).
In this paper we present a new approach by providing a deductive data model for thesauri because the ordinary RDM does not support transitive relationships typical in thesauri. If some term B is an immediate narrower term (NT) of another term A and the term C an NT of B, then C is also, transitively, an NT of A, i.e. A a is broader term (BT) of C. NTs and BTs of given terms are frequently needed in thesaurus navigation and QE. This requires the computation of the transitive closure (Ullman, 1989) among the relationships and starting terms.
In the RDM computation of the transitive closure is practically impossible but in deductive databases it is possible. In the latter, transitive relationships form the most frequent recursion type for rule-based computation (Chang & Walker, 1986). Our work has this starting point. Agrawal's (1987) extended relational algebra and our deductive query language (Niemi & Järvelin, 1992) are operation-oriented approaches to transitive queries. Our approach provides a set of specific operations instead of one transitive closure operation. Especially its direction-specific operations are valuable in thesaurus navigation. Through them we can find BTs or NTs of given terms by specifying the direction. Our approach supports the computation of transitive relationships in a collection of binary relations. This is very useful because thereby QE can be restricted to particular types of concepts (e.g., persons or things) and particular types of relationships (e.g., generic or partitive relationship).
In our thesaurus data model, deductive operations are used to manage hierarchic relationships, i.e., generic, partitive and instance relationships. They are not used to manage equivalence nor associative relationships. The former are rather relationships between concept expressions than between concepts and are managed in the RDM. The latter are non-directed, reciprocal concept relationships and thus cannot be managed by our deductive operations which presently assume acyclic binary relations. However, this is not a limitation since the associative relationship performs badly if utilized transitively in query formulation.
In our deductive data model the conceptual level represents concepts and conceptual relationships. The linguistic level represents natural language expressions for concepts. Typically there are many expressions of varying reliability for each concept. Each expression may have one or more matching models of varying reliablity at the occurrence level. Each matching model represents, in a query-language independent way, how the expression may be matched in texts or database indices built in varying ways, e.g., with or without stemming and with or without compound words split into component words.
We shall apply the deductive data model for QE and present a tool, called the ExpansionTool, for parametrized automatic QE. This tool is intended for QE:
- prior to the initial search
- for varying search topics and search exhaustivity (e.g., high recall vs. high precision)
- based on a searching thesaurus (or a semantic expansion approach)
- for natural language text retrieval in document collections lacking intellectual indexing
- in heterogeneous retrieval environments where the database index types, retrieval systems and matching methods (Boolean or term-weighted, ranked retrieval) vary; thus it must preserve query structure for retrieval systems which may utilize it.
Presently, the ExpansionTool assumes that the user already knows the concepts relevant to her/his search. The ExpansionTool then expands the concepts and constructs a query.
Return to Kal's home page.
Return to Kal's publication list.
The three abstraction levels: conceptual, linguisticand occurrence level are well-founded in the IR literature (Croft, 1986; Paice, 1991; UMLS, 1994). Thus we can differentiate between concepts and their structures (the generic, partitive and associative relations) at the conceptual level, concept expressions and their structures (the equivalence relation) at the linguistic level, and matching models (e.g., full-word strings, stems, string patterns containing wild cards) indicative of linguistic expressions at the occurrence level. Expressions represent concepts and each concept may have several expressions in several natural and artificial languages. The expressions may be basic words, compound words, phrases or larger linguistic constructs, or common codes and abbreviations (e.g., USD49.90). In our approach intended for QE the occurrence level contains matching models for matching expressions in text, and where confidence figures between concepts and their possible expressions as well as between expressions and their matching models are utilized in query construction.
Fig. 1. The abstraction levels applied to query formulation
Figure 1 illustrates the roles of the three levels for query formulation. Search concepts are first translated into search keys which are (thesaurus) terms, common codes and/or natural language expressions. Thereafter the search keys are translated into matching models, e.g. string patterns with wild cards or string constants. Language-dependent aspects are represented at the linguistic and occurrence levels. All retrieval system dependent aspects are encapsulated at the occurrence level in system-specific translators.
2.2. Thesaurus representation
Representation of concepts, expresions and matching models
We represent concepts, their linguistic expressions and matching models in a relational database illustrated in Figs. 2-3. Concepts are represented in the relation CONCEPTS which has the attributes CNO (concept number), CNAME (concept name), CATEGORY (concept category), and DEFINITION (concept definition). Concept categories are chosen according to the application domain of the thesaurus. For example, in a thesaurus for newspaper articles, the concept categories might include persons, organizations, things and events.
Fig. 2. Representation of concepts and expressions
Expressions are represented in the relation EXPRESSIONS with two attributes ENO (expression number) and EXPRESSION (the expression). The relationships between concepts and their expressions are given in the link relation CONS_EXPRS which has the identifier attributes CNO and ENO, as well as the attributes ETYPE (expression type) and STRENGTH. The attribute ETYPE defines the expression as a preferred term for the concept (term), a synonym (syno), or other type included in the ISO standard (ISO, 1986) for thesaurus construction. The attribute STRENGTH specifies the strength of the association between the concept and its expression as a real number between [0, 1]. The source of strength figures can be human judgement, statistics based on the meanings of the expression, or relevance feedback. Fidel and Efthimiadis (1995) point out the need for terminological research to analyze such attributes.
The matching models are represented in the relation OCCURRENCES. It has three attributes ONO (occurrence number), OTYPE (occurrence type), and OCCURRENCE. The occurrence type indicates whether the OCCURRENCE attribute gives a matching model for a morphological basic word form (bw) or for a stem of inflected forms (st). The idea here is that the database index may contain either morphological basic forms recognized by, e.g. the TWOL software (Koskenniemi, 1983), or inflected words as they appear in the text. The matching model representation is retrieval system independent and has the following features:
Fig. 3. Representation of matching models
- Representation of atomic words by bw(word), when word is a morphological basic form (e.g., bw(investment)), and st(stem), when stem is a stem (e.g., st(factor)).
- Representation of compound words by their morphological basic forms or stems. The basic form matching models represents compound word components because they may be represented in the database index. In many languages, the component words may occur in inflected forms in the compound but are in the basic form if split. Thus the compound word basic forms are expressed by cw((c1, ..., cn)), when c1, ..., cn are component words in the correct order. Components which may inflect in the compound are modelled by iw(basicform, inflform), where basicform and inflform are the basic and inflected forms, respectively. Other components are modeled by the basic word form construct. For example, "plywood" is modelled by cw((bw(ply), bw(wood))).
- Matching of phrases with a defined word order through morphological basic forms or stems. The model is phra(Comps), where Comps gives the component words. The components may be stems, basic words or compound words. For example, "forest industry" can be represented by phra((bw(forest), st(industr))).
- Matching of words in defined and undefined order, with intervening words allowed, through morphological basic forms or stems. The models are prox(Comps, Distance) and adj(Comps, Distance), where Comps gives the components and Distance gives the allowed distance between components. For example, "forest industry" may be modeled by prox((bw(forest), bw(industry)), 3) in this order and with distance of 0 - 3 words.
These characteristics are necessary when the document texts may have basic words, compound words and phrases which may or may not have been analysed into their morphological basic forms for the database index. Compound words are frequent in many European languages. For example, the German word Verkehrswegeplanungsbeschleunigungsgesetzveränderungsentwurf makes clear that by splitting compound words for the index, hidden components may become retrievable, e.g. gesetz + veränderung.
The matching models extend the ideas developed in the I3R system (Croft, 1986; Croft & Das, 1990) by taking possible index types into account and by providing system independent support to query generation. The matching models are not used to provide evidence of document content but, instead, to generate queries.
The relationships of expressions and occurrences are given in the link relation EXPR_OCCS which has the identifier attributes ENO and ONO, as well as the attribute RELIABILITY, which gives the matching model's reliability in matching the intended expression as a real number between [0, 1].
Representation of concept relationships
Concept relationships are either association relationships or hierarchic relationships. They are always non-synonymous relationships because the latter are relationships between expressions. The ISO thesaurus construction standard (ISO, 1986) gives examples of types of association and hierarchic relationships usable in the data model.
Fig. 4. Representation of association relationships
The relation ASSOCIATIONS (Fig. 4) represents the association relationships between concepts through the attributes CNO and ASS_CNO, containing pairs of associated concepts, as well as the attributes ASS_TYPE (association type) and ASS_STRENGTH (association strength). The association type value specifies how the concepts are associated, e.g., sibling concepts (industry - company) and process relationship (investment - factory) (ISO, 1986).
Representation of hierarchic relationships is based on binary relations partitioned according to concept categories (e.g., organizations, and processes) and hierarchy types (e.g., generic and partitive relationships). The categories and relationship types can be chosen according to the thesaurus domain. For example, our sample thesaurus database contains the binary relations of Fig. 5 where organizations have a binary relation for the generic relationship and another for the instance relationship, process and events have a binary relation for the generic relationship, etc.
The advantages of partitioning the hierarchical relationships are: (i) efficiency, because the computation of transitive relationships is faster in smaller binary relations, and (ii) precision, because concepts can be analysed and expanded in controlled relationships.
Fig. 5. Representation of hierarchic relationships by binary relations
Return to Kal's home page.
Return to Kal's publication list.
The ExpansionTool expands conceptually represented queries at the three abstraction levels. When the necessary matching models at the occurrence level have been retrieved, they are translated into the specified target query language. The ExpansionTool is an application software implemented in Prolog. It utilizes, internally, queries of the integrated deductive query language by Niemi & Järvelin (1992). Järvelin (& al., 1996) contains definitions of the functions for performing various expansions.
Concept expansion
The starting point of concept expansion is a set of concept sets interpreted as conjunctive facets representing the information need. Within each set, the concepts are alternative (or disjunctive) interpretations of the facet. Thus the starting point is a set of concept facets C = {F1, F2, ... , Fk}. In our sample case it is C1 = {{c3, c5}, {c101}} where {c3, c5} and {c101} are the facets of concept identifiers. In principle, there is an "AND" between the facets and an "OR" between the concepts within each facet, e.g., between c3 and c5. This conjunctive normal form (CNF) structure is maintained throughout query construction and rejected only in the translation phase if the retrieval setting requires it.
The expansion principle is that each concept is expanded to a disjunctive set of concepts on the basis of conceptual relationships pointed out by the user. If expansion to broader concepts is requested, only the immediate broader concepts added, because that would probably expand the meaning of the query too far. If expansion to narrower concepts is requested, the concepts are expanded to all immediate or indirect narrower concepts. If associative expansion is requested, expansion is by one link in the association relationship. In the hierarchical relationship the user has a choice of hierarchical relationship type. One or more may be chosen. If expansion to instance concepts is requested, the instance concepts of all expanded concepts are included.
The expansion parameters are (1) set of expansion type indicators for concept expansion and (2) the required reliability. The former is a set of relationship names, bcg indicating generic broader concept relationship, bcp partitive broader concept relationship, ncg generic narrower concept relationship, inst the instance relationship, asso the associative relationship, etc. Both parameters are given to each facet separately.
The expansion result is a set of expanded concept facets {F1', F2', ... , Fk'} where each facet Fi' contains the original and the expanded concept identifiers. Thus each facet is expanded separately. .
Expression expansion
Expression expansion starts with the concept expansion result {F1', ... , Fk'}. The expansion principle is that, for each concept identifier, identifiers of selected expressions are collected (ORed) as representatives. The expansion parameter is a reliability figure guiding the selection of expression identifiers. All identifiers with strength exceeding the figure are collected for each concept. The result is an expanded set of expression facets {E1', ... , Ek'}, where each facet Ei is derived on the basis of the corresponding concept facet Fi.
Occurrence expansion
The starting point of occurrence expansion is a set of expression identifier facets E = {E1, ... , Ek} constructed above. The occurrence expansion principle is to collect, for each expression identifier, all its matching models which are reliable enough and suitable for a database index of a given type specified as expansion parameters. The occurrence expansion result is a set of matching model facets O = {O1, ..., Ok} where each facet Oi is derived from the corresponding expression identifier facet Ei by replacing each expression by a set of matching models.
Return to Kal's home page.
Return to Kal's publication list.
This step translates the query language independent expression into a query of a given language. The starting point of matching model translation is the expansion result constructed above. Matching model translation is implemented in the basis of logic grammars (Abramson & Dahl, 1989). Each grammar is a set of logical rules which generate well formed expressions of a specified query language. Each query language has its own logic grammar which takes its expression types and syntax limitations into account.
Usually logic grammars must be translated into logic programs separately, e.g., the rules of the well-known logic grammar DCG (Definite Clause Grammars, Pereira & Warren, 1980) are translated into normal Prolog clauses by adding extra arguments to each non-terminal. Because Prolog as such supports parsing of functional expressions we constructed our logic grammar directly as an executable Prolog program. The heads of the rules of our logic grammars consist always of two components: the standard source language component and the target language component. By using these components we parse and generate functional expressions at the same time using the one-pass approach.
The parameters of matching model translation are (1) the facet operator, (2) the database index type indicator and (3) the target query language identifier. The first one is used to express whether the facets are combined by a disjunction (the operator OR), conjunction (AND), or a paragraph (PARA) or a sentence (SENT) proximity condition, or by a probabilistic sum (the operator SUM). The database index type indicators bw, cw and iw indicate index types "basic words with compound words split", "basic words with compound words not split" and "inflected words", respectively. Allowed query language identifiers currently are one of inquery (for INQUERY v1.6 by University of Massachusetts), iso (for the ISO standard query language; ISO, 1993), topic (for TOPIC by Verity Inc.), or trip (for TRIP by PSI Inc.).
If the target language of matching model translation does not support some specific feature of matching models or logical structure, then either the obvious closest or alternative construct of the target language is generated or query construction terminates with an error message. All such transformations are handled by the logic grammars.
The result of matching model translation is a query of the target query language for an index of the specified type. The query may be very long, if it contains many broad concepts expanded by loose criteria, and if a proximity condition is applied between the facets.
We shall consider sample queries generated for the INQUERY and TRIP retrieval systems. INQUERY allows ordinary Boolean as well as probabilistic retrieval by Boolean operators '#and', '#or', and '#not', and proximity searching by the operator '#n', where n is an integer. The proximity operator '#n' spans over sentence and paragraph boundaries. The probabilistic sum operators '#wsum' and '#sum' are also available. The retrieval system TRIP allows ordinary Boolean searching ('and', 'or', 'not') and proximity searching by operators 'and.p', 'and.s' and ' . . ' for paragraphs, sentences and phrases, and string matching by several types of wild cards. For phrases, the number of periods indicates the number of allowed intervening words. TRIP interpretes full stops as sentence delimiters.
The matching model facet set O1 translates into the following TRIP query when the facet operator is SENT and the database index type is iw for inflected word forms:
(paper . . industr# or forest# . . . industr# or wood# . . . process# . . . industr# or plywood . . . industr# or sawmill# . . . industr#) and.s (invest# or biospher#)
The two facets are combined by the operator and.s and character strings generated from the matching models by or. The proximity matching models have generated character strings containing the TRIP proximity operator ". ." for specified word order and allowed distance given in the matching models. The stem matching models have generated character strings containing wild cards. Expressions like "chemical# . . . wood . . . process# . . . industr#" are not generated because "wood . . . process# . . . industr#" matches it. The logic grammar deletes all logically redundant matching models.
The translation result of the same request into the INQUERY query language with paragraph proximity and a bw type of index yields the result (operators in bold face):
#or( #20(#2(paper, industry), investment), #20(#2(paper, industry), invest), #20(#2(paper, industry), biosphere), #20(#3(forest, industry), investment), #20(#3(forest, industry), invest),< #20(#3(forest, industry), biosphere), ...)The three dots represent three more blocks with #3(wood, processing, industry), #3(#0(ply, wood), industry), and #3(#0(saw, mill), industry) instead of #2(paper, industry) and #3(forest, industry). The query is considerably longer than the previous one. This is due to the DNF form needed in INQUERY proximity operations. The facet operator para was translated by #20. The other proximity expressions #2 and #3 have the distance given in the matching models. Because the target index splits compound words, the compound words plywood and sawmill would be matched by #0(ply, wood) and #0(saw, mill), if they were not deleted as redundant. The operator #0 indicates that the component words must have the same address in the index.
3.2. The Expansion Tool
The ExpansionTool performs automatic QE in the way outlined above. The adjustable parameters of the current implementation are:
- A concept facet specification. Each facet contains one or more disjunctive concepts, required expansion types (bcg, ncg, asso, ...) and a reliability figure [0.0 ... 1.0].
- The facet operator (or, and, para, sent).
- The database index type indicator (bw, cw, iw).
- The target IR system indicator (inquery, iso, topic, trip)
The current implementation uses only one reliability figure for concept expansion, expression identification, and matching model collection. The ExpansionTool is implemented in Prolog. Thus the tool generates automatically several query versions in sequence, if one or more of the last three parameters are given as variables.
Return to Kal's home page.
Return to Kal's publication list.
We considered query formulation based on user's identification of the concepts relevant to her/his needs. In order to support the identification of relevant concepts, the relations can be augmented by a relation WORDS(WORD, ENO, COMPTYPE) giving for each word all expressions where it is a component of type COMPTYPE, e.g. full word, compound word component (cf. Jones, 1993). Then information needs can be matched with the thesaurus through WORDS using techniques suggested by Jones (1993).
The probabilistic SUM-operator of INQUERY does not yield good results for queries expanded in this way. Work supporting the probabilistic WEIGHTED-SUM-operator, with automatic weight computation based on thesaurus relationships, is under way. The deductive operations will also be extended for cyclic transitive relationships.
Thesaurus construction would benefit from tools for acquiring domain knowledge. The knowledge represented in the model may be customized to each particular user to support his/her cognitive structures. Thus domain knowledge should be collected from the users interactively (Paice, 1991; Das & Croft, 1990). The matching models should be generated automatically from expressions. This requires integration of NLP-tools. The useability of ordinary (indexing) thesauri in the construction of a thesaurus for automatic QE presents a problem due to defective hierarchies. If related concepts or partitive narrower concepts are put into a hierarchy of generic narrower concepts, expansion will not work properly. This is, however, common in ordinary (indexing) thesauri, originally intended for human use.
The data model and the integrated query language are also usable as a tool for managing an indexing thesaurus (Järvelin & al., 1996). The main application area of the ExpansionTool, however, is filter agents for networked information retrieval. Obviously, the ExpansionTool approach can be utilized in improving the parametrizability and matching expressions of information filter agents of networked heterogeneous database environments.
Return to Kal's home page.
Return to Kal's publication list.
Agrawal, R. (1987). Alpha: An extension of relational algebra to express a class of recursive queries. In: Proceedings of the 3rd International Conference on Data Engineering. Washington, D.C.: IEEE Computer Society Press; 1987, pp. 580-590.
Chang, C.L. & Walker, A. (1986). A Prolog programming interface with SQL/DS. In Kerschberg L. (ed.), Expert Database Systems: Proceedings from the 1st International Workshop. Menlo Park, CA: Benjamin-Cummings, pp. 233-246.
Croft, W.B. (1986). User-Specified Domain Knowledge for Document Retrieval. In: Rabitti, F. (ed.) Proc. of the 13th International Conference on Research and Development in Information Retrieval. 1986, Pisa, Italy, Sept. 8-10.
Croft, W. B. & Das, Raj (1990). Experiments with query acquisition and use in document retrieval systems. Vidick, J-L. (ed.) Proc. of the 13th International Conference on Research and Development in Information Retrieval. Bruxelles: ACM, pp. 349-368.
Ekmekcioglu, F.C., Robertson, A.M. &Willett, P. (1992). Effectivenes of query expansion in ranked-output retrieval systems. Journal of Information Science, 18, 139-147.
Fidel, R. & Efthimiadis, E.N. (1995). Terminological knowledge structure for intermediary expert systems. Infomation Processing and Management, 31(1), 15-27.
Hancock-Beaulieu, M. (1992). Query expansion: Advances in research in online catalogs. Journal of Information Science, 18, 99-103.
ISO (1986). ISO International Standard 2788. Documentation - Guidelines for the establishment and development of monolingual thesauri. International Organization for Standardization.
ISO (1993). ISO International Standard 8777:1993(E). Information and documentation - commands for interactive text searching. International Organization for Standardization.
Jones, S. (1993). A thesaurus data model for an intelligent retrieval system. Journal of Information Science, 19, 167-178.
Jones, S. & al. (1995). Interactive thesaurus navigation: intelligence rules OK? Journal of the American Society of Information Science, 46(1), 389-404.
Järvelin, K. & Kristensen, J. & Niemi, T. & Sormunen, E. & Keskustalo, H. (1996). A deductive data model for thesaurus navigation and query expansion. Tampere, Finland: University of Tampere, Dept. of Information Studies, Report RN-1996-1, to be published.
Koskenniemi, K. (1983). Two-level morphology: a general computational model for word-form recognition and production. Helsinki: University of Helsinki, Dept. of General Linguistics, Publication No. 11.
Kristensen, J. (1993). Expanding end-user's query statements for free text searching with a search-aid thesaurus. Infomation Processing and Management, 29(6), 733-745.
Niemi, T. & Järvelin, K. (1992). Operation-oriented query language approach for recursive queries - Part 1. Functional definition. Information Systems, 17 (1), 49-75.
Paice, C.D. (1991). A thesaural model of information retrieval. Infomation Processing and Management, 27(5), 433-447.
Pereira, F.C.N. & Warren, D.H.D. (1980). Definite Clause Grammars for language analysis - A survey of the formalism and a comparison with Augmented Transition Networks. Artificial Intelligence, 13: 231-278.
Ullman, J.D. (1989). Principles of Database and Knowledge Base Systems. Vol. II: The new technologies. Rockville, MD: Computer Science Press.
UMLS (1994). UMLS Knowledge Sources. 5th Experimental Edition. Bethesda MD: National Library of Medicine.
Return to Kal's home page.
Return to Kal's publication list.
Paluu Kallen kotisivulle.
Paluu Kallen julkaisuluetteloon.