Schema-Free In-Graph Indexing

• US 20180129690A1
• Filed: 11/04/2016
• Published: 05/10/2018
• 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
• Granted Patent: US 10,394,788 B2
• Time in Patent Office: Days
• 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;

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 said determined 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 vertices 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 the 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 attributed 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, wherein the one or more traversal paths comprise one or more data-to-index traversal paths.

11. The computer-implemented method of claim 1, wherein the one or more traversal paths comprise one or more index-to-index traversal paths.

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

storing the generated multi-dimensional indexes as one or more graphs.

13. 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;

correlate two or more of the created indexes, 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 traversal paths facilitate processing of the query; and

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

14. 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;

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 said determined traversal paths.

15. 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;

correlating, based on the query, two or more of the created single-dimension indexes, 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 traversal paths 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.

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

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

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

19. The computer-implemented method of claim 15, wherein the one or more traversal paths comprise one or more data-to-index traversal paths.

20. The computer-implemented method of claim 15, wherein the one or more traversal paths comprise one or more index-to-index traversal paths.