MECHANISMS FOR SEARCHING ENTERPRISE DATA GRAPHS

• US 20130218899A1
• Filed: 02/16/2012
• Published: 08/22/2013
• Est. Priority Date: 02/16/2012
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Raghavan, Nikhil, Murthy, Ravi, Naimat, Aman
• Granted Patent: US 8,682,932 B2
• Time in Patent Office: Days
• US Class Current: 707/741
• CPC Class Codes: G06F 16/156 Query results presentation
• CPC Class Codes: G06F 16/3328 using graphical result space presentation or visualisation
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

Highly relevant search results for unstructured queries are efficiently identified from normalized data. A server graphs relationships between each of the data objects. For each search term, the server identifies a candidate set of data objects mapped to the term. The server calculates priority scores for the candidate data objects based at least in part on one or more of: a link analysis of the graph; or an analysis of metadata describing structural constraints upon the candidate data objects. Based on the graph, the server identifies one or more search result subgraphs, each comprising at least one data object from each of the candidate sets. The server looks for subgraphs in an order that is based on the priority scores for the candidate data objects. The server may terminate its search early, in part because prioritizing the candidate data objects increases the likelihood of receiving relevant search results first.

Claims

1. A method comprising:

generating an index mapping data objects to terms associated with the data objects;

generating a graph describing relationships between each of the data objects;

receiving a search request comprising a plurality of search terms;

based on the index, for each particular term in the plurality of search terms, identifying a candidate set of data objects that are mapped to the particular term;

calculating priority scores for the data objects in the candidate sets based at least in part on one or more of;

a link analysis of the graph;

or

metadata describing structural constraints upon the data objects;

based on the graph, identifying one or more search result subgraphs, each comprising at least one data object from each of the candidate sets;

wherein identifying the one or more search result subgraphs comprises looking for subgraphs in an order that is based on the priority scores;

providing information indicating the one or more search result subgraphs in response to the search request;

wherein the method is performed by one or more computing devices.

2. The method of claim 1, further comprising terminating identifying the one or more search result subgraphs upon one or more of:

comparing a count of the identified one or more search result subgraphs with a maximum result set size;

or

determining that all search result subgraphs of a maximum depth have been identified;

wherein terminating identifying the one or more search result subgraphs occurs prior to examining the entire graph for search result subgraphs.

3. The method of claim 1, wherein a search result subtree comprises a root node that is a common ancestor to at least one data object from each of the candidate sets, and one or more branches of nodes comprising the at least one data object from each of the candidate sets.

4. The method of claim 1, wherein the data objects are normalized and the search request is unstructured.

5. The method of claim 1, further comprising identifying the relationships based on reference data associating certain data objects with other certain data objects.

6. The method of claim 1, wherein the priority scores are based on the link analysis of the graph, wherein the graph comprises nodes and edges, the nodes corresponding to data objects and the edges corresponding to the relationships, wherein at least some of the edges have different weights corresponding to different types of relationships that are represented by the edges.

7. The method of claim 6, wherein the weights of the edges are based on popularity data indicating how often each type of relationship is involved in at least a certain type of query.

8. The method of claim 1, further comprising revising the plurality of search terms prior to locating the candidate sets, based on or more of a spelling correction engine, an auto-complete engine, or a query reformulation engine.

9. The method of claim 1, wherein the priority scores are based on the link analysis of the graph, wherein the priority score for each particular data object is based at least in part on how many of the data objects depend upon the particular data object.

10. The method of claim 1, wherein the priority scores are based on the metadata, the method further comprising:

generating a metadata graph describing relationships between each metadata item of the metadata;

performing a link analysis of the metadata graph to calculate relationship scores for the metadata items;

calculating the priority score for each particular data object based in part on the relationship score of a particular metadata item corresponding to the particular data object.

11. The method of claim 1, wherein each data object is one of:

a document, a row of a table, or a markup language element.

12. The method of claim 1:

wherein identifying the one or more search result subgraphs comprises expanding each data object in each candidate set until a common ancestor is found;

wherein looking for subgraphs in an order that is based on the priority scores comprises selecting an order in which to expand the data objects based on the priority scores.

13. The method of claim 1, further comprising ranking the one or more search result subgraphs based on a combination of node weights and edge weights.

14. The method of claim 1, wherein the information indicating the one or more search result subgraphs in response to the search request is a set of flattened data objects based upon the one or more search result subgraphs.

15. The method of claim 1,

