bibtex
groups
eswc2008's BibTeX entry:
Graph Summaries for Subgraph Frequency Estimation
Proceedings of the 5th European Semantic Web Conference, 2008.
| Authors: | Angela Maduko and Kemafor Anyanwu and Amit Sheth and Paul Schliekelman |
| Editors: | Manfred Hauswirth and Manolis Koubarakis and Sean Bechhofer |
| URL: | http://data.semanticweb.org/conference/eswc/2008/papers/330 |
| Tags: | cardinality estimation graph query-processing-2 result subgraph summaries |
| Abstract: | Graphs are increasingly used to model data in many disciplines. Structure search which matches a query graph against a data graph, is a common information retrieval paradigm for graph structured data. A crucial factor in 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 based on 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 using experiments on real and synthetic datasets |
@inproceedings{maduko2008graph,
title = {Graph Summaries for Subgraph Frequency Estimation},
address = {Berlin, Heidelberg},
author = {Angela Maduko and Kemafor Anyanwu and Amit Sheth and Paul Schliekelman},
booktitle = {Proceedings of the 5th European Semantic Web Conference},
editor = {Manfred Hauswirth and Manolis Koubarakis and Sean Bechhofer},
month = {June},
publisher = {Springer Verlag},
series = {LNCS},
url = {http://data.semanticweb.org/conference/eswc/2008/papers/330},
year = {2008},
abstract = {Graphs are increasingly used to model data in many disciplines. Structure search which matches a query graph against a data graph, is a common information retrieval paradigm for graph structured data. A crucial factor in 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 based on 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 using experiments on real and synthetic datasets},
keywords = {cardinality estimation graph query-processing-2 result subgraph summaries }
}
address = {Berlin, Heidelberg},
author = {Angela Maduko and Kemafor Anyanwu and Amit Sheth and Paul Schliekelman},
booktitle = {Proceedings of the 5th European Semantic Web Conference},
editor = {Manfred Hauswirth and Manolis Koubarakis and Sean Bechhofer},
month = {June},
publisher = {Springer Verlag},
series = {LNCS},
url = {http://data.semanticweb.org/conference/eswc/2008/papers/330},
year = {2008},
abstract = {Graphs are increasingly used to model data in many disciplines. Structure search which matches a query graph against a data graph, is a common information retrieval paradigm for graph structured data. A crucial factor in 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 based on 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 using experiments on real and synthetic datasets},
keywords = {cardinality estimation graph query-processing-2 result subgraph summaries }