Computerized method for ranking linked information items in distributed sources

• US 20060036598A1
• Filed: 08/09/2005
• Published: 02/16/2006
• Est. Priority Date: 08/09/2004
• Status: Abandoned Application

• Current Assignee: Ecole Polytechnique Federal de Lausanne
• Original Assignee: Ecole Polytechnique Federal de Lausanne
• Inventors: Wu, Jie
• Application Number:
  US11/199,363
• Publication Number:
  US 20060036598A1
• Time in Patent Office: Days
• 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

Abstract

A computerized method used by a distributed Web search engine for computing a ranking score associated with an item, such as a Web page, comprising the steps of: (1) generating a grouping of items in the Web according to Web sites, geographic criterion, and/or field, (2) determining links among groups; (3) for at least some groups, computing a group ranking using only inter-group links, (4) within at least several of the groups, computing a local item ranking for at least some items within the group, (5) for at least one item, locally computing a global item ranking by multiplying said group ranking and said local item ranking. Advantage: no need to retrieve a global link matrix. Method can be distributed. Reduction of cost in computation, better impeding of spamming, fresher ranking results.

Claims

1. A computerized method for ranking linked information items, comprising the steps of:

(1) generating a grouping of the items in accordance with a choosen grouping strategy;

(2) using the linking of the items and the grouping of the items for generating link among groups;

(3) generating a group score for each of the linked groups and, within each of the groups, generating an item score for each of the items within the group;

(4) using the group scores and the item scores in generating the ranking.

2. The method of claim 1, wherein said grouping strategy is based on an Internet domain name criterion.

3. The method of claim 1, wherein said grouping strategy is based on a personal preference criterion and/or on a geographic criterion.

4. The method of claims 1, wherein the links comprise at least one of a static hyperlink among Web items, a static reference among information items, and/or a quantified information about dynamic accessing trails among items.

5. The method of claim 1, wherein the information groups comprise at least one of:

a Web site of items, and/or

a library of items, and/or

a cluster of items, and/or

a group of items.

6. A computerized method for ranking linked information items, comprising the steps of:

(1) generating a grouping of the items in accordance with a choosen grouping strategy;

(2) determining links among groups;

(3) for at least some groups, computing a group ranking using only inter-group links,

(4) within at least several of the groups, computing a local item ranking for each items within the group,

(5) for at least some items, computing a global item ranking based on said group ranking and on said local item ranking.

7. The method of claim 6, the step of computing a local item ranking comprising:

computing a local external ranking of each item in a group, by weighting the number of links from other groups pointing to said item, using weigths depending on the group ranking of said other groups,

computing a local internal of each item in a group, taking into account links from items in said group only,

composing said local external ranking with said local internal ranking to compute said local item ranking.

8. The method of claim 7, wherein larger weights are given to said local external ranking than to said local internal ranking when computing said local item ranking.

9. The method of claim 7, wherein said step of computing a local item ranking is performed in a non iterative way by algebraic operations on said group ranking and on said local item ranking.

10. The method of claim 6, wherein said step of computing a local item ranking is performed locally in a distributed way.

11. The method of claim 10, wherein said step of computing a global item ranking based on said group ranking (Gs) and on said local item ranking (G^s_d) is performed without any knowledge of the global transition matrix.

12. The method of claim 6, wherein for each item said global item ranking (π

(i,j)) is computed by multiplying the group ranking (π

_y) of the group to which said item belongs with the local item ranking π

ⁱ_G of said item in said group.

13. The method of claim 12, wherein said step of computing a local item ranking is performed locally in a distributed way.

14. The method of claim 13, wherein said step of computing a local item ranking is performed locally in said group using information unavailable outside from said group.

15. The method of claim 14, wherein said information includes items, links to items or links from items unavailable outside from said group.

16. The method of claim 14, wherein said information includes Web user behaviour.

17. The method of claim 14, wherein said information is part of the hidden Web.

18. The method of claim 6, wherein said grouping strategy is based on an Internet domain name criterion.

19. The method of claim 6, wherein said grouping strategy is based on a personal preference criterion and/or on a geographic criterion.

20. The method of claims 6, wherein the links comprise at least one of a static hyperlink among Web items, a static reference among information items, and/or a quantified information about dynamic accessing trails among items.

21. The method of claim 6, wherein the information groups comprise at least one of:

a Web site of items, and/or

a library of items, and/or

a cluster of items, and/or

a group of items.

22. The method of claim 6, wherein different ranking algorithms are used for computing said local item rankings within different groups.

23. A computerized method used by a distributed Web search engine for computing a ranking score associated with a document, such as Web pages, in the Web, comprising the steps of:

(1) ranking at least some groups of documents using only inter-group links,

(2) within at least several of the groups, locally ranking at least some documents within the group,

(3) for at least one document, locally computing a global item ranking by multiplying said group ranking and said local document ranking

24. A ranking device for ranking linked items, said ranking depending on links between items, comprising:

means for retrieving a group ranking associated with several groups of items, wherein at least one group comprises more than one item,

means for ranking documents within at least one of said groups, in order to retrieve a local document ranking.

means for locally computing a global item ranking by composing said group ranking and said local document ranking.

25. The method of claim 24, said means for locally computing a global item comprising multiplying means for multiplying said group ranking and said local document ranking.

26. The ranking device of claim 24, being an Internet appliance.