wherein calculating priority scores for the data objects in the candidate sets is based on both a link analysis of the graph, and metadata describing structural constraints upon the data objects;

wherein the link analysis is performed asynchronous to the search request; and

wherein the metadata is scored asynchronous to the search request.

16. One or more non-transitory computer-readable media storing instructions that, when executed by one or more computing-devices, cause performance of:

generating an index mapping data objects to terms associated with the data objects;

generating a graph describing relationships between each of the data objects;

receiving a search request comprising a plurality of search terms;

based on the index, for each particular term in the plurality of search terms, identifying a candidate set of data objects that are mapped to the particular term;

calculating priority scores for the data objects in the candidate sets based at least in part on one or more of;

a link analysis of the graph;

or

metadata describing structural constraints upon the data objects;

based on the graph, identifying one or more search result subgraphs, each comprising at least one data object from each of the candidate sets;

wherein identifying the one or more search result subgraphs comprises looking for subgraphs in an order that is based on the priority scores;

providing information indicating the one or more search result subgraphs in response to the search request.

17. The one or more non-transitory computer-readable media of claim 16, wherein the instructions, when executed by the one or more computing devices, further cause terminating identifying the one or more search result subgraphs upon one or more of:

comparing a count of the identified one or more search result subgraphs with a maximum result set size;

or

determining that all search result subgraphs of a maximum depth have been identified;

wherein terminating identifying the one or more search result subgraphs occurs prior to examining the entire graph for search result subgraphs.

18. The one or more non-transitory computer-readable media of claim 16, wherein a search result subtree comprises a root node that is a common ancestor to at least one data object from each of the candidate sets, and one or more branches of nodes comprising the at least one data object from each of the candidate sets.

19. The one or more non-transitory computer-readable media of claim 16, wherein the data objects are normalized and the search request is unstructured.

20. The one or more non-transitory computer-readable media of claim 16, wherein the instructions, when executed by the one or more computing devices, further cause identifying the relationships based on reference data associating certain data objects with other certain data objects.

21. The one or more non-transitory computer-readable media of claim 16, wherein the priority scores are based on the link analysis of the graph, wherein the graph comprises nodes and edges, the nodes corresponding to data objects and the edges corresponding to the relationships, wherein at least some of the edges have different weights corresponding to different types of relationships that are represented by the edges.

22. The one or more non-transitory computer-readable media of claim 21, wherein the weights of the edges are based on popularity data indicating how often each type of relationship is involved in at least a certain type of query.

23. The one or more non-transitory computer-readable media of claim 16, wherein the instructions, when executed by the one or more computing devices, further cause revising the plurality of search terms prior to locating the candidate sets, based on or more of a spelling correction engine, an auto-complete engine, or a query reformulation engine.

24. The one or more non-transitory computer-readable media of claim 16, wherein the priority scores are based on the link analysis of the graph, wherein the priority score for each particular data object is based at least in part on how many of the data objects depend upon the particular data object.

25. The one or more non-transitory computer-readable media of claim 16, wherein the priority scores are based on the metadata, the method further comprising:

generating a metadata graph describing relationships between each metadata item of the metadata;

performing a link analysis of the metadata graph to calculate relationship scores for the metadata items;

calculating the priority score for each particular data object based in part on the relationship score of a particular metadata item corresponding to the particular data object.

26. The one or more non-transitory computer-readable media of claim 16, wherein each data object is one of:

a document, a row of a table, or a markup language element.

27. The one or more non-transitory computer-readable media of claim 16:

wherein identifying the one or more search result subgraphs comprises expanding each data object in each candidate set until a common ancestor is found;

wherein looking for subgraphs in an order that is based on the priority scores comprises selecting an order in which to expand the data objects based on the priority scores.

28. The one or more non-transitory computer-readable media of claim 16, wherein the instructions, when executed by the one or more computing devices, further cause ranking the one or more search result subgraphs based on a combination of node weights and edge weights.

29. The one or more non-transitory computer-readable media of claim 16, wherein the information indicating the one or more search result subgraphs in response to the search request is a set of flattened data objects based upon the one or more search result subgraphs.

30. The one or more non-transitory computer-readable media of claim 16,

wherein calculating priority scores for the data objects in the candidate sets is based on both a link analysis of the graph, and metadata describing structural constraints upon the data objects;

wherein the link analysis is performed asynchronous to the search request; and

wherein the metadata is scored asynchronous to the search request.