US20100100563A1

Movatterモバイル変換

Info

Publication number: US20100100563A1
Application number: US12/581,859
Authority: US
Inventors: Francisco Corella; Karen Pomian Lewison
Original assignee: Individual
Current assignee: Pomian and Corella LLC
Priority date: 2008-10-18
Filing date: 2009-10-19
Publication date: 2010-04-22
Also published as: US9069854B2; US20100100836A1

Abstract

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.

Description

CROSS-REFERENCE TO RELATED APPLICATIONS

The subject matter of this application is related to the subject matter of U.S. Provisional Patent Applications No. 61/106,570, filed on Oct. 18, 2008, and No. 61/201,855, filed on Dec. 16, 2008, priority to which is claimed under 35 U.S.C. §119(e) and which are incorporated herein by reference.

The subject matter of this application is also related to the subject matter of a companion Non-Provisional patent application entitled “Facilitating Browsing of Result Sets”, by F. Corella and K. P. Lewison, filed simultaneously with this application and incorporated herein by reference.

BACKGROUND

In information retrieval, when a query submitted by a user fails (i.e. the query has an empty result set), it is beneficial to provide to the user a so-called cooperative response, or cooperative answer, to the query that provides additional information other than the fact that there are no results. Many kinds of cooperative answers, applicable to many kinds of information retrieval systems, have been proposed in the academic literature. For example, one approach proposed one type of cooperative answer to conjunctive queries, and another, broader type of cooperative answer to Boolean queries, applicable in the context of a bibliographic information retrieval system.

Today, all Web search engines accept conjunctive queries, and some accept Boolean queries, such that the cooperative answers proposed in the above-referenced approach are applicable in the context of Web search. A cooperative answer according to this approach consists of a collection of subqueries of the failed query submitted by the user, a subquery being a query obtained by removing syntactic elements from the submitted query, the subqueries in the collection being more general than the submitted query. The collection of subqueries comprises subqueries that fail like the submitted query (even though they are more general and thus less likely to fail than the submitted query), and subqueries that succeed (i.e. that have a non-empty result set). The subqueries that succeed are useful as possible follow-up queries. The subqueries that fail are useful because they avoid the repeated failures that would occur if the user submitted those subqueries, and because each of them is, in some sense, an explanation of the failure.

Recently, an important computational architecture has emerged for Web search engines. In this architecture, the search engine is split into two independent components, a front-end that runs on a client machine operated by a user and a back-end that runs on one or more server machines, the front-end being connected to the back-end via the Internet and accessing the back-end through an HTTP-based network interface called a Web application programming interface (Web API). The front-end provides a user interface, while the back-end provides a search index. In operation, the user submits a query through the user interface on the client machine, and the client machine forwards the query to the back-end which computes a result set using the index. The back-end provides pages of the result set of the query to the front-end, and the front-end displays those pages to the user.

Many search back-ends are available on the Web today, including back-ends provided by the companies that own the most popular search engines, Google, Yahoo, and Bing, those back-ends using the same indices that are used in those popular search engines. Many hundreds of search front-ends have been developed, resulting in the many hundreds of search engines that are available on the Web today.

This split search engine architecture has important advantages, but also has a disadvantage when it comes to providing cooperative answers. A Web API, because it is accessed via the Internet, has a high latency, usually of a few hundred milliseconds. Such a high latency makes it impractical to compute a cooperative answer by any of the methods that have been proposed so far, all of which assume that the cooperative answer is computed on the same machine where result sets are computed. A cooperative answer consists of many subqueries, and its computation requires interrogating the back-end through the API about those subqueries and many more subqueries that do not end up in the cooperative answer. Computing a cooperative answer by traditional methods can easily take 30 seconds or more, which is unacceptable to the user in a modern computing environment.

SUMMARY

In one embodiment, an information retrieval system is provided which includes 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.

BRIEF DESCRIPTION OF THE DRAWINGS

