摘要
发现两类对象的相互k最近邻居可为工作匹配、大学选择等应用提供决策。现有的方法主要处理单度量空间(如L2 norm),这些方法有可能导致不公平的匹配。形式化多度量空间的相互最近邻问题,提出基于空间索引的多度量空间下的相互k最近邻算法。利用人工数据集,测试了大量的参数设置下的算法性能,结果表明提出的算法优于可选的直接算法。
Finding mutual k-nearest neighbors in two kinds of objects can provide decisions for applications such as job matching and college selection.Existing methods mainly focus on processing mutual nearest neighbor queries in one single metric space(e.g.L2 norm) and this will probably lead to an unfair assignment.This paper formally explores the problem of mutual nearest neighbors in multi-metric space.Based on space indices,algorithms are pro-posed for finding mutual k-nearest neighbors in multi-metric space.With the synthetic dataset,the algorithms are experimentally evaluated for a wide range of variable settings,and show that the proposed solutions outperform alternative brute force methods.
出处
《计算机科学与探索》
CSCD
2010年第10期881-889,共9页
Journal of Frontiers of Computer Science and Technology
基金
The National Natural Science Foundation of China under Grant No.61070024
The Natural Science Foundation of Liaoning Province of China under Grant No.20071004
the Foundation of Education Department of Liaoning Province of China under Grant No.2008600,2008596~~