FINDING PATTERNS IN A KNOWLEDGE BASE TO COMPOSE TABLE ANSWERS

• US 20150310073A1
• Filed: 04/29/2014
• Published: 10/29/2015
• Est. Priority Date: 04/29/2014
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chakrabarti, Kaushik, Chaudhuri, Surajit, Ding, Bolin, Yang, Mohan
• Application Number:
  US14/264,995
• Publication Number:
  US 20150310073A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases

Abstract

In general, the knowledge base table composer embodiments described herein provide table answers to keyword queries against one or more knowledge bases. Highly relevant patterns in a knowledge base are found for user-given keyword queries. These patterns are used to compose table answers. To this end, a knowledge base is modeled as a directed graph called a knowledge graph, where nodes represent entities in the knowledge base and edges represent the relationships among them. Each node/edge is labeled with a type and text. A pattern that is an aggregation of subtrees which contain all keywords in the texts and have the same structure and types on node/edges is sought. Patterns that are relevant to a query for a class can be found using a set of scoring functions. Furthermore, path-based indexes and various query-processing procedures can be employed to speed up processing.

Claims

1. A computer-implemented process for composing tables from a knowledge base using a keyword query, comprising:

receiving a keyword query for a table of data as an answer;

using patterns of structured data in a knowledge graph obtained from a knowledge base to create one or more tables with data relevant to the keyword query.

2. The computer-implemented process of claim 1 wherein the one or more tables are assembled from subtrees of the knowledge graph.

3. The computer-implemented process of claim 2 wherein assembling the tables from the sub-graphs of the knowledge graph further comprises:

grouping subtrees of the knowledge graph that are connected trees that have the same pattern and the same mapping of keywords to column names, table names and cell values of the same table.

4. A computer-implemented process for providing relevant tables in response to a keyword query, comprising:

receiving a keyword query;

obtaining a knowledge graph with nodes representing entities of different types and edges representing relationships between the entities from a knowledge base;

using keywords from the keyword query in the knowledge graph to find relevant subtrees in the knowledge graph;

aggregating a tree pattern from the set of valid subtrees with the same tree structures, entity types and edge types, and positions in the subtrees where keywords are matching; and

outputting the aggregated tree pattern as a table of joined entities where each row corresponds to a subtree.

5. The computer-implemented process of claim 4 wherein the knowledge graph is a directed graph wherein each node is an entity that is labeled with a text description of the value of the entity and its entity type, and wherein each edge is labeled with a text description of its edge type.

6. The computer-implemented process of claim 5 wherein multiple edges have the same edge type label.

7. The computer-implemented process of claim 5 wherein a subtree pattern relevant to a keyword query is found by finding a subtree that contains all keywords in a given keyword query in the text description of its node, node type or edge type.

8. The computer-implemented process of claim 7 further comprising aggregating a tree pattern from a set of valid subtrees with the same i) tree structures, ii) entity types and edge types and iii) positions in the subtrees where keywords are matching.

9. The computer-implemented process of claim 8 wherein the valid subtrees are scored to measure their relevance to the given keyword query.

10. The computer-implemented process of claim 9 wherein the relevance score of a tree pattern is an aggregation of relevance scores of valid subtrees that satisfy a tree pattern.

11. The computer-implemented process of claim 4 further comprising indexing path patterns that contain a keyword.

12. The computer-implemented process of claim 11 further comprising generating a pattern-first path index wherein the paths are sorted by patterns first and then paths, and wherein the following methods can be used to access the paths:

retrieving all path patterns for paths from a root node to a node or edge that contains a query keyword;

retrieving all path patterns for paths from a root node to a node or edge that contains a query keyword via a given path pattern;

retrieving all path patterns with a given path pattern that start at a root node and end at a node or edge containing a query keyword.

13. The computer-implemented process of claim 11 further comprising generating a root-first path index wherein the paths are sorted by root nodes first and then patterns, and wherein the following methods can be used to access the paths:

retrieving all root nodes that have paths that can reach a node or edge that contains a query keyword;

retrieving all patterns following which a root node can reach a node or an edge that contains a query keyword;

retrieving all paths that start at a root node and end at a node or edge that contains a query keyword;

retrieving all paths with a given pattern that start at a root node and end at a node or edge that contains a query keyword.

14. The computer-implemented process of claim 11 further comprising aggregating the indexes of path patterns of trees starting from some root and ending at a node/edge containing some keyword and following a certain pattern.

15. The computer-implemented process of claim 12 further comprising processing a keyword query by specifying the keyword or the path pattern and using a search procedure to retrieve the corresponding set of paths.

16. The computer-implemented process of claim 10 wherein the relevant tree patterns for a keyword query are found by:

enumerating combinations of root-leaf path patterns in tree patterns;

retrieving paths from the index for each path pattern; and

joining the retrieved paths together on the root node to get a set of subtrees satisfying each tree pattern.

17. The computer-implemented process of claim 10 wherein the relevant tree patterns for a keyword query are found by:

identifying all candidate root nodes using indexes;

enumerating all tree patterns containing a subtree with a given candidate root;

aggregating the enumerated tree patterns.

18. A system for creating tables from keyword queries, comprising:

a computing device;

a computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to;

obtain a knowledge graph in the form of a directed graph where nodes represent entities and edges represent the relationships among the entities;

find a pattern that is an aggregation of subtrees which contain all keywords of a keyword query and have the same structure and types on node and edges; and

convert the aggregation of subtrees into a table.

19. The computer-implemented process of claim 18 further comprising using scoring functions to find patterns that are relevant to the keyword query.

20. The computer-implemented process of claim 18 further comprising using path-based indexes to find the patterns.