The accompanying drawings are included to provide a further understanding of embodiments and are incorporated in and constitute a part of this specification. The drawings illustrate embodiments and together with the description serve to explain principles of embodiments. Other embodiments and many of the intended advantages of embodiments will be readily appreciated as they become better understood by reference to the following detailed description. The elements of the drawings are not necessarily to scale relative to each other. Reference numerals consist of a concatenation of a one- or two-digit number referring to a figure, followed by a two-digit number that locates the referenced part within the figure. A reference numeral pertaining introduced in a figure may be used in other figures to refer to the same part or a similar part.

FIG. 1 is a block diagram generally illustrating an example of an information retrieval system for providing cooperative answers to zero-result queries through a high-latency API according to embodiments described herein.

FIG. 2 is a block diagram illustrating user-interface elements presented on a display according to one embodiment.

FIG. 3 is an example of a cooperative answer displayed in a left panel according to one embodiment.

FIG. 4 is an example of a cooperative answer to a query that uses a site restriction according to one embodiment.

FIG. 5 is an example of a cooperative answer comprised of queries with associated checkboxes according to one embodiment.

FIG. 6 is an illustration of the concept of a conjunction graph of a conjunctive query.

FIG. 7 is an illustration of the concept of a conjunction graph of a conjunctive query in which conjunction operators are omitted.

FIG. 8 is an illustration of the concept of a conjunction graph of a Boolean query in negation normal form.

FIG. 9 is a flow diagram illustrating a process followed by a search application to initiate a computation of a cooperative answer to a conjunctive query.

FIG. 10 is a flow diagram illustrating a process followed by a search application, while computing a cooperative answer to a conjunctive query, when a response is received from a back-end.

FIG. 11 is a flow diagram illustrating a process followed by a search application to initiate a computation of a cooperative answer to a Boolean query in negation normal form.

FIG. 12 is a flow diagram illustrating a process followed by a search application while computing a cooperative answer to a Boolean query in negation normal form when a response is received from a back-end.

DETAILED DESCRIPTION

In the following Detailed Description, reference is made to the accompanying drawings, which form a part hereof, and in which is shown by way of illustration specific embodiments in which the invention may be practiced. It is to be understood that other embodiments may be utilized and structural or logical changes may be made without departing from the scope of the present invention. The following detailed description, therefore, is not to be taken in a limiting sense. It is to be understood that the features of the various exemplary embodiments described herein may be combined with each other, unless specifically noted otherwise.

FIG. 1 is a block diagram generally illustrating an example of aninformation retrieval system100 for providing cooperative answers, or cooperative responses to zero-result queries through a high-latency API, using a method of computing cooperative answers, or cooperative responses, according to one embodiment, that makes it practical to provide such answers in spite of the high latency of the API.

The word “response” has several meanings in the context of a search. It can, for example, refer to a page of results presented to the user after the user submits a query, to a page of results and other information returned from a search back-end in response to a request made by a front-end, to a cooperative response that consists of a set of subqueries. To avoid confusion, the term “cooperative answer” is hereafter used in lieu of the term “cooperative response”

System100 includes acomputer110 operated by auser120, anetwork130, and a search back-end140 that hosts anindex150 into a collection of documents.Computer110 is equipped with adisplay112, akeyboard114, and amouse116, and includes astorage facility160. An executable program, called asearch application162, is stored instorage facility160 and runs oncomputer110.

Given a query,index150 defines the result set of the query, each result in the result set being a data item providing information about a document that matches the query, including a link to the document. In one embodiment the collection of documents is a collection of files reachable on the World Wide Web. In one embodiment, the collection of documents comprises a collection of documents on an intranet.

Search back-end140 is connected to thenetwork130 and exposes anetwork interface142 thatcomputer110 uses to communicate with search back-end140.Network interface142 is a logical specification of messages that can be sent to and received from search back-end140. For illustrative purposes,network interface142 is shown inFIG. 1 as what appears to be a physical component.

The latency ofnetwork interface142, relative tocomputer110, is the time it takes forcomputer110 to receive a response to a request made throughnetwork interface142, including any delay due tonetwork130. In one embodiment, where thenetwork130 is the Internet and the collection of documents indexed by theindex150 of search back-end140 is a substantial portion of the set of files reachable on the World Wide Web, the latency is typically a few hundred milliseconds, such latency being considered a high latency. Methods according to the present embodiments are especially beneficial in such high latency architectures.

