Searching Digital Information and Databases

• US 20100223268A1
• Filed: 02/19/2010
• Published: 09/02/2010
• Est. Priority Date: 08/27/2004
• Status: Active Grant

• Current Assignee: Regents of the University of California (University of California)
• Original Assignee: Regents of the University of California (University of California)
• Inventors: Balmin, Andrey, Papakonstantinou, Yannis, Christidis, Evangelos
• Granted Patent: US 8,862,594 B2
• Time in Patent Office: Days
• US Class Current: 707/749
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

This application describes methods for searching digital information such as digital documents (e.g., web pages) and computer databases, and specific search techniques such as authority ranking and information retrieval (IR) relevance ranking in keyword searches. In some implementations, the technique includes analyzing digital information viewed as a labeled graph, including nodes and edges, based on a flow of authority among the nodes along the edges, the flow of authority being derived at least in part from different authority transfer rates assigned to the edges based on edge type schema information. In some implementations, the system includes an object rank module configured to generate multiple initial rankings corresponding to multiple query keywords, each of the multiple initial rankings indicating authority of nodes in a graph with respect to each respective query keyword individually; and a query module configured to combine the multiple initial rankings in response to a query.

Claims

1. A machine-implemented method comprising:

analyzing digital information viewed as a labeled graph, including nodes and edges, based on a flow of authority among the nodes along the edges, the flow of authority being derived at least in part from different authority transfer rates assigned to the edges based on edge type schema information; and

generating a keyword-specific ranking of the nodes in response to a query, including at least one keyword, based on a result of the analyzing.

2. The method of claim 1, further comprising:

receiving the query, the query including multiple keywords;

wherein the analyzing the digital information comprises generating multiple initial rankings corresponding to the multiple keywords, each of the multiple initial rankings indicating authority of the nodes with respect to each respective keyword; and

wherein the generating the keyword-specific ranking comprises combining the multiple initial rankings.

3. The method of claim 2, wherein generating each of the multiple initial rankings comprises performing a random-surfer-type authority-based search of the digital information using a base set consisting essentially of the nodes that contain a keyword of the query corresponding to each respective initial ranking being generated.

4. The method of claim 2, wherein the analyzing comprises:

generating global node rank information; and

generating keyword-specific node rank information using the global node rank information as initial values for iterative processing, the keyword-specific node rank information being generated before receipt of the query.

5. The method of claim 2, wherein the combining the multiple initial rankings comprises combining based on user definable adjusting parameters that influence a normalization scheme, which differentiates between the multiple keywords, and a global-to-keyword weighting scheme, which differentiates between global node rank information and keyword-specific node rank information.

6. The method of claim 2, wherein the generating the multiple initial rankings comprises topologically sorting the labeled graph.

7. The method of claim 6, wherein the generating the multiple initial rankings comprises

identifying and removing cycles in the labeled graph to reduce the labeled graph into a directed acyclic graph (DAG) and a set of backward edges before doing keyword-specific calculation of the multiple initial rankings;

identifying a set of backnodes, which are nodes of the labeled graph from which the backward edges start; and

calculating node rank information in a bifurcated fashion such that calculation of the node rank information is split between (1) calculating DAG node rank information while ignoring the backward edges and (2) calculating backedges node rank information, due to the backward edges, using the identified backnodes.

8. The method of claim 2, wherein the digital information comprises a database having a structural relationship among the nodes defined by semantic contents of the database, and the generating the multiple initial rankings comprises optimizing calculation of the multiple initial rankings based on the structural relationship among the nodes.

9. The method of claim 2, wherein the digital information comprises a database having a structural relationship among the nodes defined by semantic contents of the database, and the generating the multiple initial rankings comprises setting initial conditions for iterative processing based on the semantic contents and stored values for a subset of the nodes.

10. The method of claim 1, wherein the analyzing comprises analyzing the digital information based on user definable calibrating parameters including the authority transfer rates assigned to the edges.

11. The method of claim 1, further comprising modeling a database system as the labeled graph, wherein the analyzing comprises searching the database system.

12. A system comprising:

an object rank module configured to generate multiple initial rankings corresponding to multiple query keywords, each of the multiple initial rankings indicating authority of nodes in a graph with respect to each respective query keyword individually; and

a query module configured to combine the multiple initial rankings in response to a query.

13. The system of claim 12, wherein the object rank module is configured to generate the multiple initial rankings based on an analysis of a flow of authority among the nodes along edges in the graph, the flow of authority being derived at least in part from different authority transfer rates assigned to the edges based on edge type schema information of the graph.

