摘要:
针对球面上数据对象点集的特征和K最近邻查询的需求,提出2种处理球面上K最近邻查询的算法:基于查询轴的K最近邻查询算法(PAM方法)和基于查询圆面的K最近邻查询算法(PCM方法)。对2种算法进行实验比较,结果表明,PAM方法和PCM方法都适合处理球面上的最近邻查询问题,PAM方法在存储量和查询复杂度方面相对于PCM方法具有一定优势,但PAM方法的可扩展性远低于 PCM方法,尤其不适合处理受限查询和带方向的查询。
关键词:
最近邻,
球面,
查询轴,
查询圆面,
索引结构
Abstract:
According to the characteristics of the datasets on the sphere, the algorithm of the K-Nearest Neighbor query based on the query axis (PAM) and the algorithm of the K-Nearest Neighbor query based on the query circular planar(PCM) are presented. Theoretical research and experimental results show that both the two methods can handle the problem of the K-Nearest Neighbor query on the sphere, compared with the PCM, PAM has advantages on the memory capacitance and the query efficiency, but the expansibility of PAM is poor and PCM has high scalability.
Key words:
nearest neighbor,
sphere,
query axis,
query circular planar,
index structure
中图分类号:
张丽平, 李松, 郝晓红. 球面上的K最近邻查询算法[J]. 计算机工程, 2011, 37(2): 52-53.
ZHANG Li-Beng, LI Song, HAO Xiao-Gong. Algorithms for K-Nearest Neighbor Query on Sphere[J]. Computer Engineering, 2011, 37(2): 52-53.