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