Utilizing dependency among internet search results

Techniques, systems, and articles of manufacture for utilizing dependency among internet search results. A method includes associating a user search query with a search task, identifying multiple information documents that correspond to the search task, and generating a recommended sequence of the multiple information documents to present to the user in response to the user search query, wherein the recommended sequence is based on dependency information associated with the multiple information documents.

FIELD OF THE INVENTION

Embodiments of the invention generally relate to information technology, and, more particularly, to internet searching technologies.

BACKGROUND

Existing internet searching systems and approaches attempt to optimize the click-through rate for a single given user query, wherein a click-through rate refers to a measure of the number of result links clicked and/or selected in response to a given query. However, such existing searching approaches do not include consideration of a task-completion rate. In many cases, a user query is part of a larger task that requires accessing information from multiple documents and/or sources, potentially in a certain sequential order. The order and/or the correlation of the information, though, are not exploited by existing approaches and therefore, are never presented to the user. As a result, the users of such systems and approaches are encouraged and/or required to specify atomic requirements in the query. Additionally, existing approaches require a user attempting to execute a larger task to submit multiple independent queries to accomplish the task.

Accordingly, a need exists for discovering dependency among task-related search results and presenting resulting information to the user.

SUMMARY

In one aspect of the present invention, techniques for utilizing dependency among internet search results are provided. An exemplary computer-implemented method can include steps of associating a user search query with a search task, identifying multiple information documents that correspond to the search task, and generating a recommended sequence of the multiple information documents to present to the user in response to the user search query, wherein the recommended sequence is based on dependency information associated with the multiple information documents.

In another aspect of the invention, an exemplary computer-implemented method can include steps of receiving a user search query, associating the user search query with a search task, and identifying multiple information documents that correspond to the search task. The method also includes the steps of determining dependency of information among the multiple information documents based on information pertaining to one or more previous user searches associated with the multiple information documents, and generating a recommended sequence of the multiple information documents to present to the user in response to the user search query, wherein the recommended sequence is based on dependency information associated with the multiple information documents.

Another aspect of the invention or elements thereof can be implemented in the form of an article of manufacture tangibly embodying computer readable instructions which, when implemented, cause a computer to carry out a plurality of method steps, as described herein. Furthermore, another aspect of the invention or elements thereof can be implemented in the form of an apparatus including a memory and at least one processor that is coupled to the memory and configured to perform noted method steps. Yet further, another aspect of the invention or elements thereof can be implemented in the form of means for carrying out the method steps described herein, or elements thereof; the means can include hardware module(s) or a combination of hardware and software modules, wherein the software modules are stored in a tangible computer-readable storage medium (or multiple such media).

DETAILED DESCRIPTION

As described herein, an aspect of the present invention includes presenting and exploiting dependency among search results. At least one embodiment of the invention includes discovering associations between various search-related tasks and user search queries. Such associations can be discovered between indexed documents based on previous browsing history of the user and one or more additional users and/or dependency information explicitly or implicitly marked in the search documents.

When a new user query arrives, at least one embodiment of the invention includes generating and considering multiple task hypotheses with corresponding probabilities P(Task=T|query=q). These probabilities represent the likelihood of a given query belonging to a task, and such estimates are derived based on prior search history. For each such hypothesized task, a recommended order of information sources is derived based on previous user browsing histories.

Subsequently, at least one embodiment of the invention includes providing these tasks along with the determined dependency information and/or recommended order of documents to the user. The dependency information constitutes the dependency of one search result on another, and is used to determine the recommended order of documents or search results. Such dependency information illustrates whether the viewing of a document or search result requires reading or viewing another document as a prerequisite to accomplishing a task. The dependency information, accordingly, is also a function of the hypothesized task.

FIG. 1is a diagram illustrating an example system100implementing an embodiment of the invention. As described herein, at least one embodiment of the invention can include offline and online components. It should also be noted that at least one embodiment of the invention can be implemented entirely online. Accordingly, the following description should be understood merely as one exemplary means of implementing an embodiment of the invention.

