Please use this identifier to cite or link to this item:
Title: FLAG: towards graph query autocompletion for large graphs
Authors: Yi, Peipei
Li, Jianping
Choi, Byron
Bhowmick, Sourav S.
Xu, Jianliang
Keywords: Engineering::Computer science and engineering
Issue Date: 2022
Source: Yi, P., Li, J., Choi, B., Bhowmick, S. S. & Xu, J. (2022). FLAG: towards graph query autocompletion for large graphs. Data Science and Engineering, 7(2), 175-191.
Journal: Data Science and Engineering
Abstract: Graph query autocompletion (GQAC) takes a user’s graph query as input and generates top-k query suggestions as output, to help alleviate the verbose and error-prone graph query formulation process in a visual interface. To compose a target query with GQAC, the user may iteratively adopt suggestions or manually add edges to augment the existing query. The current state-of-the-art of GQAC, however, focuses on a large collection of small- or medium-sized graphs only. The subgraph features exploited by existing GQAC are either too small or too scarce in large graphs. In this paper, we present Flexible graph query autocompletion for LArge Graphs, called FLAG. We are the first to propose wildcard labels in the context of GQAC, which summarizes query structures that have different labels. FLAG allows augmenting users’ queries with subgraph increments with wildcard labels to form suggestions. To support wildcard-enabled suggestions, a new suggestion ranking function is proposed. We propose an efficient ranking algorithm and extend an index to further optimize the online suggestion ranking. We have conducted a user study and a set of large-scale simulations to verify both the effectiveness and efficiency of FLAG. The results show that the query suggestions saved roughly 50% of mouse clicks and FLAG returns suggestions in few seconds.
ISSN: 2364-1185
DOI: 10.1007/s41019-022-00182-8
Schools: School of Computer Science and Engineering 
Rights: © The Author(s) 2022. Open Access. This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SCSE Journal Articles

Files in This Item:
File Description SizeFormat 
s41019-022-00182-8.pdf2.03 MBAdobe PDFThumbnail

Citations 50

Updated on Feb 23, 2024

Page view(s)

Updated on Feb 27, 2024


Updated on Feb 27, 2024

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.