In one embodiment,network interface142 exposed by search back-end140 uses Hypertext Transfer Protocol (HTTP) messages, such an interface being called an HTTP-based interface. In one such embodiment,network130 is the Internet; the HTTP-based interface is then called a Web interface, or a Web Application Programming Interface (Web API). In one embodiment, network30 is an intranet.

In one embodiment, wherenetwork130 is the Internet,storage facility160 contains aWeb browser program168 that runs oncomputer110, andsearch application162 is downloaded by aWeb browser168 from aWeb site170 connected to the Internet. In one embodiment,search application162 runs oncomputer110 by being interpreted by a browser extension (also known as a browser plug-in)180.

In one embodiment, the browser plug-in180 is supplied by Adobe Systems, Inc. and called Flash Player®, andsearch application162 is built on a programming platform also supplied by Adobe Systems, Inc. and called Flex®. In such an embodiment,search application162 comprises project code written in MXML and ActionScript and compiled by a platform compiler, and platform code supplied by Adobe Systems, Inc., some of which is linked with the project code. The project code is an event-driven program, comprising routines that are invoked when events take place. Such a routine is called an “event listener” or “event handler”, and is said to “handle” or “react to” the event upon which it is invoked.

Search application

162 usesdisplay112,keyboard114, andmouse116 ofcomputer110 to interact withuser120.Keyboard114 is used to enter text into input fields ofdisplay112.Mouse116 is used for performing user-interface procedures, such as clicking on a button.

Search application

162 usesnetwork interface142 to fetch data from search back-end140, including data such as:

(1) an estimate of the number of results in the result set of a query, called a “cardinality estimate” for the query; and

(2) a page of the result set of a query, pages being numbered, each page containing a fixed number of consecutive results (e.g. page 1 containingresults 1 through 10, page 2 containing results 11 through 20, etc.).

In one embodiment,search application162 fetches such information by making a request to search back-end140 vianetwork130. The request conforms to networkinterface142 and specifies the query, as well as a desired range of results from the result set of the query. The request elicits a response that fulfills the request. The response also conforms to the network interface. The response contains the cardinality estimate and, if the result set is not empty, the page of results. The cardinality estimate is accurate as to whether the result set is empty or not (i.e. if the estimate is zero the result set is empty and if the estimate is not zero the result set is not empty). A response with a zero estimate is said to be negative response, while a response with a non-zero estimate is said to be a positive response.

FIG. 2 illustrates an example ofdisplay112 being used bysearch application162 to present user-interface elements touser120, according to one embodiment. The user-interface elements include aninput field210, called a “query box” or “search box”, whereuser120 can enter a query, asearch button220 thatuser120 can click to submit the query, and three panels, aleft panel230, acenter panel240 and aright panel250. In one embodiment, these user-interface elements are presented inside awindow260 opened byWeb browser168 ondisplay112. In one embodiment,right panel250 is used to display advertisements.

In one embodiment,left panel230 contains a set of queries whose result sets can be browsed simultaneously incenter panel240, as disclosed in the above-referenced companion patent application. Whenuser120 submits a query, the submitted query and additional queries are placed inleft panel230. If the submitted query has an empty result set and satisfies conditions described in the above-referenced companion application (i.e. does not consist of a single search term and is not overly complex), the additional queries placed inleft panel230 are subqueries of the submitted query that constitute a cooperative answer to the query.

FIG. 3 shows an example of a cooperative answer displayed inleft panel230, according to one embodiment.Left panel230 contains aquery310 submitted byuser120 that has an empty result set, viz. the query “smoothie asdf qwer xyz13924”.Left panel230 also contains five subqueries of thequery310 that together constitute a cooperative answer to thequery310. The subqueries have fewer search terms than the query. They are therefore more general than the query, and have result sets that are supersets of the result set of the query.

The cooperative answer lists three subqueries that have non-empty result sets,

