Scalable summarization of data graphs

• US 8,984,019 B2
• Filed: 11/20/2012
• Issued: 03/17/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): Morrison, Jay
• Assistant Examiner(s): Hoang, Ken
• Application Number:
  US13/682,245
• Publication Number:
  US 20140143280A1
• Time in Patent Office: 847 Days
• Field of Search: 707/E17.09, 707/E17.094, 707/999.002, 707/999.003, 707/999.1, 707/E17.012, 707/E17.014, 707/E17.017, 707/713, 707/723, 707/769, 707/803, 707/E17.001, 707/E17.005, 707/E17.032, 707/E17.044, 707/E17.046, 707/E17.108, 707/707, 707/737, 707/754, 707/755, 707/759, 707/792, 707/797, 707/798, 707/800, 707/802, 707/808, 707/811, 707/999.001, 707/999.004, 707/999.005, 707/999.101, 707/999.102, 715/853, 715/854, 715/763, 715/210, 715/229, 715/234, 715/255, 715/256, 715/760, 705/7.14, 705/7.17, 705/7.23, 705/32, 705/7.15, 705/7.16, 705/7.26, 705/7.27, 709/206, 709/201, 709/223, 709/224
• 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 method for summarizing resource description framework datasets, the method comprising:

creating a condensed view of the resource description framework dataset graph comprising a plurality of entity vertices, type vertices and keyword vertices connected by a plurality of predicate edges by combining entity, keyword and type vertices into a plurality of condensed vertices linked only by inter entity vertex predicate edges from the resource description framework dataset, the condensed view comprising a dataset graph;

removing entity information and keyword information from each condensed vertex and maintaining only type information in each condensed vertex;

grouping the plurality of condensed vertices by common type information;

splitting the condensed view of the resource description framework dataset graph into a plurality of partitions, each partition associated with a unique common type value selected from the type vertices and comprising a plurality of vertices and predicate edges connecting the vertices, splitting the condensed view of the resource description framework dataset graph comprising;

creating a plurality of predicate edge disjoint subgraphs by selecting condensed vertices on which to begin predicate edge disjoint graphs by group and exhausting all condensed vertices in a given group before advancing to a subsequent group, each subgraph beginning at a given condensed vertex and extending out a predetermined number of hops through the condensed view of the resource description framework, each partition comprising all subgraphs beginning at condensed vertices comprising common type information; and

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

2. The method of claim 1, wherein the step of splitting the resource description framework dataset graph into the plurality of partitions further comprises splitting the resource description framework dataset graph into a plurality of predicate edge disjoint partitions, a union of all predicate edge disjoint partitions comprising all vertices and predicate edges in the resource description framework dataset graph.

3. The method of claim 1, wherein defining the minimum set of common type based structures summarizing the plurality of partitions comprises creating a plurality of covering trees to represent the plurality of partitions by traversing each partition to create an associated covering tree comprising all distinct paths through the vertices of that partition.

4. The method of claim 3, wherein defining the minimum set of common type based structures summarizing the plurality of partitions further comprises:

extracting a core for each covering tree, the core comprising a minimum number of vertices for the covering tree; and

using the extracted core to represent the structure of that covering tree.

5. The method of claim 4, wherein defining the minimum set of common type based structures summarizing the plurality of partitions further comprises using homomorphisms among the plurality of covering trees to create the minimum set of common type based structures.

6. The method of claim 5, wherein using homomorphisms among the plurality of covering trees comprises:

sequentially comparing each extracted core to existing structures in the minimum set of common type based structures;

removing existing structures from the minimum set of common type based structures that represent a subset of a given extracted core being compared;

terminating comparison of a given extracted core upon determination that the given extracted core represents a subset of existing structures in the minimum set of common type based structures; and

adding a given extracted core to the minimum set of common type based structures upon completing a comparison of that given extracted core to all existing structures in the minimum set of common type based structures and determining that the given extract core is not a subset of any existing structure.

7. The method of claim 1, wherein the method further comprises:

maintaining a plurality of auxiliary indexes in combination with the minimum set of common type based structures; and

using the plurality of auxiliary indexes to recreate the resource description framework dataset graph from the minimum set of common type based structures and the plurality of partitions.

8. The method of claim 7, 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.

9. A non-transitory computer-readable storage medium containing a computer-readable code that when read by a computer causes the computer to perform a method for summarizing resource description framework datasets, the method comprising:

