GBLENDER: Towards blending visual query formulation and query processing in graph databases

Changjiu Jin*, Sourav S. Bhowmick, Xiaokui Xiao, James Cheng, Koon Kau CHOI

*Corresponding author for this work

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

25 Citations (Scopus)

Abstract

Given a graph database D and a query graph g, an exact subgraph matching query asks for the set S of graphs in D that contain g as a subgraph. This type of queries find important applications in several domains such as bioinformatics and chemoinformatics, where users are generally not familiar with complex graph query languages. Consequently, user-friendly visual interfaces which support query graph construction can reduce the burden of data retrieval for these users. Existing techniques for subgraph matching queries built on top of such visual framework are designed to optimize the time required in retrieving the result set S from D, assuming that the whole query graph has been constructed. This leads to sub-optimal system response time as the query processing is initiated only after the user has finished drawing the query graph. In this paper, we take the first step towards exploring a novel graph query processing paradigm, where instead of processing a query graph after its construction, it interleaves visual query construction and processing to improve system response time. To realize this, we present an algorithm called GBLENDER that prunes false results and prefetches partial query results by exploiting the latency offered by the visual query formulation. It employs a novel action-aware indexing scheme that exploits users' interaction characteristics with visual interfaces to support efficient retrieval. Extensive experiments on both real and synthetic datasets demonstrate the effectiveness and efficiency of our solution.

Original languageEnglish
Title of host publicationProceedings of the 2010 International Conference on Management of Data, SIGMOD '10
Pages111-122
Number of pages12
DOIs
Publication statusPublished - 2010
Event2010 International Conference on Management of Data, SIGMOD '10 - Indianapolis, IN, United States
Duration: 6 Jun 201011 Jun 2010

Publication series

NameProceedings of the ACM SIGMOD International Conference on Management of Data
ISSN (Print)0730-8078

Conference

Conference2010 International Conference on Management of Data, SIGMOD '10
Country/TerritoryUnited States
CityIndianapolis, IN
Period6/06/1011/06/10

Scopus Subject Areas

  • Software
  • Information Systems

User-Defined Keywords

  • frequent subgraphs
  • graph databases
  • graph indexing
  • infrequent subgraphs
  • prefetching
  • visual query formulation

Fingerprint

Dive into the research topics of 'GBLENDER: Towards blending visual query formulation and query processing in graph databases'. Together they form a unique fingerprint.

Cite this