Method for extracting, merging and ranking search engine results

• US 8,180,768 B2
• Filed: 08/13/2009
• Issued: 05/15/2012
• Est. Priority Date: 08/13/2009
• Status: Expired due to Fees

• Current Assignee: Search Engine Solutions, LLC (Equitable IP Corporation)
• Original Assignee: Politecnico di Milano
• Inventors: Fraternali, Piero, Martinenghi, Davide, Tagliasacchi, Marco, Ceri, Stefano, Braga, Daniele, Brambilla, Marco, Campi, Alessandro, Della Valle, Emanuele
• Primary Examiner(s): Mofiz, Apu
• Assistant Examiner(s): WALKER, BRYAN L
• Application Number:
  US12/540,700
• Publication Number:
  US 20110040749A1
• Time in Patent Office: 1,006 Days
• Field of Search: 707/999.101, 707/723, 707/728
• US Class Current: 707/728
• CPC Class Codes: G06F 16/9532 Query formulation
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation

Abstract

A method and a computer program product for identifying the domains, selecting for each domain one domain-specific search engine and data source to be involved, generating the domain-specific subqueries for each selected search engine, defining a strategy for sending requests to each search engine and data source, and receiving, merging and ranking results. The result of the multi-domain query is a list of combinations, where every combination consists of a tuple of data, each relative to one of the domains of the query; such data is present in the results returned either by search engines or by data sources. The method provides the combinations having the highest combination score, as computed by a monotone aggregation function over the combinations.

Claims

1. A method for extracting, merging and ranking results produced by executing multi-domain queries over “

n”

domain-specific search engines, said method comprising;

obtaining a query and an expected number of results K by the user through a user interface;

decomposing said query into “

n”

subqueries and associating each subquery with exactly one domain of the “

n”

domain-specific search engines;

selecting one search engine for each said domain and one data source for each said search engine, wherein the selection of search engines used for answering the query determines also a strategy for building a combination of “

n”

elements among those returned as result from the “

n”

domain-specific search engines and data sources, wherein every combination is produced as result of n−

1 join operations between elements, such that every combination comprises exactly one element for each domain;

wherein the method comprises the further steps of;

performing sequential accesses to each said search engine in function of the associated subquery and receiving in response results consisting of lists of elements;

performing attribute-based access to each said data sources in function of results responded by search engines and receiving in response results consisting of sets of elements;

computing a plurality of combinations, each of which comprising “

n”

elements;

associating with each combination a combination score and ranking each element combination in function of the combination score;

extracting the expected number of results K of combinations with the highest combination score, so as to minimize a global cost of execution of said query, the cost being a function of the costs of requests to search engines and to data sources.

2. The method of claim 1, wherein the association of a score to each combination is performed by aggregating the element scores retrieved by the different search engines and data sources by an aggregation function, the latter being associated with the query.

3. The method of claim 2, wherein the step of performing sequential access to the selected search engines initially performs one request to every search engines, and receives as result a first sub-list of elements produced by every search engine as answer to the requests.

4. The method of claim 1, wherein the step of computing a plurality of combinations comprises the strategy for building combinations of elements by using said sub-lists of elements, thus producing the first set of combinations, and further the step of storing said combinations are stored in the memory associated with the query.

5. The method of claim 1, wherein if the number of combinations is less than the number of results K then:

a. one or more of the search engines are chosen;

b. a sequential access is performed to every said chosen search engine, receiving as result new sub-lists of elements responding to the access, and said elements are stored in memory associated with the query;

c. the strategy for building combinations of elements is applied to the said new sub-lists of elements and the lists of already available elements, producing new combinations, and said combinations are stored in memory associated with the query.

6. The method of claim 5, wherein after step b. those search engines that have returned no elements are marked as emptied.

7. The method of claim 5, wherein after step b. if all search engines are marked as emptied, then a message informs the user that it is not possible to form the number K of combinations, and therefore the result will include only H combinations, where H is the number of currently formed combinations and if H is equal to zero the query fails.

8. The method of claim 5, wherein either after step c. at least the number K of combinations are produced, or after step b, only H combinations are produced, and K is set equal to H.

