近日,郑渤龙副教授论文"PM-LSH: A Fast and Accurate LSH Framework for High Dimensional Approximate NN Search"被在日本东京举办的第46届VLDB大会(VLDB 2020)录用。VLDB(Very Large Data Base)和另外两个会议SIGMOD、ICDE被称为数据库领域的三个顶级会议,在数据库领域具有举足轻重的地位。在中国计算机学会的国际学术会议排名中,VLDB被列为数据库领域的A类顶级会议。
该论文研究的是大规模高维数据的近似近邻搜索问题。高维数据的最近邻搜索,不仅是信息检索领域里的一个核心问题,同时也是模式识别、机器学习、数据挖掘等领域里的基础性问题。我们采用的是基于局部敏感哈希的搜索算法。首先,我们通过一种性质良好的哈希函数对数据降维,并且保证数据空间的近邻结构在降维后能被很好地保留。然后,我们采用先进的索引结构PM树来索引低维数据并在低维空间查找真实最近邻。低维空间的真实近邻将作为高维近似近邻的候选点。严格的理论证明保证了我们算法不仅有较低的查询延迟和极佳的搜索质量,而且还可以根据需求调整返回精度。
另外,经过VLDB 2020奖励委员会的评审,该论文被评为最佳论文之一(One of the Best Papers),并受邀投稿至CCF A类期刊VLDBJ的VLDB 2020最佳论文专刊中。
稿件来源:新闻中心
作者:郑渤龙