“時(shí)空數(shù)據(jù)”是兼具時(shí)間和空間屬性的數(shù)據(jù)。現(xiàn)實(shí)世界中，80%的數(shù)據(jù)均直接或間接具備時(shí)空屬性。海量時(shí)空數(shù)據(jù)高效查詢是當(dāng)前基于位置服務(wù)、社交網(wǎng)絡(luò)、物聯(lián)網(wǎng)等領(lǐng)域面臨的共性科學(xué)問(wèn)題。時(shí)空數(shù)據(jù)在時(shí)間維度不斷演化的空間屬性以及相關(guān)應(yīng)用對(duì)時(shí)空查詢的高實(shí)時(shí)性要求，使得大規(guī)模時(shí)空數(shù)據(jù)高效查詢面臨巨大技術(shù)挑戰(zhàn)。
近日，計(jì)算機(jī)與控制工程學(xué)院于自強(qiáng)副教授與加拿大約克大學(xué)禹曉輝教授、多倫多大學(xué)NickKoudas教授、南京航空航天大學(xué)李博涵副教授等國(guó)內(nèi)外專家合作，在基于路網(wǎng)的復(fù)雜時(shí)空數(shù)據(jù)查詢問(wèn)題方面取得兩項(xiàng)重要研究成果。第一項(xiàng)成果是針對(duì)路網(wǎng)環(huán)境下移動(dòng)對(duì)象k近鄰查詢問(wèn)題，創(chuàng)新性地提出一種移動(dòng)對(duì)象密度感知的動(dòng)態(tài)非平衡樹(shù)索引結(jié)構(gòu)。該索引結(jié)構(gòu)能夠根據(jù)變化的移動(dòng)對(duì)象密度分布，自適應(yīng)調(diào)整不同路網(wǎng)區(qū)域的索引層次和索引粒度，使得查詢算法在不同區(qū)域均具備高效剪枝和精準(zhǔn)搜索的能力。第二項(xiàng)成果針對(duì)動(dòng)態(tài)圖的k條最短路線分布式查詢問(wèn)題，提出了面向動(dòng)態(tài)圖的邊界路線索引技術(shù)以及基于局部敏感哈希的大規(guī)模邊界路線壓縮技術(shù)，使得索引路線免受動(dòng)態(tài)圖中不斷變化的邊的權(quán)重影響，解決了動(dòng)態(tài)圖中兩點(diǎn)之間最短距離的快速計(jì)算問(wèn)題，從而提高面向動(dòng)態(tài)圖的k條最短路線的查詢效率。
上圖為時(shí)空數(shù)據(jù)查詢技術(shù)框架圖
上述兩項(xiàng)成果的相關(guān)論文均以于自強(qiáng)副教授為第一作者被計(jì)算機(jī)領(lǐng)域國(guó)際頂級(jí)期刊《IEEE Transactions on Knowledge and Data Engineering》（IEEE TKDE）錄用為長(zhǎng)文。論文題目分別為“ODIN: Object Density Aware Index for CkNN Queries over Moving Objects on Road Networks”和“A Distributed Solution for Efficient k Shortest Paths Computation over Dynamic Road Networks”。TKDE是計(jì)算機(jī)領(lǐng)域數(shù)據(jù)庫(kù)與數(shù)據(jù)挖掘方向的國(guó)際頂級(jí)期刊，中國(guó)計(jì)算機(jī)學(xué)會(huì)（CCF）A類(lèi)推薦期刊，中科院1區(qū)期刊，影響因子為8.9。
論文鏈接：
https://arxiv.org/abs/2312.12688
https://arxiv.org/abs/2312.12687
來(lái)稿時(shí)間：12月26日 審核：劉希斌 責(zé)任編輯：徐揚(yáng)
