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 input query comprising subject nodes, object nodes and a set of predicate edges; partitioning the plurality of input queries by: identifying a plurality of groups of input queries, each group of input queries comprising input queries from the plurality of input queries; determining a Jaccard similarity for the sets of predicates edges for queries in each one of a plurality of potential groups of input queries; and including in the plurality of groups of input queries only those potential groups of input queries where the Jaccard similarity indicates a substantial overlap in the sets of predicate edges associated with the input queries in a given group of input queries; and rewriting queries in each group from a first type of query that selects results based on a set of triple patterns to a second type of query that selects results based on the set of triple patterns in combination with at least one set of optional triple patterns by merging queries in each group of queries having structurally similar sub-queries using hierarchical clustering to generate a plurality of query clusters, each query cluster comprising the second type of query.