Scalable multi-query optimization for SPARQL

1. A method for multi-query optimization, the method comprising:

identifying an input query set comprising a plurality of input queries over a given data set, each query comprising a graph pattern comprising at least one subject node, predicate edge and object node triple; and

clustering the plurality of input queries though 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 by using linegraphs, wherein clustering the plurality of inputs further comprises:

identifying a plurality of candidate merger inputs, each candidate merger input comprising an input query or an existing query cluster resulting from a previous pair-wise merging, a merger input graph pattern and a set of predicate edges contained in the merger input graph pattern; and

selecting a pair of merger inputs from the plurality of candidate merger inputs having a maximum overlap in the sets of predicate edges associated with the selected pair of merger inputs; and

each linegraph comprises:

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 a common subject node or 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.

2. The method of claim 1 , wherein selecting the pair of merger inputs further comprises selecting a pair of merger inputs having a highest Jaccard similarity between the associated sets of predicate edges.

3. The method of claim 1 , wherein clustering the plurality of inputs further comprises generating a linegraph for each merger input in the selected pair of merger inputs by:

creating a linegraph node for each predicate edge in the set of predicate edges associated with the merger input;

identifying pairs of linegraph nodes where for each identified pair of linegraph nodes the subject node or object node contained in the merger input graph pattern and connected by a first predicate in that identified pair of linegraph nodes and the subject node or object node contained in the merger input graph pattern and connected by a second predicate in that identified pair of linegraph nodes comprise a common variable; and

creating linegraph edges between each identified pair of linegraph nodes.

4. The method of claim 3 , wherein clustering the plurality of inputs further comprises:

reducing a number of nodes in the generated linegraphs; and

using structural similarities among the nodes and edges of the generated linegraphs to determine if the merger input graphs patterns associated with the linegraphs should be merged.

5. The method of claim 4 , wherein:

creating linegraph edges between each identified pair of linegraph nodes further comprises creating a pair of linegraph edges extending in opposite directions between each identified pair of linegraph nodes, each linegraph edge in a given pair of linegraph edges comprising the label that further identifies a location of the common variable in the subject nodes and object nodes contained in the merger input graph pattern and connected by the predicates in that identified pair of linegraph nodes and a direction in which that linegraph edge extends between the linegraph nodes; and

reducing the number of nodes in the generated linegraphs further comprises:

associating a set of labels with each linegraph node, each set of labels comprising labels for all linegraph edges associated with a given linegraph node;

identifying sets of labels having less than a pre-determined threshold level of similarity with all other sets of labels; and

removing the linegraph nodes associated with the identified sets of labels from the linegraphs.

6. The method of claim 4 , wherein:

creating linegraph edges between each identified pair of linegraph nodes further comprises creating a pair of linegraph edges extending in opposite directions between each identified pair of linegraph nodes, each linegraph edge in a given pair of linegraph edges comprising a label identifying a location of the common variable in the subject nodes and object nodes contained in the merger input graph pattern and connected by the predicates in that identified pair of linegraph nodes and a direction in which that linegraph edge extends between the linegraph nodes; and

using structural similarities among the nodes and edges of the generated linegraphs further comprises:

associating a set of labels with each linegraph node, each set of labels comprising labels for all linegraph edges associated with a given linegraph node;

creating pairs of linegraph nodes by selecting a linegraph node from each linegraph;

determining an intersection between sets of labels associated with each created pair of linegraph nodes; and

using all determined intersections to determine if the merger input graph patterns associated with the linegraphs should be merged.

7. The method of claim 3 , wherein clustering the plurality of inputs further comprises combining the linegraphs generated for each merger input into a single product graph comprising a unique node for each combination of nodes from the linegraphs.

8. The method of claim 7 , wherein combining the linegraphs further comprises:

identifying a pairs of nodes to combine into a given unique node in the single product graph by selecting a single node from each linegraph that corresponds to an identical predicate in the merger input graph pattern associated with the linegraph containing that identified single node; and

