Efficient Indexing Methods for Query Processing on Large Graphs PDF Download

Author: Yongjiang Liang
Publisher:
ISBN:
Category : Computer science
Languages : en
Pages : 112

Get Book Here

Book Description
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 ofquery workload information, $W = \{w_1, \ldots, w_n\}$, where $w_i \in 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\ (\textbf{W}orkload-\textbf{a}ware \textbf{S}ubgraph \textbf{Q}uerying), 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 $\mathcal{G} = \{g_1, g_2, \ldots, g_n\}$ and a query graph $q$, we aim to search the graph $g_i \in \mathcal{G}$ such that the graph edit distance between $g_i$ and $q$, GED$(g_i, q)$, is within a user-specified GED threshold, $\tau$. We propose a \emph{parameterized}, partition-based GED lower bound that can be instantiated into a series of tight lower bounds towards synergistically pruning false-positive graphs from $\mathcal{G}$ before costly GED computation is performed. We design an efficient, \emph{selectivity-aware} algorithm to partition graphs of $\mathcal{G}$ into highly selective subgraphs. They are further incorporated in a cost-effective, multi-layered indexing structure, \mlindex\ (\textbf{M}ulti-\textbf{L}ayered \textbf{I}ndex), for GED lower bound crosschecking and false-positive graph filtering with theoretical performance guarantees. In our third project, we consider the \textit{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 \emph{collective} pruning and querying capabilities for graph similarity search in a \textit{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 \emph{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.