This work revisits the age-old problem of balancing search precision and recall using the promising new approach of Selective Search which partitions the document collection into topic-based shards and searches a select few shards for any query. In prior work Selective Search has demonstrated strong search precision, however, this improvement has come at the cost of search recall. In this work, we test the hypothesis that improving the effectiveness of shard selection can better balance search precision and recall. Toward this goal we investigate two new shard selection approaches, and conduct a series of experiments that lead to three new findings:- 1. Big-document based shard selection approaches can substantially outperform the small-document approaches when provided with richer query representation, 2. Applying Learning-ToRank approach for shard ranking provides the most effective Selective Search setup, 3. If the relevant documents for a query are spread across less than 10% of the shards then Selective Search can successfully balance precision and recall.
The problem of balancing search precision and
recall is not new to the IR (Information Retrieval)
community. Improving one, almost always
results in degrading the other. The most
prominent example of IR, Web search, makes it seem
that search precision is more important than
recall. However, there are many other use cases of
IR where search recall is equally, if not more,
important than precision. Medical or health
information retrieval, prior-art search, and legal
information retrieval are a few examples of the same.
Motivated by these observations, we take a fresh look
at the problem of balancing search precision and
recall through the lenses of a promising new
approach of Selective Search
We believe that the topical organization of the
document collection along with the selective
nature of this search approach, can support a search
environment that can balance precision and
recall. We test this hypothesis in this paper through
a series of experiments where we apply
wellestablished shard ranking approach, and propose
improvements to these algorithms that leverage
the topic-based organization of the documents.
Selective Search has consistently demonstrated
good performance on precision-oriented metrics.
The reason for this trend is the purity of the search
space. The few topical shards that are selected
and searched for a query contain much less noise,
that is, false-positive documents, than the
complete collection. A purer search space reduces the
chances of non-relevant documents being included
in the search results, which directly improves the
precision. In order to improve recall, Selective
Search needs to identify all the shards containing
relevant documents. Thus when optimizing for
recall, more than a few shards need to be searched.
As such the accuracy of shard ranking algorithm
at deeper ranks also becomes critical. This
observation suggests that an effective shard ranking
algorithm would be able to improve search
recall without degrading precision. We test this
hypothesis thoroughly using empirical evaluation as
early and deeper ranks. Finally, we introduce a
novel shard ranking approach, Learning to Rank
Shards (LeToR-S), that is based on the successful
Learning-to-Rank document approach
This paper is organized as follows. The prior work that has informed and influenced our work is described in the next section. The proposed shard ranking approaches are described in Sections 3 and 4. The experimental setup used for evaluation is described in Section 5, followed by Results and Analysis, Section 6. The conclusions we draw from this work are provided in Section 7. 2
Selective Search falls under the subfield of
distributed information retrieval
In cooperative environments, the providers of target resources are willing to share the term statistics and metadata of the documents collections. The methods ranking resources based on the term statistics are called big-document approaches since the model can be extended from document retrieval model by treat each resource as a entity.
GlOSS
CORI
T =
dfi dfi + 50 + 150 ⇤ swi/avg sw
I = log( S+sf0.5 ) log(S + 1.0) Score(tk|Si) = b + (1 b) ⇤ T ⇤ I (1) (2) (3) dfi: the document frequency of the term tk in shard i.
sf : the shard frequency of the term tk (The number of shards contain tk).
swi: the number of total words in the shard i. avg sw: the average number of total words in one shard.
S: the number of shards.
tk: the kth term in the user query.
b: the minimum belief component, set to 0.4
CORI inherited the query operators from
INQUERY
Taily
In uncooperative environments, the important statistics such as term frequency or collection size can not be obtained. Therefore, big-document approaches are not capable to compute the shard scores. Small-document algorithms solve this issue by approximating the document distribution inside a resource by sampling a small subset, which is called centralized sample database, or centralized sample index (CSI) structure.
The ReDDE
Score(Siq) = Count(n, Siq) ⇥ |SiCSI | |Si| (4) Count(n, Siq) is the count of documents occurred in top n retrieved documents in CSI |Si| is the size of the shard and |SiCSI |is the size of its sample . The shard scores are then normalized to obtain a valid probability distribution used to rank the shards.
CRCS
SUSHI
The scenario in which Selective Search operates is cooperative, that is, CORI has access to the complete term statistics for each shard. While ReDDE estimates the shard ranking based on the small sample of each shard. As such, one would expect CORI to perform at least on par, if not outperform, ReDDE. However, the term statistics that CORI uses, although complete are highly misleading. This is so because traditional CORI uses unigram model where each query term is treated as an individual entity. This leads to a very poor representation of the query. For example, the query arizona fish and game when decomposed into unigrams, looses the central topic fishing in arizona. CORI cannot distinguish between shards are on topic, and shards that contain documents about arizona in some other context, and about fishing in some other state.
These observations motivated the following investigation were a richer representation of the query is used by both CORI and ReDDE. Given a query with n terms, n 1 bigrams are generated by enumerating all pairs of consecutive terms. Bigrams with stopwords are discarded, and the remaining bigrams are added to the original unigram query. As an example, for query obama family tree, this approach generates the following query representation using the Indri Query Language: #combine(obama family tree #uw2(obama family) #uw2(family tree)), where the #combine operator coalesces the scores from all the element of the query, and the #uwX operator is used for specifying an unordered phrase of length X. The ReDDE Uni+Bi runs the query generated using the above procedure against the CSI, and the rest of the search process is same as before. In case of CORI Uni+Bi, frequency statistics for bigrams, in addition to unigrams, are used in order to evaluate the richer query representation. Since the bigram statistics can be precomputed off-line, the response time of shard ranking, and query evaluation is not affected. Single-term queries or the queries containing no phrases because of stop words (e.g. ”to be or not to be”), remain unchanged. Higherorder n-grams, such as, trigrams were not included due to two reasons: 1. cost of the computing the statistics for trigrams is substantially high, and 3. the benefits from trigram representation are expected to be marginal because most queries are short, two or fewer terms. In search scenarios where the user queries are longer (legal or medical retrieval), trigram query representation could be worth the additional cost. This is part of future work. 4
The Learning-to-Rank approaches have been
successfully used to improve the document
ranking task
The different fields or sections of the document inform the features. The title, body, heading, url, whole document each generate a separate set of features. Several variants of CORI scores for the query are evaluated against the document fields, and are used as features. More specifically, CORI SUM, CORI MIN, and CORI VAR are the three variants of CORI as defined in Equations 5 through 7. Each of these scores is computed for two different query representations:- unigram, and phrasal, against all of the different document fields.
CORI SU M (Q|Si) = X Score(tk|Si) (5) tk2 Q CORI M IN (Q|Si) = min Score(tk|Si) (6) tk2 Q µ =
tk2 Q n1 X Score(tk|Si)
X (Score(tk|Si) tk2 Q CORI V AR(Q|Si) = (8)
Where Score(tk|Si) is the same as Equation 3, and µ = n1 Ptk2 Q Score(tk|Si)
For each query and shard pair, the above
vector of features is compiled, in order to learn
the ranking model or to predict the ranking
using the RandomForest
For the empirical evaluation the experimental
setup that was undertaken is described next. We
use the CategoryB dataset of ClueWeb09, which
contains 50,220,423 documents. The 92 topical
shards created for CategoryB dataset by
Kulkarni and Callan
This section describes the experiments that were conducted to test the various hypotheses about improving search effectives by leveraging topical shards. Table 1 presents a comprehensive set of results for four different investigations that we undertook. We describe these next in the following subsections, and analyze the results in Table 1. 6.1
Traditionally the choice of small- or big-document approach was dictated by the type of search environment:- uncooperative, or cooperative, respectively. Although, our scenario would categorize as cooperative, we choose to also experiment with small-document approaches because the conventional belief has been that small-document approaches provide superior search effectiveness than big-document approaches. This first experiment empirically tests this belief, specifically in the context of topical shards. We also compare Exhaustive Search with Selective Search with bigdocument, and small-document approaches. The first three rows in Table 1 are the focus of this analysis.
As compared to Exhaustive Search, CORI and (7) µ)2
ReDDE, both struggle at deeper ranks. CORI, the big document approach, is consistently inferior to ReDDE, the small document approach, across all the metrics. In fact, at deeper ranks (R@100 and ndcg) the improvements over CORI, with ReDDE are statistically significant. These results confirm that the conventional unigram language model based shard ranking approach adopted by CORI struggles to differentiate the relevant shards from non-relevant shards. This is so even for topical shards where the distribution of relevant documents across shards is highly skewed. Also, note that CORI has access to the vocabulary of the complete collection whereas ReDDE is only using 0.5% subset of the collection for estimating the shard ranking. Thus CORI’s inferior performance is especially surprising. These observations motivate the experiment described next. 6.2
Our hypothesis that we test in this section is that for multi-term queries the unigram language model used by CORI severally misinforms the shard ranking estimation. This is especially true for multi-term queries which consist of phrase(s). For example, in the query, obama family tree, it is critically important to treat the terms family and tree as a phrase and not as unigrams. The results in rows 4 through 7 in Table 1 provide evidence in support of the above hypothesis. Rows 4 and 5 are results for 52 queries, all of which are singleton queries. Across all the metrics the search effectiveness with CORI is higher in magnitude than that with ReDDE, which is exactly the opposite trend seen with multi-term queries. These results establish that CORI’s subpar performance is restricted to multi-term queries. On the other hand ReDDE struggles more with singleton queries because estimation errors due to under-sampling are more likely when there is only one term in the query to inform the shard ranking. 6.3
CORI’s inferior performance with multi-term queries motivates the investigation in this section. The results with CORI and ReDDE when using this richer query representation are given in rows 8 and 9 of Table 1. These results show an opposite trend as that with unigram query representation (rows 2 and 3). The big-document approach (CORI Uni+Bi) performances better, although not significantly, than the small-document approach (ReDDE Uni+Bi). CORI clearly benefits more from the richer query representation than ReDDE. CORI Uni+Bi results are significantly better than those with CORI. This is not the case for ReDDE Uni+Bi. At early ranks, CORI Uni+Bi is significantly better than even Exhaustive Search. This indicates substantial reduction in false-positives in the retrieved documents at early ranks. This is facilitated by two factors:topic-based shards reduce the noise (false-positive matches) in each shard, and CORI Uni+Bi selects the shards such that the resulting search space is purer than that used by Exhaustive Search.
Although, not shown in the table, the results for multi-term queries show similar trends as before:- for all the metrics the magnitude of search effectiveness with CORI Uni+Bi is higher than with ReDDE Uni+Bi, and CORI Uni+Bi is significantly better than CORI. However, for ReDDE that is not the case. For singleton queries the results do not change because the richer query representation does not yield a different query. In summary, CORI Uni+Bi provides the best search effectiveness until now. In the next section we investigate if we can improve the performance further. 6.4
The last row in Table 1 reports the results with Learning to Rank Shards approach (LeToR-S). The first obvious trend in these results is that LeToR-S significantly outperforms the current best, CORI Uni+Bi, at deeper ranks. At early ranks, however, the two approaches provide comparable precision and recall. To understand these results better we analyze a few queries in detail.
For one of the queries, getting organized, CORI Uni+Bi ranks the shard with most number of relevant documents at 11th position, while LeToR-S ranks it at 3rd. This is a difficult query because both the query terms are common terms. Even when the terms are treated as a phrase, it is still not a focused query. This is reflected in the low scores assigned to relevant shards by CORI Uni+Bi. LeToR-S, however, uses metadata in addition to the document contents for defining the features. One particular meta-data feature, url field, proves to be especially valuable for this query that consists of common terms. Documents that contain getting organized in their field are relevant to the query. In turn, shards that contain such documents should be ranked higher too. In short, LeToR-S benefits from having the field score features, while CORI Uni+Bi suffers because it only uses document contents for shard ranking. A few more example queries that highlight the value of the field score features are battles in the civil war and kansas city mo. For both queries, CORI Uni+Bi ranks the most relevant shard at a much deeper rank than LeToR-S.
Another feature category that helps LeToR-S outperform CORI Uni+Bi is the CORI minimum score features. Recall that the CORI minimum score feature is lowest CORI score computed for the individual query terms against a shard. This feature models the intuition that all of the query terms should have high CORI score for a relevant shard. Low CORI score, even if only for one of the query terms, indicates less likelihood of shard relevance. For query, pacific northwest laboratory only one shard contains all the relevant documents, LeToR-S ranks this shard at 8th place, while CORI Uni+Bi ranks it at 11. Through the CORI minimum score feature, several falsepositive shards are eliminated by LeToR-S from the shard ranking. These false-positive shards have high overall CORI score because some of the query terms have high CORI score, and thus dominate the cumulative score. However, the CORI minimum score captures that some query terms have low CORI score for these false-positive shards and thus push them down in the shard ranking.
The results in Table 1 also indicate that at early ranks LeToR-S performs significantly better than Exhaustive Search. This improvement often but not always comes from single term queries that may have one than one meaning or aspect associated with them (euclid, avp, iron, unc). The topicbased partitioning of the collection organizes the documents with similar meaning or aspect into the same shard. Often one of the meanings is more dominant than others in the collection, that is also often the relevant meaning for the query. Shards with the dominant meaning have higher document frequency (df ) than shards with the rare meaning, and thus documents with dominant meaning only are searched. This reduces the false-positive documents (documents with rare meaning) from the result, and thus improves the search precision. 6.5
When comparing the best performing Selective Search approach, LeToR-S, with Exhaustive Search we see in Table 1 that at early ranks, LeToR-S performs at par or better than Exhaustive Search in precision and recall both. However, at deeper ranks, LeToR-S struggles on recall more than precision, which is indicated by the significantly lower ndcg value. Our hypothesis for the reason behind this trend is that LeToR-S is unable to retrieve all the shards containing relevant documents. In order to test this hypothesis we conduct the following experiment.
The effectiveness of shard ranking algorithm is dependent on the distribution of the relevant documents across shards. If all the relevant documents are concentrated in a few shards then the shard ranking task is straightforward, however if the relevant documents are spread across many shards then task is much more challenging for any shard ranker. Figure 1 provides the histogram of the spread of relevant documents for the 194 queries. For a large fraction of the queries (27) the spread of the relevant documents are restricted to 4 shards. 70% of the total queries have a spread of 7 or less. For the remaining 30% of the queries the relevant documents can be spread across as many as 31 shards, indicating that the topic-based sharding approach failed to concentrate the relevant documents into few shards for these queries. We are however interested in the 70% of the queries for which the spread of relevant documents is restricted to 7 shards. We believe that LeToR-S should be able to provide effective shard ranking for these subset of queries, which in turn should help improve both, precision and recall. To test this intuition we separate the 194 queries into two groups based on the spread cutoff of 7. This gives us one group of 133 queries for which the relevant documents are spread across 7 or fewer shards, and the other group contains 61 queries.
The results for the two query groups with the various search approaches are given in Tables 2 and 3. For the first group of queries (Table 2) LeToR-S (and also CORI Uni+Bi) provides statistically significant improvement over Exhaustive Search in precision at both, early and deep ranks. Furthermore these improvements in precision do not come at the cost of recall, the recall (at all ranks) with LeToR-S stays comparable to that with Exhaustive Search. Even ndcg with LeToR-S is not statistically different from that of Exhaustive Search. This is a rare phenomenon:- a search approach being able to balance precision and recall.
The results in Table 3 tell a different story. At deeper ranks, precision and recall, both suffer with all the Selective Search approaches. These results clearly establish the importance of concentrating the relevant documents into few shards. Doing so not only reduces the search cost but substantially
CORI Uni+Bi ReDDE Uni+Bi LeToR-S
CORI Uni+Bi
ReDDE Uni+Bi
LeToR-S
improves search precision without degrading the
recall.
For all the experiments until now we have held the
parameter, shard cutoff (T), constant at 10. That
is, for all the Selective Search experiments the top
10 shards, out of 92 shards, were searched for
each query. Changing this parameter directly
affects the cost of Selective Search, and it also
influences the search effectiveness. The influence
of this parameter in the general distributed search
seup has been extensively investigated by Markov
and Crestani
Table 4 provides the results for this analysis. At early ranks, LeToR-S performs on par with Exhaustive Search while searching just the top three shards. The corresponding search cost, approximated by A, is orders of magnitude lower for LeToR-S than for Exhaustive Search. When comparing LeToR-S with CORI Uni+Bi, the former consistently outperforms the latter at all the shard cutoff values. Even the search cost for LeToR-S are marginally lower than those with CORI Uni+Bi, indicating a bias toward smaller shards in case of LeToR-S.
As more shards are searched the recall at deeper ranks with LeToR-S becomes on par with Exhaustive. The analysis in the previous section demonstrated that LeToR-S becomes comparable to Exhaustive Search even on the ndcg metric if the spread of the relevant documents is restricted. The corresponding search cost of Selective Search approaches is at least an order of magnitude lower than that of Exhaustive Search. 7
Our goal for this work was to investigate ways to balance search precision and recall. Selective Search proved to be an effective search environment for this investigation, and focusing on the shard ranking problem to achieve this goal also proved to the correct choice. We revived an old shard selection approach, CORI, which supported competitive search performance when it was provided with richer query representation. We also introduced a novel shard ranking algorithm based on the well-established Learning-To-Ranking ap
A 50.22 0.561 0.560 1.672 1.666 2.773 2.768 3.874 3.869 5.513 5.510
Search Approach Exh CORI Uni-Bi LeToR-S CORI Uni-Bi LeToR-S CORI Uni-Bi LeToR-S CORI Uni-Bi LeToR-S CORI Uni+Bi LeToR-S 0.377¶ proach, which provided the best search precision while also sustaining the recall. A thorough analysis of the results showed that simply searching more shards does not necessarily increase search effectiveness. Instead the two factors that are critically important for Selective Search to successfully balance precision and recall are:- 1. partitioning the collection such that the relevant documents for the query are spread across less than 10% of the shards, and 2. to employ an effective shard ranking approach, like the ones proposed in this work.