1887
2022-09-03 00:05:46
2022-09-03
https://mp.weixin.qq.com/s/5yKFzDJdnqTPhZnaeWPCWQ
DSE精選文章
FLAG：一種面向大圖的圖查詢自動完成方法
FLAG: Towards Graph Query Autocompletion for Large Graphs
圖查詢自動完成（GQAC）將用戶的圖查詢作為輸入，并生成前k個查詢結(jié)果建議作為輸出，以幫助減輕可視化界面中冗長且容易出錯的圖查詢過程。要使用GQAC組合目標查詢，用戶可以迭代地采用建議或手動添加邊以擴充現(xiàn)有查詢。然而，當前最先進的GQAC方法只關注大量中小型圖?，F(xiàn)有GQAC方法所利用的子圖特征在大圖中要么太小，要么太少。對此，本文提出了用于大圖的靈活圖查詢自動完成方法，簡稱為FLAG，框架如圖1所示。本文首次在GQAC 的上下文中提出通配符標簽，并總結(jié)了具有不同標簽的查詢結(jié)構(gòu)。FLAG允許使用帶有通配符標簽的子圖增量來擴展用戶的查詢以形成建議。為了支持啟用通配符的建議，本文提出了一種新的建議排名功能，提出一種高效的排名算法并通過擴展索引來進一步優(yōu)化在線建議排名。本文進行了用戶研究和一組大規(guī)模模擬實驗，以驗證FLAG的有效性和效率。結(jié)果表明，查詢建議節(jié)省了大約50%的鼠標點擊，F(xiàn)LAG在幾秒鐘內(nèi)返回建議。該論文在已有工作基礎上的主要貢獻如下：
圖1. FLAG : 大圖的圖查詢自動完成
本文采用了幾種流行的指標來衡量建議的質(zhì)量。其中，總利潤指標（TPM） 量化了在可視化查詢制定過程中采用建議所節(jié)省的鼠標點擊百分比，是FLAG的質(zhì)量指標。
本文研究了FLAG的主要參數(shù)對三個數(shù)據(jù)集CITESEER、WORDNET和TWITTER的影響。例如，表1展示了代表性的模擬的TPM結(jié)果。
表1. δmax改變對三個數(shù)據(jù)集TPM值的影響
表1顯示了在三個數(shù)據(jù)集上具有各種δmax的Q5（即5條邊的查詢）的TPM值。結(jié)果表明，隨著δmax的增加，質(zhì)量將會下降。TPM顯示FLAG在查詢公式中節(jié)省大約53%的手動專業(yè)化。同時，WORDNET和TWITTER的結(jié)果與CITESEER的趨勢相同。WORDNET和TWITTER的質(zhì)量指標值低于CITESEER，因為WORDNET和TWITTER的作品數(shù)量相對較少。
圖2. 默認設置下FLAG的平均響應時間(ART)
本文對在線FLAG處理的效率進行了詳細評估。圖2報告了默認設置下FLAG的平均響應時間（ART）。對于CITESEER，ART為3秒左右。對于TWITTER，本文獲得了簡短的ART，因為作品的數(shù)量相對較少。因此，F(xiàn)LAG的響應時間通常很短。
圖3. 僅改變排名函數(shù)的α時FLAG的ART
圖3展示了僅改變排名函數(shù)的α時FLAG的ART。將α范圍從0到1，ART總是少于3.5s。同時，當α接近1時，ART會下降。α的值越高，GQAC過程更喜歡具有大專業(yè)化和小摘要的建議，這導致更新候選建議的摘要的時間更短。
圖4. 僅改變用戶指定的k時FLAG的ART
圖4中報告了僅改變用戶指定的k時FLAG的ART。本文將k設定為從10到50。k測試的最大值為50，對于常見的可視化界面來說已經(jīng)足夠大了。結(jié)果表明，ART隨著k的增加而增加。當k小于20時，F(xiàn)LAG在5s內(nèi)返回建議。當k達到50時，GQAC過程可能需要8s來提供建議。
圖5. 僅改變目標查詢大小|q|時FLAG的ART
圖5展示了僅改變目標查詢大小|q|時FLAG的ART。結(jié)果表明，對于最多8條邊的查詢，F(xiàn)LAG的自動完成過程在6秒內(nèi)完成。查詢大小|q|增加時，ART增加，主要是因為大型查詢需要更多時間來生成更多候選建議，然后對它們進行排名。
本文提出了FLAG模型，它利用通配符標簽概念生成top-k查詢建議，以幫助大型圖的查詢公式化。考慮到現(xiàn)有GQAC研究利用的圖特征在大圖中要么不存在要么很少見，本文建議為查詢圖和查詢建議引入通配符標簽，以允許更多的查詢建議候選者。候選查詢建議由一個新的排名函數(shù)進行排名，該函數(shù)考慮了該建議對現(xiàn)有查詢的擴充程度以及它總結(jié)了多少其他建議。本文提出了有效的建議排名算法。本文的用戶研究和實驗驗證了FLAG的有效性和效率。
Peipei Yi，于2013年獲得中國電子科技大學計算機科學學士學位，于2018年獲得香港浸會大學計算機科學博士學位。畢業(yè)后就職于聯(lián)想機器的數(shù)據(jù)科學家香港情報中心。研究興趣包括圖數(shù)據(jù)處理和圖數(shù)據(jù)庫可用性。
Jianping Li，網(wǎng)絡工程師，于2013年獲得哈爾濱工業(yè)大學電氣和通信碩士學位。研究興趣包括數(shù)據(jù)庫系統(tǒng)的用戶界面。
Byron Choi副教授，于2006年獲得賓夕法尼亞大學計算機和信息科學博士學位，現(xiàn)為香港浸會大學數(shù)據(jù)庫研究組的成員。研究方向包括圖結(jié)構(gòu)數(shù)據(jù)庫，數(shù)據(jù)庫安全，時間序列分析，數(shù)據(jù)庫系統(tǒng)的用戶界面和增量維護算法和視圖更新等。
Sourav S. Bhowmick，南洋理工大學計算機科學與工程學院副教授，研究興趣包括數(shù)據(jù)管理、數(shù)據(jù)分析、計算社會科學和計算系統(tǒng)生物學，在這些領域的主要會議發(fā)表了許多論文，例如SIGMOD、VLDB、ICDE、SIGKDD等國際會議。
徐建良教授，于2002年獲得香港科技大學計算機科學博士學位，畢業(yè)后加入香港浸會大學計算機科學系，于1998年獲得浙江大學計算機科學與工程學士學位，曾是賓夕法尼亞州立大學大學公園分校和復旦大學的訪問學者?，F(xiàn)為香港浸會大學區(qū)塊鏈和金融科技實驗室主任，并領導數(shù)據(jù)庫研究小組。研究方向包括大數(shù)據(jù)、區(qū)塊鏈、移動計算、數(shù)據(jù)安全和隱私。
Data Science and Engineering（DSE）是由中國計算機學會（CCF）主辦、數(shù)據(jù)庫專業(yè)委員會承辦、施普林格 自然（Springer Nature）出版的Open Access期刊。為了迎合相關領域的快速發(fā)展需求，DSE致力于出版所有和數(shù)據(jù)科學與工程領域相關的關鍵科學問題與前沿研究熱點，以大數(shù)據(jù)作為研究重點，征稿范疇主要包括4方面：（1）數(shù)據(jù)本身，（2）數(shù)據(jù)信息提取方法，（3）數(shù)據(jù)計算理論，和（4）用來分析與管理數(shù)據(jù)的技術(shù)和系統(tǒng)。
目前期刊已被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
