Scalable summarization of data graphs

• US 8,977,650 B2
• Filed: 11/21/2012
• Issued: 03/10/2015
• Est. Priority Date: 11/20/2012
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Duan, Songyun, Fokoue-Nkoutche, Achille Belly, Kementsietsidis, Anastasios, Le, Wangchao, Li, Feifei, Srinivas, Kavitha
• Primary Examiner(s): Beausoliel, Jr., Robert
• Assistant Examiner(s): HOANG, HAU HAI
• Application Number:
  US13/683,057
• Publication Number:
  US 20140143281A1
• Time in Patent Office: 839 Days
• Field of Search: None
• US Class Current: 707/798
• CPC Class Codes: G06F 16/211 Schema design and management

Abstract

Keyword searching is used to explore and search large Resource Description Framework datasets having unknown or constantly changing structures. A succinct and effective summarization is built from the underlying resource description framework data. Given a keyword query, the summarization lends significant pruning powers to exploratory keyword searches and leads to much better efficiency compared to previous work. The summarization returns exact results and can be updated incrementally and efficiently.

Claims

1. A system for summarizing resource description framework datasets, the system comprising:

a computer in communication with a network; and

a database in communication with the computer, the database comprising;

a resource description framework dataset graph comprising entity vertices associated with data accessible across the network, type vertices associated with the entity vertices, keyword vertices associated with the entity vertices and a plurality of predicate edges connecting pairs of entity vertices, type vertices and keyword vertices;

a plurality of partitions, each partition comprising;

a portion of the vertices and predicate edges from the resource description framework dataset graph; and

one or more predicate edge disjoint subgraphs, each subgraph comprising a given condensed vertex and any additional condensed vertices extending out a predetermined number of hops from the given condensed vertex, the condensed vertices linked only by inter entity vertex predicate edges from the resource description framework dataset; and

a minimum set of common type based structures summarizing the plurality of partitions.

2. The system of claim 1, wherein the plurality of partitions further comprises a plurality of predicate edge disjoint partitions, a union of all predicate edge disjoint partitions comprising the resource description framework dataset graph.

3. The system of claim 1, wherein the database further comprises a condensed view of the resource description framework dataset graph, the condensed view comprising a plurality of condensed vertices linked only by inter entity vertex predicate edges from the resource description framework dataset, each condensed vertex associated with an entity vertex in the resource description framework dataset graph and comprising only type information from a given type vertex associated with that entity vertex.

4. The system of claim 3, wherein each partition in the plurality of partitions further comprises a portion of the condensed vertices and the inter entity vertex predicate edges from the condensed view of the resource description framework data graph.

5. The system of claim 1, wherein the given condensed vertices from which the predicate edge disjoint subgraphs in a given partition are initiated comprise common type information.

6. The system of claim 1, wherein the minimum set of common type based structures summarizing the plurality of partitions comprises a plurality of covering trees representing the plurality of partitions, each covering tree comprising all distinct paths through the vertices of the partitions.

7. The system of claim 6, wherein each covering tree comprises a core, the core comprising a minimum number of vertices for the covering tree.

8. The system of claim 7, wherein each core in the plurality of covering trees cores in the minimum set of common type based structures represents a superset of other covering tree cores having common type based information that are not include in the minimum set of common type based structures.

9. The system of claim 1, wherein the database further comprises a plurality of auxiliary indexes in combination with the minimum set of common type based structures, the plurality of auxiliary indexes sufficient to recreate the resource description framework dataset graph from the minimum set of common type based structures and the plurality of partitions.

10. The system of claim 9, wherein the plurality of auxiliary indexes comprises a first index comprising an identification of portals in each partition, a second index mapping each partition to a covering tree associated with that partition and a third index mapping data nodes in each partition to summary nodes in the minimum set of common type based structures.

11. A system for summarizing resource description framework datasets, the system comprising:

a computer in communication with a network; and

a database in communication with the computer, the database comprising;

a resource description framework dataset graph comprising entity vertices associated with data accessible across the network, type vertices associated with the entity vertices, keyword vertices associated with the entity vertices and a plurality of predicate edges connecting pairs of entity vertices, type vertices and keyword vertices;

a plurality of partitions, each partition comprising a portion of the vertices and predicate edges from the resource description framework dataset graph; and

a minimum set of common type based structures summarizing the plurality of partitions; and

a plurality of auxiliary indexes in combination with the minimum set of common type based structures, the plurality of auxiliary indexes sufficient to recreate the resource description framework dataset graph from the minimum set of common type based structures and the plurality of partitions.

12. The system of claim 11, wherein the plurality of partitions further comprises a plurality of predicate edge disjoint partitions, a union of all predicate edge disjoint partitions comprising the resource description framework dataset graph.

13. The system of claim 11, wherein the database further comprises a condensed view of the resource description framework dataset graph, the condensed view comprising a plurality of condensed vertices linked only by inter entity vertex predicate edges from the resource description framework dataset, each condensed vertex associated with an entity vertex in the resource description framework dataset graph and comprising only type information from a given type vertex associated with that entity vertex.

14. The system of claim 13, wherein each partition in the plurality of partitions further comprises a portion of the condensed vertices and the inter entity vertex predicate edges from the condensed view of the resource description framework data graph.

15. The system of claim 14, wherein each partition further comprises one or more predicate edge disjoint subgraphs, each subgraph comprising a given condensed vertex and any additional condensed vertices extending out a predetermined number of hops through the condensed view of the resource description framework from the given condensed vertex.

16. The system of claim 15, wherein the given condensed vertices from which the predicate edge disjoint subgraphs in a given partition are initiated comprise common type information.

17. The system of claim 11, wherein the minimum set of common type based structures summarizing the plurality of partitions comprises a plurality of covering trees representing the plurality of partitions, each covering tree comprising all distinct paths through the vertices of the partitions.

18. The system of claim 17, wherein each covering tree comprises a core, the core comprising a minimum number of vertices for the covering tree and each core in the plurality of covering trees cores in the minimum set of common type based structures represents a superset of other covering tree cores having common type based information that are not include in the minimum set of common type based structures.

19. The system of claim 11, wherein the plurality of auxiliary indexes comprises a first index comprising an identification of portals in each partition, a second index mapping each partition to a covering tree associated with that partition and a third index mapping data nodes in each partition to summary nodes in the minimum set of common type based structures.

20. A system for summarizing resource description framework datasets, the system comprising:

a computer in communication with a network; and

a database in communication with the computer, the database comprising;

a resource description framework dataset graph comprising entity vertices associated with data accessible across the network, type vertices associated with the entity vertices, keyword vertices associated with the entity vertices and a plurality of predicate edges connecting pairs of entity vertices, type vertices and keyword vertices;

a plurality of partitions, each partition comprising a portion of the vertices and predicate edges from the resource description framework dataset graph;

a minimum set of common type based structures summarizing the plurality of partitions;

a condensed view of the resource description framework dataset graph, the condensed view comprising a plurality of condensed vertices linked only by inter entity vertex predicate edges from the resource description framework dataset, each condensed vertex associated with an entity vertex in the resource description framework dataset graph and comprising only type information from a given type vertex associated with that entity vertex;

wherein each partition in the plurality of partitions further comprises;

a portion of the condensed vertices and the inter entity vertex predicate edges from the condensed view of the resource description framework data graph; and

one or more predicate edge disjoint subgraphs, each subgraph comprising a given condensed vertex and any additional condensed vertices extending out a predetermined number of hops through the condensed view of the resource description framework from the given condensed vertex.