-
题名近邻问题的亚线性算法研究现状综述
- 1
-
-
作者
马恒钊
李建中
-
机构
哈尔滨工业大学海量数据计算研究中心
中科院深圳理工大学
-
出处
《智能计算机与应用》
2022年第6期1-6,共6页
-
基金
国家自然科学基金(61832003)
-
文摘
大数据时代已经来临,海量数据计算要求设计亚线性算法。本文选择了大数据分析问题中比较重要的问题、即近邻问题,包括近似最近邻问题、近似k-最近邻问题以及全k-最近邻问题,对其亚线性算法的研究现状做了综述。
-
关键词
全k-最近邻
近似最近邻
近似k-最近邻
亚线性算法
-
Keywords
All-k-Nearest Neighbors
Approximate Nearest Neighbors
Approximate k-Nearest Neighbors
sub-linear algorithms
-
分类号
TP311.13
[自动化与计算机技术—计算机软件与理论]
-
-
题名近似最近邻归约问题在泊松点过程上的再研究
- 2
-
-
作者
马恒钊
闫跃
李建中
-
机构
哈尔滨工业大学计算机科学与技术学院
哈尔滨金融学院计算机系
中国科学院深圳先进技术研究院先进计算与数字工程研究所
-
出处
《软件学报》
EI
CSCD
北大核心
2023年第10期4821-4829,共9页
-
基金
国家自然科学基金(61732003,61832003,U1811461)。
-
文摘
在已发表文献中,研究了基于图灵归约求解ε-NN的问题,即给定查询点q、点集P及近似参数ε,找到q在P中近似比不超过1+ε的近似最近邻,并提出了一个具有O(logn)查询时间复杂度的图灵归约算法,这里的查询时间是调用神谕的次数.经过对比,此时间优于所有现存的归约算法.但是已发表文献中提出的归约算法的缺点在于,其预处理时间和空间复杂度中有O((d/ε)^(d))的因子,当维度数d较大或者近似参数ε较小时,此因子将变得不可接受.因此,重新研究了该归约算法,在输入点集服从泊松点过程的情况下,分析算法的期望时间和空间复杂度,将算法的期望预处理时间复杂度降到O(n logn),期望空间复杂度降到O(nlogn),而期望查询时间复杂度保持O(logn)不变,从而完成了在已发表文献中所提出的未来工作.
-
关键词
近似最近邻
归约
泊松点过程
复杂度
-
Keywords
approximate nearest neighbor
reduction
Poisson point process
complexity
-
分类号
TP311
[自动化与计算机技术—计算机软件与理论]
-
