Login| Sign Up| Help| Contact|

Patent Searching and Data


Title:
OBTAINING USER PREFERENCES FOR QUERY RESULTS
Document Type and Number:
WIPO Patent Application WO/2008/083208
Kind Code:
A1
Abstract:
One embodiment of the present invention provides a system that obtains user preferences for query results. First, in response to a query, the system presents a ranked list of query results to a user. The system then receives a request from the user to change the position of a query result in the ranked list of query results. Based on the change in position of the query result, the system infers at least one preference of the user between the query result and other query results in the ranked list.

Inventors:
BOSTOCK MICHAEL (US)
Application Number:
PCT/US2007/088917
Publication Date:
July 10, 2008
Filing Date:
December 27, 2007
Export Citation:
Click for automatic bibliography generation   Help
Assignee:
GOOGLE INC (US)
BOSTOCK MICHAEL (US)
International Classes:
G06F17/30
Foreign References:
US20060004711A12006-01-05
US20030055831A12003-03-20
US20060074864A12006-04-06
Attorney, Agent or Firm:
PARK, A. Richard (Davis, CA, US)
Download PDF:
Claims:
What Is Claimed Is:

1. A method for obtaining user preferences for query results, comprising: in response to a query, presenting a ranked list of query results to a user; receiving a request from the user to change the position of a query result in the ranked list of query results; and inferring at least one preference of the user between the query result and other query results in the ranked list based on the change in position of the query result.

2. The method of claim 1, wherein the change of position defines a partial ordering for the ranked list of query results.

3. The method of claim 1 , wherein the method further involves recording user preferences on a per-user and/or a per-query basis.

4. The method of claim 3, wherein the method further involves using the recorded user preferences to rank future query results.

5. The method of claim 4, wherein information describing the position change request is sent to a server.

6. The method of claim 1 , wherein receiving the request to change the position of the query result involves receiving a command from the user to change the position of a graphical icon representing the query result in a ranked list of graphical icons representing query results; and wherein the command is received through a pointing device, such as a mouse.

7. The method of claim 1 , wherein the method further involves aggregating user preferences for one or more users and/or queries.

8. The method of claim 7, wherein aggregating user preferences involves gathering and aggregating user preferences to determine rules for ranking query results.

9. The method of claim 1 , wherein the method further comprises dynamically reordering the ranked list of query results based on the position change request.

10. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for obtaining user preferences for query results, the method comprising: in response to a query, presenting a ranked list of query results to a user; receiving a request from the user to change the position of a query result in the ranked list of query results; and inferring at least one preference of the user between the query result and other query results in the ranked list based on the change in position of the query result.

11. The computer-readable storage medium of claim 10, wherein the change of position defines a partial ordering for the ranked list of query results.

12. The computer-readable storage medium of claim 10, wherein the method further involves recording user preferences on a per-user and/or a per-query basis.

13. The computer-readable storage medium of claim 12, wherein the method further involves using the recorded user preferences to rank future query results.

14. The computer-readable storage medium of claim 13, wherein information describing the position change request is sent to a server.

15. The computer-readable storage medium of claim 10, wherein receiving the request to change the position of the query result involves receiving a command from the user to change the position of a graphical icon representing the query result in a ranked list of graphical icons representing query results; and wherein the command is received through a pointing device, such as a mouse.

16. The computer-readable storage medium of claim 10, wherein the method further involves aggregating user preferences for one or more users and/or queries.

17. The computer-readable storage medium of claim 16, wherein aggregating user preferences involves gathering and aggregating user preferences to determine rules for ranking query results.

18. The computer-readable storage medium of claim 10, wherein the method further comprises dynamically reordering the ranked list of query results based on the position change request.

19. An apparatus that obtains user preferences for query results, comprising: a display mechanism, wherein the display mechanism is configured to present a ranked list of query results to a user in response to a query; a receiving mechanism configured to receive a request from the user to change the position of a query result in the ranked list of query results; and a determining mechanism configured to infer at least one preference of the user between the query result and other query results in the ranked list based on the change in position of the query result.

20. The apparatus of claim 19, wherein the change of position defines a partial ordering for the ranked list of query results.

Description:

OBTAINING USER PREFERENCES FOR QUERY

RESULTS

Inventor: Michael C. Bostock

BACKGROUND

Field of the Invention

[0001] The present invention relates to techniques for gathering user preference data. More specifically, the present invention relates to obtaining user preferences for query results by analyzing user interactions with a set of query results. Related Art [0002] The relentless growth of the Internet has been largely fueled by the development of sophisticated search engines, which enable users to comb through billions of web pages looking for specific pages of interest. Because a given query can return millions of search results it is important to be able to rank these search results to present the highest- quality results to the user. [0003] It is extremely difficult if not impossible to measure the quality of results directly. Early techniques for ranking results considered intrinsic properties of each candidate result document, including how recently the document was updated, and/or how close the search terms are to the beginning of the document. Another technique considers an extrinsic property, the back-links for linked documents. However, these techniques are based on properties that are under authorial control, and do not necessarily indicate the direct preferences of users. It is desirable to obtain a more direct measurement of search result quality from users themselves. However, it is difficult to obtain such measurements from users.

