Please use this identifier to cite or link to this item:
Title: Blending visual subgraph similarity query formulation and query processing on large graphs
Authors: Ho, Hoang Hung.
Keywords: DRNTU::Engineering::Computer science and engineering
Issue Date: 2011
Abstract: 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.
Rights: Nanyang Technological University
Fulltext Permission: restricted
Fulltext Availability: With Fulltext
Appears in Collections:SCSE Student Reports (FYP/IA/PA/PI)

Files in This Item:
File Description SizeFormat 
  Restricted Access
3.38 MBAdobe PDFView/Open

Page view(s)

checked on Sep 22, 2020


checked on Sep 22, 2020

Google ScholarTM


Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.