CONCEPT-AWARE RANKING OF ELECTRONIC DOCUMENTS WITHIN A COMPUTER NETWORK

• US 20080033932A1
• Filed: 06/27/2007
• Published: 02/07/2008
• Est. Priority Date: 06/27/2006
• Status: Abandoned Application

• Current Assignee: Regents of The University of Minnesota (University of Minnesota)
• Original Assignee: Regents of The University of Minnesota (University of Minnesota)
• Inventors: Mane, Sandeep, DeLong, Colin, Srivastava, Jaideep
• Application Number:
  US11/769,509
• Publication Number:
  US 20080033932A1
• Time in Patent Office: Days
• US Class Current: 707/5
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Techniques are described for ranking the relevance of electronic documents, such as web pages. An algorithm extracts keywords and recurring phrases from the anchor tag data in electronic documents to define a set of concepts. The algorithm then uses link, concept pairs to create nodes in a graph. In this graph, edges can represent both explicit and implicit conceptual links between nodes. By including conceptual data, the algorithm may model and utilize inter-concept relationships when using graph ranking algorithms. This may improve result accuracy by not only retrieving links which are more authoritative given a users'"'"' context, but also by utilizing a larger pool of web pages that are limited by concept-space, rather than keyword-space.

Claims

1. A computer-implemented method comprising:

extracting a set of concepts from a set of electronic documents from a computer network;

constructing a graph having nodes interconnected by edges, wherein each of the nodes in the graph represents an electronic document in the set of documents and a concept extracted from that electronic document, and further wherein each of the edges in the graph represents a link from a first one of the electronic documents to a second one of the electronic documents for a corresponding one of the concepts;

assigning a rank to each node in the graph based on a number of incoming edges connecting to the node; and

responding to a query with a list containing a subset of the nodes, wherein the list is sorted according to the rank assigned to the nodes.

2. The method of claim 1, wherein extracting a set of concepts comprises:

compiling an array of source page identifiers, wherein each of the source page identifiers in the array is associated with a pair comprising a target page identifier and a link text associated with the link from source page to the target page; and

for each of the pairs;

adding all individual words in the link text into a concept array;

initializing the concept array with word frequencies;

adding all left-to-right multi-word combinations of the link text to the concept array; and

initializing the concept array with the frequencies of the multi-word combinations.

3. The method of claim 1, wherein constructing a graph comprises:

removing concepts from the graph that occur only once globally; and

removing concepts from the graph which are string subsets of longer concepts having a common global frequency.

4. The method of claim 1, wherein constructing a graph comprises adding implicit links to the graph.

5. The method of claim 1, wherein assigning a rank comprises:

transforming graph entries the form {source_page_id, target_page_id, concept_id} into the form {source_node_id, target_node_id};

generating an adjacency matrix using the transformed graph entries; and

applying a PageRank algorithm to the adjacency matrix.

6. The method of claim 5, further comprising assigning a “

null”

concept to pages that do not have incoming links.

7. The method of claim 1, wherein responding to a query comprises:

breaking search terms of the query into individual words;

querying a ranked concept-page graph with the individual words to retrieve one or more result nodes;

assembling the result nodes into groups, wherein the result nodes in each of the groups refers to a common one of the electronic documents;

determining sums for each of the groups, wherein each of the sums equals the sum total of the rank assigned to each result node in one of the groups; and

returning a list containing the common electronic documents in order of sums for each of the groups.

8. A computing device comprising:

a concept extraction software module executing on the computer device to extract a set of concepts from a set of electronic documents;

a graphing software module executing on the computing device to construct a graph, wherein each node in the graph refers to an electronic document in the set of documents and a concept extracted from that electronic document, and wherein each edge in the graph represents a conceptual link from a first one of the electronic documents to a second one of the electronic documents along a concept;

a ranking software module executing on the computing device to assign a rank to each node in the graph based on a number of incoming edges connecting to the node; and

a query engine software module executing on the computing device to respond to a query with a list containing a subset of the nodes, wherein the list is sorted according to the rank assigned to the nodes.

9. The computing device of claim 8,

wherein the concept extraction module compiles an array of source page identifiers, wherein each of the source page identifiers in the array is associated with a pair comprising a target page identifier and a link text;

and

wherein for each of the pairs, the concept extraction module;

adds all individual words in the link text into a concept array;

initializes the concept array with word frequencies;

adds all left-to-right multi-word combinations of the link text to the concept array;

initializes the concept array with the frequencies of the multi-word combinations.

10. The computing device of claim 8,

wherein the graphing module removes concepts from the graph that occur only once globally;

and

wherein the graphing module removes concepts from the graph which are string subsets of longer concepts having a common global frequency.

11. The computing device of claim 8, wherein the graphing module adds implicit links to the graph.

12. The computing device of claim 8,

wherein the ranking module transforms graph entries the form {source_page_id, target_page_id, concept_id} into the form {source_node_id, target_node_id};

wherein the ranking module generates an adjacency matrix using the transformed graph entries; and

wherein the ranking module applies a PageRank algorithm to the adjacency matrix.

13. The computing device of claim 8, wherein the ranking module assigns a “

null”

concept to pages that do not have incoming links

14. The computing device of claim 8,

wherein the query engine module breaks search terms of the query into individual words;

wherein the query engine module queries a ranked concept-page graph with the individual words to retrieve one or more result nodes;

wherein the query engine module assembles the result nodes into groups, wherein the result nodes in each of the groups refers to a common one of the electronic documents;

wherein the query engine module determines sums for each of the groups, wherein each of the sums equals the sum total of the rank assigned to each result node in one of the groups; and

wherein the query engine module returns a list containing the common electronic documents in order of sums for each of the groups.

15. A computer-readable medium comprising instructions, the instruction causing a programmable processor to:

extract a set of concepts from a set of electronic documents;

constructing a graph, wherein each node in the graph refers to an electronic document in the set of documents and a concept extracted from that electronic document, and wherein each edge in the graph represents a conceptual link from a first one of the electronic documents to a second one of the electronic documents along a concept;

assign a rank to each node in the graph based on a number of incoming edges connecting to the node; and

respond to a query with a list containing a subset of the nodes, wherein the list is sorted according to the rank assigned to the nodes.