Method for assigning quality scores to documents in a linked database

• US 7,668,822 B2
• Filed: 09/18/2006
• Issued: 02/23/2010
• Est. Priority Date: 12/23/2004
• Status: Expired due to Fees

• Current Assignee: Connexity, Inc.
• Original Assignee: Become Incorporated (Connexity, Inc.)
• Inventors: Yun, Yeogirl, Kaul, Rohit, Kim, Seong-Gon
• Primary Examiner(s): Ali; Mohammad
• Assistant Examiner(s): Ruiz; Angelica
• Application Number:
  US11/523,361
• Publication Number:
  US 20070016579A1
• Time in Patent Office: 1,254 Days
• Field of Search: None
• US Class Current: 707/723
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Exemplary methods for assigning relative rank values to a plurality of linked documents are provided. In one embodiment, the method comprises constructing or modeling a nodal network according to a connectivity graph of a linked database and determining conductance of inter-nodal links based on a link structure of the nodal network and rank values of end-nodes. The method may further comprise computing rank values of nodes in the nodal network through an iterative process, and obtaining quality scores for documents from the rank values of the nodes. The method may also include obtaining the quality scores for groups of documents.

Claims

1. A method for assigning quality scores to documents in a linked database, the method comprising:

constructing a nodal network stored in memory, the nodal network comprising;

(1) a plurality of nodes that each correspond to a document, wherein one or more of the plurality of nodes are selected as reference nodes that correspond to authoritative documents;

(2) unidirectional links connecting nodes that correspond to documents that are hyperlinked together, the unidirectional links originating at nodes that correspond to source documents and terminating at nodes that correspond to destination documents;

(3) a reservoir node connected to each of the plurality of nodes by unidirectional links that terminate at the reservoir node; and

(4) a quality point pump connected to the reservoir by a unidirectional link that terminates at the quality point pump, the quality point pump connected to each of the reference nodes by unidirectional links that terminate at the reference nodes, the quality point pump configured to circulate quality points through the nodal network;

initializing input rank values such that reference node ranks are fixed as the highest rank, a reservoir node rank is fixed as the lowest rank, and each of the plurality of nodes have intermediary and unfixed ranks, wherein quality points flow from nodes having a higher rank to nodes having a lower rank when the nodes are connected by a unidirectional link that terminates at the node having the lower rank;

executing instructions using a processor to adjust quality point flow rates for the unidirectional links such that the number of quality points flowing into each node equals the number of quality point flowing out of each node; and

computing a quality score for each node based on the number of quality points contained therein.

2. The method of claim 1, further comprising determining a classification for the documents.

3. The method of claim 2, wherein the initialized ranks of the plurality of nodes are dependent on classifications of the documents that corresponding thereto.

4. The method of claim 1, wherein the documents comprise hypermedia documents.

5. The method of claim 1, wherein the documents comprise web pages.

6. The method of claim 1, wherein the total number of quality points is fixed.

7. The method of claim 1, further comprising updating which of the plurality of nodes are selected as reference nodes.

8. The method of claim 1, wherein the quality point flow rates are related, at least in part, to differences of ranks between nodes that correspond to source documents and nodes that correspond to destination documents.

9. The method of claim 1, wherein a portion of the plurality of nodes is grouped.

10. The method of claim 9, wherein the portion is assigned a group ranking.

11. A computer readable storage medium having instructions embodied thereon, the instructions executable by a processor to perform a method for assigning quality scores to documents in a linked database, the method comprising:

constructing a nodal network stored in memory, the nodal network comprising;

(1) a plurality of nodes that each correspond to a document, wherein one or more of the plurality of nodes are selected as reference nodes that correspond to authoritative documents;

(2) unidirectional links connecting nodes that correspond to documents that are hyperlinked together, the unidirectional links originating at nodes that correspond to source documents and terminating at nodes that correspond to destination documents;

(3) a reservoir node connected to each of the plurality of nodes by unidirectional links that terminate at the reservoir node; and

(4) a quality point pump connected to the reservoir by a unidirectional link that terminates at the quality point pump, the quality point pump connected to each of the reference nodes by unidirectional links that terminate at the reference nodes, the quality point pump configured to circulate quality points through the nodal network;

initializing input rank values such that reference node ranks are fixed as the highest rank, a reservoir node rank is fixed as the lowest rank, and each of the plurality of nodes have intermediary and unfixed ranks, wherein quality points flow from nodes having a higher rank to nodes having a lower rank when the nodes are connected by a unidirectional link that terminates at the node having the lower rank;

executing instructions using a processor to adjust quality point flow rates for the unidirectional links such that the number of quality points flowing into each node equals the number of quality point flowing out of each node; and

computing a quality score for each node based on the number of quality points contained therein.

12. The computer readable storage medium of claim 11, further comprising determining a classification for the documents.

13. The computer readable storage medium of claim 12, wherein the initialized ranks of the plurality of nodes are dependent on classifications of the documents that corresponding thereto.

14. The computer readable storage medium of claim 11, wherein the documents comprise hypermedia documents.

15. The computer readable storage medium of claim 11, wherein the documents comprise web pages.

16. The computer readable storage medium of claim 11, wherein the total number of quality points is fixed.

17. The computer readable storage medium of claim 11, further comprising updating which of the plurality of nodes are selected as reference nodes.

18. The computer readable storage medium of claim 11, wherein the quality point flow rates are related, at least in part, to differences of ranks between nodes that correspond to source documents and nodes that correspond to destination documents.

19. The computer readable storage medium of claim 11, wherein a portion of the plurality of nodes is grouped.

20. The computer readable storage medium of claim 19, wherein the portion is assigned a group ranking.