324 DAVID MCSHERRY the user's initial query. A more detailed account of the recommenda tion process in Front Case is given in Section 5 As we show in the following theorem, whether or not a given sub query of a failing query Q is successful can be inferred from the recovery set for Q Lemma 1: Any sub-query Q1 of a successful query Q2 is also a suc- cessful query Proof: Any case that satisfies all the constraints in Q2 must also satisfy all the constraints in Q1 Theorem 1: A given sub-query @* of a failing query e is a successful query if and only if there exists goErs(Q) such that Q* is a sub-query of o Proof: If there exists QE rs(@) such that @* is a sub-query of Q°, then Q*isas by Lemma l Suppose now that Q is a successful sub-query of 0, and let @o be a successful sub-query of maximum length among the successful sub-queries of @(including Q* itself) of which Q* is a sub-query. Clearly Q is a maximally suc- cessful sub-query of @. We have established as required the existence ofQ∈rs(Q) such that Q* is a sub- query of g° Though also an important result in its own right, Theorem I con- firms our claim that the recovery set for a failing query e covers all possible sets of compromises that the user might be prepared to con- sider without knowing the extent of the compromises involved. Sup pose the user is prepared to consider the compromises associated with a successful sub-query @" that is not included in the recovery set for e. By Theorem l, the that Q* is a sub-query of o. As the set of compromises associated with Q must be a subset of the compromises associated with Q*, it is reasonable to assume that the user would never select Q" in pref erence to g. Moreover, it can easily be shown that the recovery set is the smallest set of successful relaxations that covers all possible sets of compromises in this way. Our algorithm for finding all maximally successful sub-queries of a failing query, called Relax, is shown in Figure 2. Sub-Queries is a list f all sub-queries, in order of decreasing query length, of a query Q for which a retrieval failure has occurred. For each sub-query e1 for which there is a matching case in the case library, Relax adds Q1 to
324 DAVID MCSHERRY the user’s initial query. A more detailed account of the recommendation process in Front Case is given in Section 5. As we show in the following theorem, whether or not a given subquery of a failing query Q is successful can be inferred from the recovery set for Q. Lemma 1: Any sub-query Q1 of a successful query Q2 is also a successful query. Proof: Any case that satisfies all the constraints in Q2 must also satisfy all the constraints in Q1. Theorem 1: A given sub-query Q∗ of a failing query Q is a successful query if and only if there exists Q◦ ∈rs(Q) such that Q∗ is a sub-query of Q◦. Proof: If there exists Q◦ ∈ rs(Q) such that Q∗ is a sub-query of Q◦, then Q∗ is a successful query by Lemma 1. Suppose now that Q∗ is a successful sub-query of Q, and let Q◦ be a successful sub-query of maximum length among the successful sub-queries of Q (including Q∗ itself) of which Q∗ is a sub-query. Clearly Q◦ is a maximally successful sub-query of Q. We have established as required the existence of Q◦ ∈ rs(Q) such that Q∗ is a sub-query of Q◦. Though also an important result in its own right, Theorem 1 con- firms our claim that the recovery set for a failing query Q covers all possible sets of compromises that the user might be prepared to consider without knowing the extent of the compromises involved. Suppose the user is prepared to consider the compromises associated with a successful sub-query Q∗ that is not included in the recovery set for Q. By Theorem 1, the recovery set includes a sub-query Q◦ such that Q∗ is a sub-query of Q◦. As the set of compromises associated with Q◦ must be a subset of the compromises associated with Q∗, it is reasonable to assume that the user would never select Q∗ in preference to Q◦. Moreover, it can easily be shown that the recovery set is the smallest set of successful relaxations that covers all possible sets of compromises in this way. Our algorithm for finding all maximally successful sub-queries of a failing query, called Relax, is shown in Figure 2. Sub-Queries is a list of all sub-queries, in order of decreasing query length, of a query Q for which a retrieval failure has occurred. For each sub-query Q1 for which there is a matching case in the case library, Relax adds Q1 to
RETRIEVAL FAILURE AND RECOVERY IN RECOMMENDER SYSTEMS 325 algorithm Relax(o, Subqueries) RS←φ while Subqueries>0 d Q1←fmst( SubQueries) Deletions∈-{g if @1 is a successful query RS UO1 for all O2E rest(Sub queries)do if @2 is a sub-query of 21 then Deletions Deletions U(023 Subqueries < SubQueries-Deletions return rs Figure 2. Algorithm for finding all maximally successful sub-queries of a given query. the recovery set and deletes any sub-query Q2 which is a sub-query of Q from the remaining list of candidate sub-queries 3. Recovery Set Size Cognitive load is an important consideration in any approach to recovery from retrieval failure. Showing the user only the maximally successful sub-queries of her query helps to reduce cognitive load in our approach, but for longer queries there may be several such sub queries In the following theorem, we establish an upper bound for the number of maximally successful sub-queries, and hence the size of the recovery set in our approach Lemma 2: For any failing query Q and distinct sub-queries 01, Q rs(2), @I is not a sub-query of 22. Proof: By definition of rs(@), there can be no successful sub-query of Q of which @1 is a proper sub-query
RETRIEVAL FAILURE AND RECOVERY IN RECOMMENDER SYSTEMS 325 Figure 2. Algorithm for finding all maximally successful sub-queries of a given query. the recovery set and deletes any sub-query Q2 which is a sub-query of Q1 from the remaining list of candidate sub-queries. 3. Recovery Set Size Cognitive load is an important consideration in any approach to recovery from retrieval failure. Showing the user only the maximally successful sub-queries of her query helps to reduce cognitive load in our approach, but for longer queries there may be several such subqueries. In the following theorem, we establish an upper bound for the number of maximally successful sub-queries, and hence the size of the recovery set in our approach. Lemma 2: For any failing query Q and distinct sub-queries Q1, Q2 ∈ rs(Q), Q1 is not a sub-query of Q2. Proof: By definition of rs(Q), there can be no successful sub-query of Q of which Q1 is a proper sub-query