文章介绍

图查询自动完成（GQAC）将用户的图查询作为输入，并生成前k个查询结果建议作为输出，以帮助减轻可视化界面中冗长且容易出错的图查询过程。要使用GQAC组合目标查询，用户可以迭代地采用建议或手动添加边以扩充现有查询。然而，当前最先进的GQAC方法只关注大量中小型图。现有GQAC方法所利用的子图特征在大图中要么太小，要么太少。对此，本文提出了用于大图的灵活图查询自动完成方法，简称为FLAG，框架如图1所示。本文首次在GQAC 的上下文中提出通配符标签，并总结了具有不同标签的查询结构。FLAG允许使用带有通配符标签的子图增量来扩展用户的查询以形成建议。为了支持启用通配符的建议，本文提出了一种新的建议排名功能，提出一种高效的排名算法并通过扩展索引来进一步优化在线建议排名。本文进行了用户研究和一组大规模模拟实验，以验证FLAG的有效性和效率。结果表明，查询建议节省了大约50%的鼠标点击，FLAG在几秒钟内返回建议。该论文在已有工作基础上的主要贡献如下： 

图1. FLAG : 大图的图查询自动完成

实验效果

本文采用了几种流行的指标来衡量建议的质量。其中，总利润指标（TPM） 量化了在可视化查询制定过程中采用建议所节省的鼠标点击百分比，是FLAG的质量指标。

本文研究了FLAG的主要参数对三个数据集CITESEER、WORDNET和TWITTER的影响。例如，表1展示了代表性的模拟的TPM结果。

表1. δmax改变对三个数据集TPM值的影响

表1显示了在三个数据集上具有各种δmax的Q5（即5条边的查询）的TPM值。结果表明，随着δmax的增加，质量将会下降。TPM显示FLAG在查询公式中节省大约53%的手动专业化。同时，WORDNET和TWITTER的结果与CITESEER的趋势相同。WORDNET和TWITTER的质量指标值低于CITESEER，因为WORDNET和TWITTER的作品数量相对较少。

图2. 默认设置下FLAG的平均响应时间(ART)

本文对在线FLAG处理的效率进行了详细评估。图2报告了默认设置下FLAG的平均响应时间（ART）。对于CITESEER，ART为3秒左右。对于TWITTER，本文获得了简短的ART，因为作品的数量相对较少。因此，FLAG的响应时间通常很短。

图3. 仅改变排名函数的α时FLAG的ART

图3展示了仅改变排名函数的α时FLAG的ART。将α范围从0到1，ART总是少于3.5s。同时，当α接近1时，ART会下降。α的值越高，GQAC过程更喜欢具有大专业化和小摘要的建议，这导致更新候选建议的摘要的时间更短。

图4. 仅改变用户指定的k时FLAG的ART

图4中报告了仅改变用户指定的k时FLAG的ART。本文将k设定为从10到50。k测试的最大值为50，对于常见的可视化界面来说已经足够大了。结果表明，ART随着k的增加而增加。当k小于20时，FLAG在5s内返回建议。当k达到50时，GQAC过程可能需要8s来提供建议。

图5. 仅改变目标查询大小|q|时FLAG的ART

图5展示了仅改变目标查询大小|q|时FLAG的ART。结果表明，对于最多8条边的查询，FLAG的自动完成过程在6秒内完成。查询大小|q|增加时，ART增加，主要是因为大型查询需要更多时间来生成更多候选建议，然后对它们进行排名。

结语

本文提出了FLAG模型，它利用通配符标签概念生成top-k查询建议，以帮助大型图的查询公式化。考虑到现有GQAC研究利用的图特征在大图中要么不存在要么很少见，本文建议为查询图和查询建议引入通配符标签，以允许更多的查询建议候选者。候选查询建议由一个新的排名函数进行排名，该函数考虑了该建议对现有查询的扩充程度以及它总结了多少其他建议。本文提出了有效的建议排名算法。本文的用户研究和实验验证了FLAG的有效性和效率。

作者简介

Peipei Yi，于2013年获得中国电子科技大学计算机科学学士学位，于2018年获得香港浸会大学计算机科学博士学位。毕业后就职于联想机器的数据科学家香港情报中心。研究兴趣包括图数据处理和图数据库可用性。

Jianping Li，网络工程师，于2013年获得哈尔滨工业大学电气和通信硕士学位。研究兴趣包括数据库系统的用户界面。

Byron Choi副教授，于2006年获得宾夕法尼亚大学计算机和信息科学博士学位，现为香港浸会大学数据库研究组的成员。研究方向包括图结构数据库，数据库安全，时间序列分析，数据库系统的用户界面和增量维护算法和视图更新等。

Sourav S. Bhowmick，南洋理工大学计算机科学与工程学院副教授，研究兴趣包括数据管理、数据分析、计算社会科学和计算系统生物学，在这些领域的主要会议发表了许多论文，例如SIGMOD、VLDB、ICDE、SIGKDD等国际会议。

徐建良教授，于2002年获得香港科技大学计算机科学博士学位，毕业后加入香港浸会大学计算机科学系，于1998年获得浙江大学计算机科学与工程学士学位，曾是宾夕法尼亚州立大学大学公园分校和复旦大学的访问学者。现为香港浸会大学区块链和金融科技实验室主任，并领导数据库研究小组。研究方向包括大数据、区块链、移动计算、数据安全和隐私。

期刊简介

Data Science and Engineering（DSE）是由中国计算机学会（CCF）主办、数据库专业委员会承办、施普林格 自然（Springer Nature）出版的Open Access期刊。为了迎合相关领域的快速发展需求，DSE致力于出版所有和数据科学与工程领域相关的关键科学问题与前沿研究热点，以大数据作为研究重点，征稿范畴主要包括4方面：（1）数据本身，（2）数据信息提取方法，（3）数据计算理论，和（4）用来分析与管理数据的技术和系统。

目前期刊已被EI、ESCI与SCOPUS收录，CiteScore 2021为6.4，在Computer Science Applications领域排名# 157/747（位列前21%）。稿件处理费由赞助商中新赛克（Sinovatio）承担，欢迎大家免费下载阅读期刊全文，并积极投稿。

论文原文链接：https://link.springer.com/article/10.1007/s41019-022-00182-8