彭智勇教授研究组发表论文解决空间数据集的快速搜索问题-武汉大学计算机学院

彭智勇教授研究组发表论文解决空间数据集的快速搜索问题

发布时间:2022-11-04     浏览量:

近日,彭智勇教授研究组一篇论文,题目为“FastDatasetSearchwithEarthMover’s Distance”,被数据库领域A类会议International Conference on Very Large Databases (VLDB 2022)录用。该论文第一作者为2020级博士生杨文哲,通讯作者为王胜副教授和彭智勇教授。

该论文主要解决了空间数据集的快速搜索问题。目前数据集搜索已经受到了学者们的广泛关注与研究,但是现有的搜索引擎主要还是针对关键词的查询。为了提供多样化的查询,“范例查询”这一新型查询方式被提出,即用户向数据库中输入一个感兴趣的示例数据,并快速查找到与输入相似的数据。本篇论文主要关注空间数据集中的快速查询,该研究有许多重要的现实应用,如自动驾驶运动预测,数据增强等场景。现有的空间数据集相似度查询方法大多是基于最小边界矩形重叠或者豪斯多夫距离等进行的,有一定的局限性。为了解决现有空间数据集的快速相似度查询问题,本文提出了一套基于推土距离(Earth Mover’s Distance, EMD)的双重界限框架(Dual-Bound Filtering, DBF)。具体来说,论文通过空间区域进行网格划分,设计了空间数据压缩存储数据结构,减少了存储空间的开销。此外,为了应对多种网格尺寸的要求,提出了基于pooling的方法大大缩短了数据建模时间。为了实现查询加速,该论文设计了两层的过滤框架,以实现最大的过滤比例。首先在粗粒度过滤阶段,文章设计了一个新型的树状索引和基于poolingEMD距离上下界;通过对索引树进行深度优先遍历,计算查询数据集与树节点之间的上下界,对不相似的数据集进行批量过滤。在细粒度查询阶段,文章提出了一个更紧的迭代约束传输EMD界限(Tighter Iterative Constrained TransfersTICT),进一步减少了候选集的数量。文章通过在4个真实数据集上进行大量实验并与现有方法进行多方面对比,证明了文章所提出算法与框架的有效性。更多细节大家可以进一步阅读原文(论文链接:https://vldb.org/pvldb/vol15/p2517-yang.pdf)。

国际顶级数据库学术会议VLDB 202295日在澳大利亚悉尼开幕。VLDB作为数据库领域的三大顶级会议之一,每年吸引全球顶尖研究机构投稿,收录研究机构以及科技企业在数据库领域最前沿的研究成果,在数据库领域有着举足轻重的地位。本次VLDB2022会议将举办超过250场研究讲座、11场主题演讲和受邀演讲、2个专家小组会议、9个专题报告、40多个演示和10个研讨会。它涵盖了数据管理、数据库架构、图形数据管理、数据隐私和安全、数据挖掘、机器学习、人工智能和数据库系统研究等问题,这些都是21世纪新兴应用的基本技术基石。