A novel method for the evaluation of Boolean query effectiveness across a wide operational range.
Traditional methods for the system-oriented evaluation of Boolean IR system suffer from validity and reliability problems. Laboratory-based research neglects the searcher and studies suboptimal queries. Research on operational systems fails to make a distinction between searcher performance and system performance. This approach is neither capable of measuring performance at standard points of operation (e.g. across R0.0-R1.0). A new laboratory-based evaluation method for Boolean IR systems is proposed. It is based on a controlled formulation of inclusive query plans, on an automatic conversion of query plans into elementary queries, and on combining elementary queries into optimal queries at standard points of operation. Major results of a large case experiment are reported. The validity, reliability, and efficiency of the method are considered in the light of empirical and analytical test data.
Figure

1. An example of a high recall Oriented
query used by Harter [10] to illustrate the facet
based query planning approach.
(information retrieval OR
online systems OR
AND
trial(1w)error
expert systems OR
artificial intelligence OR
behavior?/DE,ID,TI
fundamental validity problem. Queries exploit the Boolean IR
model in a suboptimal way.
1.2 Harter's Idea: the Most Rational Path
Harter [10] introduced an idea for an evaluation method based
on the notion of elementary queries (EQ).1 Harter used a single
search topic to illustrate how the method could be applied. He
designed a high recall oriented query plan (see Fig 1). Harter
applied the building block search strategy which quite
commonly used by professional searchers [6, 9, 12, 16].
The major steps of the building blocks strategy are 1) Identify
major facets and their logical relationships with one another.
query terms that represent each facet: words, phrases,
etc. Combine the query terms of a facet by disjunction (OR
operation). Combine the facets by conjunction or negation
(AND or ANDNOT operation) [9].
The notion of facet is important in query planning. It is a
concept that is identified from, and defines one exclusive aspect
of a search topic. In step 2, a typical goal is to discover all
plausible query terms appropriate in representing the selected
facet.
Next, Harter retrieved all documents matching the conjunction
of facets A and B represented by the disjunction of all selected
query terms, and assessed the relevance of resulting 371
documents. In addition, all conjunctions of two query terms
(called elementary queries) from the query plan representing
facets A and B in Fig. 1 were composed and executed. A sample
from the 24 elementary queries and the summary of their
retrieval results are presented in Table 1.
Harter [10] demonstrated the procedure of constructing optimal
queries (called the most rational path). An estimate for
maximum precision across the whole relative recall range was
determined by applying a simple incremental algorithm:
1. To create the initial optimal query, choose the EQ that
achieves the highest precision.
Actually Harter talked about elementary postings sets. This is very
confusing since it applies set-based terminology to address queries as
logical statements.
Elementary queries
# of
Docs
# of Rel
Docs
cision
Recall
s22
information retrieval
AND tactic?
information retrieval
AND heuristic?
information retrieval
AND trial(1w)error
behavior?/DE,ID,TI
cognitive/de

Table

1. Retrieval results for the 24 elementary queries
in the case search by Harter (1990).
Precision
0,00
s3 or s18
or s18 or s24
Recall
Most rational path Elementary queries

Figure

