What is Graph Search? A unified definition [6](in the name of graph matching) Given a pattern graph Gp and a data graph G check whether G."matches"G, and identify all"matched subgraphs Remarks Two classes of queries Boolean queries(Yes or No) Functional queries, which may use Boolean queries as a subroutine Graphs contain a set of nodes and a set of edges, typically with labels Pattern graphs are typically small( e.g., 10), but data graphs are usually huge(e.g, 108)What is Graph Search? 9 A unified definition [6] (in the name of graph matching): Remarks: • Given a pattern graph Gp and a data graph G: – check whether Gp ‘‘matches’’ G; and – identify all ‘‘matched’’ subgraphs. – Two classes of queries: – Boolean queries (Yes or No) – Functional queries, which may use Boolean queries as a subroutine – Graphs contain a set of nodes and a set of edges, typically with labels – Pattern graphs are typically small (e.g., 10), but data graphs are usually huge (e.g., 108 )