In this colloquium, Claus Stadler will present the paper Effective Caching Techniques for Accelerating Pattern Matching Queries by Arash Fard, Satya Manda, Lakshmish Ramaswamy, and John A. Miller.
Abstract: Using caching techniques to improve response time of queries is a proven approach in many contexts. However, it is not well explored for subgraph pattern matching queries, mainly because of subtleties enforced by traditional pattern matching models. Indeed, efficient caching can greatly impact the query answering performance for massive graphs in any query engine whether it is centralized or distributed. This paper investigates the capabilities of the newly introduced pattern matching models in graph simulation family for this purpose. We propose a novel caching technique, and show how the results of a query can be used to answer the new similar queries according to the similarity measure that is introduced. Using large real-world graphs, we experimentally verify the efficiency of the proposed technique in answering subgraph pattern matching queries