METHOD OF COMPUTING A COOPERATIVE ANSWER TO A ZERO-RESULT QUERY THROUGH A HIGH LATENCY API
An information retrieval system including a user operated computer having a display and a storage facility, a search back-end containing an index into a collection of documents, the index defining results sets of queries relative to the collection of documents, and a search application stored in the storage facility which is executable by the computer to perform a method of providing a cooperative answer to a query submitted by the user, the submitted query having an empty result set, the cooperative answer comprising subqueries of the submitted query and, for each subquery, cardinality information indicative of whether the subquery has an empty result set. The method includes making an initial set of requests to the search back-end, a request specifying a query and calling for a response that provides cardinality information indicative of whether the subquery has an empty result set, the response being said to be positive if the result set is non-empty and negative if the result set is empty, the requests in the initial set of requests being made in parallel and specifying queries that are subqueries of the submitted query. When a positive response to a request is received, the method includes displaying the query specified by the request together with cardinality information provided by the response which enables the user to determine that the result set of the specified query is not empty, the specified query and the cardinality information being part of the cooperative answer. When a negative response to a request is received, the method includes making a subsequent set of requests to the search back-end, the requests being made in parallel and specifying queries that are subqueries of the query specified by the request for which the negative response is received.
1 . An information retrieval system comprising:
a computer operated by a user, the computer having a display and a storage facility;
a search back-end containing an index into a collection of documents, the index defining results sets of queries relative to the collection of documents; and
a search application stored in the storage facility which is executable by the computer to perform a method of providing a cooperative answer to a query submitted by the user, the submitted query having an empty result set, the cooperative answer comprising subqueries of the submitted query and, for each subquery, cardinality information indicative of whether the subquery has an empty result set, the method comprising:
making an initial set of requests to the search back-end, a request specifying a query and calling for a response that provides cardinality information indicative of whether the subquery has an empty result set, the response being said to be positive if the result set is non-empty and negative if the result set is empty, the requests in the initial set of requests being made in parallel and specifying queries that are subqueries of the submitted query;
when a positive response to a request is received, displaying the query specified by the request together with cardinality information provided by the response which enables the user to determine that the result set of the specified query is not empty, the specified query and the cardinality information being part of the cooperative answer; and
when a negative response to a request is received, making a subsequent set of requests to the search back-end, the requests being made in parallel and specifying queries that are subqueries of the query specified by the request for which the negative response is received.
2 . The system of claim 1 , wherein the computer is connected to the search back-end via a network and the search application uses a network interface exposed by the search back-end to make requests to the search back-end and obtain responses.
3 . The system of claim 2 wherein the network interface comprises an HTTP-based interface.
4 . The system of claim 3 , wherein the network is the Internet.
5 . The system of claim 4 , wherein the collection of documents comprises a collection of files reachable on the World Wide Web.
6 . A method of providing a cooperative answer to a query submitted by a user to an information retrieval system, the submitted query having an empty result set, the cooperative answer comprising subqueries of the submitted query and, for each subquery, cardinality information indicative of whether the subquery has an empty result set, the information retrieval system comprising a computer operated by the user, the computer having a display, the method comprising:
making an initial set of requests to a search back-end, each request specifying a query and calling for a response that provides cardinality information indicative of whether the subquery has an empty result set, the response being said to be positive if the result set is non-empty, and the response being said to be negative and the query said to have failed and to be a failing query if the result set is empty, the requests in the initial set of requests being made in parallel and specifying queries that are subqueries of the submitted query;
when a positive response to a request is received, displaying the query specified by the request together with cardinality information provided by the response which enables the user to determine that the result set of the specified query is not empty, the specified query and the cardinality information being part of the cooperative answer; and
when a negative response to a request is received, making a subsequent set of requests to the search back-end, the requests being made in parallel and specifying queries that are subqueries of the query specified by the request for which the negative response is received.
7 . The method of claim 6 , wherein the submitted query is a conjunctive query and the queries specified by the initial set of requests are children of the submitted query in a conjunction graph of the submitted query.
8 . The method of claim 7 , wherein the queries specified by the subsequent set of requests made when the response is a negative response, which is a response to a request that specifies a failing query, are those nodes of a conjunction graph of the submitted query that are children of the failing query and whose parents have all failed.
9 . The method of claim 8 , further comprising:
creating an empty list of zero-result queries before making the initial set of requests;
when a negative response is received, the negative response being a response to a request that specifies a failing query, removing from the list of zero-result queries every query subsumed by the failing query, then adding the failing query to the list; and
when there are no pending requests and all requests in initial and subsequent sets of requests having been fulfilled, displaying the zero-result queries contained in the list together with cardinality information that enables the user to determine that every such displayed query has an empty result set, the queries thus displayed and the cardinality information being part of the cooperative answer.
10 . The method of claim 9 , wherein, when a positive response to a request is received, the cardinality information provided by the response and displayed together with the query specified by the request is an estimate of the number of results in the result set of the query.
11 . A method of providing a cooperative answer to a Boolean query submitted by a user to an information retrieval system, the submitted query having an empty result set, the cooperative answer comprising subqueries of a negation normal form of the submitted query and, for each subquery, cardinality information indicative of whether the subquery has an empty result set, the system comprising a computer operated by the user, the computer having a display, the method comprising:
making an initial set of requests to a search back-end, a request specifying a query and calling for a response that provides cardinality information indicative of whether the subquery has an empty result set, the response being said to be positive if the result set is non-empty and negative if the result set is empty, the requests in the initial set of requests being made in parallel and specifying queries that are subqueries of a negation normal form of the submitted query;
when a positive response to a request is received, displaying the query specified by the request together with cardinality information provided by the response which enables the user to determine that the result set of the specified query is not empty, the specified query and the cardinality information being part of the cooperative answer; and
when a negative response to a request is received, making a subsequent set of requests to the search back-end, the requests being made in parallel and specifying queries that are subqueries of the query specified by the request for which the negative response is received.
12 . The method of claim 11 , wherein the specified queries of the initial set of requests are those nodes of a conjunction graph of a negation normal form of the submitted query that are children of nodes that are roots of the graph.
13 . The method of claim 12 , wherein the specified queries of the subsequent set of requests made when the response is a negative response, which is a response to a request that specifies a failing query, are those nodes of a conjunction graph of a negation normal form of the submitted query that are children of the failing query and whose parents have all failed.
14 . The method of claim 13 , further comprising:
creating an empty list of zero-result queries before making the initial set of requests;
when a negative response is received, the negative response being a response to a request that specifies a failing query, removing from the list of zero-result queries every query subsumed by the failing query, then adding the failing query to the list; and
when there are no pending requests and all requests in initial and subsequent sets of requests having been fulfilled, displaying the zero-result queries contained in the list together with cardinality information that enables the user to determine that every such displayed query has an empty result set, the queries thus displayed and the cardinality information being part of the cooperative answer.
15 . The method of claim 14 , wherein, when a positive response to a request is received, the cardinality information provided by the response and displayed together with the query specified by the request is an estimate of the number of results in the result set of the query.
16 . A computer readable storage medium storing computer executable instructions for controlling a computing device to perform a method of providing a cooperative answer to a query submitted by a user via a computing device to a search back-end containing an index into a collection of documents and defining result sets of queries relative to the collection of documents, the method comprising:
making an initial set of requests to the search back-end, a request specifying a query and calling for a response that provides cardinality information indicative of whether the subquery has an empty result set, the response being said to be positive if the result set is non-empty and negative if the result set is empty, the requests in the initial set of requests being made in parallel and specifying queries that are subqueries of the submitted query;
when a positive response to a request is received, displaying the query specified by the request together with cardinality information provided by the response which enables the user to determine that the result set of the specified query is not empty, the specified query and the cardinality information being part of the cooperative answer; and
when a negative response to a request is received, making a subsequent set of requests to the search back-end, the requests being made in parallel and specifying queries that are subqueries of the query specified by the request for which the negative response is received.
17 . The computer readable storage medium of claim 16 , wherein the computing device is connected to the search back-end via a network and the search application uses a network interface exposed by the search back-end to make requests to the search back-end and obtain responses.
18 . The computer readable storage medium of claim 17 , wherein the network interface comprises an HTTP-based interface.
19 . The computer readable storage medium of claim 18 , wherein the network is the Internet.
20 . The computer readable storage medium of claim 19 , wherein the collection of documents comprises a collection of files reachable on the World Wide Web.