using only the identified pairs of nodes corresponding to identical predicates in the single product graph.

9. The method of claim 8 , wherein:

creating linegraph edges between each identified pair of linegraph nodes further comprises:

creating a pair of linegraph edges extending in opposite directions between each identified pair of linegraph nodes, each linegraph edge in a given pair of linegraph edges comprising a label identifying a location of the common variable in the subject nodes and object nodes contained in the merger input graph pattern and connected by the predicates in that identified pair of linegraph nodes and a direction in which that linegraph edge extends between the linegraph nodes; and

associating a set of labels with each linegraph node, each set of labels comprising labels for all linegraph edges associated with a given linegraph node; and

combining the linegraphs further comprises combining the set of labels for the identified pairs of nodes corresponding to identical predicates in the single product graph.

10. The method of claim 7 , wherein clustering the plurality of inputs further comprises:

identifying a largest clique in the single product graph, the largest clique comprising a largest combined graph pattern obtainable from the merger input graph patterns of the selected pair of merger inputs; and

using a size of the largest clique to determine if the selected pair of merger inputs comprise sufficient structural similarities.

11. The method of claim 10 , wherein clustering the plurality of inputs further comprises:

identifying a plurality of candidate combined graph patterns obtainable from the merger input graph patterns if the largest combined graph pattern exceeds a predetermined size, each candidate combined graph pattern smaller than the largest combined graph pattern and representing a unique overlapping of the merger input graph patterns;

associating a search cost optimization realization level with each candidate combined graph pattern;

selecting the candidate combined graph pattern representing a most cost effective balance of merger input graph pattern overlap and search cost optimization realization level; and

using the selected candidate combined graph pattern to generate the optimized query set.

12. The method of claim 1 , the method further comprising:

evaluating the optimized query set over the data set to generate a set of query answers; and

parsing and distributing the set of query answers to the input queries in the input query set.

13. The method of claim 1 , wherein the input queries comprise SPARQL queries and the data set comprises a resource description framework dataset.

14. The method of claim 1 , wherein:

each input query comprises a set of predicate edges contained in its graph pattern;

the method further comprises:

identifying input queries having sufficiently similar sets of predicate edges; and

partitioning the input query set into a plurality of groups, each group comprising input queries having sufficiently similar sets of predicate edges; and

clustering the plurality of inputs further comprises clustering the input queries from one of the plurality of groups.

15. The method of claim 14 , wherein identifying input queries having sufficiently similar sets of predicate edges further comprises using Jaccard similarity between sets of predicates edges to identify the input queries.

16. 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 multi-query optimization, the method comprising:

identifying an input query set comprising a plurality of input queries over a given data set, each query comprising a graph pattern comprising at least one subject node, predicate edge and object node triple; and

clustering the plurality of input queries though 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 by using linegraphs, wherein clustering the plurality of inputs further comprises:

identifying a plurality of candidate merger inputs, each candidate merger input comprising an input query or an existing query cluster resulting from a previous pair-wise merging, a merger input graph pattern and a set of predicate edges contained in the merger input graph pattern; and

selecting a pair of merger inputs from the plurality of candidate merger inputs having a maximum overlap in the sets of predicate edges associated with the selected pair of merger inputs; and

each linegraph comprises:

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 a common subject node or 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.

17. The non-transitory computer-readable medium of claim 16 , wherein clustering the plurality of inputs further comprises generating a linegraph for each merger input in the selected pair of merger inputs by:

creating a linegraph node for each predicate edge in the set of predicate edges associated with the merger input;

identifying pairs of linegraph nodes where for each identified pair of linegraph nodes the subject node or object node contained in the merger input graph pattern and connected by a first predicate in that identified pair of linegraph nodes and the subject node or object node contained in the merger input graph pattern and connected by a second predicate in that identified pair of linegraph nodes comprise a common variable; and