2. Recall and precision of the 24 elementary queries and
the most rational path in the case search presented by Harter [10].
2. Create in turn the disjunction of each of the remaining EQs
with the current optimal query. Select the disjunction with
the EQ that maximizes precision. The disjunction of the
current optimal query and the selected EQ creates a new
optimal query.
3. Repeat step 2 until all elementary queries have been
exhausted.
Precision and recall values for the 24 elementary queries and
the respective curve for the optimal queries are presented in Fig
2.
Harter never reported full-scale evaluation results based on the
idea of the most rational path except this single example. He did
neither develop operational guidelines for a fluent use of the
method in practice.
1.3 Research Goals
The main goal of the study was to create an evaluation method
for measuring performance of Boolean queries across a wide
operational range by elaborating the ideas introduced by Harter
[10]. The method is presented and argued using the framework
suggested by Newell M={domain, procedure, justification}
[19]:
1. The domain of the method specifies the appropriate
application area for the method.
2. The procedure of the method consists of the ordered set of
operations required in the proper use of the method.
Especially, two major operations unique to the procedure
need to be elaborated: a) Query formulation. How the set of
elementary queries is composed from a search topic? b)
Query optimization. What algorithm should be used for
combining the elementary queries to find the optimal query
for different operational levels?
3. The justification of the method. The appropriateness,
validity, reliability and efficiency of the method within the
specified domain must be justified.
The structure of this paper is the following: First, some basic
concepts and the procedure of the method are introduced.
Second, a case experiment is briefly reported to illustrate the
domain and the use of the proposed method in a concrete
experimental setting. Third, the other justification issues of the
method: validity, reliability and efficiency are discussed.
Several empirical tests were carried out to assess the potential
validity and reliability problems in applying the method.
2. OUTLINE FOR THE METHOD
The aim of this section is to introduce a sound theoretical
framework for the procedure of the method and to formulate
operational guidelines for exercising it.
2.1 Query Structures and Query Tuning Spaces
models address the issue of comparing a query as a
representation of a request for information with representations
of texts. The Boolean IR model supports rich query structures, a
binary representation of texts, and an exact match
technique for comparing queries and text representations [2].
A Boolean query consists of query terms and operators. Query
terms are usually words, phrases, or other character strings
typical of natural language texts. The Boolean query structures
are based on three logic connectives conjunction (),
disjunction (), negation ( ), and on the use of parentheses. A
query expresses the combination of terms that retrieved
documents have to contain. If we want to generate all possible
Boolean queries for a particular request, we have to identify all
query terms that might be useful, and to generate all logically
reasonable query structures.
Facet, as defined in section 1.2, is a very useful notion in
representing relationships between Boolean query structures
and the search topic. Terms within a facet are naturally
combined by disjunctions. Facets themselves present the
exclusive aspects of desired documents, and are naturally
combined by Boolean conjunction or negation. [9].
Expert searchers tend to formulate query plans applying the
notion of facet [9, 16]. Resulting query plans are usually in a
standard form, the conjunctive normal form (CNF) (for a formal
definition, see [1]). The structure of a Boolean query can be
easily characterized in CNF queries: Query exhaustivity (Exh) is
the number of facets that are exploited. Query extent (QE)
characterizes the broadness of a query, and can be measured,
e.g. as the average number of query terms per facet. For
instance, in the query plan designed by Harter Exh=2 and
QE=5.5 (see Fig. 1).
The changes made in query exhaustivity and extent to achieve
appropriate retrieval goals are called here query tuning. The
range within which query exhaustivity and query extent can
change sets the boundaries for query tuning. The set of all
elementary queries and their feasible combinations composed at
all available exhaustivity and extent levels form the query
tuning space.
In the example by Harter (Fig 1), seven different disjunctions of
query terms can be generated from facet A (=23-1) and 255 from
(=28-1). The total number of possible EQ combinations
is then 7 x 255 =1,785 at Exh= 2. In addition, 7 and 255 EQ
combinations can be formed at Exh=1 from facets A and B,
respectively. Thus, the total number of EQ combinations
creating the query tuning space across exhaustivity levels 1 and
2 for the sample query plan is 2,047.
1.2 The Procedure of the Method
The procedure of the proposed method consists of eight
operations at three stages:
STAGE I. INCLUSIVE QUERY PLANNING
1. Design inclusive query plans. Experienced searchers
formulate inclusive query plans for each given search topic.
It yields a comprehensive representation of the query tuning
space available for a search topic.
2. Execute extensive queries. The goal of extensive queries is
to gain reliable recall base estimates.
3. Determine the order of facets. The facet order of inclusive
query plans is determined by ranking the facets according to
their measured recall power, i.e. their capability to retrieve
relevant documents.
STAGE II. QUERY OPTIMISATION
4. Generate the set of elementary queries (EQ). Inclusive query
plans in the conjunctive normal form (CNF) at different
exhaustivity levels are transformed into the disjunctive
normal form (DNF) where the elementary conjunctions
create the set of elementary queries. All elementary queries
are executed to find the set of relevant and non-relevant
documents associated with each EQ.
5. Select standard points of operation (SPO). Both fixed recall
levels R0.1,,R1.0 and fixed document cut-off values, e.g.
DCV2, DCV5,,DCV500 may be used as SPOs.
6. Optimization of queries. An optimisation algorithm is used
to compose the combinations of EQs performing optimally at
each selected SPO.
STAGE III. EVALUATION OF RESULTS
7. Measure precision at each SPO. Precision can be used as a
performance measure. Precision is averaged over all search
topics at each SPO.
8. Analyse the characteristics of optimal queries. The optimal
queries are analysed to explain the changes in the
performance of an IR system.
The above steps describe the ordered set of operations
constituting the procedure of the proposed method. Inclusive
query planning (steps 1-3) and the search for the optimal set of
elementary queries (steps 4-6), are in the focus of this study.
1.3 Inclusive Query Planning
The techniques of query planning are routinely taught to novice
searchers [9, 16]. A common feature in different query planning
techniques is that they emphasize the analysis and identification
of searchable facets, and the representation of each facet as an
exhaustive disjunction of query terms. The goal of inclusive
query planning is similar, but the thoroughness of identification
task is stressed even more. In inclusive query planning, the goal
is to identify
1. all searchable facets of a search topic, and
2. all plausible query terms for each facet.
A major doubt in using human experts to design queries is
probably associated with the reliability of experimental designs.
For instance, the average inter-searcher overlap in selection of
query terms (measured character-by-character) is usually around
per cent [25]. Fortunately, the situation is not so bad when
are considered. For instance, in a study by Iivonen [12],
the average concept-consistency rose up to 88 per cent, and
experienced searchers were even more consistent. This indicates
that expert searchers are able to identify the facets of a topic
consistently although the overlap of queries at string level may
be low.
The identification of all plausible query terms for each
identified facet is another task requiring searching expertise.
Basically, the comprehensiveness of facet representations is
mostly a question of how much effort are used to identify
potential query terms. The query designer is freed from the
needs to make compromised query term selections typical of
practical search situations. The optimization operation will
automatically reject ill-behaving query terms. The process can
be improved by appropriate tools (dictionaries, thesauri,
browsing tools for database indexes, etc.
The final step is to decide the order of facets in the query plan.
In the case of a laboratory test collection, full relevance data (or
at least its justified estimate) is available. The facets of an
inclusive query plan can be ranked in the descending order of
recall. The disjunction of all query terms identified for a facet is
used to measure recall values.
1.4 Search for the Optimal Set of EQs
The size of the query tuning space increases exponentially as a
function of the number of EQs. We are obviously facing the risk
of combinatorial explosion since we do not know the upper
limit of query exhaustivity and, especially, query extent in
inclusive query plans. Solving the optimization problem by
blind search algorithms could lead to unmanageably long
running times. The search for the optimal set of EQs is a NP-hard
problem.
Harter [10] introduced a simple heuristic algorithm but he did
not define it formally. Query optimization resembles a
traditional integer programming case called the Knapsack
Problem. The problem is to fill a container with a set of items
so that the value of the cargo is maximized, and the weight limit
for the cargo is not exceeded [4]. The special case where each
item is selected once only (like EQs), is called the 0-1 Knapsack
Problem. Efficient approximation algorithms have been
developed to find a feasible lower bound for the optimum [17].
The problem of finding the optimal query from the query tuning
space can be formally defined by applying the definitions of the
Knapsack Problem as follows:
Select a set of EQs so as to
subject to nixi  DCVj
1,if eqi isselected
0,otherwise
and
The above definition of the optimization problem is in its
maximization version. The number of relevant documents is
maximized while the total number of retrieved documents is
restricted by the given DCVj. In the minimization version of the
problem, the goal is to minimize the total number of documents
while requiring that the number of relevant documents exceeds
some minimum value (a fixed recall level).
Unfortunately, standard algorithms designed for physical
objects would not work properly with EQs. Different EQs tend
to overlap and retrieve at least some joint documents. This
means that, in a disjunction of elementary queries, the profit ri
and the weight ni of the elementary query eqi have
dynamically changing effective values that depend on the EQs
selected earlier. The effect of overlap in a combination of
several query sets is hard to predict.
A simple heuristic procedure for an incremental construction of
the optimal queries was designed applying the notion of
efficiency list [17]. The maximization version of the algorithm
contains seven steps:
Remove all elementary queries eqi
a) retrieving more documents than the upper limit for the
number of documents (i.e. ni > residual document cut-off
value DCV', starting from
b) retrieving no relevant documents (ri=0).
2. Stop, if no elementary queries eqi are available.
3. Calculate the efficiency list using precision values ri/ni for
remaining m elementary queries and sort elementary queries
in order of descending efficiency. In the case of equal values,
use the number of relevant documents (ri) retrieved as the
second sorting criterion.
4. Move eq1 at the top of the efficiency list to the optimal
query.
5. Remove all documents retrieved by eq1 from the result sets
of remaining elementary queries eq2, ., eqm.
6. Calculate the new value for free space DCV'.
7. Continue from step one.
The basic algorithm favors narrowly formulated EQs retrieving
a few relevant documents with high precision at the expense of
broader queries retrieving many relevant documents with
medium precision. The problem can be reduced by running the
optimization in an alternative mode differing only in step four
of the first iteration round: eqi retrieving the largest set of
relevant documents is selected from the efficiency list instead of
eq1. The alternative mode is called the largest first optimization
and the basic mode the precision first optimization.
3. A CASE EXPERIMENT
The goal of the case experiment was to elucidate the potential
uses of the proposed method, to clarify the types of research
questions that can be effectively solved by the method, and to
explicate the operational pragmatics of the method.
3.1 Research Questions
The case experiment focused on the mechanism of falling
effectiveness of Boolean queries in free-text searching of large-
full-text databases. The work was inspired by the debate
concerning the results of the STAIRS study [3, 22]. The goal
was to draw a more detailed picture of system performance and
optimal query structures in search situations typical of large
databases.
Assuming an ideally performing searcher, the main question
was: What is the difference in maximum performance of
Boolean queries between a small database and two types of
large databases? The large & dense database contained a larger
volume of documents than the small database but the density of
relevant documents (generality) was the same. In the large &
sparse database, both the volume of documents was higher and
the density of relevant documents was lower than in the small
database.
Twelve hypotheses were formulated concerning effectiveness,
exhaustivity and proportional query extent of queries in large
databases. For details, see [26].
3.2 Data and Methods
3.2.1 Optimization Algorithm
The optimization algorithm described in Section 2.5 was
programmed in C for Unix. Both a maximization version
exploiting a standard set of document cut-off values (DCV2,
DCV5,, DCV500) and a minimization version exploiting fixed
recall levels (R0.1R1.0) were implemented. At each SPO, the
iteration round (called optimization lap) was executed ten times
starting each round by selecting a different top EQ from the
efficiency list: five laps in the largest first mode, and five in the
precision first mode. The alternative results at a particular SPO
achieved by the algorithm in different optimization laps were
sorted to find the most optimal queries for further analysis.
3.2.2 Test Collection
The Finnish Full-Text Test Collection developed at the
University of Tampere was used in the case experiment [14].
The test database contains about 54,000 newspaper articles from
three Finnish newspapers. A set of 35 search topics are
available including verbal topic descriptions and relevance
assessments.
The test database is implemented for the TRIP retrieval
systems2. The test database played the role of the large & dense
database. Other databases, the small database and the large &
sparse database, were created through sampling from EQ result
sets. The large & sparse database was created by deleting about
% of the relevant documents, and the small database by
deleting about 80 % of all documents of the EQ result sets.
Thus, the EQ result sets for the small database contained the
same relevant documents as those for the large & sparse
database. Query optimization was done separately on these
three EQ data sets.
3.2.2.1 Inclusive Query Plans
The initial versions of inclusive query plans were designed by
an experienced search analyst working for three months on the
project. Query planning was an interactive process based on
thorough test queries and on the use of vocabulary sources.
Later parallel experiments (probabilistic queries) revealed that
the initial query plans failed to retrieve some relevant
documents. These documents were analyzed, and some new
query terms were added to represent the facets
comprehensively. The final inclusive query plans were capable
to retrieve 1270 (99,3 %) out of the 1278 known relevant
documents at exhaustivity level one.
In total, inclusive query plans contained 134 facets. The average
exhaustivity of query plans was 3.8 ranging from 2 to 5. The
total number of query terms identified was 2,330 (67 per query
plan and per facet). The number of terms ranged from 23 to
per query plan, and from 1 to 74 per facet. The wide
variation in the number of query terms per facet characterizes
the difference between specific concepts (e.g. named persons or
organizations) and general concepts (e.g., domains or
processes).
3.2.2.2 Data Collection and Analysis
Precision, query exhaustivity and query extent data were
collected for the optimal queries at SPOs. The sensitivity of
results to changes in search topic characteristics like the size of
a recall base, the number of facets identified, etc. were analyzed.
Also the searchable expressions referring to query plan facets
were identified in all relevant documents of a sample of test
topics to find explanations for the observed performance
differences. Statistical tests were applied to all major results.
3.3 Sample Results