[0004] Hence, what is needed is a method and an apparatus for accurately ranking search results based on user preferences,

SUMMARY

[0005] One embodiment of the present invention provides a system that obtains user preferences for query results. First, in response to a query, the system presents a ranked list of query results to a user. The system then receives a request from the user to change the position of a query result in the ranked list of query results. Based on the change in position of the query result, the system infers at least one preference of the user between the query result and other query results in the ranked list.

[0006] In a variation on this embodiment, the change of position defines a partial ordering for the ranked list of query results. [0007] In a variation on this embodiment, the system records user preferences on a per-user and/or per-query basis.

[0008] In a further variation, the system uses the recorded user preferences to rank future query results.

[0009] In a further variation, information describing the position change request is sent to a server.

[0010] In a variation on this embodiment, the position change request is a command received from the user to change the position of a graphical icon representing the query result in a ranked list of graphical icons representing query results. In a further variation, this command is received via a pointing device, such as a mouse. [0011] In a variation on this embodiment, the system aggregates user preferences for one or more users and/or queries.

[0012] In a further variation, the system gathers and aggregates user preferences to determine rules for ranking query results.

[0013] In a variation on this embodiment, the system dynamically reorders the ranked list of query results based on the position change request.

BRIEF DESCRIPTION OF THE FIGURES

[0014] FIG. 1 illustrates the crawling, ranking and searching processes in accordance with an embodiment of the present invention. [0015] FIG. 2A illustrates a web page that displays a search field and search results in accordance with an embodiment of the present invention.

[0016] FIG. 2B illustrates the process of reordering a search result in a web page in accordance with an embodiment of the present invention.

[0017] FIG. 2C illustrates a reordered result in an updated list of search results in accordance with an embodiment of the present invention. [0018] FIG. 3A illustrates partial orderings that result when a list is reordered in accordance with an embodiment of the present invention.

[0019] FIG. 3B illustrates a new result which is inserted into a reordered list of search results in accordance with an embodiment of the present invention.

[0020] FIG. 3C illustrates a changed ranking for two search results in a reordered list of search results in accordance with an embodiment of the present invention.

[0021] FIG. 4 presents a flow chart illustrating the process of using reordering of search results to obtain user preferences in accordance with an embodiment of the present invention.

[0022] FIG. 5 presents a flow chart illustrating the process of leveraging user preferences to adjust search result rankings in accordance with an embodiment of the present invention.

DETAILED DESCRIPTION

[0023] The following description is presented to enable any person skilled in the art to make and use the invention, and is provided in the context of a particular application and its requirements. Various modifications to the disclosed embodiments will be readily apparent to those skilled in the art, and the general principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the present invention. Thus, the present invention is not limited to the embodiments shown, but is to be accorded the widest scope consistent with the claims.

[0024] The data structures and code described in this detailed description are typically stored on a computer-readable storage medium, which may be any device or medium that can store code and/or data for use by a computer system. This includes, but is not limited to, volatile memory, non-volatile memory, magnetic and optical storage devices such as disk drives, magnetic tape, CDs (compact discs), DVDs (digital versatile discs or digital video discs), or other media capable of storing computer readable media now known or later developed.

Crawling Ranking and Searching Processes

[0025] FIG. 1 illustrates the crawling, ranking and searching processes. During the crawling process, a web crawler 104 crawls or otherwise searches through websites on web 102 to select web pages to be stored in indexed form in data center 108. The selected web pages are then compressed, indexed and ranked in module 105 (using the ranking process described above) before being stored in data center 108.

[0026] During a subsequent search process, a search engine 112 receives a query 113 from a user 111 through a web browser 114. This query 113 specifies a number of terms to be searched for in the set of documents. In response to query 113, search engine 112 uses search terms specified in the query to identify highly-ranked documents that satisfy the query. Search engine 112 then returns a response 115 through web browser 114, wherein the response 115 includes a list of matching pages along with ranking information and references to the identified pages. [0027] FIG. 2A illustrates a web page that displays a search field 202 and search results 204 in web browser 114. After a user enters one or more search terms into search field 202 (e.g. suppose the user enters the query "user interface" in search field 202), the system performs a search operation and displays the list of search results 204 for the query. The user can then browse through the search results 204 to determine whether or not they include the desired information.

Gathering User Preferences Via Reordered Search Results

