GFocus: User Focus-Based Graph Query Autocompletion

Peipei Yi*, Byron Choi, Zhiwei Zhang, Sourav S Bhowmick, Jianliang Xu

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review


Graph query autocompletion (gQAC) generates a small list of ranked query suggestions during the graph query formulation process in a visual environment. The current state-of-the-art of gQAC provides suggestions that are formed by adding subgraph increments to arbitrary places of an existing (partial) user query. However, according to the research results on human-computer interaction (HCI), humans can only interact with a small number of recent software artifacts in hand. Hence, many of such suggestions could be irrelevant. In this paper, we present the GFocus framework that exploits a novel notion of user focus of graph query formulation (or simply focus). Intuitively, the focus is the subgraph that a user is working on. We formulate locality principles inspired by the HCI research to automatically identify and maintain the focus. We propose novel monotone submodular ranking functions for generating popular and comprehensive query suggestions only at the focus. In particular, the query suggestions of GFocus have high result counts (when they are used as queries) and maximally cover the possible suggestions at the focus. We propose efficient algorithms and an index for ranking the suggestions. Our results show that GFocus saves 12-32 percent more mouse clicks and is 35× more efficient than the state-of-the-art competitor.

Original languageEnglish
Pages (from-to)1788-1802
Number of pages15
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number4
Publication statusPublished - 1 Apr 2022

Scopus Subject Areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

User-Defined Keywords

  • database usability
  • query autocompletion
  • Subgraph query


Dive into the research topics of 'GFocus: User Focus-Based Graph Query Autocompletion'. Together they form a unique fingerprint.

Cite this