Figures

3-5 summarize the comparisons between the small,
large & dense, and large & sparse databases: average precision,
exhaustivity and proportional extent of optimal queries at recall
levels R0.1-R1.0.3
The case experiment could reveal interesting performance
characteristics of Boolean queries in large databases. The
average precision across R0.1-R1.0 was about 13 % lower in the
2 TRIP by TietoEnator, Inc.
3 Proportional query extent (PQE) was measured only for high recall
and high precision searching because of research economical reasons.
PQE is the share of query terms actually used of the available terms
in inclusive query plans (average over facets).
Precision
0,00
Recall

Figure

3. Average precision at fixed recall levels in
optimal queries for small, large&dense and
large&sparse databases.
Small db
L&d db
L&s db
4,0
Exhaustivity
Small db
L&d db
L&s db
Recall

Figure

4. Exhaustivity of high recall queries
optimised for small, large&dense and large&sparse
databases.
Proportional query
extent
0,6
0,4
0,3
Small db
L&d db
L&s db
Recall

Figure

5. Proportional query extent (PQE) of
optimal queries in the small, large&dense, and
large&sparse databases.
large & dense database (database size effect), and about 40 %
lower in the large & sparse database (database size + density
effect) than in the small database (see Fig 3). The average
exhaustivity of optimal queries was higher in the large databases
than in the small one, but the level of precision could not be
maintained. Proportional query extent was highest in the large
dense database suggesting that more query terms are needed
per facet when a larger number of documents have to be
retrieved.
topics
The number of
Large recall base
Small recall base
Query exhaustivity

