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-queryRETRIEVAL 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 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 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