Gregory Todd Williams Graph Summaries

From Semantic Portal Wiki

Presentation given at CSCI 6966 Advanced Semantic Web (Fall 2008) - Lesson 7

Local copy of paper: File:QpII-4.pdf

Presentation slides

• Speaker: Gregory Todd Williams
• Title: Graph Summaries for Subgraph Frequency Estimation
• Authors: Angela Maduko, Kemafor Anyanwu, Amit Sheth, Paul Schliekelman
• Conference: ESWC2008
• URL: http://www.eswc2008.org/final-pdfs-for-web-site/qpII-4.pdf
• Date of Presentation: 2008/10/09

Questions

ID	Question	Name	Answer
Gregory Todd Williams Graph Summaries Jesse Weaver	Consider Figures 8a-f. For MD-Tree, the worst case shown is lg(error)=25, which means that error=2^25=33,554,432. How is it that MD-Tree estimated a frequency that deviated from the actually frequency by about 33.5x10^6 when there aren't even that many nodes or edges in the SwetoDBLP dataset? (or did I read something wrong?) In Figures 8g-h, the worst case for P-Tree is similar and on an even smaller dataset (TOntoGen).	Jesse Weaver	The evaluation section is a mess. The axis labeling in figure 8 is unintelligible if, as you mention, the values are to be understood as lg(error) = ~25. Another issue in the evaluation is the (somewhat suspicious) use of a subset of SwetoDBLP that has only ~0.8 edges for every node (which seems like it might lead to a somewhat uninteresting graph).
Gregory Todd Williams Graph Summaries Joshua Shinavier 1	Is Example 2 correct? The edge type (5, 1, 4) appears three times in the patterns of Figure 4a, while it appears only twice in Figure 4b. Instead, edge type (6, 3, 2) appears once too often in Figure 4b, in place of (5, 1, 4).	Joshua Shinavier
Williams Khandelwal Summaries Joshua Taylor 1	This question is for two presentations, and maybe it can be discussed once both presentations have been given. The two papers both look at ways of summarizing a graph structure in order to quicken certain types of queries. I wonder if the presenters, or anyone else, has any thoughts about whether the techniques described in each of these papers might be applied to the problems described in the other, or whether some hybrid approach might be useful for some tasks.	Joshua A. Taylor

Attendees

Tim Lebo