subqueries

320,330, and340, followed by two subqueries that have empty result sets,

subqueries

350 and360. Queries that have a non-empty result set are said to succeed and are called “succeeding subqueries”. Queries that have empty result sets are said to fail and are called “failing queries” or “zero-result queries”.

Succeeding subqueries are included in the cooperative answer because they are useful as possible follow-up queries. A succeeding subquery is included in the cooperative answer only if there is no succeeding subquery that is more specific (i.e. that has more search terms). For example, the succeeding subquery “smoothie” is not included because the succeedingsubquery320 “smoothie asdf” and thesubquery330 “smoothie qwer” are more specific succeeding subqueries.

Failing subqueries are also useful because they helpuser120 avoid repeated failures. For example, after the failure of thequery310 “smoothie asdf qwer xyz13924”,user120 may try “smoothie asdf qwer”, which also fails. This is avoided by the lettinguser120 know that this query, included in the response assubquery350, also fails even though it is more general than the submittedquery310. A failing subquery is included in the cooperative answer only if there is no failing subquery that is more general (i.e. that has fewer search terms). For example, the failing subquery “smoothie xyz13924” is not included because the failingsubquery360 “xyz13924” is more general.

Another reason why failing subqueries are useful is that they can be viewed as explanations of the failure of the submitted query. For example, thequery310 can be viewed as failing for two independent reasons: because there are no Web pages containing the words “smoothie”, “asdf” and “query”, and because there are no Web pages containing the word “xyz13924”.

A contrived example was used inFIG. 3 because few queries that target the Web at large and consist of a combination of a few dictionary words have empty result sets. Empty result sets, however, occur more frequently when queries target a subset of the Web, such as a particular Web site. In one embodiment, a query can be made to target a site by using a site restriction, which is a search term consisting of the operator “site:” immediately followed by the DNS domain of the site.

FIG. 4 shows an example of a cooperative answer to a query that uses a site restriction, according to one embodiment. Thequery410 “smoothie banana durian site:myrecipes.com” has an empty result set. The

subqueries

420,430, and440 of thequery410 constitute a cooperative answer to thequery410. Thesubquery420 informsuser120 that results for “smoothie banana query” can be found outside the targeted site, while thesubquery430 informsuser120 that results for “smoothie banana” can be found in the site; both are possible follow-up queries. Thesubquery440 informsuser120 that the word “durian” does not appear at all in the targeted site.

In one embodiment, a query can be made to target a particular site without using a site restriction, by specifying the DNS domain of the site in a separate input box.

FIG. 5 shows thesame query410 and the same cooperative

answer comprising subqueries

420,430,440, according to one embodiment, where every query inleft panel230 has an associated checkbox, as described in the above-referenced companion patent application.FIG. 5 shows the state ofpanel230 immediately afteruser120 has submitted thequery410. The

queries

410,420,430, and440 will be deleted fromleft panel230 whenuser120 submits a subsequent query, unlessuser120 removes a checkmark from a checkbox in order to retain the associated query.

Queries

510 and520 illustrate unrelated queries that were added earlier toleft panel230 and have been retained.

In one embodiment, a query is a Boolean expression consisting of the Boolean operators AND, OR, and NOT, and of search terms, with spaces used to separate syntactic elements and parentheses used for grouping, such a query being called a Boolean query. A search term can be a word or a phrase surrounded by double quotes. In one embodiment, a search term can be a colon expression, which begins with an operator consisting of a keyword followed by a colon. An example of a colon expression is the site restriction used above in the example ofFIG. 4, which uses the operator “site:” consisting of the keyword “site” followed by a colon.

A Boolean query is said to be a conjunction, or a conjunctive query, if its operator with broadest scope, called the top-level operator, is the conjunction operator AND. It is said to be a disjunction, or a disjunctive query, if its top-level operator is the disjunction operator OR. It is said to be a negation if its top-level operator is the negation operator NOT. Since AND and OR are associative operators, parentheses can be omitted without ambiguity around an inner conjunction that is an operand of an outer conjunction, and around an inner disjunction that is an operand of an outer disjunction.

