Click distance determination

• US 7,827,181 B2
• Filed: 09/29/2005
• Issued: 11/02/2010
• Est. Priority Date: 09/30/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Petriuc, Mihai
• Primary Examiner(s): Mofiz; Apu M
• Assistant Examiner(s): Le; Hung D
• Application Number:
  US11/238,906
• Publication Number:
  US 20060069982A1
• Time in Patent Office: 1,860 Days
• Field of Search: 707/711, 707/742, 707/749
• US Class Current: 707/742
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

An efficient determination of a click distance value is made for each document in a corpus of documents from data included in a locally-stored inverted index. The click distance is measurement of the number clicks or user navigations from a first document on the network to another document. Specialized words are included in the locally-stored inverted index. The specialized words relate source documents to a set of target documents. A click distance is assigned to a source document when an inverted index is queried for the corresponding set of target documents according to a query that passes in one of the specialized words. The process is repeated for each document in the corpus of documents.

Claims

1. A computer-implemented method for determining a click distance associated with documents on a network, comprising:

storing document and link information for the documents;

within the document and link information, additionally storing a specialized word in association with a target document, wherein the specialized word is a variation of a document identifier for a source document that provides a unique word that associates the target document with the source document;

wherein the specialized word is appended to anchor text that is associated with the target document;

including the specialized word and any target identifiers for the specialized word in an inverted index, wherein the locally stored inverted index relates the specialized word with an identifier of the target document; and

assigning a click distance to the source document when an inverted index is queried for the target document according to a query that passes in the specialized word.

2. The computer-implemented method of claim 1, wherein the inverted index corresponds to an anchor text index that is arranged to store a listing of words contained in the anchor text and documents identified as associated with each word.

3. The computer-implemented method of claim 1, wherein storing the document and link information further comprises storing anchor text included in the source document, wherein the anchor text is stored such that the anchor text is associated with the target document.

4. The computer-implemented method of claim 3, further comprising storing the document and link information including the anchor text in an anchor text table.

5. The computer-implemented method of claim 4, wherein the click distance of one of the target nodes is set to the click distance of the current node plus a variable when the click distance of the one of the target nodes is greater than the click distance of the current node plus the variable.

6. The computer-implemented method of claim 1, wherein storing the specialized word further comprises appending the specialized word to anchor text stored within an anchor text table.

7. The computer-implemented method of claim 6, further comprising constructing an anchor graph that includes the documents of the network as nodes and further includes records of the anchor text table as links of the anchor graph.

8. The computer-implemented method of claim 1, wherein including the specialized word in the inverted index further comprises inserting the specialized word into the inverted index when anchor text to which the specialized word is appended is also inserted into the inverted index.

9. The computer-implemented method of claim 1, wherein assigning a click distance to the source document further comprises assigning an initial click distance value to the source document when the source document corresponds to a high authority node within an anchor graph.

10. The computer-implemented method of claim 9, wherein more than one high authority node is designated for the anchor graph.

11. The computer-implemented method of claim 9, further comprising assigning an initial infinity value as the click distance value when the source document corresponds to a node other than a high authority node.

12. The computer-implemented method of claim 11, further comprising inserting the source document into a queue when the source node has a click distance value other than the initial infinity value.

13. The computer-implemented method of claim 11, further comprising retrieving the source document from the queue to query the inverted index.

14. A computer-readable storage medium having stored thereon instructions that when executed implements the computer-implemented method of claim 1.

15. A system, comprising:

a processor;

a document interface that is arranged to provide access to documents stored on a network;

an anchor text table that is arranged to store document and link information corresponding to the documents on the network, wherein the anchor text table includes records of target documents and their associated anchor text;

specialized words that are appended to the anchor text associated with each target document, wherein each of the specialized words is a variation of a document identifier for a source document that provides a unique word that associates a source document with one or more of the target documents;

an inverted index that is arranged to list words included in anchor text and the target documents associated with each word, such that the specialized words are also listed in the inverted index with target identifiers for each of the target documents associated with each specialized word; and

a client interface that is arranged to implement a search engine, wherein the search engine determines a click distance associated with each document stored on the network by incrementing a click distance value associated with each document stored on the network when a query to the inverted index for the target documents correspond to the document stored on the network is made.

16. The system of claim 15, wherein the inverted index corresponds to an anchor text index that is arranged to store a listing of words contained in the anchor text and documents identified as associated with each word.

17. The system of claim 15, wherein the inverted index is locally-stored in comparison to the documents on the network.

18. The system of claim 15, wherein the inverted index corresponds to a partitioned index, wherein a first partition corresponds to a main index, and a second partition corresponds to an anchor text index.

19. A computer-readable storage medium having stored thereon instructions that when executed implements the system of claim 15.

20. A computer-readable storage medium that includes computer-executable instructions for determining click distance, the instructions comprising:

storing document and link information for documents on a network such that a network graph representing the network is initiated in memory;

storing each document represented in the network graph in a queue when the document has a click distance value that is different from a first click distance value; and

when the queue is not empty;

retrieving a document from the queue,

determining target documents associated with the retrieved document by querying an anchor index, wherein the anchor index includes appended specialized words that are a variation of document identifiers for source documents that provide unique words that associate the target documents with source documents and any target identifiers for the specialized word;

assigning a click distance for each of the target documents associated with the retrieved document, wherein each target document is updated with a new click distance value other than the first click distance value when each target document'"'"'s click distance is greater than the click distance associated with the removed document plus a variable, and

adding each of the target documents to the queue that have been updated.