System and method for aggregating ranking results from various sources to improve the results of web searching

• US 7,188,106 B2
• Filed: 04/30/2002
• Issued: 03/06/2007
• Est. Priority Date: 05/01/2001
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Sivakumar, Dandapani, Ravikumar, Shanmugasundaram, Dwork, Cynthia, Naor, Simeon
• Primary Examiner(s): TRUONG, CAM Y T
• Application Number:
  US10/136,911
• Publication Number:
  US 20030037074A1
• Time in Patent Office: 1,771 Days
• Field of Search: 707 2- 6, 707/10
• 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
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A system and method for aggregating rankings from a plurality of ranking sources to generate a maximally consistent ranking by minimizing a distance measure. The ranking sources may be search engines executing queries on web pages that have been deliberately modified to cause an incorrect estimate of their relevance. The invention supports combining partial rankings.

Claims

1. A computer-implemented method for aggregating rankings comprising:

constructing an initial aggregated ranking from a plurality of source rankings;

for each element of the plurality of source rankings;

a) computing a distance measure comparing a plurality of source rankings output by at least one search engine that has incorrectly estimated the relevance of at least one web page;

b) altering elements in an altered aggregated ranking to minimize said distance measure, wherein an element is inserted into said altered aggregated ranking only if

(1) there exists a majority among said source rankings that prefers said element to a lowest-ranked element in said altered aggregated ranking; and

(2) there exists a majority among said source rankings that prefers said element to all successors of said lowest-ranked element in said altered aggregated ranking; and

outputting the altered aggregated ranking after each element is processed and said altering ends.

2. The method of claim 1 wherein said source rankings include partial rankings.

3. The method of claim 2 wherein said distance measure is an induced distance measure between said initial aggregated ranking and the projection of a full ranking with respect to a union of elements in said partial rankings.

4. The method of claim 1 wherein said incorrect relevance estimate is due to deliberate manipulation of at least one said web page.

5. The method of claim 1 wherein said distance measure describes a level of inconsistency between said plurality of source rankings.

6. The method of claim 1 wherein said distance measure is a Kendall distance.

7. The method of claim 1 wherein said distance measure is a Spearman footrule distance.

8. The method of claim 1 wherein said distance measure is a normalized footrule distance.

9. The method of claim 1 wherein said distance measure is a scaled footrule distance.

10. The method of claim 1 wherein said distance measure is a scaled Kendall distance measure.

11. A computerized system for aggregating rankings comprising:

means for constructing an initial aggregated ranking from a plurality of source rankings;

for each element of the plurality of source rankings;

means for computing a distance measure comparing a plurality of source rankings output by at least one search engine that has incorrectly estimated the relevance of at least one web page;

means for altering elements in an altered aggregated ranking to minimize said distance measure, wherein an element is inserted into said altered aggregated ranking only if

(1) there exists a majority among said source rankings that prefers said element to a lowest-ranked element in said altered aggregated ranking; and

(2) there exists a majority among said source rankings that prefers said element to all successors of said lowest-ranked element in said altered aggregated ranking; and

means for outputting the altered aggregated ranking after each element is processed and said altering ends.

12. A computer program product comprising a machine-readable medium tangibly embodying machine-executable instructions thereon comprising:

a first code means for constructing an initial aggregated ranking from a plurality of source rankings;

for each element of the plurality of source rankings;

a second code means for computing a distance measure comparing a plurality of source rankings output by at least one search engine that has incorrectly estimated the relevance of at least one web page;

a third code means for altering elements in an altered aggregated ranking to minimize said distance measure, wherein an element is inserted into said altered aggregated ranking only if

(1) there exists a majority among said source rankings that prefers said element to a lowest-ranked element in said altered aggregated ranking; and

(2) there exists a majority among said source rankings that prefers said element to all successors of said lowest-ranked element in said altered aggregated ranking; and

a fourth code means for outputting the altered aggregated ranking after each element is processed and said altering ends.