Fast Graph Query Processing Algorithms Using Dynamic Programming
김현준 · Seoul National University Open Repository (Seoul National University) · 2020
Over the last several decades, a great deal of efforts have been made to develop practical solutions for NP-hard graph query processing problems because of diverse graph data publicly available.Despite such efforts, the existing algorithms still show a limited scalability in handling large and/or many graphs.In this thesis we consider three important and well-known graph query processing problems, which are subgraph query processing, subgraph matching, and supergraph search.First, we propose fast algorithms for subgraph query processing and subgraph matching.We describe three advanced techniques including dynamic programming.Experiments on real-world and synthetic datasets show that our algorithms are faster than state-of-the-art subgrpah query processing and subgraph matching algorithms by up to orders of magnitude in terms of query processing time.Second, we develop a fast and scalable algorithm for the supergraph search problem.We use four novel techniques including dynamic programming.Extensive experiments with real datasets show that our approach outperforms i state-of-the-art algorithms by up to orders of magnitude in terms of indexing time and query processing time.