creating linegraph edges between each identified pair of linegraph nodes.

18. The non-transitory computer-readable storage medium of claim 17 , wherein clustering the plurality of inputs further comprises:

reducing a number of nodes in the generated linegraphs; and

using structural similarities among the nodes and edges of the generated linegraphs to determine if the merger input graphs patterns associated with the linegraphs should be merged.

19. The non-transitory computer-readable storage medium of claim 18 , wherein:

creating linegraph edges between each identified pair of linegraph nodes further comprises creating a pair of linegraph edges extending in opposite directions between each identified pair of linegraph nodes, each linegraph edge in a given pair of linegraph edges comprising the label that further identifies a location of the common variable in the subject nodes and object nodes contained in the merger input graph pattern and connected by the predicates in that identified pair of linegraph nodes and a direction in which that linegraph edge extends between the linegraph nodes; and

reducing the number of nodes in the generated linegraphs further comprises:

associating a set of labels with each linegraph node, each set of labels comprising labels for all linegraph edges associated with a given linegraph node;

identifying sets of labels having less than a pre-determined threshold level of similarity with all other sets of labels; and

removing the linegraph nodes associated with the identified sets of labels from the linegraphs; and

using structural similarities among the nodes and edges of the generated linegraphs further comprises:

associating a set of labels with each linegraph node, each set of labels comprising labels for all linegraph edges associated with a given linegraph node;

creating pairs of linegraph nodes by selecting a linegraph node from each linegraph;

determining an intersection between sets of labels associated with each created pair of linegraph nodes; and

using all determined intersections to determine if the merger input graph patterns associated with the linegraphs should be merged.

20. The non-transitory computer-readable storage medium of claim 17 , wherein clustering the plurality of inputs further comprises combining the linegraphs generated for each merger input into a single product graph comprising a unique node for each combination of nodes from the linegraphs by:

identifying a pairs of nodes to combine into a given unique node in the single product graph by selecting a single node from each linegraph that corresponds to an identical predicate in the merger input graph pattern associated with the linegraph containing that identified single node; and

using only the identified pairs of nodes corresponding to identical predicates in the single product graph.

21. The non-transitory computer-readable storage medium of claim 20 , wherein:

creating linegraph edges between each identified pair of linegraph nodes further comprises:

creating a pair of linegraph edges extending in opposite directions between each identified pair of linegraph nodes, each linegraph edge in a given pair of linegraph edges comprising a label identifying a location of the common variable in the subject nodes and object nodes contained in the merger input graph pattern and connected by the predicates in that identified pair of linegraph nodes and a direction in which that linegraph edge extends between the linegraph nodes; and

associating a set of labels with each linegraph node, each set of labels comprising labels for all linegraph edges associated with a given linegraph node; and

combining the linegraphs further comprises combining the set of labels for the identified pairs of nodes corresponding to identical predicates in the single product graph.

22. The non-transitory computer-readable storage medium of claim 20 , wherein clustering the plurality of inputs further comprises:

identifying a largest clique in the single product graph, the largest clique comprising a largest combined graph pattern obtainable from the merger input graph patterns of the selected pair of merger inputs; and

using a size of the largest clique to determine if the selected pair of merger inputs comprise sufficient structural similarities.

23. The non-transitory computer-readable storage medium of claim 22 , wherein clustering the plurality of inputs further comprises:

identifying a plurality of candidate combined graph patterns obtainable from the merger input graph patterns if the largest combined graph pattern exceeds a predetermined size, each candidate combined graph pattern smaller than the largest combined graph pattern and representing a unique overlapping of the merger input graph patterns;

associating a search cost optimization realization level with each candidate combined graph pattern;

selecting the candidate combined graph pattern representing a most cost effective balance of merger input graph pattern overlap and search cost optimization realization level; and

using the selected candidate combined graph pattern to generate the optimized query set.