Scalable summarization of data graphs

摘要

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.

主权项

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; andone 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; anda minimum set of common type based structures summarizing the plurality of partitions.