Figure

6. The number of search topics where full recall can
be achieved as a function of query exhaustivity in the small
and large recall bases (18 topics in total).
A very interesting deviation was identified in the precision and
exhaustivity curves at the highest recall levels. In the large &
dense database, the precision and exhaustivity of optimal
queries fell dramatically between R0.9 and R1.0.
The results of the facet analysis of all relevant documents in a
sample of test topics clarified the role of the recall base size
in falling effectiveness at R1.0. The more documents need to be
retrieved to achieve full recall, the more there occur relevant
documents where some query plan facets are expressed
implicitly. The results are presented in Fig 6. For Exh=1 full
recall was possible in all but one test topic for both recall bases.
At higher exhaustivity levels, the number of test topics where
full recall is possible fell much faster in the large recall base.
Above results are just examples from the case study findings to
illustrate the potential uses of the proposed method. High
precision searching was also studied by applying DCVs as
standard points of operation. It turned out, for instance, that the
database size alone does not induce efficiency problems at low
DCVs. On the contrary, highest precision was achieved in the
large & dense database. It was also shown that earlier results
indicating the superiority of proximity operators over the AND
operator in high precision searching are invalid. Queries
optimized separately for both operators show similar average
performance. For details, see [26].
4. JUSTIFICATION OF THE METHOD
Evaluation methods should themselves be evaluated in regard to
appropriateness, validity, reliability, and efficiency [24, 29].
The appropriateness of a method was verified in the case study
by showing that new results could be gained. Validity,
reliability, and efficiency are more complex issues to evaluate.
The main concerns were directed at the unique operations:
inclusive query planning and query optimization.
4.1 Facet Selection Test
Three subjects having good knowledge of text retrieval and
indexing were asked to make a facet identification test using a
sample of 14 test topics. The results showed that the
exhaustivity of inclusive query plans used in the case
experiment were not biased downwards (enough exhaustivity
tuning space). The test also verified earlier results that the
consistency in the selection of query facets is high between
search experts.
4.2 Facet Representation Test
The facet analysis of all relevant documents in the sample of
search topics showed that the original query designer had
missed or neglected about one third of the available expressions
in the relevant documents. However, the effect of missed query
terms was regarded as marginal since their occurrences in
documents mostly overlapped with other expressions already
covered by the query plan. The effect was shown to be much
smaller than the effect of implicit expressions. In the interactive
query optimization test (see next section), precision was
observed to drop less than 4 %.
4.3 Interactive Query Optimization Test
The idea of the interactive query optimization test was to
replace the automatic optimization operation by an expert
searcher, and compare the achieved performance levels as well
as query structures. A special WWW-based tool, the IR Game
[27], designed for rapid analysis of query results was used in
this test. When interfaced to a laboratory test collection, the tool
offers immediate performance feedback at the level of
individual queries in the form of recall-precision curves, and a
visualization of actual query results. The searcher is able to
study, in a convenient and effortless way, the effects of query
changes.
An experienced searcher was recruited to run the interactive
query optimization test. A group of three control searchers were
used to test the overall capability of the test searcher. The test
searcher was working for a period of 1.5 months trying to find
optimal queries for the sample of test topics for which the
full data of facet analysis was available. In practice, the test
searcher did not face any time constraints.
The results showed that the algorithm was performing better
than or equally with the test searcher in 98 % out of the 198 test
cases. This can be regarded as an advantageous result for a first
version of a heuristic algorithm.
4.4 Efficiency of the Method
The investment in inclusive query planning was justified to be
reasonable in the context of a test collection. It was also shown
that the growth of running time of the optimization algorithm
can be characterized by O(n log n), and that it is manageable
for all EQ sets of finite size.
5. CONCLUSIONS AND DISCUSSION
The main goal of this study was to design, demonstrate and
evaluate a new evaluation method for measuring the
performance of Boolean queries across a wide operational
range. Three unique characteristics of the method help to
comprehend its potential:
1. Performance can be measured at any selected point across
the whole operational range, and different standard points of
operation (SPO) may be applied.
2. Queries under consideration estimate optimal performance at
each SPO, and query structures are free to change within the
defined query tuning space in search of the optimum.
3. The expertise of professional searchers could be brought into
a system-oriented evaluation framework in a controlled way.
The domain of the method can be characterized by
illustrating the kinds of research variables that can be
appropriately studied by applying the method. Query
precision, exhaustivity and extent are used as dependent
variables, and the standard points of operation as the control
variable. Independent variables may relate to:
1. documents (e.g. type, length, degree of relevance)
2. databases (e.g. size, density)
3. database indexes (e.g. type of indexing, linguistic
normalization of words)
4. search topics (e.g. complexity, broadness, type)
5. matching operations (e.g. different operators).
The proposed method offers clear advantages over traditional
evaluation methods. It helps to acquire new information about
the phenomena observed and challenge present findings because
it is more accurate (averaging at defined SPOs). The method is
also economical in experiments where a complex query tuning
space is studied. The query tuning space contains all potential
candidates for optimal queries, but data are collected only on
those queries that turn out to be optimal at a particular SPO.
The proposed method yielded two major innovations: inclusive
query planning, and query optimization. The former innovation
is more universal since it can be used both in Boolean as well as
in best match experiments, see [14]. The query optimization
operation in the proposed form is restricted to the Boolean IR
model since it presumes that the query results are distinct sets.
The inclusive query planning idea is easier to exploit since its
outcome, the representation of the available query tuning space,
can also be exploited in experiments on best-match IR systems.
Traditional test collections were provided with complete
relevance data. Inclusive query plans are a similar data set that
can be used in measuring ultimate performance limits of
different matching algorithms. Inclusive query plans help also
in categorizing test topics according to their properties, e.g.
complex vs. simple (exhaustivity tuning dimension), and broad
vs. narrow (extent tuning dimension). This opens a way to
create experimental settings that are more sensitive to
situational factors, the issue that has been raised in the
Boolean/best-match comparisons [11, 20].
6.

