BOOMER: Blending visual formulation and processing of P-homomorphic queries on large networks

Yinglong Song, Huey Eng Chua, Sourav S. Bhowmick, Koon Kau CHOI, Shuigeng Zhou

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

6 Citations (Scopus)

Abstract

Visual graph query interfaces (a.k.a gui) make it easy for non-expert users to query graphs. Recent research has laid out and implemented a vision of a novel subgraph query processing paradigm where the latency offered by the gui is exploited to blend visual query construction and processing by generating and refining candidate result matches iteratively during query formulation. This paradigm brings in several potential benefits such as superior system response time (srt) and opportunities to enhance usability of graph databases. However, these early efforts focused on subgraph isomorphismbased graph queries where blending is performed by iterative edgeto-edge mapping. In this paper, we explore how this vision can be realized for more generic but complex 1-1 p-homomorphic (phom) queries introduced by Fan et al. A 1-1 p-hom query maps an edge of the query to paths in the data graph. We present a novel framework called Boomer for blending bounded 1-1 p-hom (bph) queries, a variant of 1-1 p-hom where the length of the path is bounded instead of arbitrary length. Our framework is based on a novel online, adaptive indexing scheme called cap index.We present two strategies for cap index construction, immediate and defermentbased, and show how they can be utilized to facilitate judicious interleaving of visual bph query formulation and query processing. Boomer is also amenable to modifications to a bph query during visual formulation. Experiments on real-world datasets demonstrate both efficiency and effectiveness of Boomer for realizing the visual querying paradigm on an important type of graph query.

Original languageEnglish
Title of host publicationSIGMOD 2018 - Proceedings of the 2018 International Conference on Management of Data
EditorsGautam Das, Christopher Jermaine, Ahmed Eldawy, Philip Bernstein
PublisherAssociation for Computing Machinery
Pages927-942
Number of pages16
ISBN (Electronic)9781450317436
DOIs
Publication statusPublished - 27 May 2018
Event44th ACM SIGMOD International Conference on Management of Data, SIGMOD 2018 - Houston, United States
Duration: 10 Jun 201815 Jun 2018

Publication series

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

Conference

Conference44th ACM SIGMOD International Conference on Management of Data, SIGMOD 2018
Country/TerritoryUnited States
CityHouston
Period10/06/1815/06/18

Scopus Subject Areas

  • Software
  • Information Systems

Fingerprint

Dive into the research topics of 'BOOMER: Blending visual formulation and processing of P-homomorphic queries on large networks'. Together they form a unique fingerprint.

Cite this