[0028] One embodiment of the present invention provides a system that allows users to reorder search results, and gathers user preference data based on the users' reordering of search results. Gathering such preference data directly from users, when possible, can provide more accurate preference data than other approaches, such as predicting user preferences based on the content of selected pages.

[0029] FIG. 2B illustrates the process of reordering a search result in a web page. During this process, a user can, for instance, select a search result using a mouse, and can then drag the selected result 206 up or down in the list of search results. FIG. 2C illustrates the reordered result 208 in the updated list of search results. By re-ordering results, a user provides constrained input about whether a certain result is better and/or worse than one or more other results. Note that reordering a search result does not necessarily imply that the

user has visited the page for the search result. For instance, the user may have decided to reorder search results before visiting them based on the information presented in the list (such as a universal resource locator (URL) or a representative data snippet displayed in the list).

[0030] In one embodiment of the present invention, the system records partial orderings based on reordered search results to improve rankings which are used to generate personalized search results. A partial ordering is an ordering relation for a set that specifies a preferred precedence for some pairs of items in the set, but might not specify the preferred precedence for all pairs in the set. The system can determine a partial ordering from both direct and implied preferences indicated by user reorderings. [0031] FIG. 3A illustrates a partial ordering that is created when a result in an initial list 300 is reordered, thereby forming a reordered list 302. For instance, by moving the item 'D' up in the initial list 300, a user implies that 'D' is more relevant than both 'B' and 'C. This reordering also strongly implies that 'A' is more relevant than 'D', since if the reverse were true, the user would have reordered the list placing 'D' above 'A' as well. [0032] Note that the system can also gather preference data implied by results that are not reordered. For instance, for the example in FIG. 3 A, reordering 'D' in the list as shown might also imply that a user is satisfied with the existing ordering of 'A', 'B', and 'C. However, because this is a passive observation rather than an active reflection of user preferences, the system may weigh such implied preferences more lightly than explicit user preferences (such as those described in relation to 'D' in this example).

[0033] Note also that reordering a search result is a stronger statement of preference than selecting ("clicking") a result in a list of search results. For example, a user may not see a page without clicking on it, and so a click does not necessarily correspond to a good result. While selecting a search result, a user may not know the content of the result, and might merely be selecting the result in order to evaluate the contents of the result. Hence, passive observation techniques such as click-tracking are noisy and often difficult to interpret. A reordering operation, on the other hand, is more likely to indicate that a user prefers one result more or less than other results, and hence directly indicates preferences between search results. [0034] Note also that examining reorderings of search results has benefits over other techniques for gathering user preference data, such as tracking when a user saves, blocks, or marks ("stars") a result. For instance, the system can preserve the specified preferences

implied by the reordering while updating search results located above, below, and between the reordered results. For example, if the user performs the same query in a later timeframe, and the system finds a higher-ranked result 304, 'E', the system can insert 'E' at the top of the list of search results while simultaneously preserving the user preference detected from the reordering 306 (as shown in FIG. 3B). Alternatively, if the relative ranks of 'C and 'B' change, the system can update their rank 308 in the list while maintaining the partial ordering that ranks 'D' higher than both 'C and 'B' (as shown in FIG. 3C).

[0035] A reordering system that directly benefits the user by improving search results is more likely to be used than other direct solicitation techniques, such as satisfaction surveys. The system described in the present invention can also overcome problems with other preference-gathering techniques such as: low response rates; being difficult for users to understand; and being difficult to aggregate into a ranking, because users vary greatly in the degree and direction of their opinions.

[0036] FIG. 4 presents a flow chart illustrating the process of using reorderings of search results to obtain user preferences. First, the system presents an initial ranking of search results to a user in response to a query (step 400). Next, the system receives a result selection event from the user (step 402), along with a new position for the selected result (step 404). The system then updates the list of results (step 406), and determines preferences based on the reordering (step 408). [0037] In one embodiment of the present invention, the system typically expects a sequence of reorderings. For instance, rather than moving just a single search result, users may perform a number of reorderings on a given list. Hence, after updating the list of results (step 406) or determining partial preference data for an individual reordering (step 408), the process may include looping back (returning to step 402) to receive and handle one or more additional reorderings. While the system can gather preference data from individual or partial sequences of reorderings, the user's preferences may not be fully known until all of the reorderings are completed. Typically, the more reorderings the system receives, the more confident the system can be in the implied preference data.

[0038] In one embodiment of the present invention, preference data is used to evaluate and/or improve the ranking of search results. Ranking systems often use machine- learning techniques to boost search results based on a set of input signals. The system can analyze user preference data to identify signals from web pages that indicate a higher (or

lower) page ranking. Any number of signals for web pages can be correlated based on such user preference data, with the system then using such correlations to train a set of machine- learning techniques. For instance, after a user searches for the name of a music artist (e.g., [britney spears]), they might reorder the results so that a result corresponding to an entry in an online, collaborative encyclopedia ranks higher than a result corresponding to an official fan site directly maintained by the artist. Machine-learning techniques can detect patterns and trends based on such reorderings.