As such, for example, as part of the offline component, at least one embodiment of the invention includes discovering and exploiting dependency of information documents from multiple databases via dependency determination module110. This can be denoted, for example, via P(D2|D1). Such a probability measures the dependency of D2on D1. In other words, the probability represents how important it is to go through or access the contents of D1before proceeding to the contents of D2. Here, in this detailed example, D2and D1are two indexed documents. The discovery of dependency information can ultimately facilitate generation of a recommended ordering of information documents in connection with a given search task, as further described herein.

Additionally, as depicted inFIG. 1, databases such as referenced above can include, for example, a database112maintaining previous user queries and session logs, a database114maintaining click-through logs, a database116maintaining outbound links present in various information documents, a database118maintaining case documentation (for example, in the case of call centers), and a database120maintaining procedural information corresponding to multiple information documents.

Databases112and118, for example, can be used to compute task probability, given a user query, denoted by P(task|query). Database114, for example, can be used to compute the probability of a given document being relevant, given a user query and a task, denoted by P(D|query, task). Databases116and120can be used to compute the explicit document dependency denoted by P(D2|D1). Additionally, given a user query q, a hypothesized task T and an already-shown document D1, the probability of a document D2being dependent on D1can be computed as P(D2|D1, q)=P(T|q)*P(D2|q, T)*P(D2|D1). P(task|query) is described further herein.

Further, as part of the offline component, at least one embodiment of the invention includes determining, via query association module104, an association between user queries, provided via a user interface such as102, and one or more search tasks maintained in database106. This can be denoted, for example, via P(Task=T|query=q). This is useful because a query can belong to multiple tasks. This can be computed, for example, as the ratio of the number of times query=q appears in Task=T (obtained from Databases112and118), and the number of times query=q appears overall. The search task (or tasks) determined to be associated with a user query can be provided to and/or applied to the dependency determination module110to identify various information documents and/or categories of information documents derived from the above-noted dependency analysis among the multiple databases.

As part of the online component, given a user query q (such as submitted via user interface102), at least one embodiment of the invention includes utilizing one or more metrics (such as detailed herein) for generating a recommended and/or optimal sequence of information documents via dependency recommendation module122based additionally on the dependency analysis carried out via dependency determination module110.

For instance, the search task T determined to be associated with the query q and applied to the dependency determination module110(as noted above), may identify two information documents or two types or categories of information documents (Diand Dj) that correspond (historically) to this search task. Accordingly, as carried out via the dependency recommendation module122, the relevance of the document Dito the query q can be represented as P(Di|q). This can be computed, for example, as the ratio of the total number of times document Diwas shown and clicked in response to a given query q based on the information stored in the database114. The relevance of the query q to the task T can be represented as P(T|q). Further, the dependency of the document Dito document Dj, which, as noted, is also relevant to the query context provided by the task T, can be represented as P(Di|Dj, T). Additionally, at least one embodiment of the invention includes determining and presenting a set of possibilities P(Task=T|query=q), each corresponding to one possible task (Tj).

Accordingly, as detailed herein, for each such potential task T, a recommended and/or optimized order of documents is generated and presented to the user (that is, the user that submitted the query q), via user interface102, for example, by which the user can efficiently consult the information provided in the noted documents. In the offline computation, P(D2|D1) can be computed based on databases116and120. P(Task|query) can also be computed in offline mode. In the online portion of the processing, P(D2|D1, query, T) can be computed as P(Task|query)*P(D2|query T)*P(D2|D1), where P(D2|D1) and P(Task|query) have been computed in the offline portion.

By way of illustration of one or more embodiments of the invention, consider the following example scenario. A query is submitted that states “Travelling to Thailand.” Such a query may return results covering aspects such as foreign regulations and/or travel advice, visa requirements, hotel reviews, things to do in Thailand, weather in Thailand, etc. Accordingly, at least one embodiment of the invention includes determining that this query is related to accomplishing the larger task of identifying and/or compiling a variety of information pertaining to travelling to Thailand and determining and/or identifying information from multiple sources that are to be exploited and/or leveraged to present results (from these multiple sources) to the user in a recommended order.

