“时空数据”是兼具时间和空间属性的数据。现实世界中，80%的数据均直接或间接具备时空属性。海量时空数据高效查询是当前基于位置服务、社交网络、物联网等领域面临的共性科学问题。时空数据在时间维度不断演化的空间属性以及相关应用对时空查询的高实时性要求，使得大规模时空数据高效查询面临巨大技术挑战。

近日，计算机与控制工程学院于自强副教授与加拿大约克大学禹晓辉教授、多伦多大学NickKoudas教授、南京航空航天大学李博涵副教授等国内外专家合作，在基于路网的复杂时空数据查询问题方面取得两项重要研究成果。第一项成果是针对路网环境下移动对象k近邻查询问题，创新性地提出一种移动对象密度感知的动态非平衡树索引结构。该索引结构能够根据变化的移动对象密度分布，自适应调整不同路网区域的索引层次和索引粒度，使得查询算法在不同区域均具备高效剪枝和精准搜索的能力。第二项成果针对动态图的k条最短路线分布式查询问题，提出了面向动态图的边界路线索引技术以及基于局部敏感哈希的大规模边界路线压缩技术，使得索引路线免受动态图中不断变化的边的权重影响，解决了动态图中两点之间最短距离的快速计算问题，从而提高面向动态图的k条最短路线的查询效率。

上图为时空数据查询技术框架图

上述两项成果的相关论文均以于自强副教授为第一作者被计算机领域国际顶级期刊《IEEE Transactions on Knowledge and Data Engineering》（IEEE TKDE）录用为长文。论文题目分别为“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是计算机领域数据库与数据挖掘方向的国际顶级期刊，中国计算机学会（CCF）A类推荐期刊，中科院1区期刊，影响因子为8.9。

论文链接：

https://arxiv.org/abs/2312.12688

https://arxiv.org/abs/2312.12687

来稿时间：12月26日  审核：刘希斌  责任编辑：徐扬