14. The system of claim 13, wherein the object rank module is configured to generate the multiple initial rankings by performing a random-surfer-type authority-based search using a base set consisting essentially of the nodes that contain a keyword of the query corresponding to each respective initial ranking being generated.

15. The system of claim 13, wherein the analysis generates keyword-specific node rank information using previously generated global node rank information as initial values for iterative processing.

16. The system of claim 13, wherein the query module is configured to combine the multiple initial rankings based on user definable adjusting parameters that influence a normalization scheme, which differentiates between the multiple query keywords, and a global-to-keyword weighting scheme, which differentiates between global node rank information and keyword-specific node rank information.

17. The system of claim 13, wherein the object rank module is configured to topologically sort the graph.

18. The system of claim 17, wherein the object rank module is configured to:

identify and remove cycles in the graph to reduce the graph into a directed acyclic graph (DAG) and a set of backward edges before doing keyword-specific calculation of the multiple initial rankings;

identify a set of backnodes; and

calculate node rank information in a bifurcated fashion such that calculation of the node rank information is split between (1) calculating DAG node rank information while ignoring the backward edges and (2) calculating backedges node rank information, due to the backward edges, using the identified backnodes.

19. The system of claim 13, wherein the graph represents a database having a structural relationship among the nodes defined by semantic contents of the database, and the object rank module is configured to optimize calculation of the multiple initial rankings based on the structural relationship among the nodes.

20. The system of claim 13, wherein the graph represents a database having a structural relationship among the nodes defined by semantic contents of the database, and the object rank module is configured to set initial conditions for iterative processing based on the semantic contents and stored values for a subset of the nodes.

21. The system of claim 13, wherein the analysis is based on user definable calibrating parameters including the authority transfer rates assigned to the edges.

22. A program operable to cause one or more machines to perform operations comprising:

analyzing digital information viewed as a labeled graph, including nodes and edges, based on a flow of authority among the nodes along the edges, the flow of authority being derived at least in part from different authority transfer rates assigned to the edges based on edge type schema information; and

generating a keyword-specific ranking of the nodes in response to a query, including at least one keyword, based on a result of the analyzing.

23. The program of claim 22, further comprising:

receiving the query, the query including multiple keywords;

wherein the analyzing the digital information comprises generating multiple initial rankings corresponding to the multiple keywords, each of the multiple initial rankings indicating authority of the nodes with respect to each respective keyword; and

wherein the generating the keyword-specific ranking comprises combining the multiple initial rankings.

24. The program of claim 23, wherein generating each of the multiple initial rankings comprises performing a random-surfer-type authority-based search of the digital information using a base set consisting essentially of the nodes that contain a keyword of the query corresponding to each respective initial ranking being generated.

25. The program of claim 23, wherein the analyzing comprises:

generating global node rank information; and

generating keyword-specific node rank information using the global node rank information as initial values for iterative processing, the keyword-specific node rank information being generated before receipt of the query.

26. The program of claim 23, wherein the combining the multiple initial rankings comprises combining based on user definable adjusting parameters that influence a normalization scheme, which differentiates between the multiple keywords, and a global-to-keyword weighting scheme, which differentiates between global node rank information and keyword-specific node rank information.

27. The program of claim 23, wherein the generating the multiple initial rankings comprises topologically sorting the labeled graph.

28. The program of claim 27, wherein the generating the multiple initial rankings comprises

identifying and removing cycles in the labeled graph to reduce the labeled graph into a directed acyclic graph (DAG) and a set of backward edges before doing keyword-specific calculation of the multiple initial rankings;

identifying a set of backnodes, which are nodes of the labeled graph from which the backward edges start; and

calculating node rank information in a bifurcated fashion such that calculation of the node rank information is split between (1) calculating DAG node rank information while ignoring the backward edges and (2) calculating backedges node rank information, due to the backward edges, using the identified backnodes.

29. The program of claim 23, wherein the digital information comprises a database having a structural relationship among the nodes defined by semantic contents of the database, and the generating the multiple initial rankings comprises optimizing calculation of the multiple initial rankings based on the structural relationship among the nodes.

30. The program of claim 23, wherein the digital information comprises a database having a structural relationship among the nodes defined by semantic contents of the database, and the generating the multiple initial rankings comprises setting initial conditions for iterative processing based on the semantic contents and stored values for a subset of the nodes.

31. The program of claim 22, wherein the analyzing comprises analyzing the digital information based on user definable calibrating parameters including the authority transfer rates assigned to the edges.

32. The program of claim 22, wherein the operations further comprise modeling a database system as the labeled graph, wherein the analyzing comprises searching the database system.