As described herein, the recommended order of information documents can be derived and/or determined from previous browsing histories of users' previously submitted queries similar or related to the stated “Travelling to Thailand” query provided by the current user. For example, one previous browsing history corresponding to a query for “end-to-end planning of a trip to Thailand” might be associated with a stored ordering of information document results as follows: Advice for tourists in Thailand→Visa information→Tickets→Hotels in Thailand→Things to do in Thailand→Weather in Thailand. A second previous browsing history corresponding to a query for “things to do in Thailand” might be associated with a stored ordering of information document results as follows: Amusements in Thailand→Events in Thailand→Places to stay in Thailand→Restaurants in Thailand. Further, a third previous browsing history corresponding to a query for “health and weather advice in Thailand” might be associated with a stored ordering of information document results as follows: Thailand travel advice→Recent health hazards in Thailand→Weather forecast in Thailand.

Based, for instance, on previous browsing histories such as these, one example ordering may be presented as follows: Travel advice→Visa requirements→Download and submit application→Ticketing→Hotel reviews and booking→Things to do in Thailand→Climate in Thailand→Pictures of Thailand, etc.

FIG. 2is a flow diagram illustrating techniques according to an embodiment of the present invention. Step202includes associating a user search query with a search task. At least one embodiment of the invention can additionally include receiving the user search query via a user interface.

Step204includes identifying multiple information documents that correspond to the search task. Identifying multiple information documents that correspond to the search task can be based on one or more previous user search histories.

Step206includes generating a recommended sequence of the multiple information documents to present to the user in response to the user search query, wherein the recommended sequence is based on dependency information associated with the multiple information documents. Dependency information can include context-dependent information pertaining to the multiple information documents derived from one or more previous user search histories.

Additionally, as described herein, generating the recommended sequence can include executing one or more metrics. For example, this can include determining a measure of relevance of each of the multiple information documents to the user search query. This can also include determining a measure of relevance of the user search query to the search task, as well as determining a measure of relevance of each of the multiple information documents to each of one or more other documents from the multiple information documents.

The techniques depicted inFIG. 2can additionally include determining an association between multiple search queries and one or more search tasks, wherein each said association is maintained in a database. Further, the techniques depicted inFIG. 2can include displaying the recommended sequence of the multiple information documents to the user. Also, at least one embodiment of the invention includes generating a set of multiple recommended sequences of the multiple information documents.

FIG. 3is a flow diagram illustrating techniques according to an embodiment of the invention. Step302includes receiving a user search query (for example, via a user interface). Step304includes associating the user search query with a search task. Step306includes identifying multiple information documents that correspond to the search task.

Step308includes determining dependency of information among the multiple information documents based on information pertaining to one or more previous user searches associated with the multiple information documents. Information pertaining to one or more previous user searches associated with the multiple information documents can include, for example, one or more previous user queries and corresponding session logs, one or more click-through logs, one or more outbound links present in the multiple information documents, case documentation information, and procedural information corresponding to the multiple information documents.

Additionally, step310includes generating a recommended sequence of the multiple information documents to present to the user in response to the user search query, wherein the recommended sequence is based on dependency information associated with the multiple information documents. Further, the techniques depicted inFIG. 3can include displaying the recommended sequence of the multiple information documents to the user.

A data processing system suitable for storing and/or executing program code will include at least one processor402coupled directly or indirectly to memory elements404through a system bus410. The memory elements can include local memory employed during actual implementation of the program code, bulk storage, and cache memories which provide temporary storage of at least some program code in order to reduce the number of times code must be retrieved from bulk storage during implementation.

Input/output or I/O devices (including but not limited to keyboards408, displays406, pointing devices, and the like) can be coupled to the system either directly (such as via bus410) or through intervening I/O controllers (omitted for clarity).

Program code embodied on a computer readable medium may be transmitted using an appropriate medium, including but not limited to wireless, wireline, optical fiber cable, radio frequency (RF), etc., or any suitable combination of the foregoing.

These computer program instructions may also be stored in a computer readable medium that can direct a computer, other programmable data processing apparatus, or other devices to function in a particular manner, such that the instructions stored in the computer readable medium produce an article of manufacture including instructions which implement the function/act specified in the flowchart and/or block diagram block or blocks. Accordingly, an aspect of the invention includes an article of manufacture tangibly embodying computer readable instructions which, when implemented, cause a computer to carry out a plurality of method steps as described herein.

At least one aspect of the present invention may provide a beneficial effect such as, for example, exploiting dependency and ordering among search results.