Catapult: Data-driven selection of canned patterns for efficient visual graph query formulation

Kai Huang, Huey Eng Chua, Sourav S. Bhowmick, Koon Kau CHOI, Shuigeng Zhou

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

1 Citation (Scopus)

Abstract

Visual graph query interfaces (a.k.a gui) widen the reach of graph querying frameworks across different users by enabling non-programmers to use them. Consequently, several commercial and academic frameworks for querying a large collection of small- or medium-sized data graphs (e.g., chemical compounds) provide such visual interfaces. Majority of these interfaces expose a fixed set of canned patterns (i.e., small subgraph patterns) to expedite query formulation by enabling pattern-at-a-time in lieu of edge-at-a-time construction mode. Canned patterns to be displayed on a gui are typically selected manually based on domain knowledge. However, manual generation of canned patterns is labour intensive. Furthermore, these patterns may not sufficiently cover the underlying data graphs to expedite visual formulation of a wide range of subgraph queries. In this paper, we present a generic and extensible framework called Catapult to address these limitations. Catapult takes a data-driven approach to automatically select canned patterns, thereby taking a concrete step towards the vision of data-driven construction of visual query interfaces. Specifically, it first clusters the underlying data graphs based on their topological similarities and then summarize each cluster to create a cluster summary graph (csg). The canned patterns within a user-specified pattern budget are then generated from these csgs by maximizing coverage and diversity, and minimizing cognitive load of the patterns. Experimental study with real-world datasets and visual graph interfaces demonstrates the superiority of Catapult compared to traditional techniques.

Original languageEnglish
Title of host publicationSIGMOD 2019 - Proceedings of the 2019 International Conference on Management of Data
PublisherAssociation for Computing Machinery
Pages900-917
Number of pages18
ISBN (Electronic)9781450356435
DOIs
Publication statusPublished - 25 Jun 2019
Event2019 International Conference on Management of Data, SIGMOD 2019 - Amsterdam, Netherlands
Duration: 30 Jun 20195 Jul 2019

Publication series

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

Conference

Conference2019 International Conference on Management of Data, SIGMOD 2019
Country/TerritoryNetherlands
CityAmsterdam
Period30/06/195/07/19

Scopus Subject Areas

  • Software
  • Information Systems

Fingerprint

Dive into the research topics of 'Catapult: Data-driven selection of canned patterns for efficient visual graph query formulation'. Together they form a unique fingerprint.

Cite this