Method and apparatus for merging result lists from multiple search engines

• US 6,728,704 B2
• Filed: 08/27/2001
• Issued: 04/27/2004
• Est. Priority Date: 08/27/2001
• Status: Expired due to Term

• Current Assignee: Valtrus Innovations Limited (f/k/a Dolya Holdco 9 Limited) (Key Patent Innovations Limited)
• Original Assignee: Verity Incorporated (Healthstream Incorporated)
• Inventors: Mao, Jianchang, Raghavan, Prabhakar, Mukherjee, Rajat, Tsaparas, Panayiotis
• Primary Examiner(s): Metjahic, Safet
• Assistant Examiner(s): Alaubaidi, Haythim J.
• Application Number:
  US09/940,600
• Publication Number:
  US 20030041054A1
• Time in Patent Office: 974 Days
• Field of Search: 707/1, 707/3, 707/5, 707/7
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9532 Query formulation
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

This invention includes the step of transmitting a query to a set of search engines. Any result lists returned from these search engines is received, and a subset of entries in each result list is selected. Each entry in this subset is assigned a scoring value according to a scoring function, and each result list is then assigned a representative value according to the scoring values assigned to its entries. A merged list of entries is produced based upon the representative value assigned to each result list.

Claims

1. A method of merging result lists from multiple search engines, said method comprising:

transmitting a query to a set of search engines;

receiving in response to said query a result list from each search engine of said set of search engines, each result list including one or more entries;

selecting a subset of entries from each result list to form a set of selected entries;

assigning to each selected entry of said set of selected entries a scoring value according to a scoring function;

assigning to each subset a representative value according to the scoring values assigned to its entries; and

producing a merged list of entries in a predetermined manner based on the representative value assigned to each result list,

wherein the representative value varies in accordance with predetermined manner.

2. The method of claim 1 wherein said selecting includes selecting a consecutive number of entries from each result list, including the first entry from each result list.

3. The method of claim 1 wherein said selecting includes selecting a uniform number of entries that are uniformly spaced within each result list.

4. The method of claim 1 wherein said selecting includes selecting a uniform number of entries at random from each result list.

5. The method of claim 1 wherein said producing includes (A) selecting the result list having the highest average value so as to form a selected list, (B) selecting from said selected list the first entry that has not already been selected for ranking, (C) decrementing the average value of said result list by a specified number, and repeating (A), (B) and (C) in order until every entry in every result list has been selected.

6. The method of claim 1 wherein said producing includes (A) assigning to each result list a probability value based on its avenge value, (B) selecting a result list preferentially based on its probability value so as to form a selected list, (C) selecting from said selected list the first entry that has not already been selected for ranking, and repeating (A), (B) and (C) in order until every entry in every result list has been selected.

7. A computer-readable memory to instruct a computer to function in a specified manner, comprising:

executable instructions stored in said memory, said executable instructions including;

instructions for forming a set of selected entries by selecting a subset of entries from each result list of a set of result lists, wherein each result list in said set of result lists has been generated in response to a query processed by a search engine;

instructions for assigning each entry of said set of selected entries a scoring value according to a scoring function;

instructions for assigning each result list in said set of result lists a representative value based on the scoring values assigned to its entries; and

instructions for ranking every entry based on the representative value assigned to its result list,

wherein said instructions for ranking include instructions for (A) assigning to each result list a probability value that is based on its average value, (B) selecting a result list preferentially based on its probability value so as to form a selected list, (C) selecting from said selected list the first entry that has not already been selected for ranking, and repeating (A), (B) and (C) in order until every entry in every result list has been selected.

8. The computer-readable memory of claim 7 wherein said instructions for forming include instructions to select a consecutive number of entries from each result list, including the first entry from each result list.

9. The computer-readable memory of claim 7 wherein said instructions for forming include instructions to select a uniform number of entries that are uniformly spaced within each result list.

10. The computer-readable memory of claim 7 wherein said instructions for forming include instructions to select a uniform number of entries at random from each result list.

11. The computer-readable memory of claim 7 wherein said instructions for ranking include instructions for (A) selecting the result list having the highest average value so as to form a selected list, (B) selecting from said selected list the first entry that has not already been selected for ranking, (C) decrementing the average value of said result list by a specified number, and repeating (A), (B) and (C) in order until every entry in every result list has been selected.

12. A method of merging result lists from multiple search engines, said method comprising:

transmitting a query to a set of search engines;

receiving in response to said query a set of result lists, each result list in said set of result lists including one or more entries;

selecting a subset of entries from each result list;

determining a scoring value for each entry of said subset of entries;

characterizing said subset in accordance with a representative value; and

merging entries in a predetermined manner into a single list based on said representative value,

wherein said representative value varies in accordance with said predetermined manner.

13. The method of claim 12 wherein said selecting includes selecting a consecutive number of entries from each result list, including the first entry from each result list.

14. The method of claim 12 wherein said selecting includes selecting a uniform number of entries that are uniformly spaced within each result list.

15. The method of claim 12 wherein said selecting includes selecting a uniform number of entries at random from each result list.

16. The method of claim 12 wherein said merging includes (A) selecting the result list having the highest average value so as to form a selected list, (B) selecting from said selected list the first entry that has not already been selected for ranking, (C) decrementing the average value of said result list by a specified number, and repeating (A), (B) and (C) in order until every entry in every result list has been selected.

17. The method of claim 12 wherein said merging includes (A) assigning to each result list a probability value based on its average value, (B) selecting a result list preferentially based on its probability value so as to form a selected list, (C) selecting from said selected list the first entry that has not already been selected for ranking, and repeating (A), (B) and (C) in order until every entry in every result list has been selected.

18. A computer-readable memory to instruct a computer to function in a specified manner, comprising:

executable instructions stored in said memory, said executable instructions including;

instructions for transmitting a query to a set of search engines;

instructions for receiving in response to said query a set of result lists, each result list in said set of result lists including one or more entries;

instructions for selecting a subset of entries from each result list;

instructions for determining a scoring value for each entry of said subset of entries;

instructions for characterizing said subset in accordance with a representative value; and

instructions for merging entries in a predetermined manner into a single list based on said representative value,

wherein said representative value varies in accordance with said predetermined manner.

19. The computer-readable memory of claim 18 wherein said instructions for selecting include instructions to select a consecutive number of entries in each result list, including the first entry from each result list.

20. The computer-readable memory of claim 18 wherein said instructions for selecting include instructions to select a uniform number of entries that are uniformly spaced within each result list.

21. The computer-readable memory of claim 18 wherein said instructions for selecting include instructions to select a uniform number of entries at random from each result list.

22. The computer-readable memory of claim 18 wherein said instructions for merging include instructions for (A) selecting the result list having the highest average value so as to form a selected list, (B) selecting from said selected list the first entry that has not already been selected for ranking, (C) decrementing the average value of said result list by a specified number, and repeating (A), (B) and (C) in order until every entry in every result list has been selected.

23. The computer readable memory of claim 18 wherein said instructions for merging include instructions for (A) assigning to each result list a probability value that is based on its average value, (B) selecting a result list preferentially based on its probability value so as to form a selected list, (C) selecting from said selected list the first entry that has not already been selected for ranking, and repeating (A), (B) and (C) in order until every entry in every result list has been selected.