关键词: 相互k最近邻, 多度量空间, R树, Minkowski区域

Abstract: 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 ex-plores 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 al-ternative brute force methods.

Key words: mutual k-nearest neighbors, multi-metric space, R-tree, Minkowski region