{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T22:16:45Z","timestamp":1740176205852,"version":"3.37.3"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,4,16]],"date-time":"2022-04-16T00:00:00Z","timestamp":1650067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,4,16]],"date-time":"2022-04-16T00:00:00Z","timestamp":1650067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Hong Kong Research Grants Council","award":["C6030-18GF","12201119","12201518"],"award-info":[{"award-number":["C6030-18GF","12201119","12201518"]}]},{"DOI":"10.13039\/501100001747","name":"Hong Kong Baptist University","doi-asserted-by":"crossref","award":["IRCMS\/19-20\/H01"],"award-info":[{"award-number":["IRCMS\/19-20\/H01"]}],"id":[{"id":"10.13039\/501100001747","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Data Sci. Eng."],"published-print":{"date-parts":[[2022,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Graph query autocompletion (<jats:sc>GQAC<\/jats:sc>) takes a user\u2019s graph query as input and generates top-<jats:italic>k<\/jats:italic> 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 <jats:sc>GQAC<\/jats:sc>, the user may iteratively adopt suggestions or manually add edges to augment the existing query. The current state-of-the-art of <jats:sc>GQAC<\/jats:sc>, however, focuses on a large collection of small- or medium-sized graphs only. The subgraph features exploited by existing <jats:sc>GQAC<\/jats:sc> are either too small or too scarce in large graphs. In this paper, we present <jats:italic>Flexible<\/jats:italic> graph query autocompletion for LArge Graphs, called <jats:sc>FLAG<\/jats:sc>. We are the first to propose <jats:italic>wildcard labels<\/jats:italic> in the context of <jats:sc>GQAC<\/jats:sc>, which summarizes query structures that have different labels. <jats:sc>FLAG<\/jats:sc> allows augmenting users\u2019 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 <jats:sc>FLAG<\/jats:sc>. The results show that the query suggestions saved roughly 50% of mouse clicks and <jats:sc>FLAG<\/jats:sc> returns suggestions in few seconds.<\/jats:p>","DOI":"10.1007\/s41019-022-00182-8","type":"journal-article","created":{"date-parts":[[2022,4,16]],"date-time":"2022-04-16T16:03:03Z","timestamp":1650124983000},"page":"175-191","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["FLAG: Towards Graph Query Autocompletion for Large Graphs"],"prefix":"10.1007","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5515-1012","authenticated-orcid":false,"given":"Peipei","family":"Yi","sequence":"first","affiliation":[]},{"given":"Jianping","family":"Li","sequence":"additional","affiliation":[]},{"given":"Byron","family":"Choi","sequence":"additional","affiliation":[]},{"given":"Sourav S.","family":"Bhowmick","sequence":"additional","affiliation":[]},{"given":"Jianliang","family":"Xu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,4,16]]},"reference":[{"key":"182_CR1","doi-asserted-by":"crossref","unstructured":"Abiteboul S, Amsterdamer Y, Milo T, Senellart P (2012) Auto-completion learning for xml. In SIGMOD, pages 669\u2013672","DOI":"10.1145\/2213836.2213928"},{"key":"182_CR2","doi-asserted-by":"crossref","unstructured":"Bast H, Weber I (2006) Type less, find more: fast autocompletion search with a succinct index. In SIGIR, pages 364\u2013371","DOI":"10.1145\/1148170.1148234"},{"key":"182_CR3","first-page":"984","volume":"9","author":"SS Bhowmick","year":"2016","unstructured":"Bhowmick SS, Choi B, Dyreson CE (2016) Data-driven visual graph query interface construction and maintenance: challenges and opportunities. PVLDB 9:984\u2013992","journal-title":"PVLDB"},{"key":"182_CR4","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex optimization","author":"S Boyd","year":"2004","unstructured":"Boyd S, Vandenberghe L (2004) Convex optimization. Cambridge University Press, Cambridge"},{"key":"182_CR5","doi-asserted-by":"crossref","unstructured":"Braga D, Campi A, Ceri S (2005) XQBE (XQuery By Example): a visual interface to the standard xml query language. In TODS, pages 398\u2013443","DOI":"10.1145\/1071610.1071613"},{"key":"182_CR6","doi-asserted-by":"crossref","unstructured":"Comai S, Damiani E, Fraternali P (2001) Computing graphical queries over xml data. TOIS, pages 371\u2013430","DOI":"10.1145\/502795.502797"},{"key":"182_CR7","doi-asserted-by":"crossref","unstructured":"Cordella LP, Foggia P, Sansone C, Vento M (2004) A (sub)graph isomorphism algorithm for matching large graphs. PAMI, pages 1367\u20131372","DOI":"10.1109\/TPAMI.2004.75"},{"key":"182_CR8","first-page":"517","volume":"7","author":"M Elseidy","year":"2014","unstructured":"Elseidy M, Abdelhamid E, Skiadopoulos S, Kalnis P (2014) Grami: frequent subgraph and pattern mining in a single large graph. PVLDB 7:517\u2013528","journal-title":"PVLDB"},{"key":"182_CR9","doi-asserted-by":"crossref","unstructured":"Feng J, Li G (2012) Efficient fuzzy type-ahead search in xml data. TKDE, pages 882\u2013895","DOI":"10.1109\/TKDE.2010.264"},{"key":"182_CR10","doi-asserted-by":"crossref","unstructured":"Huang K, Chua H, Bhowmick SS, Choi B, Zhou S (2019) CATAPULT: data-driven selection of canned patterns for efficient visual graph query formulation. In SIGMOD, pages 900\u2013917","DOI":"10.1145\/3299869.3300072"},{"key":"182_CR11","doi-asserted-by":"crossref","unstructured":"Hung HH, Bhowmick SS, Truong BQ, Choi B, Zhou S (2013) QUBLE: blending visual subgraph query formulation with query processing on large networks. In SIGMOD, pages 1097\u20131100","DOI":"10.1145\/2463676.2463681"},{"key":"182_CR12","doi-asserted-by":"crossref","unstructured":"Ioannidis YE, Viglas S (2006) Conversational querying. Inf. Syst., pages 33\u201356","DOI":"10.1016\/j.is.2004.09.002"},{"key":"182_CR13","doi-asserted-by":"crossref","unstructured":"Jayaram N, Goyal S, Li C (2015) VIIQ: Auto-suggestion enabled visual interface for interactive graph query formulation. PVLDB, pages 1940\u20131951","DOI":"10.14778\/2824032.2824106"},{"key":"182_CR14","doi-asserted-by":"crossref","unstructured":"Jayaram N, Gupta M, Khan A, Li C, Yan X, Elmasri R (2014) GQBE: querying knowledge graphs by example entity tuples. In ICDE, pages 1250\u20131253","DOI":"10.1109\/ICDE.2014.6816753"},{"issue":"11","key":"182_CR15","first-page":"1250","volume":"8","author":"L Jiang","year":"2015","unstructured":"Jiang L, Nandi A (2015) Snaptoquery: providing interactive feedback during exploratory query specification. PVLDB 8(11):1250\u20131261","journal-title":"PVLDB"},{"key":"182_CR16","doi-asserted-by":"crossref","unstructured":"Leskovec J, Faloutsos C (2006) Sampling from large graphs. In KDD","DOI":"10.1145\/1150402.1150479"},{"key":"182_CR17","doi-asserted-by":"crossref","unstructured":"Li J, Cao Y, Ma S (2017) Relaxing graph pattern matching with explanations. In CIKM","DOI":"10.1145\/3132847.3132992"},{"key":"182_CR18","doi-asserted-by":"crossref","unstructured":"Li Y, Yu C, Jagadish HV (2008) Enabling schema-free xquery with meaningful query focus. VLDB J., pages 355\u2013377","DOI":"10.1007\/s00778-006-0003-4"},{"key":"182_CR19","doi-asserted-by":"crossref","unstructured":"Lin C, Lu J, Ling TW, Cautis B (2012) LotusX: a position-aware xml graphical search system with auto-completion. In ICDE, pages 1265\u20131268","DOI":"10.1109\/ICDE.2012.123"},{"key":"182_CR20","doi-asserted-by":"crossref","unstructured":"Marchionini G (2006) Exploratory search: from finding to understanding. Commun. ACM, pages 41\u201346","DOI":"10.1145\/1121949.1121979"},{"key":"182_CR21","doi-asserted-by":"crossref","unstructured":"McGregor JJ (1982) Backtrack search algorithms and the maximal common subgraph problem. Softw., Pract. Exper., pages 23\u201334","DOI":"10.1002\/spe.4380120103"},{"key":"182_CR22","doi-asserted-by":"crossref","unstructured":"Mottin D, Bonchi F, Gullo F (2015) Graph query reformulation with diversity. In KDD, pages 825\u2013834","DOI":"10.1145\/2783258.2783343"},{"key":"182_CR23","doi-asserted-by":"crossref","unstructured":"Mottin D, M\u00fcller E (2017) Graph exploration: From users to large graphs. In SIGMOD, pages 1737\u20131740","DOI":"10.1145\/3035918.3054778"},{"key":"182_CR24","doi-asserted-by":"crossref","unstructured":"Nandi A, Jagadish HV (2007) Assisted querying using instant-response interfaces. In SIGMOD, pages 1156\u20131158","DOI":"10.1145\/1247480.1247640"},{"key":"182_CR25","unstructured":"Nandi A, Jagadish HV (2007) Effective phrase prediction. In VLDB, pages 219\u2013230"},{"issue":"4","key":"182_CR26","first-page":"289","volume":"7","author":"A Nandi","year":"2013","unstructured":"Nandi A, Jiang L, Mandel M (2013) Gestural query specification. PVLDB 7(4):289\u2013300","journal-title":"PVLDB"},{"key":"182_CR27","doi-asserted-by":"crossref","unstructured":"Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functions - i. Math. Program., pages 265\u2013294","DOI":"10.1007\/BF01588971"},{"key":"182_CR28","doi-asserted-by":"crossref","unstructured":"Ng N, Yi P, Zhang Z, Choi B, Bhowmick SS, Xu J (2019) Fgreat: focused graph query autocompletion. In ICDE, pages 1956\u20131959","DOI":"10.1109\/ICDE.2019.00213"},{"key":"182_CR29","doi-asserted-by":"crossref","unstructured":"Pienta R, Hohman F, Tamersoy A, Endert A, Navathe SB, Tong H, Chau DH (2017) Visual graph query construction and refinement. In SIGMOD, pages 1587\u20131590","DOI":"10.1145\/3035918.3056418"},{"key":"182_CR30","first-page":"420","volume":"11","author":"S Sahu","year":"2017","unstructured":"Sahu S, Mhedhbi A, Salihoglu S, Lin J, \u00d6zsu MT (2017) The ubiquity of large graphs and surprising challenges of graph processing. PVLDB 11:420\u2013431","journal-title":"PVLDB"},{"issue":"13","key":"182_CR31","first-page":"2182","volume":"8","author":"M Vartak","year":"2015","unstructured":"Vartak M, Rahman S, Madden S, Parameswaran A, Polyzotis N (2015) Seedb: efficient data-driven visualization recommendations to support visual analytics. PVLDB 8(13):2182\u20132193","journal-title":"PVLDB"},{"issue":"5","key":"182_CR32","doi-asserted-by":"publisher","first-page":"973","DOI":"10.1007\/s00778-020-00601-0","volume":"29","author":"C Wang","year":"2020","unstructured":"Wang C, Xie M, Bhowmick SS, Choi B, Xiao X, Zhou S (2020) FERRARI: an efficient framework for visual exploratory subgraph search in graph databases. VLDB J 29(5):973\u2013998","journal-title":"VLDB J"},{"key":"182_CR33","first-page":"1774","volume":"6","author":"Y Wu","year":"2013","unstructured":"Wu Y, Yang S, Srivatsa M, Iyengar A, Yan X (2013) Summarizing answer graphs induced by keyword queries. PVLDB 6:1774\u20131785","journal-title":"PVLDB"},{"key":"182_CR34","doi-asserted-by":"crossref","unstructured":"Xiao C, Qin J, Wang W, Ishikawa Y, Tsuda K, Sadakane K (2013) Efficient error-tolerant query autocompletion. PVLDB, pages 373\u2013384","DOI":"10.14778\/2536336.2536339"},{"key":"182_CR35","unstructured":"Yan X, Han J (2002) gSpan: graph-based substructure pattern mining. In ICDM, pages 721\u2013724"},{"issue":"3","key":"182_CR36","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/s00778-017-0454-9","volume":"26","author":"P Yi","year":"2017","unstructured":"Yi P, Choi B, Bhowmick SS, Xu J (2017) Autog: a visual query autocompletion framework for graph databases. VLDB J 26(3):347\u2013372","journal-title":"VLDB J"},{"key":"182_CR37","doi-asserted-by":"crossref","unstructured":"Yi P, Li J, Choi B, Bhowmick SS, Xu J (2020) Gfocus: user focus-based graph query autocompletion. TKDE","DOI":"10.1109\/TKDE.2020.3002934"},{"key":"182_CR38","doi-asserted-by":"crossref","unstructured":"Zhang A, Goyal A, Kong W, Deng H, Dong A, Chang Y, Gunter CA, Han J (2015) adaqac: adaptive query auto-completion via implicit negative feedback. In SIGIR, pages 143\u2013152","DOI":"10.1145\/2766462.2767697"}],"container-title":["Data Science and Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41019-022-00182-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41019-022-00182-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41019-022-00182-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,12]],"date-time":"2022-05-12T17:09:20Z","timestamp":1652375360000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s41019-022-00182-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,16]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["182"],"URL":"https:\/\/doi.org\/10.1007\/s41019-022-00182-8","relation":{},"ISSN":["2364-1185","2364-1541"],"issn-type":[{"type":"print","value":"2364-1185"},{"type":"electronic","value":"2364-1541"}],"subject":[],"published":{"date-parts":[[2022,4,16]]},"assertion":[{"value":"26 April 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 January 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 February 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 April 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}