9. The method of claim 8, wherein every distinct value V of every join attribute of every said K combinations is used for determination of required attribute-based accesses, and then all said attribute-based accesses are performed, producing as result new sets of elements, and said elements are stored in memory associated with the query.

10. The method of claim 1, wherein the strategy for building combinations of elements is applied to the said new sub-lists of elements and the lists of already available elements, producing new combinations, and said combinations are stored in memory associated with the query.

11. The method of claim 10, wherein the K combinations with the highest score present in memory are presented as the result of the query.

12. A computer program product comprising a set of executable instruction codes stored on a computer readable storage medium, wherein said set of executable instruction codes performs the steps of a method for extracting, merging and ranking results produced by executing multi-domain queries over “

n”

domain-specific search engines, the method comprising;

obtaining a query and an expected number of results K by the user through a user interface;

decomposing said query into “

n”

subqueries and associating each subquery with exactly one domain of the “

n”

domain-specific search engines;

selecting one search engine for each said domain and one data source for each said search engine, wherein the selection of search engines used for answering the query determines also a strategy for building a combination of “

n”

elements among those returned as result from the “

n”

domain-specific search engines and data sources, wherein every combination is produced as result of n−

1 join operations between elements, such that every combination comprises exactly one element for each domain;

wherein the method comprises the further steps of;

performing sequential accesses to each said search engine in function of the associated subquery and receiving in response results consisting of lists of elements;

performing attribute-based access to each said data sources in function of results responded by search engines and receiving in response results consisting of sets of elements;

computing a plurality of combinations, each of which comprising “

n”

elements;

associating with each combination a combination score and ranking each element combination in function of the combination score;

extracting the expected number of results K of combinations with the highest combination score, so as to minimize a global cost of execution of said query, the cost being a function of the costs of requests to search engines and to data sources.

13. A computer program product according to claim 12, wherein it comprises further:

a first set of instruction codes for reading the query from an interface;

a second set of instruction codes for storing the data which is used for responding to the query;

a third set of instruction codes for processing the query and writing the results of the query on an interface presented to the user.

14. The computer program of claim 13, wherein the said first set of instruction codes for reading the query comprises:

a set of instruction codes for reading the number K of expected results by the user from the interface;

a set of instruction codes for decomposing the query into subqueries and associating each subquery with one domain;

a set of instruction codes for selecting one search engine for each domain and one data source for each selected search engine.

15. The computer program of claim 13, wherein the data used for responding to the query comprise:

data existing prior to the query execution, comprising;

domain descriptions;

search engine descriptions, said descriptions including the association of search engines to their domain of specialization;

data source description, including the association of data sources to search engines; and

interface description parameters, said parameters including the average cost of each request to a search engine or data source;

data produced during query execution, comprising elements with properties, said properties consisting of pairs including one attribute and one value; and

combinations of elements with their element scores.

16. The computer program of claim 13, wherein the said instruction codes for processing the query comprise:

instructions for choosing the search engines to be invoked in the next step of said query processing method;

instructions for presenting to said chosen search engines a new request and for receiving the response, consisting of an element sub-list, and for storing said sub-list of elements in the memory associated with the query;

instructions for computing the new combinations and combination scores which are produced by using the said new sub-lists of elements and the already available lists of elements, and for storing said combinations and combination scores in the memory associated with the query; and

instructions for testing if existing combinations are less than K, and repeating until existing combinations are at least K or all existing elements have been retrieved without producing K combinations, but producing instead H combinations, with H<

K.

17. The computer program of claim 14, wherein the said instruction codes for processing the query comprises in addition:

instructions for determining the attribute-based queries that should be addressed to the data sources;

instructions for performing said attribute-based queries to said data sources and retrieving new elements;

instructions for storing said elements in the memory associated with the query;

instructions for computing the new combinations and combination scores which are produced by using the said new elements and the already available lists of elements, and for storing said combinations and combination scores in the memory associated with the query;

instructions for selecting the K combinations with the highest combination score; and

instructions for assembling the best combinations into the query result and present them to the user.