GBLENDER: Towards blending visual query formulation and query processing in graph databases
Download as PPTX, PDF
0 likes638 views
I created the slides for presenting the following paper in the class: http://dl.acm.org/citation.cfm?id=1807182
GBLENDER: Towards blending visual query formulation and query processing in graph databases
- 1. GBLENDER: Towards Blending Visual Query Formulation and Query Processing in Graph Databases Changjiu Jin et al. at SIGMOD 2010 Presented by: Abolfazl Asudeh CSE 6339 Spring 2013
- 2. Outline Motivation Goals and Contributions Preliminaries Indices Query Processing 2 4/12/2013
- 3. Motivation Formulating a graph(query) programming" skill 3 4/12/2013
- 4. Motivation Graph matching Subgraph Isomorphism NP- Complete 4 4/12/2013
- 5. Outline Motivation Goals and Contributions Preliminaries Indices Query Processing 5 4/12/2013
- 6. Goals and Contributions 1. Produce a visual interface to formulate a query by clicking-and-dragging items 6 4/12/2013
- 7. Goals and Contributions Improve System Response Time They blend Visual Query Construction and Query Processing Use the latency of Query production to process current part of query. Start query processing before the user hits the RUN button They assume user doesnt make mistake during the query formulation (doesnt UNDO) 7 4/12/2013
- 8. Challenges How to mix query construction and evaluation with MINIMAL DISK ACCESS How to Index the data How to make the pre-fetch processing transparent from the user 8 4/12/2013
- 9. Overview: Indexing action-aware frequent index (A2F) Use Preprocessing action-aware infrequent index (A2I) If the final query is infrequent, probe A2I 9 4/12/2013
- 10. Outline Motivation Goals and Contributions Preliminaries Indices Query Processing 10 4/12/2013
- 11. PRELIMINARIES Graph DB: A set of Graphs (V,E) Graph Fragment: a small sub-graph existing in graph databases or query graphs 11 4/12/2013
- 12. Example: Fragment samples in a chemical compound database 12 4/12/2013
- 13. PRELIMINARIES: Frequent Fragment A fragment is frequent if its support is not less than : the number of graphs in the data base e.g. if =0.1 and =10000 13 4/12/2013
- 14. PRELIMINARIES: Infrequent Fragment A fragment is frequent if its support is less than e.g. if =0.1 and =10000 14 4/12/2013
- 15. Discriminative Infrequent Fragment If all sub-graphs of a fragment are frequent but itself is infrequent 15 4/12/2013
- 16. Outline Motivation Goals and Contributions Preliminaries Indices Query Processing 16 4/12/2013
- 17. Indexing Because of the visual interface structure, the query size is grown by one in each step. The indexing has to (given a list of graphs that satisfy the fragment in Step ) to support efficient strategy for identifyingthe graphs that match the fragment 霞 (generated at Step + 1) 17 4/12/2013
- 18. A2F index Being able to fit the matches in the memory , Frequent indices are divide to Memory-Resident and Disk-Resident Smaller frequent fragments are processed more frequently in various visual queries Smaller fragments have more matches If |g|< (threshold) it is saved in memory (MF-index) otherwise it is saved in the disk (DF-index) 18 4/12/2013
- 19. MF index structure - example 19 4/12/2013
- 20. MF index structure - example 20 4/12/2013
- 21. MF index structure - example 21 4/12/2013
- 22. MF index structure - example 22 4/12/2013
- 23. DF-Index 23 4/12/2013
- 24. DF-Index 24 4/12/2013
- 25. A2I index Just Index the discriminative infrequent graphs For other infrequent graphs use sub-graph isomorphism test over its discriminative infrequent 25 4/12/2013
- 26. Outline Motivation Goals and Contributions Preliminaries Indices Query Processing 26 4/12/2013
- 27. GBlender Algorithm 27 4/12/2013
- 28. example 28 4/12/2013
- 29. example 29 4/12/2013
- 30. example 30 4/12/2013
- 31. example 31 4/12/2013
- 32. Thank you 32 4/12/2013