AutoG: a visual query autocompletion framework for graph databases

Peipei Yi*, Byron Koon Kau Choi, Sourav S. Bhowmick, Jianliang Xu

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

23 Citations (Scopus)
2 Downloads (Pure)


Composing queries is evidently a tedious task. This is particularly true of graph queries as they are typically complex and prone to errors, compounded by the fact that graph schemas can be missing or too loose to be helpful for query formulation. Despite the great success of query formulation aids, in particular, automatic query completion, graph query autocompletion has received much less research attention. In this paper, we propose a novel framework for subgraph query autocompletion (called AutoG). Given an initial query q and a user’s preference as input, AutoG returns ranked query suggestions Q as output. Users may choose a query from Q and iteratively apply AutoG to compose their queries. The novelties of AutoG are as follows: First, we formalize query composition. Second, we propose to increment a query with the logical units called c-prime features that are (i) frequent subgraphs and (ii) constructed from smaller c-prime features in no more than c ways. Third, we propose algorithms to rank candidate suggestions. Fourth, we propose a novel index called feature Dag (FDag) to optimize the ranking. We study the query suggestion quality with simulations and real users and conduct an extensive performance evaluation. The results show that the query suggestions are useful (saved roughly 40% of users’ mouse clicks), and AutoG returns suggestions shortly under a large variety of parameter settings.

Original languageEnglish
Pages (from-to)347-372
Number of pages26
JournalVLDB Journal
Issue number3
Early online date27 Jan 2017
Publication statusPublished - 1 Jun 2017

Scopus Subject Areas

  • Information Systems
  • Hardware and Architecture

User-Defined Keywords

  • Database usability
  • Graphs
  • Query autocompletion
  • Subgraph query


Dive into the research topics of 'AutoG: a visual query autocompletion framework for graph databases'. Together they form a unique fingerprint.

Cite this