[0039] FIG. 5 presents a flow chart illustrating the process of leveraging user preferences to adjust search result rankings. During operation, the system collects user preference data (step 500). In a user-localized approach, the system may adjust the rankings for future search results on a per-user basis based on the user preference data for each individual user (step 502). Alternatively, in an aggregating approach, the system aggregates user preference data to find correlations (step 504). The system then proceeds to adjust a set of machine-learning techniques based on correlations from these aggregated results (step 506), and then ranks future search results based on these adjusted machine-learning techniques (step 508).

[0040] By allowing users to reorder search results, the system in the present invention can collect user preference data from the user population at large, thereby providing a scalable source of training data for machine-learning techniques and improving the ranking of user search results both on an individual and/or aggregate scale. For instance, on the scale of an individual user, the system may keep a set of results fixed (with respect to rankings) for an individual user to maintain preferences specified by that user. Alternatively (e.g. in the previously-mentioned search for the name of a music artist), the preferences of users can be aggregated either within the context of the original query, or across queries. For example, if users often reorder results from the online, collaborative encyclopedia to have a higher rank than other results, the machine-learning system might infer that results from the online, collaborative encyclopedia should be ranked highly for all queries, or perhaps for other queries that are deemed similar.

[0041] In one embodiment of the present invention, the system extrapolates preference rankings for the user from the preference data derived from reorderings, and then uses these preference rankings to perform a user-directed, personalized search. During this process, the system can maintain state on a per-user and/or per-query basis, and, based on the

user input, can infer that the user is seeking a particular interpretation of the search results and that the user has a preference for a certain type of search result. The system attempts to preserve partial orderings, but also infers from the results that were not reordered that there may be a better result ordering that is more consistent with the user's desired results. For instance, after a user reorders a first set of results, the system may change characteristics

(such as the ranking or ordering) for a second set of results, based on the preferences derived from the reordering of the first set of results. By providing customized dynamic reordering of user search results, the system allows users to subtly influence the type and ordering of results at a finer granularity than directly changing the query terms. [0042] In one embodiment of the present invention, the system aggregates preference data derived from a set of user reorderings to change the preference rankings for search results. By aggregating user preferences across all users, the system can determine an ordering that satisfies the majority of users. For instance, the system may analyze correlations between signals based on user preferences, in order to identify and generalize properties of web pages that indicate more highly-desirable search results for users.

[0043] Note that the system may weigh preferences differently for a given reordering. For instance, preference data for the reordering may be applied in the scope of a single query and/or single user, or may be extrapolated to: all queries for a user; all users for the same query; or all users for all queries. [0044] In one embodiment of the present invention, the web browser 114 sends back reordering information to a server, such as the search engine 112 and/or the data center 108. For instance, the system can send back an "insert" event that specifies the search result that was moved, as well as the destination for the search result. The server can then start with the set of initial results and play back the events to determine partial orderings. [0045] In one embodiment of the present invention, the ability to reorder search results can be an invisible user interface feature. This technique does not add additional fields to the list of search results, but instead adds additional capabilities to an existing display of search results. Users who are aware of the feature and wish to give feedback via reordering can do so, while the system does not add any additional cost or overhead to users who are unaware of the feature and/or do not want to use the feature. Alternatively, the ability to reorder search results can also be included as a visible user interface feature, in order to make the feature more easily discoverable by prospective users.

[0046] Although the present invention is described in the context of ranking web pages, note that the technique is not limited to web pages. In general, the present invention can be applied to many different ranking domains, such as images, documents, products, advertisements, video clips, audio clips and any other items that users can compare. [0047] Note that the present invention gathers preference data in a manner that is not under authorial control, and is hence less vulnerable to "spamming" techniques. Unlike techniques that rank results based on properties under the control of page authors (e.g., the latest update time, the location of search terms in the document, or the back-links for linked documents), the technique described in the present invention collects preferences from users directly. This provides a more direct measurement of the quality of the page, and may allow the search engine to return results in an order that more closely matches the collective opinion of users, rather than page authors.

[0048] In summary, one embodiment of the present invention provides a system that allows users to reorder search results, and then gathers user preference data based on user reordering of search results. Gathering such preference data directly from users provides a clearer set of preferences than other approaches, such as predicting user preferences based on the content of selected pages. Statistics gathered from such reorderings can be used to improve the search process and the quality of search results.

[0049] The foregoing descriptions of embodiments of the present invention have been presented only for purposes of illustration and description. They are not intended to be exhaustive or to limit the present invention to the forms disclosed. Accordingly, many modifications and variations will be apparent to practitioners skilled in the art. Additionally, the above disclosure is not intended to limit the present invention. The scope of the present invention is defined by the appended claims.