PRAGUE: Towards blending practical visual subgraph query formulation and query processing

Changjiu Jin*, Sourav S. Bhowmick, Byron Choi, Shuigeng Zhou

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

15 Citations (Scopus)

Abstract

In a previous paper, we laid out the vision of a novel graph query processing paradigm where instead of processing a visual query graph after its construction, it interleaves visual query formulation and processing by exploiting the latency offered by the GUI to filter irrelevant matches and prefetch partial query results [8]. Our first attempt at implementing this vision, called GBLENDER [8], shows significant improvement in system response time (SRT) for sub graph containment queries. However, GBLENDER suffers from two key drawbacks, namely inability to handle visual sub graph similarity queries and inefficient support for visual query modification, limiting its usage in practical environment. In this paper, we propose a novel algorithm called PRAGUE (Practical visu Al Graph QUery Blender), that addresses these limitations by exploiting a novel data structure called spindle-shaped graphs (SPIG). A SPIG succinctly records various information related to the set of super graphs of a newly added edge in the visual query fragment. Specifically, PRAGUE realizes a unified visual framework to support SPIG-based processing of modification-efficient sub graph containment and similarity queries. Extensive experiments on real-world and synthetic datasets demonstrate effectiveness of PRAGUE.

Original languageEnglish
Title of host publicationProceedings - 2012 IEEE 28th International Conference on Data Engineering
PublisherIEEE
Pages222-233
Number of pages12
ISBN (Electronic)9780769547473
ISBN (Print)9781467300421
DOIs
Publication statusPublished - Apr 2012
Event28th IEEE International Conference on Data Engineering, ICDE 2012 - Arlington, VA, United States
Duration: 1 Apr 20125 Apr 2012
https://ieeexplore.ieee.org/xpl/conhome/6226952/proceeding

Publication series

NameProceedings - International Conference on Data Engineering
PublisherIEEE
ISSN (Print)1084-4627
ISSN (Electronic)2375-026X

Conference

Conference28th IEEE International Conference on Data Engineering, ICDE 2012
Country/TerritoryUnited States
CityArlington, VA
Period1/04/125/04/12
Internet address

Scopus Subject Areas

  • Software
  • Signal Processing
  • Information Systems

Fingerprint

Dive into the research topics of 'PRAGUE: Towards blending practical visual subgraph query formulation and query processing'. Together they form a unique fingerprint.

Cite this