Patent Document ID: 9542444
Application ID: 15008547

Base Claim:
1. A system for multi-query optimization over a given data set, the system comprising: a hardware memory comprising a database in communication with a network, the database comprising an input query set comprising a plurality of input queries over the given data set across the network, each input query comprising a graph pattern comprising at least one subject node, predicate edge and object node triple and a set of predicate edges contained in its graph pattern; and a computing system in communication with the database and the given dataset, the computing system comprising: a computer processor; a clustering module to cluster the plurality of input queries through incremental pair-wise merging based on structural similarities between graph patterns and query search cost optimization realized by a given merged graph pattern to generate an optimized query set comprising at least one query cluster; and a partitioning module to identify input queries having sufficiently similar sets of predicate edges and to partition the input query set into a plurality of groups, each group comprising input queries having sufficiently similar sets of predicate edges; wherein the clustering module clusters the plurality of input queries by using linegraphs, each linegraph comprising: linegraph nodes, each linegraph node corresponding to a given predicate edge in the input queries; linegraph edges between pairs of linegraph nodes that are associated with predicate edges sharing at least one of a common subject node and a common object node in the input queries; and a label associated with each linegraph edge and indicating a type of join between subject nodes and object nodes; and the clustering module is configured to cluster the input queries from one of the plurality of groups.

---

Claim 15:
15. The system of claim 1 , wherein partitioning module comprises a Jaccard similarity comparison module to identify input queries having sufficiently similar sets of predicate edges using Jaccard similarity between sets of predicates edges to identify the input queries.