Schema-free in-graph indexing

• US 10,394,788 B2
• Filed: 11/04/2016
• Issued: 08/27/2019
• Est. Priority Date: 11/04/2016
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Jagannath, Srikanta B., Lakshminarasimhan, Sriram, Mehta, Sameep, Neelam, Sumit
• Primary Examiner(s): Le, Debbie M
• Application Number:
  US15/343,801
• Publication Number:
  US 20180129690A1
• Time in Patent Office: 1,026 Days
• Field of Search: None
• CPC Class Codes: G06F 16/211 Schema design and management
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/2453 Query optimisation

Abstract

Methods, systems, and computer program products for schema-free in-graph indexing are provided herein. A computer-implemented method includes creating multiple indexes directed to data within a knowledge graph; correlating two or more of the created indexes, thereby generating one or more multi-dimensional indexes; determining, based on a received query, one or more traversal paths within the data of the knowledge graph and the generated multi-dimensional indexes, wherein the traversal paths facilitate processing of the query; and outputting a response to the query based on the determined traversal paths.

Claims

1. A computer-implemented method, comprising:

creating multiple indexes directed to data within a knowledge graph, wherein each of the multiple indexes is created as a graph;

correlating at least a first created index and at least a second created index by linking one or more nodes of the first created index with one or more nodes of the second created index, thereby generating one or more multi-dimensional indexes;

determining, based on a received query, one or more traversal paths within the data of the knowledge graph and the generated multi-dimensional indexes, wherein the one or more traversal paths comprise one or more data-to-index traversal paths and facilitate processing of the query; and

outputting a response to the query based on said determined one or more traversal paths;

wherein the steps are carried out by at least one computing device.

2. The computer-implemented method of claim 1, wherein said creating comprises creating one or more indexes directed to one or more data attributes within the knowledge graph.

3. The computer-implemented method of claim 2, wherein the one or more data attributes within the knowledge graph comprise one or more data attributes associated with one or more nodes of the knowledge graph.

4. The computer-implemented method of claim 2, wherein the one or more data attributes within the knowledge graph comprise one or more data attributes associated with one or more edges of the knowledge graph.

5. The computer-implemented method of claim 1, wherein the created indexes comprise schema-free indexes.

6. The computer-implemented method of claim 1, wherein the root node of each created index comprises a representation of a range of values associated with a given data attribute.

7. The computer-implemented method of claim 6, wherein one or more sub-nodes of the root node comprise a narrower range of values associated with the given data attribute than the range associated with the root node.

8. The computer-implemented method of claim 1, wherein said creating comprises creating one or more indexes directed to one or more data paths within the knowledge graph.

9. The computer-implemented method of claim 1, comprising:

annotating the generated multi-dimensional indexes with one or more items of information related to the data within the multi-dimensional indexes.

10. The computer-implemented method of claim 1, comprising:

storing the generated multi-dimensional indexes within the knowledge graph.

11. A computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a device to cause the device to:

create multiple indexes directed to data within a knowledge graph, wherein each of the multiple indexes is created as a graph;

correlate at least a first created index and at least a second created index by linking one or more nodes of the first created index with one or more nodes of the second created index, thereby generating one or more multi-dimensional indexes;

determine, based on a received query, one or more traversal paths within the data of the knowledge graph and the generated multi-dimensional indexes, wherein the one or more traversal paths comprise one or more data-to-index traversal paths and facilitate processing of the query; and

output a response to the query based on said determined one or more traversal paths.

12. A system comprising:

a memory; and

at least one processor operably coupled to the memory and configured for;

creating multiple indexes directed to data within a knowledge graph, wherein each of the multiple indexes is created as a graph;

correlating at least a first created index and at least a second created index by linking one or more nodes of the first created index with one or more nodes of the second created index, thereby generating one or more multi-dimensional indexes;

determining, based on a received query, one or more traversal paths within the data of the knowledge graph and the generated multi-dimensional indexes, wherein the one or more traversal paths comprise one or more data-to-index traversal paths and facilitate processing of the query; and

outputting a response to the query based on said determined one or more traversal paths.

13. A computer-implemented method, comprising:

obtaining a query pertaining to data encompassed within a knowledge graph;

creating multiple single-dimension indexes directed to data within the knowledge graph, wherein each of the single-dimension indexes is created as a graph;

correlating, based on the query, two or more of the created single-dimension indexes by linking one or more nodes of at least a first created single-dimension index with one or more nodes of at least a second created single-dimension index, thereby generating one or more multi-dimensional indexes;

determining, based on the query, one or more traversal paths within the data of the knowledge graph and the generated multi-dimensional indexes, wherein the one or more traversal paths comprise one or more index-to-index traversal paths and facilitate identification of a response to the query; and

outputting the response to the query to at least one user;

wherein the steps are carried out by at least one computing device.

14. The computer-implemented method of claim 13, wherein the created single-dimension indexes comprise schema-free indexes.

15. The computer-implemented method of claim 13, wherein said creating comprises creating one or more single-dimension indexes directed to one or more data attributes within the knowledge graph.

16. The computer-implemented method of claim 13, wherein said creating comprises creating one or more single-dimension indexes directed to one or more data paths within the knowledge graph.