The conjuncts of a conjunctive query can be defined as follows: remove all unnecessary parentheses, then consider the sequence of top-level AND operators as an n-ary conjunction; the conjuncts are then the operands of the n-ary conjunction. Consider for example the expression “asdf AND (qwer AND (xyz OR (abc AND def)))”. It has an unnecessary pair of parentheses. After removing the unnecessary parentheses it becomes “asdf AND qwer AND (xyz OR (abc AND def))”. This can be viewed as a ternary conjunction with operands “asdf”, “qwer” and “xyz OR (abc AND def)”. Those three operands are the conjuncts of the conjunction.

The disjuncts of a disjunctive query are defined in the same way as the conjuncts of a conjunctive query, mutatis mutandis.

Given a conjunctive query, a “conjunctive subquery” of the query is obtained by removing one or more conjuncts from the query, an “immediate conjunctive subquery” being obtained by removing exactly one conjunct. For example, “asdf AND poiu” is an immediate conjunctive subquery of “asdf AND qwer AND poiu”, obtained by removing the middle conjunct “qwer”; and “poiu” is a conjunctive subquery obtained by removing the first two conjuncts.

It should be observed that, whereas in the phrase “conjunctive query” the word “conjunctive” refers to the contents of the query, in the phrase “conjunctive subquery” the word “conjunctive” refers to how the subquery is derived from a query that contains it. Thus, a conjunctive subquery is not necessarily a conjunctive query. For example, “poiu” is a conjunctive subquery of “asdf AND qwer AND poiu” but it is not a conjunctive query (i.e. it is not a conjunction), since it consists of a single search term.

A conjunctive query defines a graph whose nodes are the query and its conjunctive subqueries. There is an edge between a first node and a second node if the second node is an immediate conjunctive subquery of the first node; the first node is then said to be a parent of the second node, and the second node a child of the first node.

As an example,FIG. 6 shows theconjunction graph600 of the query “asdf AND qwer AND (xyz OR (abc AND def))”. Thetop node610 is the query itself.

Nodes

620,630, and640 are the immediate conjunctive subqueries of the query, each obtained by removing one of the conjuncts of the query.

Nodes

650,660, and670 are conjunctive subqueries of the query obtained by removing two conjuncts.

Nodes

