软件学报

作者：马恒钊，闫跃，李建中

单位：马恒钊，哈尔滨工业大学 计算机科学与技术学院, 黑龙江 哈尔滨 150001;中国科学院深圳先进技术研究院 先进计算与数字工程研究所, 广东 深圳 51805511,闫跃，哈尔滨金融学院 计算机系, 黑龙江 哈尔滨 15000102,李建中，哈尔滨工业大学 计算机科学与技术学院, 黑龙江 哈尔滨 15000103

关键词：近似最近邻;归约;泊松点过程;复杂度

基金：国家自然科学基金(61732003,61832003,U1811461)

在已发表文献中, 研究了基于图灵归约求解$ \varepsilon $-NN的问题, 即给定查询点q、点集P及近似参数$ \varepsilon $, 找到q在P中近似比不超过$ 1 + \varepsilon $的近似最近邻, 并提出了一个具有${\rm{O}}(\log n)$查询时间复杂度的图灵归约算法, 这里的查询时间是调用神谕的次数. 经过对比, 此时间优于所有现存的归约算法. 但是已发表文献中提出的归约算法的缺点在于, 其预处理时间和空间复杂度中有${\rm{O}}({(d/\varepsilon )^d})$的因子, 当维度数d较大或者近似参数$ \varepsilon $较小时, 此因子将变得不可接受. 因此, 重新研究了该归约算法, 在输入点集服从泊松点过程的情况下, 分析算法的期望时间和空间复杂度, 将算法的期望预处理时间复杂度降到${\rm{O}}(n\log n)$, 期望空间复杂度降到${\rm{O}}(n\log n)$, 而期望查询时间复杂度保持${\rm{O}}(\log n)$不变, 从而完成了在已发表文献中所提出的未来工作.

来源：2023年第10期

《软件学报》期刊编辑部

查看软件学报杂志2023年第10期