检索规则说明:AND代表“并且”;OR代表“或者”;NOT代表“不包含”;(注意必须大写,运算符两边需空一格)
检 索 范 例 :范例一: (K=图书馆学 OR K=情报学) AND A=范并思 范例二:J=计算机应用与软件 AND (U=C++ OR U=Basic) NOT M=Visual
作 者:马恒钊 闫跃 李建中[1] MA Heng-Zhao;YAN Yue;LI Jian-Zhong(School of Computer Science and Technology,Harbin Institute of Technology,Harbin 150001,China;Department of Computer Science,Harbin Finance University,Harbin 150001,China;Institute of Advanced Computing and Digital Engineering,Shenzhen Institute of Advanced Technology,Chinese Academy of Sciences,Shenzhen 518055,China)
机构地区:[1]哈尔滨工业大学计算机科学与技术学院,黑龙江哈尔滨150001 [2]哈尔滨金融学院计算机系,黑龙江哈尔滨150001 [3]中国科学院深圳先进技术研究院先进计算与数字工程研究所,广东深圳518055
出 处:《软件学报》2023年第10期4821-4829,共9页Journal of Software
基 金:国家自然科学基金(61732003,61832003,U1811461)。
摘 要:在已发表文献中,研究了基于图灵归约求解ε-NN的问题,即给定查询点q、点集P及近似参数ε,找到q在P中近似比不超过1+ε的近似最近邻,并提出了一个具有O(logn)查询时间复杂度的图灵归约算法,这里的查询时间是调用神谕的次数.经过对比,此时间优于所有现存的归约算法.但是已发表文献中提出的归约算法的缺点在于,其预处理时间和空间复杂度中有O((d/ε)^(d))的因子,当维度数d较大或者近似参数ε较小时,此因子将变得不可接受.因此,重新研究了该归约算法,在输入点集服从泊松点过程的情况下,分析算法的期望时间和空间复杂度,将算法的期望预处理时间复杂度降到O(n logn),期望空间复杂度降到O(nlogn),而期望查询时间复杂度保持O(logn)不变,从而完成了在已发表文献中所提出的未来工作.In a published study,the problem of using Turing reduction to solveε-NN is studied.In other words,given a query point q,a point set P,and an approximate factorε,the purpose is to return the approximate nearest neighbor of q in P with an approximation ratio of not more than 1+ε.Moreover,a Turing reduction algorithm with O(logn)query time complexity is proposed,where the query time is the number of times that the oracle is invoked.The comparison indicates that the O(logn)query time is the lowest compared to that of all the existing algorithms.However,the disadvantage of the proposed algorithm is that there is a factor of O((d/ε)^(d))in the preprocessing time complexity and space complexity.When the number of dimensions d is high,or the approximation factorεis small,the factor would become unacceptable.Therefore,this study revises the reduction algorithm and analyzes the expected time complexity and space complexity of the algorithm when the input point set follows the Poisson point process.As a result,the expected preprocessing time complexity is reduced to O(nlogn),and the expected space complexity is reduced to O(nlogn),while the expected query time complexity remains O(logn).In this sense,the future work raised in the published study is completed.
分 类 号:TP311[自动化与计算机技术—计算机软件与理论]
正在载入数据...
正在载入数据...
正在载入数据...
正在载入数据...
正在载入数据...
正在载入数据...
正在载入数据...
正在链接到云南高校图书馆文献保障联盟下载...
云南高校图书馆联盟文献共享服务平台 版权所有©
您的IP:3.15.22.62