650,660, and670 are also the conjuncts of the conjunctive query. The lines in the Figure represent the edges of the graph. There is anedge680, for example, betweennode640 andnode660, because thequery660 “(xyz OR (abc AND def)” is an immediate conjunctive subquery of thequery640 “qwer AND (xyz OR (abc AND def))”.Node660 is a child ofnode640, andnode640 is a parent ofnode660.

In one embodiment, the conjunction operator can be omitted, so that juxtaposition is interpreted as conjunction. For example, the query “asdf qwer poiu” is a conjunctive query with implicit conjunction operators, logically equivalent to the query “asdf AND qwer AND poiu” where the conjunction operators are explicit. In one embodiment, no explicit Boolean operators are recognized by the parser, and therefore every query consists either of one search term, or of a sequence of search terms interpreted as a conjunction.FIG. 7 shows theconjunction graph700 of the conjunctive query “asdf qwer poiu” with implicit conjunction operators.

A Boolean expression, and in particular a Boolean query, is said to be in negation normal form if it contains no negated conjunctions or disjunctions (i.e. if the negation operator NOT only occurs in the query applied to atomic Boolean expressions). Every Boolean expression can be put in negation normal form using De Morgan's laws.

The concept of a “conjunction graph” can be extended to apply to a query in negation normal form, as follows. If the query is a single search term or a negation, the graph has a single node, which is the query itself. If the query is a conjunction, the conjunction graph is as defined before. If the query is a disjunction, the nodes of the graph are the disjuncts of the disjunction, as well as the conjunctive subqueries of any disjuncts that are conjunctions. It should be noted that a node can be a conjunctive subquery of multiple disjuncts. The edges of the graph and the concepts of “parent” and “child” are defined as before. A root is a node that has no parents. If the query is a search term, a negation, or a conjunction, it has a single root; but if it is a disjunction, each disjunct is a root.

The conjunction graph of a disjunction is a subgraph of the conjunction graph of the conjunction obtained by combining the conjuncts of all the disjuncts, which will be referred to as the extended conjunction graph of the query.

As an example,FIG. 8 shows the conjunction graph and the extended conjunction graph of the Boolean query:

- (asdf AND qwer AND (xyz OR (abc AND def))) OR
- (asdf AND (NOT poiu) AND (xyz OR (abc AND def))),
  which is in negation normal form. Dashed rounded boxes indicate nodes that are part of the extended graph but not of the non-extended graph. The query has two disjuncts, which are theroots810 and820 of the non-extended graph. Nodes such asnode830 which are not part of the non-extended conjunction graph are deemed not to be of interest touser120 and are excluded from a cooperative answer to the query.

In one embodiment, whensearch application162 provides a cooperative answer to a Boolean query having an empty result set, the cooperative answer consists of the most general nodes in the conjunction graph of the negation normal form of the query that have an empty result set, and the most specific nodes in the same graph that have a non-empty result set. As a special case, if the query is a conjunctive query, the cooperative answer consists of the most general conjunctive subqueries of the query that have an empty result set, and the most specific ones that have a non-empty result set.

FIGS. 9 and 10 illustrate two processes used bysearch application162 to perform a method of providing a cooperative answer to a conjunctive query submitted byuser120 that has an empty result set. To compute the cooperative answer,search application162 makes requests to search back-end140 through thenetwork interface142. Each request specifies a query that is a conjunctive subquery of the submitted query, and produces a response that includes a cardinality estimate for the specified query.

Search application

162 makes sets of requests in parallel. A set of requests is made in parallel, by definition, if each request is made without waiting for responses to previous requests to be received. By making use of parallel requests, the present implementation is able to reduce the delay that would be caused by multiple serial interactions with the network interface. In one embodiment, where the latency ofnetwork interface142 with respect to thecomputer110, including the latency due tonetwork130, is a few hundred milliseconds, experiments show that the present implementation is able to provide a cooperative answer in only a few seconds for queries that necessitate interactions withnetwork interface142 that would take 30 seconds or more if done serially.

Search application

162 uses a first counter to keep track of the number of requests that have been made since the beginning of the computation, and a second counter to keep track of the number of responses that have been received. The first counter is called the “counter of requests made” and the second counter is called the “counter of responses received. The value of the first counter minus the value of the second counter is equal to the number of pending requests. The computation ends when the number of pending requests is equal to zero. The two counters are kept in thestorage facility160.

Search application

162 constructs in storage facility160 a list of zero-result queries that it uses to collect failing conjunctive subqueries of the submitted query during the computation. At the end of the computation, the list of zero-result queries contains the most general failing conjunctive subqueries of the submitted query.

In the descriptions ofFIGS. 9 and 10, the meaning of the terms “parent” and “child” is relative to the conjunction graph of the submitted query.

FIG. 9 is a flow diagram generally illustrating one embodiment of aprocess900 employed bysearch application162 to initiate the computation of a cooperative answer to a conjunctive query submitted byuser120. At910,search application162 creates an empty list of zero-result queries and proceeds to920.

At920,search application162 initializes the counter of responses received, setting the value of the counter to zero, and then proceeds to930. At930,search application162 makes an initial set of requests to search back-end140, the initial set of requests consisting of requests specifying queries that are children of the submitted query, one such request for each child, and initializes the counter of requests made to the number of such requests.

FIG. 10 is a flow diagram generally illustrating one embodiment of aprocess1000 employed bysearch application162 when a response is received, the response fulfilling a request. At1010,search application162 increments the counter of responses received and proceeds to1020. At1020,search application162 checks if the cardinality estimate contained in the response is zero. If so,search application162 proceeds to1030. Otherwise,search application162 proceeds to1050.

At1030,search application162 removes from the list of zero-result queries any query subsumed by the query specified by the fulfilled request. A query in the list is subsumed by the specified query if the specified query is a conjunctive subquery of the query in the list, and therefore is more general than the query in the list.Search application162 then proceeds to1040.

At1040,search application162 makes a subsequent set of requests and increments accordingly the counter of requests made, the requests specifying queries that are children of the query specified by the fulfilled request, the set consisting of one such request for each child whose parents have all failed.Search application162 then proceeds to1060.

In one embodiment,search application162 tests whether the parents of a node have all failed by keeping a count of the number of times that a request specifying the node has been fulfilled and checking whether the count is equal to the number of parents of the node. In another embodiment,search application162 tests such condition by remembering what nodes have failed.

At1050,search application162 displays the query specified by the fulfilled request, together with the cardinality estimate contained in the response, in theleft panel230, and then proceeds to1060. At1060,search application162 checks whether the number of requests made equals the number of responses received according to the respective counters. If so,search application162 proceeds to1070. Otherwise, theprocess1000 terminates. At1070,search application162 displays in theleft panel230 the queries contained in the list of zero-result queries, each with a cardinality estimate of zero.

FIGS. 11 and 12 are flow diagrams generally illustrating two processes used bysearch application162 to perform a method of providing a cooperative answer to a Boolean query submitted byuser120 that has an empty result set. The method is an extension of the method of providing a cooperative answer to a conjunctive query illustrated byFIGS. 9 and 10. As before,search application162 makes sets of requests to search back-end140 in parallel, uses a counter of requests made and a counter of responses received, and builds a list of zero-result queries.

FIG. 11 is a flow diagram generally illustrating one embodiment of aprocess1100 employed bysearch application162 to initiate the computation of a cooperative response to the Boolean query submitted byuser120. At1110,search application162 puts the Boolean query in negation normal form and proceeds to1120.

At1120,search application162 creates an empty list of zero-result queries, and then proceeds to1130. At1130,search application162 initializes the counter of responses received, setting the value of the counter to zero, and then proceeds to1140. At1140,search application162 makes an initial set of requests to search back-end140, consisting of requests specifying queries that are children of the roots of the conjunction graph of the negation normal form of the submitted query, one such request for each child, and initializes the counter of requests made to the number of such requests.

FIG. 12 is a flow diagram generally illustrating one embodiment of aprocess1200 employed bysearch application162 when a response is received, the response fulfilling a request. The description of the process is not repeated here because as it is substantially similar to the description of corresponding portions ofprocess1000, except at1240, which differs from1040.

At1240,search application162 makes a subsequent set of requests and increments accordingly the counter of requests made, the requests specifying queries that are children of the query specified by the fulfilled request, the set consisting of one such request for each child whose parents in the conjunction graph of the negation normal form have all failed.

In one embodiment,search application162 tests whether the parents of a node have all failed by remembering what nodes have failed. It is noted that when enumerating the parents to check if they have all failed, care must be taken to avoid the error of including parents of the node in the extended graph that are not parents of the node in the non-extended graph.

In summary, the embodiments described enable the computation of cooperative answers through any high-latency API in a much shorter period of time than is possible with traditional methods. One important case of a high-latency API is a Web API. Embodiments that utilize a Web API make it practical to provide cooperative answers in a split search engine architecture. However, in a addition to Web APIs, the teachings of the present embodiments may be applied to anytype of high-latency API, such as network interfaces based on protocols other than HTTP (e.g. LDAP, and interfaces that are not necessarily accessed across a network, such as database interfaces). Furthermore, although time savings provided by the present embodiments increase with the API latency, time savings can be realized for any latency and, thus, the benefits of the present embodiments can be realized in embodiments that utilize any API.

According to one embodiment, the teachings of the browsing techniques described by the companion application cross-referenced above so that result sets of the queries that comprise a cooperative answer can be browsed simultaneously, or in an interleaved fashion.

Although specific embodiments have been illustrated and described herein, it will be appreciated by those of ordinary skill in the art that a variety of alternate and/or equivalent implementations may be substituted for the specific embodiments shown and described without departing from the scope of the present invention. This application is intended to cover any adaptations or variations of the specific embodiments discussed herein.