Dual web graph

• US 8,122,030 B1
• Filed: 01/13/2006
• Issued: 02/21/2012
• Est. Priority Date: 01/14/2005
• Status: Expired due to Fees

• Current Assignee: Walmart Apollo, LLC (WalMart Inc.)
• Original Assignee: Wal Mart Stores Inc (WalMart Inc.)
• Inventors: Harinarayan, Venky, Rajaraman, Anand
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): SOMERS, MARC S
• Application Number:
  US11/332,847
• Time in Patent Office: 2,230 Days
• Field of Search: 707/5, 707/7, 707/705, 707/736, 707/748
• US Class Current: 707/748
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Scoring a document is disclosed. One or more metrics is determined in a forward direction. One or more backwards metrics is determined. The document is scored based at least in part on a combination of the metrics.

Claims

1. A computer implemented method of scoring a document in a collection comprising:

determining one or more metrics in a forward direction;

determining one or more backward metrics; and

scoring the document based at least in part on a combination of the metrics;

wherein the one or more backward metrics is determined, at least in part, using a dual graph; and

wherein the dual graph is constructed such that a random walk of a random surfer through a sequence of documents in the collection occurs with equal probability in the dual graph as a corresponding random walk through the same documents'"'"' corresponding dual-graph nodes in reverse order.

2. The method of claim 1 wherein determining one or more metrics includes using reversible Markov chains.

3. The method of claim 1 wherein the combination is a product.

4. The method of claim 1 wherein the combination includes weighting at least one of the metrics.

5. The method of claim 1 wherein the combination includes weighting the metrics determined in a forward direction differently from the backward metrics.

6. The method of claim 1 wherein the combination includes normalizing at least one of the metrics.

7. A system for scoring a document in a collection comprising:

a processor, configured to;

determine one or more metrics in a forward direction;

determine one or more backward metrics; and

score the document based at least in part on a combination of the metrics;

wherein the one or more backward metrics is determined, at least in part, using a dual graph; and

wherein the dual graph is constructed such that a random walk of a random surfer through a sequence of documents in the collection occurs with equal probability in the dual graph as a corresponding random walk through the same documents'"'"' corresponding dual-graph nodes in reverse order; and

a memory, coupled with the processor, wherein the memory is configured to provide the processor with instructions.

8. The system of claim 7 wherein determining one or more metrics includes using reversible Markov chains.

9. The system of claim 7 wherein the combination is a product.

10. The system of claim 7 wherein the combination includes weighting at least one of the metrics.

11. The system of claim 7 wherein the combination includes weighting the metrics determined in a forward direction differently from the backward metrics.

12. The system of claim 7 wherein the combination includes normalizing at least one of the metrics.

13. A computer program product for scoring a document, the computer program product being embodied in a computer readable storage medium and comprising computer instructions for:

determining one or more metrics in a forward direction;

determining one or more backward metrics; and

scoring the document based at least in part on a combination of the metrics;

wherein the one or more backward metrics is determined, at least in part, using a dual graph; and

wherein the dual graph is constructed such that a random walk of a random surfer through a sequence of documents in the collection occurs with equal probability in the dual graph as a corresponding random walk through the same documents'"'"' corresponding dual-graph nodes in reverse order.

14. The computer program product of claim 13 wherein determining one or more metrics includes using reversible Markov chains.

15. The computer program product of claim 13 wherein the combination is a product.

16. The computer program product of claim 13 wherein the combination includes weighting at least one of the metrics.

17. The computer program product of claim 13 wherein the combination includes weighting the metrics determined in a forward direction differently from the backward metrics.