Source: http://patents.com/us-9495460.html
Timestamp: 2019-01-23 09:14:30
Document Index: 200910930

Matched Legal Cases: ['Application No. 10781247', 'Application No. 201080023853', 'Application No. 201080023853', 'Application No. 201080023853', 'Application No. 201080023853', 'Application No. 2011148231', 'Application No. 2012513274', 'Application No. 201080023853', 'Application No. 2011148231', 'Application No. 2012', 'Application No. 201102944', 'Application No. 2944', 'Application No. 215753', 'Application No. 2011148231', 'Application No. 201102944', 'Application No. 201102944', 'Application No. 215753']

US Patent # 9,495,460. Merging search results - Patents.com
United States Patent 9,495,460
Taylor , et al. November 15, 2016
Taylor; Michael J. (Cambridge, GB), Radlinski; Filiip (Cambridge, GB), Shokouhi; Milad (Cambridge, GB)
Radlinski; Filiip
Shokouhi; Milad
Family ID: 1000002231041
12/473,158
US 20100306213 A1 Dec 2, 2010
6185534 February 2001 Breese et al.
6665653 December 2003 Heckerman et al.
7346613 March 2008 Hurst-Hiller et al.
8032535 October 2011 Strehl et al.
2002/0052880 May 2002 Fruensgaard et al.
2004/0215607 October 2004 Travis, Jr.
2005/0071465 March 2005 Zeng et al.
2005/0163302 July 2005 Mock et al.
2005/0251437 November 2005 Meuleman
2007/0106688 May 2007 Chang et al.
2007/0208730 September 2007 Agichtein et al.
2007/0276812 November 2007 Rosen
2008/0005090 January 2008 Khan et al.
2008/0040316 February 2008 Lawrence
2008/0077558 March 2008 Lawrence et al.
2008/0082625 April 2008 Karaoguz et al.
2008/0091650 April 2008 Fontoura et al.
2008/0104140 May 2008 Vierich et al.
2008/0215553 September 2008 Badros et al.
2008/0256036 October 2008 Falk et al.
2009/0144244 June 2009 Maghoul et al.
2009/0172730 July 2009 Schiff et al.
2009/0287645 November 2009 Dasdan et al.
2010/0070486 March 2010 Punaganti Venkata et al.
2010/0174704 July 2010 Ciravegna et al.
2010/0228804 September 2010 Dasgupta et al.
2010/0299367 November 2010 Chakrabarti et al.
2011/0040741 February 2011 Korte et al.
2011/0145234 June 2011 Hu
2012/0005200 January 2012 Lawrence
2012/0226675 September 2012 Dexter et al.
H0756948 Mar 1995 JP
H11-110406 Apr 1999 JP
H11-184862 Jul 1999 JP
2001142908 May 2001 JP
2002032401 Jan 2002 JP
2004094813 Mar 2004 JP
2004530195 Sep 2004 JP
2005032193 Feb 2005 JP
2006155043 Jun 2006 JP
2006524871 Nov 2006 JP
2008217600 Sep 2008 JP
2009015552 Jan 2009 JP
10-2006-0017502 Feb 2006 KR
2343537 Jan 2009 RU
02073864 Sep 2002 WO
03019420 Mar 2003 WO
PCT International Search Report dated Jan. 3, 2011 from corresponding PCT International Application No. PCT/US2010/036487, filed May 27, 2010, 4 pages. cited by applicant .
Drake, "New Ovid Universal Search Reaches Out to Web Databases", retrieved from the internet at http://newsbreaks.infotoday.com/nbReader.asp?ArticleId=51182. cited by applicant .
"Exalead Desktop Portal Edition", retrived from the Internet at http://www.exalead.com/software/common/pdfs/products/desktop-search/Exale- ad-Desktop-Search-White-Label-Edition.pdf. cited by applicant .
Hawking, "Challenges in Enterprise Search", Australian Computer Societ, 2004, appeared in 15th Australian Database Conference (ADC2004) Dunedin, NZ, retrieved from the Internet at http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.4.5854&rep=rep1&- type=pdf. cited by applicant .
Radlinski, et al., "How Does Clickthrough Data Reflect Retrieval Quality?" Proceedings of the 17th ACM Conference on Information and Knowledge Management, Oct. 26-30, 2008, Napa Valley, CA. cited by applicant .
Teevan, et al., "Discovering and Using Groups to Improve Personalized Search", WSDM'09, Feb. 9-12, 2009, Barcelona, Spain, retrieved from the internet at http://research.microsoft.com/pubs/76827/wsdm09-groupization.pdf. cited by applicant .
"Universal Search", retrieved from the internet at http://www.prepfire.com/16.html. cited by applicant .
<<http://www.google.com/enterprise/universal.sub.--search.html>&g- t;, archived on Jan. 21, 2009, retrieved from <<http://web.archive.org/web/20090121152414/http://google.com/enter- prise/universal.sub.--search.html>> on Dec. 20, 2011, 2 pages. cited by applicant .
<< http://code.google.com/p/relatedwebresults/ >>, archived on Oct. 25, 2008, retrieved from <<http://web.archive.org/web/20081025105235/http://code.google.com/- p/relatedwebresults/>> on Dec. 20, 2011, 1 page. cited by applicant .
Thomas, Server characterisation and selection for personal metasearch, a thesis submitted for the degree of Doctor of Philosophy of the Australian National University, May 2008, 221 pages. cited by applicant .
Extended European Search Report dated Dec. 10, 2012 for European Application No. 10781247.1, 7 pages. cited by applicant .
Keyhanipour et al. "Aggregation of web search engines based on users' preferences in WebFusion", Knowledge-Based Systems, Elsevier, vol. 20, No. 4, Apr. 13, 2007, pp. 321-328. cited by applicant .
"Fifth Office Action Issued in Chinese Patent Application No. 201080023853.7", Mailed Date: Aug. 7, 2014, 14 Pages. cited by applicant .
"Fourth Office Action Issued in Chinese Patent Application No. 201080023853.7", Mailed Date: Apr. 23, 2014, 12 Pages. cited by applicant .
"Second Office Action Issued in Chinese Patent Application No. 201080023853.7", Mailed Date: Sep. 10, 2013, 15 Pages. cited by applicant .
"Third Office Action Issued in Chinese Patent Application No. 201080023853.7", Mailed Date: Jan. 22, 2014, 12 Pages. cited by applicant .
"Office Action Issued in Russian Patent Application No. 2011148231", Mailed Date: Jun. 25, 2014, 5 Pages. cited by applicant .
"Office Action Issued in Japanese Patent Application No. 2012513274", Mailed Date: Jan. 28, 2014, 4 Pages. cited by applicant .
"Office Action Issued in Chinese Patent Application No. 201080023853.7", Mailed Date: Jan. 15, 2015, 13 Pages. cited by applicant .
"Notice of Allowance Issued in Russian Patent Application No. 2011148231", Mailed Date: Nov. 24, 2014, 11 Pages. (Without English Translation). cited by applicant .
"Office Action Issued in Japanese Patent Application No. 2012-513274", Mailed Date: Jan. 6, 2015, 4 Pages. cited by applicant .
"Office Action Issued in Chile Patent Application No. 201102944", Mailed Date: Oct. 13, 2014, 6 Pages. (Without English Translation). cited by applicant .
"Office Action Issued in Chile Patent Application No. 2944-2011", Mailed Date: Apr. 7, 2015, 6 Pages. (Without English Translation). cited by applicant .
"Office Action Issued in Israel Patent Application No. 215753", Mailed Date: May 3, 2015, 3 Pages. (Without English Translation). cited by applicant .
"Notice of Allowance Issued in Russian Patent Application No. 2011148231", Mailed Date: Nov. 20, 2014, 11 Pages. (Without English Translation). cited by applicant .
"Office Action Issued in Chilean Patent Application No. 201102944", Mailed Date: Oct. 13, 2014, 6 Pages. (Without English Translation). cited by applicant .
"Office Action Issued in Chilean Patent Application No. 201102944", Mailed Date: Apr. 7, 2015, 6 Pages. (Without English Translation). cited by applicant .
"Office Action Issued in Israel Patent Application No. 215753", Mailed Date: Aug. 16, 2015, 8 Pages. cited by applicant.
Attorney, Agent or Firm: Wong; Tom Minhas; Micky Zete Law, P.L.L.C.
1. A method at an information retrieval system arranged to retrieve results from a plurality of different sources comprising: at an input, receiving a query; at an output, issuing the query to the plurality of different sources, at least one of which is a public domain search engine and at least one of which is a private domain search engine; at the input, receiving a results list from each of the plurality of different sources; determining whether to merge said results lists based on a relevancy determination made using a merging model; forming, by a processor, a complete results list from the received results lists using the merging model, forming the complete results list comprising forming a merged results list using a merging model in a data structure comprising a plurality of weighted event variables describing a complete results list presentation event, the merging model comprising a decision process that determines whether or not to merge results based on the relevance of the results, the decision process deciding to not merge results when a difference between a first measure of relevance of a first set of results and a second measure of relevance of a second set of results satisfies a threshold condition; arranging a user interface to present the complete results list; observing user behavior in response to the presented complete results list; and using the observed user behavior to update the merging model.
8. A method as claimed in claim 1, which further comprises: receiving a user input specifying a change to the plurality of different sources; updating the complete results list according to the change; and arranging the user interface to present the updated complete results list.
9. A method as claimed in claim 1, which further comprises: receiving a user input specifying an impersonating user condition; storing the merging model using a data structure comprising a plurality of event variables including an impersonating user event variable; and updating the merging model to a higher degree than for observed user behavior where no impersonating user condition applies.
10. A method as claimed in claim 1, wherein the query is received from a user, and wherein the method further comprises: receiving user information for that user; and modifying the received query at least based on the user information before issuing the modified query to the plurality of sources.
12. A method as claimed in claim 1, which further comprises: arranging an evaluator to evaluate the merging model at intervals; and modifying the merging model on the basis of the evaluation.
14. A method, at an information retrieval system arranged to retrieve results from a plurality of different sources, the method comprising: receiving a query from a user in a private domain; receiving information about the user, including user input specifying an impersonating user condition; issuing the query to the plurality of sources, at least one of which is in a public domain and at least one of which is in the private domain to which the information retrieval system has access; receiving a results list from each of the plurality of sources; forming a merged results list by a processor from the received results lists using a merging model which takes into account the user information, wherein the forming comprises using the merging model to determine a probability value for each result being the probability that the result will be clicked by a user and using the probability values to form the merged results list; arranging a user interface to present the merged results list; observing user behavior in response to the presented merged results list; and using the observed user behavior to update the merging model.
16. A method as claimed in claim 14, in which the merging model further comprises: determining whether to merge results list based at least on the merging model; and forming, by a processor, a complete results list from the received results list using the merging model.
17. An information retrieval system comprising: an input arranged to receive a query; an output arranged to issue the query to a plurality of sources; the input being arranged to receive a results list from each of the plurality of sources; memory storing a merging model in a data structure comprising a plurality of weighted event variables describing a complete results list presentation event, the merging model comprising a decision process that determines whether or not to merge results based on the relevance of the results, the decision process deciding to not merge results when a difference between a first measure of relevance of a first set of results and a second measure of relevance of a second set of results satisfies a threshold condition; a processor forming a complete results list from the received results lists using the merging model; and a user interface arranged to present the complete results list; wherein the processor is arranged to observe user behavior in response to the presented complete results list and to use the observed user behavior to update the merging model.
Where federated search is carried out there is typically a need to merge search results received from different search engines that may retrieve information from different sources. For example, federated search can be carried out at a search portal which receives a search query and sends that to a plurality of different search engines. It collects the results and typically provides a user interface whereby the collected results may be accessed. The process of sending the query to the different search engines and receiving the results occurs automatically without the need for user input and may be carried out "behind the scenes" so that the user may be unaware that it is occurring.
Existing federated search systems often simply collect lists of results obtained from different information sources without providing any additional "intelligence" in the way the results are presented. For example, in some federated search systems the portal provides a user interface means whereby the end user is required to manually merge, de-duplicate and sort the results lists from the different information sources. This is time consuming and complex and places undue burden on the end user. This is especially so where the end user is a novice or child with no knowledge even of the existence of the individual data sources being searched.
The term "simultaneous scope search" is used herein to refer to using a single search engine to automatically search a plurality of information sources at least one of which is in a private domain to which the single search engine has access and at least one other of which is in a public domain.
A user at a client terminal 107 is able to input user query terms 108 to the user interface for simultaneous scope search 205 and to obtain a ranked list of merged documents 200. The simultaneous scope search engine is arranged to send the query terms 108 to both the intranet search engine 105 and the internet search engine 112 and to receive the results. It is arranged to merge the results using the merging engine 203 and display the ranked, merged results list to the end user at the user interface 205. Implicit and/or explicit feedback 201 is observed at the user interface 205 and fed back to the simultaneous scope search engine. This feedback is used to update the merging engine. That is, a machine learning system at the merging engine enables it to learn how best to merge results. An evaluator 204 is provided to check the performance of the merging engine 203 at intervals in order to ensure that the learning process has been working appropriately. Any suitable evaluator may be used. For example, an interleaved evaluation process may be used as described in Radlinski et al. "How does clickthrough data reflect retrieval quality" Proceedings of 17.sup.th ACM conference on Information and Knowledge management, pp 43-52, 2008 which is incorporated herein by reference in its entirety.
The term "explicit feedback" is used to refer to proactive feedback from a user about the relevance of a document retrieved by an information retrieval system. For example, this may be a label assigned to a document by a human user, given a specified query. The label may act to classify the document into one of a plurality of classes depending on how relevant the user perceives the document to be to the query. Explicit feedback can also be thought of as an evaluation of one or more documents in a ranked list in view of the query terms used to obtain that ranked list. Explicit feedback may also be referred to as explicit relevance information.
In order for feedback to be explicit, active user input or action by a user is required in response to a query or request to that user to make a judgment. In contrast, for "implicit feedback" (also referred to as implicit relevance information) active user input in response to a request to make a judgment is not required. It can also be thought of as passive feedback. Examples of implicit feedback include click data such as query-document pairs. A query-document pair is a query entered by a user to a search engine in combination with a link or other identifier of a document. The document was listed in a ranked list of documents presented by the search engine in response to the query and was clicked on by the user. Other examples of implicit feedback include absence of activity at the user interface. For example, an event such as a user not accessing a document from a results list is assumed to be correlated with document irrelevance. There are many other possible types of implicit feedback. For example, dwell time (how long a user directs a user interface pointer over a link in a document list). Different grades of implicit feedback can be envisaged. For example, if a user copies and pastes a link from the results list, or bookmarks the link this can be taken as high quality implicit feedback.
For example, the merging model is a model of search result presentation events and is used to predict whether a result will be selected (or clicked) by a user and also which source or search scope will be preferred (clicked). In this way, observed information about a merged search result presentation event may be used to update the merging model and this process may continue as merged search result presentation events are observed. The merging is then adaptive and learns to merge results in a manner most likely to result in "clicks" in future. Any suitable merging model may be used which models search result presentation events and which may be used to predict whether a result will be selected by a user. This can also be thought of as a model which predicts how relevant a result will be to a given user.
FIG. 8 is an example of a user interface display for use by the simultaneous scope user interface 205 in an education domain. This is a particular example described with reference to an education application. The technology is also suitable for use with other application fields by tailoring the user interface display appropriately. It comprises a main display region 801 and a side panel 802. The main display region 801 comprises a text box 800 to enable a user to enter a query and send that query to the simultaneous scope search engine. Below the text box 800 are scope check boxes 803, 804, 805 which enable the user to specify whether the Intranet and Internet should be searched (box 803), only the Intranet should be searched (box 804) or only the Internet should be searched (box 805). Another check box 806 enables the user to impersonate another user which in this example, is a "year 5 child" being a school pupil who is 10 years old. Below the scope check boxes a display of the results is given in a ranked list 807. An indication may be provided alongside each result indicating the source that the result was obtained from. However, this is not essential. Results may also be displayed in the side panel 802 as mentioned above.
In some embodiments it is possible for a user to impersonate another user in order to influence the way in which the merging engine learns. For example, a teacher may want to impersonate a child for a given query, to promote the selected results for a subsequent child search. An event variable referred to as "impersonating user" 504 in FIG. 5 is used together with a user interface check box 806 or other user input means. If the impersonating user event variable 504 is set the merging engine is arranged to modify the update process of FIG. 3 (step 310) to associate more weight to the corresponding search result presentation event than it would for other events.
Previous Patent US 9,495,459 | Next Patent US 9,495,461