As the standard formalism and powerful abstraction of networked data, graphs have been used to model and interpret structured information from protein interaction and program dependence, to business coordination and Internet topology. The proliferation of graphs has sparked a growing interest in enabling efficient accessmethods and flexible, structure-aware querying capabilities on large graphs. In order to account for noisy and distorted information arising unavoidably in real-world graphs, and to virtually any graph management tasks, it is essential and highly desirable to enable locating user-specified graph patterns on large graphs. In this thesis, we worked on subgraph query and similarity search problems on large graphs. In our first project, we worked on subgraph query problem. We consider subgraph querying with the availability of query workload information, W = {w₁,...,wₙ}, where wᵢ ϵ W is a previously issued query with all its subgraph-isomorphic embeddings identified and cached beforehand. Given a new query q, our goal is to exploit W for subgraph query processing and optimization of q in g. We introduce a new, workload-aware subgraph querying framework, WaSQ (Workload-aware Subgraph Querying), built upon key insights that query workload can be effectively leveraged for subgraph query rewriting, search plan refinement, partial results reusing, and false-positive embedding filtering toward expediting the whole subgraph querying process. In our second project, we worked on the single-query based similarity search problem. Formally, given a graph database {G} = {g₁, g₂,..., gₙ} and a query graph q, we aim to search the graph gᵢ ϵ {G} such that the graph edit distance between gᵢ and q, GED(gᵢ, q), is within a user-specified GED threshold, τ. We propose a parameterized, partition-based GED lower bound that can be instantiated into a series of tight lower bounds towards synergistically pruning false-positive graphs from {G} before costly GED computation is performed. We design an efficient, selectivity-aware algorithm to partition graphs of {G} into highly selective subgraphs. They are further incorporated in a cost-effective, multi-layered indexing structure, ML-index (Multi-Layered Index), for GED lower bound crosschecking and false-positive graph filtering with theoretical performance guarantees. In our third project, we consider the multi-query optimization problem, where a set of graph similarity queries, modeled by the well-known graph edit distance (GED) constraint, are posed against a graph database. We examine a new approach to enhancing collective pruning and querying capabilities for graph similarity search in a multi-query scenario. In light of the key observation that relates varying-size frequent and rare subgraph patterns to (mis)matching partitions, we select in a principled way salient features to enable selectivity-aware, feature-based graph partitioning, leading to enhanced filtering capabilities for multi-query optimization. Furthermore, we propose multi-query grouping and ordering techniques to further speedup multi-query processing.
