Blending visual subgraph similarity query formulation and query processing on large graphs

• Main Author: Ho, Hoang Hung.
• Other Authors: Sourav Saha Bhowmick
• Format: Final Year Project
• Language: English
• Published: 2011
• Subjects: DRNTU::Engineering::Computer science and engineering
• Online Access: http://hdl.handle.net/10356/44869
• Institution: Nanyang Technological University

Recently, a novel graph query processing paradigm is proposed and realized in a system called GBLENDER++. It interleaves visual query graph formulation and processing by exploiting the latency offered by the GUI to remove false matches and prefetch partial results. The system can handle both exact and similar subgraph matching. This interleaving results in improvement in system response time. However, GBLENDER++ cannot be applied to databases consisting of large graphs, graphs that have thousands of vertices and edges. In this report, we present a method that addresses this limitation by partitioning the large data graph into many smaller graphs, called basic graph. GBLENDER++ method can then be utilized on these basic graphs in the same way as normal small-graph databases. Matches in the original large graph that belong to many basic graphs are detected by combining adjacent basic graphs together. The combination process is governed by some rules to ensure effectiveness. Real datasets of different size and parameter values as well as queries of different sizes are used to evaluate the efficiency and scalability of the method. We also evaluate its performance against SAPPER, another approximate subgraph matching technique.