METHOD FOR EXTRACTING, MERGING AND RANKING SEARCH ENGINE RESULTS

• US 20110040749A1
• Filed: 08/13/2009
• Published: 02/17/2011
• Est. Priority Date: 08/13/2009
• Status: Active Grant

• Current Assignee: Politecnico di Milano
• Original Assignee: Politecnico di Milano
• Inventors: Della Valle, Emanuele, Brambilla, Marco, Fraternali, Piero, Ceri, Stefano, Martinenghi, Davide, Campi, Alessandro, Tagliasacchi, Marco, Braga, Daniele
• Granted Patent: US 8,180,768 B2
• Time in Patent Office: Days
• US Class Current: 707/723
• 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 through a user interface;

decomposing said query into “

n”

subqueries and associating each subquery to at exactly one domain;

selecting one search engine for each said domain and one data source for each said search engine;

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 to each combination a combination score and ranking each element combination in function of the combination score;

extracting a number 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 selection of search engines used for answering the query determines also a strategy for building a combination of the elements returned as result from the search engines and data sources, wherein every combination is produced as result of n−

1 join operations, such that every combination comprises exactly one element for each domain.

3. 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 means of an aggregation function, the latter being associated with the query.

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

5. The method of claim 2, wherein the strategy for building combinations of elements is used upon said sub-lists of elements, thus possibly producing the first set of combinations, and said combinations are stored in the memory associated with the query.

6. The method of claim 2, wherein if the number of combinations is less than K then:

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

b. a request is performed to every said chosen search engine, receiving as result new sub-lists of elements responding to the request, 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, possibly producing new combinations, and said combinations are stored in memory associated with the query.

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

8. The method of claim 6, 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 be include only H combinations, where H is the number of currently formed combinations. If H is equal to zero the query fails.

9. The method of claim 6, 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.

10. The method of claim 9, 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.

11. The method of claim 2, 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, possibly producing new combinations, and said combinations are stored in memory associated with the query.

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

13. A computer program product comprising a set of executable instruction codes stored on a computer readable medium, wherein said set of executable instruction codes performs the steps of the method for extracting, merging and ranking results produced by executing multi-domain queries over several domain-specific search engines as claimed in claim 1.

14. A computer program product according to claim 13, 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.

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

a set of instruction codes for reading a number of expected results K 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.

16. The computer program of claim 14, 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.

17. The computer program of claim 14, 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.

18. The computer program of claim 15, 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.