ACKNOWLEDGMENTS

I am grateful to my supervisor Kalervo Jrvelin, and to the
FIRE group: Heikki Keskustalo, Jaana Keklinen, and others.
7.


--R

Logic and Boolean algebra.
Retrieval Techniques.
An evaluation of retrieval effectiveness for a full-text document retrieval system

The Cranfield tests on index language devices.
Searcher's Selection of Search Keys.
Boolean
The First Text Retrieval Conference (TREC-1)
Online Information retrieval.
Search Term Combinations and Retrieval Overlap: A Proposed Methodology and Case Study.
An Evaluation of Interactive Boolean and Natural Language Searching with Online Medical Textbook.
Consistency in the selection of search
An Introduction to Algorithmic and Cognitive Approaches for Information Retrieval.

Information Retrieval Systems:
Information Retrieval Today.
Knapsack Problems.
The Medline Full-Text Project
Heuristic programming: Ill-structured problems
Freestyle vs. Boolean: A comparison of partial and exact match retrieval systems.
A new comparison between conventional indexing (MEDLARS) and automatic text processing (SMART).
--TR
An evaluation of retrieval effectiveness for a full-text document-retrieval system
Another look at automatic text-retrieval systems
Retrieval techniques
Knapsack problems: algorithms and computer implementations
The pragmatics of information retrieval experimentation, revisited
Natural language vs. Boolean query evaluation
Consistency in the selection of search concepts and search terms
An evaluation of interactive Boolean and natural language searching with an online medical textbook
Evaluation of evaluation in information retrieval
A deductive data model for query expansion
Freestyle vs. Boolean
Boolean search
Information Retrieval Experiment
Information Retrieval Today
Introduction to Modern Information Retrieval
Online Information Retrieval

--CTR
Eero Sormunen, Extensions to the STAIRS StudyEmpirical Evidence for the Hypothesised Ineffectiveness of Boolean Queries in Large Full-Text Databases, Information Retrieval, v.4 n.3-4, p.257-273, September-December 2001
Caroline M. Eastman , Bernard J. Jansen, Coverage, relevance, and ranking: The impact of query operators on Web search engine results, ACM Transactions on Information Systems (TOIS), v.21 n.4, p.383-411, October
structured queries;test collections;evaluation general;testing methodology