splitting a resource description framework dataset graph comprising a plurality of entity vertices, type vertices and keyword vertices connected by a plurality of predicate edges into a plurality of partitions, each partition associated with a unique common type value selected from the type vertices and comprising a plurality of vertices and predicate edges connecting the vertices; and

defining a minimum set of common type based structures summarizing the plurality of partitions, wherein defining the minimum set of common type based structures summarizing the plurality of partitions comprises;

creating a plurality of covering trees to represent the plurality of partitions by traversing each partition to create an associated covering tree comprising all distinct paths through the vertices of that partition;

extracting a core for each covering tree, the core comprising a minimum number of vertices for the covering tree;

using the extracted core to represent the structure of that covering tree; and

using homomorphisms among the plurality of covering trees to create the minimum set of common type based structures, wherein using homomorphisms among the plurality of covering trees comprises;

sequentially comparing each extracted core to existing structures in the minimum set of common type based structures;

removing existing structures from the minimum set of common type based structures that represent a subset of a given extracted core being compared;

terminating comparison of a given extracted core upon determination that the given extracted core represents a subset of existing structures in the minimum set of common type based structures; and

adding a given extracted core to the minimum set of common type based structures upon completing a comparison of that given extracted core to all existing structures in the minimum set of common type based structures and determining that the given extract core is not a subset of any existing structure.

10. The non-transitory computer-readable storage medium of claim 9, wherein the step of splitting the resource description framework dataset graph into the plurality of partitions further comprises splitting the resource description framework dataset graph into a plurality of predicate edge disjoint partitions, a union of all predicate edge disjoint partitions comprising all vertices and predicate edges in the resource description framework dataset graph.

11. The non-transitory computer-readable storage medium of claim 9, wherein the method further comprises:

creating a condensed view of the resource description framework dataset graph by combining entity, keyword and type vertices into a plurality of condensed vertices linked only by inter entity vertex predicate edges from the resource description framework dataset, the condensed view comprising a dataset graph; and

removing entity information and keyword information from each condensed vertex and maintaining only type information in each condensed vertex.

12. The non-transitory computer-readable storage medium of claim 11, wherein splitting the resource description framework dataset graph into the plurality of partitions further comprises splitting the condensed view of the resource description framework data graph into the plurality of partitions.

13. The non-transitory computer-readable storage medium of claim 12, wherein splitting the condensed view of the resource description framework dataset graph comprises creating a plurality of predicate edge disjoint subgraphs, each subgraph beginning at a given condensed vertex and extending out a predetermined number of hops through the condensed view of the resource description framework, each partition comprising all subgraphs beginning at condensed vertices comprising common type information.

14. The non-transitory computer-readable storage medium of claim 13, wherein:

the method further comprises grouping the plurality of condensed vertices by common type information; and

creating the plurality of predicate edge disjoint subgraphs further comprises selecting condensed vertices on which to begin predicate edge disjoint graphs by group, exhausting all condensed vertices in a given group before advancing to a subsequent group.

15. The non-transitory computer-readable storage medium of claim 9, wherein the method further comprises:

maintaining a plurality of auxiliary indexes in combination with the minimum set of common type based structures; and

using the plurality of auxiliary indexes to recreate the resource description framework dataset graph from the minimum set of common type based structures and the plurality of partitions.

16. The non-transitory computer-readable storage medium of claim 15, 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.

17. A method for summarizing resource description framework datasets, the method comprising:

creating a condensed view of a resource description framework dataset graph comprising a plurality of entity vertices, type vertices and keyword vertices connected by a plurality of predicate edges by combining entity, keyword and type vertices into a plurality of condensed vertices linked only by inter entity vertex predicate edges from the resource description framework dataset;

removing entity information and keyword information from each condensed vertex and maintaining only type information in each condensed vertex;

grouping the plurality of condensed vertices by common type information;

selecting condensed vertices sequentially by group;

creating a plurality of predicate edge disjoint subgraphs, each subgraph beginning at a given condensed vertex within a given group and extending out a predetermined number of hops through the condensed view of the resource description framework;

defining a plurality of partitions, each partition comprising all subgraphs beginning at condensed vertices comprising common type information;

creating a plurality of covering trees to represent the plurality of partitions by traversing each partition to create an associated covering tree comprising all distinct paths through the vertices of that partition;

extracting a core for each covering tree, the core comprising a minimum number of vertices for the covering tree;

using homomorphisms among the plurality of covering trees to creating a minimum set of common type based structures summarizing the plurality of partitions; and

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