01464nas a2200205 4500008004100000245005400041210005400095260002900149520085700178653001901035653002501054653002001079653002301099653002401122100001901146700002101165700002301186700001601209856003301225 2008 eng d00aGraph Summaries for Subgraph Frequency Estimation0 aGraph Summaries for Subgraph Frequency Estimation aTenerife, Spainc06/20083 aA fundamental problem related to graph structured databases is searching for substructures. One issue with respect to optimizing such searches is the ability to estimate the frequency of substructures within a query graph. In this work, we present and evaluate two techniques for estimating the frequency of subgraphs from a summary of the data graph. In the first technique, we assume that edge occurrences on edge sequences are position independent and summarize only the most informative dependencies. In the second technique, we prune small subgraphs using a valuation scheme that blends information about their importance and estimation power. In both techniques, we assume conditional independence to estimate the frequencies of larger subgraphs. We validate the effectiveness of our techniques through experiments on real and synthetic datasets.10aData summaries10aFrequency estimation10aGraph summaries10aRDF graph patterns10aRDF query optimizer1 aMaduko, Angela1 aAnyanwu, Kemafor1 aSchliekelman, Paul1 aSheth, Amit uhttp://knoesis.org/node/128201128nas a2200157 4500008004100000245005300041210005300094260004500147520049700192653016900689100001900858700002300877700002100900700001600921856003300937 2007 eng d00aEstimating the Cardinality of RDF Graph Patterns0 aEstimating the Cardinality of RDF Graph Patterns b16th World Wide Web Conference (WWW2007)3 aMost RDF query languages allow for graph structure search through a conjunction of triples which is typically processed using join operations. A key factor in optimizing joins is determining the join order which depends on the expected cardinality of intermediate results. This work proposes a pattern-based summarization framework for estimating the cardinality of RDF graph patterns. We present experiments on real world and synthetic datasets which confirm the feasibility of our approach.10aRDF and RDF graph patterns and RDF Semantic Summary and RDF Structural Summary and RDF Query processing and Statistical Summaries and Pattern Cardinality Estimation1 aMaduko, Angela1 aSchliekelman, Paul1 aAnyanwu, Kemafor1 aSheth, Amit uhttp://knoesis.org/node/1673